Theoretische Informatik: Berechenbarkeit und Komplexität
Wintersemester 2026/27
bei Prof. Dr. Sibylle Schwarz
Pflichtmodul C144
im 1. Semester Master Informatik
Lernziele / Kompetenzen
Nach erfolgreichem Abschluss des Moduls sind die Studierenden in der Lage,
fundiert die prinzipiellen Möglichkeiten und Grenzen der verschiedenen Berechenbarkeitsmodelle einzuschätzen. Ebenso können sie Abwendungsprobleme hinsichtlich ihrer Schwere einschätzen.
So können sie treffsicher adäquate Mittel für zu lösende algorithmische Aufgaben auswählen und
einsetzen. Ferner können sie unlösbare oder schwer handhabbare Probleme als solche erkennen und
ggf. z.B. auf Methoden für handhabbare Spezialfälle, Näherungslösungen ausweichen.
Inhalt
- Algorithmenmodelle und ihre
Rolle bei der Untersuchung von Grenzen der Berechenbarkeit
- Ausdrucksstärke und Zusammenhang verschiedener
Berechnungsmodelle
- Grenzen der Berechenbarkeit:
Entscheidbarkeit, Aufzählbarkeit,
- Komplexität von Problemen: P, NP, NP-Vollständigkeit, PSPACE
- praktische Folgerungen
Vorlesung
Vorlesungen und Seminare werden während des Semesters im unregelmäßigen
Wechsel stattfinden.
Mehr dazu in der ersten Lehrveranstaltung zum Modul am 12.10.2026
Seminare
Jeder Teilnehmer
nimmt am wöchentlich
stattfindenden Seminar teil.
In den Seminaren werden vorwiegend die Lösungen der schriftlichen
Hausaufgaben besprochen und damit die Zulassungen zur Prüfung
erworben.
Zur vertieften begleiteten Diskussion der Modulinhalte und
Lösungsansätze zu den Übungsaufgaben sind die Foren im
OPAL-Kurs zum Modul
vorgesehen.
Jeder Student nimmt an der wöchentlich stattfindenden Übung zum Modul teil.
In den Übungen werden vorwiegend die Lösungen der schriftlichen
Hausaufgaben besprochen und damit die Zulassungen zur Prüfung erworben.
Praktische Übungsaufgaben gibt es als Hausaufgaben im
Autotool.
(Hinweise für Autotool-Neulinge)
Literaturempfehlungen
Folien zur aktuellen Vorlesung
(werden jeweils nach der Vorlesung veröffentlicht):
Die
Unterlagen zum Modul
Theoretische Informatik: Berechenbarkeit und Komplexität
im WS 2025/26 stehen
hier.
Unterlagen zu den Grundlagen-Modulen aus INB:
Bücher:
- Uwe Schöning:
Theoretische Informatik - kurzgefasst, Spektrum 2001
- John E. Hopcroft, Jeffrey D. Ullman:
Einführung in die Automatentheorie, Formale Sprachen und
Komplexitätstheorie, Addison-Wesley 1990
- Juraj Hromkovic:Theoretische Informatik --
Formale Sprachen, Berechenbarkeit,
Komplexitätstheorie, Algorithmik,
Kommunikation und Kryptographie, Vieweg 2014
- Ingo Wegener: Theoretische Informatik,
Teubner 2005
- Dirk W. Hoffmann:
Theoretische Informatik, Hanser 2009
- Gottfried Vossen, Kurt-Ulrich Witt:
Grundkurs Theoretische Informatik, Vieweg 2016
- Alexander Asteroth, Christel Baier:
Theoretische Informatik. Eine Einführung in Berechenbarkeit,
Komplexität und formale Sprachen, Pearson 2002
- Renate Winter: Theoretische Informatik, Oldenbourg 2002
https://informatik.htwk-leipzig.de/schwarz
mailto:sibylle.schwarz@htwk-leipzig.de