Berechenbarkeit und Komplexität

Inhalt

Die Vorlesung gibt eine Einführung in die Gebiete der Berechenbarkeits- und Komplexitätstheorie.

Dazu werden verschiedene Zugänge zum Berechenbarkeitsbegriff vorgestellt und miteinander verglichen. Darüber hinaus wird problematisiert, welche Problemstellungen effizient lösbar sind und welche nicht.

  • Berechenbarkeit: Intuitiver Berechenbarkeitsbegriff und Churchsche These, verschiedene äquivalente Formalisierungen des Berechenbarkeitskonzepts, Halteproblem, Reduzierbarkeit und Unentscheidbarkeit.
  • Primitiv-rekursive und LOOP-berechenbare Funktionen sowie Ackermannfunktion
  • Komplexitätstheorie: Komplexitätsklassen, das P-NP Problem, effiziente Reduzierbarkeit, NP-Vollständigkeit des Erfüllbarkeitsproblems und verschiedener Graphenprobleme.

Moodle

Der gesamte Vorlesungs-, Übungs- bzw. Tutorienbetrieb sowie wichtige Ankündigungen und Informationen zu Klausuren wird über die Lernplattform Moodle durchgeführt.

Literatur

  • Vorlesungsskript: Berechenbarkeit und Komplexität
  • U. Schöning: Theoretische Informatik - kurz gefasst. Spektrum Akademischer Verlag, 5. Auflage, 2008.
  • A. Meier, H. Vollmer: Komplexität von Algorithmen. Nachdruck. Lehmanns media, 2015.
  • M. Garey, D. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. Nachdruck. W H Freeman & Co, 1979.
  • M. Sipser: Introduction to the Theory of Computation. Cengage Learning, 3. Auflage, 2013.

    Übungsleiter

    Jan-Hendrik Lorenz

    Weitere Informationen

    LSF-Eintrag