Komplexitätstheorie

SS 2006

Termine

Art Termin Ort   Veranstalter
V4 Di 10:00 - 11:30 AH I 4. April E. Grädel
Fr. 10:00 - 11:30 AH I 21. April E. Grädel
Ü2 Mi 17:15 - 18:45 5056 12. April E. Grädel

Übungen

Skript

  • Kapitel 1: Turingmaschinen und deterministische Komplexitätsklassen [ps] [pdf]
  • Kapitel 2: Nichtdeterministische Komplexitätsklassen [ps] [pdf]
  • Kapitel 3: NP-vollständige Probleme [ps] [pdf]
  • Kapitel 4: PSPACE und die polynomiale Hierarchie [ps] [pdf]
  • Kapitel 5: Paralelle Berechnungsmodelle I: Alternierende Turingmaschinen [ps] [pdf]
  • Kapitel 6: Paralelle Berechnungsmodelle II: Schaltkreise [ps] [pdf]
  • Kapitel 7: Komplexitätstheorie für Optimierungsprobleme [ps] [pdf]
  • Kapitel 8: Komplexitätstheorie für probabilistische Algorithmen – erweiterte Fassung, mit Artus-Merlin-Spielen [ps] [pdf]

Inhalt

Die Komplexitätstheorie klassifiziert algorithmische Probleme aufgrund der zur ihrer Lösung benötigten Ressourcen (wie Rechenzeit, Speicherplatz, Hardware, ....). In der Vorlesung werden die wichtigsten Komplexitätsklassen für deterministische, nichtdeterministische, parallele und probabilistische Berechnungen behandelt. Von besonderer Bedeutung sind die Zusammenhänge zwischen verschiedenen Berechnungsmodellen und vollständige Probleme in den wichtigsten Komplexitätsklassen.

Literatur

Einführende Literatur

Weiterführende Literatur

Voraussetzungen

  • Grundbegriffe zur Berechenbarkeit und Komplexität

Zuordnung

  • Informatiker: Theoretische Informatik, Vertiefungsfach
  • Mathematiker: Angewandte Mathematik
  • Lehramtskandidaten: Angewandte Mathematik (D)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science
  • Sonstige: Informatik

Leistungsnachweis

  • Informatiker und Mathematiker: Übungsschein bei aktiver Teilnahme an den Übungen
  • Software Systems Engineering (M.Sc.): active participation in exercises and final examination

Rückfragen

Erich Grädel, Vince Bárány, Tobias Ganzow, Łukasz Kaiser