Berechenbarkeit und Komplexität

Mitteilungen

Die mündlichen Prüfungen im SS 2026 nimmt Prof. Kuske vom 18.08. - 21.08.2026 ab. Bitte beachten Sie zur Terminvergabe die Hinweise.
Um bei Interesse aktuelle Informationen (Raumänderungen, korrigierte Übungsaufgaben, ...) zu erhalten, tragen Sie sich bitte im Moodle-Kurs ein.

Vorlesung 01 (09.04.): Intuitiver Berechenbarkeitsbegriff und Loop-Vermutung
Folien, Mitschnitt
Vorlesung 02 (16.04.): Primitiv-rekursive Funktionen und Hilberts Vermutung
Folien, Mitschnitt
Vorlesung 03 (23.04.): Ackermann-Funktion, partielle Funktionen
Folien, Mitschnitt
Vorlesung 04 (30.04.): while- und goto-Berechenbarkeit, μ-Rekursivität
Folien, Mitschnitt
Vorlesung 05 (07.05.): Die Turing-Maschine
Folien, Mitschnitt
Turings Artikel "On computable numbers ..." finden Sie hier.
Vorlesung 06 (13.05.): Turing-Berechenbarkeit
Folien, Mitschnitt
Vorlesung 07 (21.05.): Entscheidbarkeit und unentscheidbare Probleme
Folien, Mitschnitt
Vorlesung 08 (28.05.): Der Satz von Rice, Semi-Entscheidbarkeit
Folien, Mitschnitt
Vorlesung 09 (04.06.): Universelle Turing-Maschinen, Posts Korrespondenzproblem
Folien, Mitschnitt
Vorlesung 10 (11.06.): Logik-Probleme
Folien, Mitschnitt
Vorlesung 11 (18.06.): Kontextfreie Sprachen
Folien, Mitschnitt
Vorlesung 12 (25.06.): Komplexitätsklassen
Folien, Mitschnitt
Vorlesung 13 (09.07.): NP-Vollständigkeit
Folien, Mitschnitt

Übung 01 (17.04.): Aufgabenblatt
Übung 02 (04.05.): Aufgabenblatt
Übung 03 (15.05.): Aufgabenblatt
Übung 04 (29.05.): Aufgabenblatt
Übung 05 (12.06.): Aufgabenblatt
Übung 06 (26.06.): Aufgabenblatt
Übung 07 (10.07.): Aufgabenblatt

Vorlesung: (Prof. Dr. Dietrich Kuske)

Donnerstag, 13:00 - 14:30 Uhr, HU-Hs (Humboldtbau)
Übungen: (M. Sc. Sebastian Pfau)

Freitag (G), 11:00 - 12:30 Uhr, Sr H 1518 (Helmholtzbau)
Montag (U), 13:00 - 14:30 Uhr, Sr H 2509 (Helmholtzbau)
Konsultation: (M. Sc. Sebastian Pfau)

Dienstag (G), 13:00 - 14:30 Uhr, Sr K 2003B (Kirchhoffbau)

Wir veröffentlichen jede zweite Woche ein Übungsblatt, dessen Aufgaben Sie bitte jeweils vor der Übung lösen. Zu den angegebenen Übungsterminen bespricht Herr Pfau mit Ihnen Ihre Lösungen. Zudem haben Sie die Möglichkeit, die Lösung gesondert markierter Aufgaben abzugeben. (jeweils Freitag 11 Uhr, Abgabe vor der Übung, im Briefkasten im Flur vor Raum Z 1047 oder handschriftliche Abgaben über moodle).
Ihre Abgaben werden anschließend von uns kontrolliert und bewertet; sie gehen als Bonus in die Bewertung des Modulabschlusses ein.
Zu bestimmten Übungstermin wird ein kurzer Test geschrieben, in dem Definitionen, Sätze etc. abgefragt werden. Auch die hierbei erhaltenen Punkte gehen als Bonus in die Bewertung ein.
Der erste Test wird zu Beginn der zweiten Übung geschrieben.