Entscheidbarkeit, Berechenbarkeit und Komplexität (EBK)
1/2. Semester
5 ECTS | 4 SWS
Klausur 90 Minuten (K90)
Inhalte
- 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
Lernziele/Kompetenzen
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.
Literatur
- 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.
Dozentinnen / Dozenten
- Prof. Dr. Lutz Strüngmann
Empfohlene Vorkenntnisse
Es ist sinnvoll, folgende Voraussetzungen mitzubringen:
Daten zum Modul
| Semester |
1/2 |
| Unterrichtssprache |
Deutsch und Englisch |
|
Häufigkeit
|
Unregelmäßig
|
| Kreditpunkte |
5 |
| Modulverantwortlich |
Prof. Dr. Lutz Strüngmann |
| Dauer |
1 Semester |
| Studienleistung |
Keine |
| Prüfungsvorleistung |
Pflichtübung (PU) |
| Prüfungsleistung |
Klausur 90 Minuten (K90) |
Semesterwochenstunden
| Vorlesung |
2 SWS |
| Übung |
2 SWS |
| Summe |
4 SWS |
Arbeitsaufwand (work load)
| Vorlesung |
45 h |
| Selbststudium |
70 h |
| Aufgaben |
15 h |
| Prüfungsvorbereitung |
20 h |
| Summe |
150 h |