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.