Komplexitätstheorie
Vortragender: Prof. Carsten Lutz
K4, Modulbereich Theorie
Di 17-19 MZH 7250
Do 15-17 MZH 7250
Prüfungstermin: 9.9.2009. Konkrete Termine bitte per
Mail
abmachen.
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 Neugier 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
- Probabilistische Komplexitätsklassen
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