Komplexitätstheorie (Sommersemester 2024)

Vorlesung: Prof. Dr. Markus Müller-Olm

Übungen: Prof. Dr. Markus Müller-Olm, Roman Lakenbrink

Eintrag für diese Veranstaltung im HIS/LSF

Learnwebkurs zu dieser Veranstaltung

Ort und Zeit

  • Vorlesung: Mo 10:15-12:00 Uhr, M3 und Do 10:15-12:00 Uhr, M3
  • Übung: Mi 10:15-12:00 Uhr, M6

Hinweise

  • Die erste Vorlesung ist am 8. April 2024 im Hörsaal M3.
  • Weitere Hinweise zu dieser Veranstaltung finden Sie im Learnwebkurs. Der Einschreibschlüssel wird in der ersten Vorlesung bekannt gegeben.

Vorlesungsinhalt

Die Komplexitätstheorie ist ein zentrales Gebiet der (theoretischen) Informatik. Sie beschäftigt sich mit der Frage, welche Mindestresourcen zur Lösung algorithmischer Probleme benötigt werden. Mit der Frage, ob die Klassen P und NP tatächlich, wie von nahezu allen Experten vermutet, verschieden sind, hat die Komplexitätstheorie ein sehr prominentes, auch Nichtexperten bekanntes offenes Problem. Die Vorlesung soll eine Einführung in klassische Techniken und Resultate der Komplexitätstheorie geben und behandelt deshalb Themen wie:

  • Das Berechnungsmodell und die Klasse P
  • NP und NP-Vollständigkeit
  • Hierarchiesätze und Diagonalisierung
  • Platzkomplexitätsklassen
  • Die polynomielle Hierarchie und Alternierung
  • Randomisierte Komplexitätsklassen

Literatur

  1. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
  2. Steven Homer and Alan L. Selman, Computability and Complexity Theory, Springer-Verlag, 2013.
  3. Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
  4. Ingo Wegener, Komplexitätstheorie: Grenzen der Effizienz von Algorithmen, Springer-Verlag, 2003.
  5. Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1993