Theoretische Informatik: Berechenbarkeit und Komplexität
Wintersemester 2021/22
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.
Praktische Übungsaufgaben gibt es als Hausaufgaben im
Autotool.
(Hinweise für Autotool-Neulinge)
Literaturempfehlungen
Zusammenfassung,
alle Folien
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