RUB » LMI » Lehre » Komplexitätstheorie SS10

Komplexitätstheorie Sommer 2010

LVR-Nr: 150 262
Veranstaltung: Komplexitätstheorie
4 std.
NA 1/64 Di 12.00-14.00
NA 3/24 Do 16.00-18.00
Dozent: Hans U. Simon
Übungen: Malte Darnstädt
2 std.
NA 2/64 Mi 14.00-16.00
Korrektur: Florian Giesen NA 5/71

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.
Weiterhin kann das Buch "Computational Complexity (A Modern Approach)" von Arora und Barok, Cambridge University Press, empfohlen werden.

Materialien

Übungsblätter

Auf jedem Blatt können in vier Aufgaben jeweils maximal vier Punkte erreicht werden. Gruppen von bis zu drei Teilnehmern können einen gemeinsamen Zettel einreichen. Die bearbeiteten Blätter werden am Anfang der Übung, mittwochs um 14 Uhr c.t., abgegeben. Eine frühere Abgabe ist bei Florian (NA 5/71) oder Malte (NA 1/70) möglich. Neue Übungsblätter werden mittwochnachmittags online gestellt. Einen Übungschein erhält, wer mindestens die Hälfte der Punkte erreicht hat und in den Übungen eine eigene Lösung zu einer Aufgabe vorgetragen hat.

Die Punkte aus den Übungsblättern geben folgenden Bonus in der Prüfung:

  • mit mindestens sechzig Prozent der Punkte verbessert sich die Note um eine Drittel-Note
  • mit mindestens achtzig Prozent der Punkte verbessert sie sich um zwei Drittel-Noten

Eine weitere Vorraussetzung ist das Vortragen einer eigenen Lösung zu einer der Übungsaufgaben in den Übungen.

Begleitmaterial zur Vorlesung

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

Mündliche Prüfungen

Für mündliche Prüfungen werden zwei Termine angeboten: Do 29.07.2010 und Do 30.09.2010

Bitte vor der Anmeldung über VSPL einen Termin mit Uhrzeit von Malte Darnstädt geben lassen! Die Prüfungsanmeldung über VSPL ist notwendig.

Anmeldefrist für die Prüfung am 29.07.: Bis zum 15.07.
Anmeldefrist für die Prüfung am 30.09.: Bis zum 16.09.

Kontakt