course: Komplexitätstheorie

number:
150262
teaching methods:
lecture with tutorials
media:
Moodle
responsible person:
Prof. Dr. Thomas Zeume
lecturer:
Prof. Dr. Thomas Zeume (Mathematik)
language:
german
HWS:
6
CP:
9
offered in:
summer term

dates in summer term

  • start:

Exam

Date according to prior agreement with lecturer.

Form of exam:oral
Registration for exam:FlexNow
Duration:30min

goals

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.

Diese Veranstaltung richtet sich an Studierende der Mathematik und Informatik.

content

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.

requirements

Keine

recommended knowledge

Grundlagen der Theoretischen Informatik

literature

  1. Papadimitroiu, C. "Computational Complexity ", Addison-Wesley, 1993
  2. "Computational Complexity: A Modern Approach", Cambridge University Press, 2009 http://theory.cs.princeton.edu/complexity/book.pdf
  3. Wegener, Ingo "Komplexitätstheorie: Grenzen der Effizienz von Algorithmen", Springer Verlag, 2003
  4. Kozen, Dexter "Theory of Computation", Springer, 2006