Automaten und Berechenbarkeit

Sowohl die Vorlesung als auch die Übung finden zu den jeweils angegebenen Zeiten online statt.

Modultitel	Automaten und Berechenbarkeit
Modul-Verantwortliche/r	Dr. Jörg Vogel
Zusammensetzung des Moduls / Lehrformen (V, Ü, S, Praktikum, …)	4V + 2Ü
Inhalte	Formale Sprachen und Automaten (u.a. Chomsky-Hierarchie, Grammatiken, endliche Automaten, Kellerautomaten, Turingmaschinen) Berechenbarkeit (u.a. Berechnungsmodelle und deren Äquivalenz, Entscheidbarkeit und Aufzählbarkeit, Reduktionen, Halteproblem, Postsches Korrespondenzproblem) Theorie der NP-Vollständigkeit
Termine	Vorlesung: Di. 08:00 – 10:00 Uhr Mi. 10:00 – 12:00 Uhr Übung: Do. 10:00 – 12:00 Uhr Do. 12:00 – 14:00 Uhr