RUB » LMI » Lehre » Komplexitätstheorie WS12/13

Komplexitätstheorie Winter 2012/13

LVR-Nr: 150 262
Veranstaltung: Komplexitätstheorie
4 std.
NA 3/64 Di 12.00-14.00
NA 3/64 Do 12.00-14.00
Dozent: Hans U. Simon
Übungen: in die Vorlesung integriert (ohne Korrektur)

News

Die Wiederholungsprüfung im Sommersemester 2013 findet am 18. Juli 2013 statt.
Die Prüfungsanmeldung erfolgt nach den Regeln des für Sie zuständigen Prüfungsamtes. Studierende der Mathematik melden sich bis zu 14 Tage vor dem Prüfungstermin schriftlich im Prüfungsamt an.
Bitte vor der Anmeldung zur Prüfung sich einen Termin (Datum + Uhrzeit) von Frau Weissmann geben lassen.

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)

Literatur

Zur Theorie der NP-Vollständigkeit empfehle ich den Klassiker:
Garey and Johnson, Computers and Intractability. (A Guide to the Theorie of NP-Completeness), Freeman and Company.
Die Vorlesung orientiert sich stark an dem Buch "Computational Complexity (A Modern Approach)" von Arora und Barak, Cambridge University Press.

Materialien

Vorwissen aus der Vorlesung "Theoretische Informatik

Ergänzungen zum Lehrbuch von Arora und Barak

Übungsaufgaben

Zum Trainieren von polynomiellen Reduktionen eignen sich Aufgaben 2.2, 2.3, 2.4 des zweiten Übungsblattes der Vorlesung aus dem SS 2010. (Die organisatorischen Hinweise auf dem Übungsblatt waren nur im SS 2010 gültig und sind zu ignorieren.)

Zum Trainieren Cook- bzw. Levin-Reduktionen und dem Nachweis der Selbstreduzierbarkeit eignen sich die Aufgaben 3.2, 3.3, 3.4 des dritten Übungsblattes der Vorlesung aus dem SS 2008. Dabei steht KP in Aufgabe 3.2 für KNAPSACK und VC in Aufgabe 3.3 für VERTEX COVER. Aufgabe 3.4 bezieht sich auf die Beweisskizze aus der Vorlesung zur Selbstreduzierbarkeit von Graphisomorphie. (Die Verweise des Übungsblattes auf ein Skriptum waren nur im SS 2008 gültig und sind zu ignorieren.)

Zur Exploration der Grenze zwischen P und NPC eignen sich die Aufgaben 2.3, 2.4 des zweiten Übungsblattes der Vorlesung aus dem SS 2008.

Zum Training bezüglich pseudopolynomieller Algorithmen und starker NP-Härte entwerfe erstens einen pseudopolynomiellen Algorithmus, der entscheidet, ob n gegebene natürliche Zahlen in drei gleich grosse Teilsummen zerlegbar sind. Zweitens reduziere 3-PARTITION pseudopolynomiell auf 4-PARTITION.

Zum Training bezüglich Approximationsalgorithmen und NP-harter Approximation s. die Randnotizen im betreffenden Skriptteil. Weiterhin sind zu empfehlen die Aufgaben 9.2, 9.3 und 9.4 des neunten Übungsblattes sowie die Aufgaben 10.1 und 10.2 des zehnten Übungsblattes aus dem SS 2008. Dabei bedeutet "relativer Fehler" a eines Approximationsalgorithmus A (vgl. Aufgabe 9.4), dass A einen Bruchteil von mindestens 1-a des grösstmöglichen Profites erzielt.

Zum Training bezüglich Festparameter-Behandelbarkeit empfehlen wir die Aufgaben aus Kapitel 3 des Buches "Parameterized Complexity" von Downey und Fellows (s. Mathe-Bibliothek). Zum Training bezüglich der Struktur von NP s. die Randnotizen im betreffenden Skriptteil.

Die Techniken "Lazy Evaluation" und "Hashing", die im Beweis des Satzes von Berman (Existenz einer unären NP-harten Sprache impliziert P=NP) zum Einsatz kommen, können mit Hilfe der Aufgabe 10.1 des Übungsblattes Übung zu Lazy Evaluation und Hashing trainiert werden.

Das Trainig zum Kapitel "Uniforme versus nicht-uniforme Komplexität" kann anhand der ersten drei Übungsaufgaben des Übungsblattes 8 aus dem SS 2010 erfolgen.

Das Trainig zum Kapitel "Probabilistische Komplexität" kann anhand der vierten Aufgabe des Übungsblattes 8 und anhand der zweiten und vierten Aufgabe des Übungsblattes 9 aus dem SS 2010 erfolgen.

  • Einen Übungsschein erhält, wer dem Dozenten korrekte Lösungen zu insgesamt vier Übungsaufgaben vorgetragen hat. Die Aufgaben sollten sich auf vier verschiedene Themen verteilen. Ort und Zeit für die Präsentation der Lösungen werden per Absprache festgelegt.

Begleitmaterial zur Vorlesung

Zu dem Buch "Computational Complexity (A Modern Approach)" siehe die Seite: http://www.cs.princeton.edu/theory/complexity/

Prüfungen

Die Prüfungsleistung zum Modul Komplexitätstheorie ist in Form einer mündlichen Prüfung zu erbringen. Zu diesem Zweck werden zwei Termine angeboten: Do 07.02.2013 und Do 11.04.2013.

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

Bitte vor der Anmeldung zur Prüfung sich einen Termin (Datum + Uhrzeit) von Frau Weissmann geben lassen.

Kontakt