Vorlesung Komplexitätstheorie (WS 2016/17)
Aktuelles
- Am Freitag, 21.10.2016,10:00-12:00, findet anstatt der Übung eine Vorlesung statt (Raum H-F 104/05)
- Die Vorlesungen am 18.10. und 20.10 finden im Raum H-C 5324/25 anstatt dem H-F 001 statt
- Die Übung am 02.12.2016, 10:00-12:00, fällt aus. Ein Ersatztermin wird am 09.12 vereinbart.
Organisatorisches
- Veranstalter: Prof. Dr. Markus Lohrey (Raum H-A 7103, Tel. 0271-740-2826)
- Übungsleiter: Danny Hucke (Raum H-A 7104, Tel. 0271-740-3415)
- Termine Vorlesung:
- Dienstag, 12:00-14:00, im H-F 001
- Donnerstag, 10:00-12:00, im H-F 001
- Termin Übung: Freitag, 10:00-12:00, im H-F 104/05
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 (21.01.2017)
Übungsblätter
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