Theoretische Informatik: Berechenbarkeit und Komplexität

Wintersemester 2019/20

Pflichtmodul 3020 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
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 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 bis 23. 10. 2019
Serie bis 28. 10. 2019
Serie bis 7. 11. 2019
Serie bis 21. 11. 2019
Serie bis 28. 11. 2019
Serie bis 9. 12. 2019
Serie bis 18. 12. 2019
Serie bis 9. 1. 2020
Serie bis 15. 1. 2020
Serie bis 23. 1. 2020
Serie bis 23. 1. 2020
Serie bis 30. 1. 2020

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

Literaturempfehlungen

Zusammenfassung, alle Folien

Die vollständigen Unterlagen zum Modul Theoretische Informatik: Berechenbarkeit und Komplexität im WS 2018/19 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
Dirk W. Hoffmann: Theoretische Informatik, Hanser 2009
Rolf Socher: Theoretische Grundlagen der Informatik, Hanser 2008
Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik, Vieweg 2006
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.

http://www.imn.htwk-leipzig.de/~schwarz mailto:sibylle.schwarz@htwk-leipzig.de