Kurs Komplexitätstheorie (Sommersemester 2018)
Prof. Dr. Thomas Schneider
K4, Modulbereich Theorie, Profile SQ, KIKR
Di 12–14 SH D1020
Do 14–16 SFG 2030
Kurzbeschreibung
Die Komplexitätstheorie beschäftigt sich mit der
inhärenten Komplexität von Berechnungsproblemen: wie viel
Zeit (oder andere Ressourcen) benötigt man, um ein gegebenes
Problem zu lösen—unabhängig davon, wie clever der
Algorithmus ist, den man verwendet? Es geht also um die Grenzen der
Berechenbarkeit unter beschränkten Ressourcen. Damit stellt die
Komplexitätstheorie eine wichtige Grundlage für den Entwurf
und das Verständnis von effizienten Algorithmen dar. Ausserdem
versucht sie, die natürliche Neugierde nach dem in der Informatik
prinzipiell machbaren zu befriedigen. Die Vorlesung wird sich mit
folgenden Themen beschäftigen:
- Grundlegende Begriffe wie Reduktionen, Härte und Vollständigkeit
- Das P vs. NP Problem und dessen Variationen
- NP-vollständige Probleme aus verschiedenen Teilgebieten der Informatik
- Hierarchietheoreme und verwandte Resultate
- Platzkomplexitätsklassen wie PSpace und LogSpace
- Schaltkreiskomplexität und effiziente Parallelisierbarkeit
- Die Polynomalzeithierarchie
Folien
Übungsaufgaben
Übungsblatt 1 (Abgabe am 17. 4. in Stud.IP, Besprechung am 19. 4.)
Übungsblatt 2 (Abgabe am 6. 5. in Stud.IP, Besprechung am 8. 5.)
Übungsblatt 3 (Abgabe am 22. 5. in Stud.IP, Besprechung am 24. 5.)
Übungsblatt 4 (Abgabe am 5. 6. in Stud.IP, Besprechung am 7. 6.)
Übungsblatt 5 (Abgabe am 19. 6. in Stud.IP, Besprechung am 21. 6.)
Übungsblatt 6 (Abgabe am 3. 7. in Stud.IP, Besprechung am 5. 7.)
Prüfungen
Die Prüfungsmodalitäten werden in der Vorlesung bekanntgegeben.
Literatur
- Oded Goldreich. Computational Complexity: a Conceptual Perspective.
Cambridge University Press, 2008.
- Sanjeev Arora, Boaz Barak. Computational Complexity: A Modern Approach.
Cambridge University Press, 2009.
- Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- Ingo Wegener. Komplexitätstheorie - Grenzen der Effizienz von Algorithmen.
Springer, 2003.
- Michael Sipser. Introduction to the Theory of Computation (2nd Edition).
Thomson Course Technology, 2006
AG Theorie der künstlichen Intelligenz
2. Juli 2018
Thomas Schneider
