Theoretische Informatik: Berechenbarkeit und Komplexität
Wintersemester 2020/21
bei Prof. Dr. Sibylle Schwarz
Pflichtmodul C144
im 1. Semester Master Informatik (bis INM19 im 3. Semester)
Aktuelles
Prüfung am 15.2.2021, 8:00 Uhr im Autotool
Vorbesprechung 7:40 Uhr (20 min vor der Prüfung) im BBB,
Zugangsdaten an der üblichen Stelle
Vorlesungen und eine Übung finden für alle Teilnehmer gemeinsam als
synchrone Online-Veranstaltungen über BigBlueButton statt. Die
Zugangsdaten werden im OPAL-Kurs zum Modul bekanntgegeben.
Vertiefende Diskussionen der Inhalte finden asynchon im Forum im
OPAL-Kurs zum Modul statt.
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
- Zusammenhang zwischen Ausdrucksstärke der
Algorithmenmodelle und Komplexität der Probleme
- Grenzen der Berechenbarkeit: P/NP, NP-Vollständigkeit, Entscheidbarkeit, Aufzählbarkeit, praktische Folgerungen
Vorlesung
Wöchentlich findet eine Vorlesung statt.
Übungen
Jeder Teilnehmer
nimmt an der wöchentlich online synchron stattfindenden Übung teil.
In den Übungen 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
Folien zur aktuellen Vorlesung
(werden jeweils nach der Vorlesung veröffentlicht):
Die vollständigen Unterlagen zum Modul
Theoretische Informatik: Berechenbarkeit und Komplexität
im WS 2019/20 stehen
hier.
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