50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Computational Complexity


Veranstaltungsart und -inhalt

Titel Computational Complexity
Dozent PD Dr. Andreas Jakoby
Einordnung Diplom-Studiengang 6. Semester, Master-Studiengang 2. Semester, Master-Studiengang CLS 2. Semester
Inhalte
  • Struktur von Zeit- und Platz-Klassen
  • Schaltkreis-Komplexität
  • Polynomielle Hierarchie
  • Orakel-Turingmaschinen und Relativierung
  • Vergleich verschiedener Reduktionsarten
  • Probabilistische Klassen
  • Separation von Komplexitätsklassen
  • Berechenbarkeit
Qualifikationsziele
  • Fähigkeit, Probleme bezüglich verschiedener Aufwandmaße einzuordnen
  • Kenntnis der Beziehungen zwischen Maschinenmodellen und Aufwandsmaßen
  • Verständnis der grundlegenden Begriffe und Methoden der Komplexitätsanalyse
Empfohlene Literatur
  • Reischuk, Komplexitätstheorie Teubner 1990
  • D. Kozen, Theory of Computation, Springer 2000
  • K. Wagner, G. Wechsung, Computational Complexity, Reidel 1986
  • B. Cooper, Computability Theory, Chapman & Hall, 2004

Vorlesung

Dozent PD Dr. Andreas Jakoby
Umfang 2 SWS, ECTS-Credits: 4
Termine Mo 14:00 – 16:00, ITCS Seminarraum 2021
Folien [V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | V11 | V12 | V13 | V14 | V15 | alle]

Übung

Assistent Dipl.-Inf. Michael Elberfeld
Umfang 1 SWS
Termine Do 10:00 – 11:00, ITCS Seminarraum 2021
Aufgaben Übungswiki