Theoretische Informatik: Berechenbarkeit und Komplexität

Wintersemester 2023/24

Pflichtmodul C144 im 1. Semester Master Informatik

Aktuelles

Auf Wunsch der Modulteilnehmer wird eine freiwillige Konsultation zur Vorbereitung auf die Prüfung angeboten:
Donnerstag, 8. 2. 2024, 14:00 - 15:30 Uhr in GU102
Konkrete Fragen dafür werden vorher im Opal-Forum gesammelt.

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.

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.

Serie 0 vom 19. 10. 2023 (Wiederholung Grundlagen)
Serie 1 vom 2. 11. 2023
Serie 2 vom 9. 11. 2023
Serie 3 vom 16. 11. 2023
Serie 4 vom 30. 11. 2023
Serie 5 vom 4. 12. 2023
Serie 6 vom 7. 12. 2023
Serie 7 vom 14. 12. 2023
Serie 8 vom 21. 12. 2023
Serie 9 vom 11. 1. 2024
Serie 10 vom 22. 1. 2024
Serie 11 vom 29. 1. 2024

Praktische Übungsaufgaben gibt es als Hausaufgaben im Autotool. (Hinweise für Autotool-Neulinge)

Literaturempfehlungen

alle Folien

Die Unterlagen zum Modul Theoretische Informatik: Berechenbarkeit und Komplexität im WS 2022/23 stehen hier.

Unterlagen zu den Grundlagen-Modulen aus INB:

Theoretische Informatik: Automaten und formale Sprachen im SS 2022
Modellierung im WS 2022/23

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