Automaten und Berechenbarkeit

Modultitel

Automaten und Berechenbarkeit

Modul-Verantwortlicher

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