Theoretische Informatik: Berechenbarkeit und Komplexität
Wintersemester 2022/23
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
Wöchentlich findet eine Vorlesung statt.
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.
Praktische Übungsaufgaben gibt es als Hausaufgaben im
Autotool.
(Hinweise für Autotool-Neulinge)
Literaturempfehlungen
Zusammenfassung,
alle Folien
Die
Unterlagen zum Modul
Theoretische Informatik: Berechenbarkeit und Komplexität
im WS 2021/22 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
Unter
http://wilfridhodges.co.uk/cognitive01.pdf
gibt es sieben uneingeschränkt richtige Hinweise zum Lernen von Mathematik, die
selbstverständlich genauso für die theoretische Informatik gelten.
https://informatik.htwk-leipzig.de/schwarz
mailto:sibylle.schwarz@htwk-leipzig.de