| 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 einzuordnenund 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 ihreralgorithmischen 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.