Komplexitätstheorie

NUMMER: 211028
KÜRZEL: KompTh
MODULBEAUFTRAGTE:R: Prof. Dr. Thomas Zeume
DOZENT:IN: Prof. Dr. Thomas Zeume
FAKULTÄT: Fakultät für Informatik
SPRACHE: Deutsch
SWS: 6 SWS
CREDITS: 9 CP
ANGEBOTEN IM: unregelmäßig

PRÜFUNGEN

FORM: mündlich
TERMIN: Siehe Prüfungsamt.

LERNFORM

Vorlesung mit begleitenden Übungen

LERNZIELE

Die Studierenden lernen, algorithmische Probleme bezüglich ihrer Komplexität einzuordnen
und so geeignete algorithmische Techniken zu ihrer Lösung zu identifizieren. Sie können insbesondere
algorithmische Methoden für NP-vollständige Probleme anwenden. Sie können mit
unterschiedlichen Berechnungsmodellen umgehen und sind in der Lage, einfache Aussagen
über sie zu beweisen. Sie lernen im Diskurs eigene und fremde Lösungsansätze zu bewerten.

INHALT

Die Komplexitätstheorie untersucht und klassifiziert Berechnungsprobleme bezüglich ihrer
algorithmischen Schwierigkeit. Ziel ist es, den inhärenten Ressourcenverbrauch bezüglich verschiedener
Ressourcen wie Rechenzeit oder Speicherplatz zu bestimmen, und Probleme mit
ähnlichem Ressourcenverbrauch in Komplexitätsklassen zusammenzufassen. Die bekanntesten
Komplexitätsklassen sind sicherlich P und NP, die die in polynomieller Zeit lösbaren bzw.
verifizierbaren Probleme umfassen. Die Frage, ob P und NP verschieden sind, wird als eine
der bedeutendsten offenen Fragen der theoretischen Informatik, ja sogar der Mathematik,
angesehen. P und NP sind jedoch nur zwei Beispiele von Komplexitätsklassen. Andere Klassen
ergeben sich unter anderem bei der Untersuchung der des benötigten Speicherplatzes,
der effizienten Parallelisierbarkeit von Problemen, der Lösbarkeit durch zufallsgesteuerte Algorithmen,
und der approximativen Lösbarkeit von Problemen. Die Vorlesung hat das Ziel,
einen breiten Überblick über die grundlegenden Konzepte und Resultate der Komplexitätstheorie
zu geben:
∙ Klassische Resultate für Platz- und Zeitkomplexitätsklassen: z.B. die Korrespondenz
zwischen Spielen und Speicherplatz-Beschränkungen, der Nachweis, dass sich mit mehr
Platz oder Zeit auch mehr Probleme lösen lassen, weitere grundlegende Beziehungen
zwischen Zeit- und Platzbasierten Klassen, und die Komplexitätswelt zwischen NP und
PSPACE
∙ Grundzüge der Komplexitätstheorie paralleler, zufallsbasierter und approximativer Algorithmen
∙ Einführung in ausgewählte neuere Themen: Komplexitätstheorie des interaktiven Rechnens,
des probabilistischen Beweisens und Fine-grained Complexity.

VORAUSSETZUNGEN CREDITS

Bestandene mündliche Prüfung

EMPFOHLENE VORKENNTNISSE

Kenntnisse aus einem Grundkurs in theoretischer Informatik (Grundlagen der Komplexitätstheorie einschließlich NP-Vollständigkeit und Reduktionen) werden erwartet

LITERATUR

Einstiegsliteratur für diese Veranstaltung sind die Bücher:
∙ Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer. 2003.
∙ Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University
Press. Eine Vorabversion ist verfügbar unter: http://theory.cs.princeton.edu/
complexity/book.pdf
∙ Papadimitriou. Computational Complexity. Addison-Wesley. Reading. 1995.
∙ Kozen. Theory of Computation. Springer. 2006.

AKTUELLE INFORMATIONEN

Erst wieder ab SS 22!