Vorlesung Komplexitätstheorie (Sommersemester 2021)
Prof. Dr. Carsten Lutz
Dr. Leif Sabellek
K4, Modulbereich Theorie, Profile AI, SQ
Di 12–14
Do 14–16
Die Vorlesung findet aufgrund der COVID19 Pandemie online in Zoom statt. Die
Vorlesung wird zu den jeweils angegebenen Terminen live gehalten,
Rückfragen und Diskussionen sind wie in einer Präsenzvorlesung
jederzeit möglich. Zudem wird eine Aufzeichnung der Veranstaltung zum asynchronen Ansehen zur Verfügung gestellt.
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
Vorlesungsmaterialien und Übungsaufgaben
Werden in Stud.IP zur Verfügung gestellt.
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