Entscheidbarkeit, Berechenbarkeit und Komplexität

Entscheidbarkeit, Berechenbarkeit und Komplexität (EBK)

1/2. Semester 5 ECTS | 4 SWS Klausur 90 Minuten (K90)

Die Berechenbarkeits- und Komplexitätstheorie bilden mit die wichtigsten Grundlagen der (theoretischen) Informatik. Hierbei geht es um zentrale Fragestellungen der Form: was kann überhaupt (mittels Computern) berechnet werden? Und wie aufwendig ist diese Berechnung? Gibt es Probleme, die unentscheidbar sind? Das bekannteste und vor allem auch mit Abstand das wichtigste bisher ungelöste Problem der theoretischen Informatik ist das P versus NP Problem, welches sich mit der algorithmischen Lösbarkeit von Problemen in polynomieller Zeit beschäftigt. Auch dieses wird Bestandteil der Vorlesung sein.
Im Rahmen dieser Veranstaltung werden grundlegende Kenntnisse zu den Bereichen Berechenbarkeit, Entscheidbarkeit und Komplexität vermittelt. Unter anderem beschäftigen wir uns mit
dem abstrakten Modell eines Rechners - der Turing-Maschine
dem intuitiven Berechenbarkeitsbegriff
der These von Church
den primitiv rekursiven und mu-rekursiven Funktionen
rekursiven und rekursiv aufzählbaren Sprachen
dem Halteproblem
der Unentscheidbarkeit
diversen Komplexitätsklassen
Reduktionen
der NP-Vollständigkeit
einigen NP-vollständigen Problemen (SAT, 3SAT, Node-cover)
einigen NP-harten Problemen

Die Studierenden sind in der Lage,

das Konzept der Turingmaschine zu erläutern und auf aktuelle Fragestellungen anzuwenden,
nicht eingearbeiteten Fachkollegen den Begriff der Unentscheidbarkeit auch anhand von Beispielen zu erläutern,
zentrale Konzepte und Methoden der Komplexitätstheorie zu benennen und anzuwenden,
den Berechenbarkeitsbegriff zu erläutern und
einschlägige, aktuelle Forschungsthemen einzuordnen.

M. Aigner. Diskrete Mathematik. Vieweg Verlag.
J. Hromkovic. Theoretical Computer Science. Texts in Theoretical Computer Science. Springer.
O. Goldreich. Computational Complexity. A Conceptual Perspective. Cambridge University Press.
J. E. Hopcroft and J. D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Oldenbourg Verlag.
K. R. Reischuk. Komplexitätstheorie - Band I: Grundlagen. B. G. Teubner.
I. Wegener. Complexity Theory. Exploring the Limits of Efficient Algorithms. Springer.

Es ist sinnvoll, folgende Voraussetzungen mitzubringen: