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.

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

• 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.