RUB » LMI » Lehre » Komplexitätstheorie WS13/14

Komplexitätstheorie Winter 2013/14

LVR-Nr: 150 262
Veranstaltung: Komplexitätstheorie
4 std.
NA 2/99 Di 12.00-14.00
NA 2/99 Do 12.00-14.00
Dozent: Hans U. Simon
Übungen: N.N.

       

NEWS: Prüfungstage sind 12. Februar und 02. April. Zu weiteren Details s. unten.

Kommentar

Die Komplexitätstheorie stellt sich die Aufgabe Berechnungsprobleme anhand des zu ihrer Lösung erforderlichen Verbrauchs an Rechenzeit oder Speicherplatz in Klassen einzuordnen. Probleme von (annähernd) gleicher Komplexität landen dabei in derselben Klasse. Gegenstand der Vorlesung sind hauptsächlich die Komplexitätsklassen zwischen P und PSpace wie zum Beispiel die Klasse NP. Hierbei bezeichnet P die Klasse der in Polynomialzeit und PSpace die Klasse der mit polynomiell beschränktem Speicherplatz erkennbaren Sprachen. NP ist das nichtdeterministische Pendant zu P und bezeichnet die Klasse der nichtdeterministisch in Polynomialzeit erkennbaren Sprachen. Die Klasse enthält eine Vielzahl von grundlegenden Problemen aus verschiedenen Wissenschaftsbereichen. Eine der wichtigsten ungeklärten Fragen der theoretischen Informatik ist, ob die Klassen P und NP überhaupt verschieden sind. In der Vorlesung behandeln wir eingehend die NP-Vollständigkeitstheorie, die sich mit schwersten Problemen innerhalb NP beschäftigt. Weitere Themen sind die polynomielle Hierarchie von Stockmeyer, schwerste Probleme in PSpace und schließlich randomisierte Algorithmen bzw. Approximationsalgorithmen und die jeweils dazu passenden Komplexitätsklassen.

Voraussetzungen

Elementare Grundkenntnisse zu der Thematik, wie sie etwa in der Vorlesung "Theoretische Informatik" vermittelt werden, werden weitgehend vorausgesetzt. (Diese Voraussetzungen sind aber von mathematisch gebildeten Studierenden relativ rasch im Selbststudium herstellbar)

Materialien

Übungsaufgaben

Skript

Vorwissen aus der Vorlesung "Theoretische Informatik

Prüfungen

Die Prüfungsleistung zum Modul Komplexitätstheorie ist in Form einer mündlichen Prüfung zu erbringen.

Die Prüfungsanmeldung erfolgt nach den Regeln des für Sie zuständigen Prüfungsamtes.

Für die mündlichen Prüfungen sind die Tage 12. Februar und 02. April vorgesehen. Bitte vor der Anmeldung zur Prüfung sich eine Uhrzeit von Frau Weissmann (Sekretariat in NA 1/72) geben lassen.

Kontakt