Vorlesung Komplexitätstheorie (WS 2014/15)
Aktuelles
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7109, Tel. 0271-740-2826)
- Übungsleiter: Eric Nöth (Raum H-A 7104, Tel. 0271-740-3415)
- Termin: Donnerstag, 12:00-14:00 und 14:00-16:00, in H-F 115
- Termin Übung: Freitag, 12:00-13:30 (bitte pünktlich), in H-A 8107
Die Komplexitätstheorie beschäftigt sich mit der für die Lösung algorithmischer Fragestellungen notwendigen Rechenzeit und Speicherplatz. Insbesondere sollen Techniken entwickelt werden, mittels derer sich beweisen lässt, dass die Lösung gewisser Probleme schwierig (d.h. viel Speicher oder eine hohe Laufzeit benötigt). Die Vorlesung soll die zentralen Konzepte der Komplexitätstheorie vermitteln.
Einige Themen
- Zeit- und Platzkomplexitätsklassen
- Hierarchiesätze
- Reduktionen
- Komplementabschluss nichtdeterministischer Platzklassen (Satz von Immerman, Szelepcsenyi)
- Vollständige Probleme für P, NP, PSPACE
- Orakel-Turingmaschinen
- Alternierende Maschinen
- Schaltkreiskomplexität
- Interaktive Beweissysteme
Folien (15.01.2015)
Übungsblätter
- Blatt 1
- Blatt 2
- Blatt 3
- Blatt 4
- Blatt 5
- Blatt 6
- Blatt 7
- Blatt 8
- Blatt 9
- Blatt 10
- Blatt 11
- Blatt 12
- Blatt 13
- Blatt 14
Java-Applets (von Roy Mennicke)
Lehrbücher
- Sanjeev Arora und Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press 2009
- Christo H. Papadimitriou: Computational complexity. Addison-Wesley 2005
- Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer 2003
Impressum