Komplexität von Algorithmen

Dozent: Dr. Arne Meier

Frequenz: jährlich im Sommersemester, empf. 4. Semester

Veranstaltungsart: Vorlesung und Übung (2V + 2Ü, 5 LP)

Prüfung: Klausur

Das Modul vermittelt grundlegende Kenntnisse über Begriffe der Zeit- und Raumkomplexität. Nach erfolgreichem Abschluss der LV können die Studierenden algorithmische Probleme hinsichtlich ihrer Komplexität analysieren. Sie entwickeln NP-Vollständigkeitsbeweise und entwerfen Approximationsalgorithmen.

Inhalt:

In dieser Vorlesung beschäftigen wir uns mit der Frage, welche Berechnungsprobleme effizient algorithmisch lösbar sind. Dazu werden wir die Komplexitätsmaße Laufzeit und Speicherbedarf formal einführen und untersuchen. Eine zentrale Rolle werden dabei die Komplexitätsklassen P und NP sowie sog. NP-vollständige Probleme spielen. Dies sind Probleme, für die weder ein effizienter Algorithmus bekannt ist noch bewiesen wurde, dass keiner existieren kann. NP-vollständige Probleme kommen in vielen Bereichen der Informatik (VLSI-Design, Netzwerk-Optimierung, Operations-Research, etc.) vor. Erstaunlicherweise zeigt sich, dass alle diese Probleme äquivalent in dem Sinne sind, dass sie alle effizient lösbar sind, wenn man nur für eines von ihnen einen effizienten Algorithmus entdeckt. Abschließend beschäftigen wir uns mit Optimierungsproblemen und Approximationsalgorithmen, um für solche Probleme Lösungen zu erreichen.

Gliederung:

• Raum- und Zeitkomplexität
• Beziehungen zwischen den Komplexitätsklassen
• Die Hierarchiesätze
• Die Klasse P
• Die Klasse NP
• NP-Vollständigkeit
• Der Satz von Cook
• Weitere NP-vollständige Probleme
• Approximierbarkeit
• Das Problem des Handlungsreisenden
• Das Partitionierungsproblem

Die Abschlussprüfung des Moduls ist eine schriftliche Klausur über 90 Minuten.

Termin

Die Prüfungstermine finden Sie im zentralen Webauftritt der Universität (siehe Link unten).

Anmeldung

Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten). Zur Teilnahme als Zulassungsauflage benötigen Sie keine Anmeldung.

Hilfsmittel

Es sind keine Hilfsmittel erlaubt. Sie benötigen kein eigenes Papier!

Klausurbonus

Die Modalitäten für das Erreichen eines Klausurbonus finden Sie im Foliensatz im Stud.IP.

Studienleistung

Die Modalitäten für das Erreichen der Studienleistung finden Sie im Foliensatz im Stud.IP.