Komplexitätstheorie
Vortragender: Prof. Carsten Lutz
K4, Modulbereich Theorie
Di 10-12 MZH 1090
Mi 16-18 MZH 1100
Kurzbeschreibung
Die Komplexitätstheorie beschäftigt sich mit der
inhärenten Komplexität von Berechnungsproblemen: wieviel
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 polynomielle Hierarchie
Folien
Übungsaufgaben
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