Theoretische Informatik

In diesem Modul werden die folgenden Themengebiete behandelt:

Grundbegriffe: Alphabete, Wörter, formale Sprachen, Entscheidungsprobleme
Reguläre Sprachen: deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, Abschlusseigenschaften, Pumping-Lemma, Myhill-Nerode-Äquivalenz, Automatenminimierung
Kontextfreie Sprachen: kontextfreie Grammatiken, Kellerautomaten, deterministische Kellerautomaten, Abschlusseigenschaften, Normalformen, CYK-Algorithmus, Pumping-Lemma
Turingmaschinen und Turing-Berechenbarkeit, WHILE-Programme und WHILE-Berechenbarkeit, universelle Turingmaschine und Chuch'sche These
Entscheidbare und Semi-entscheidbare Probleme/Sprachen: Halteproblem, Reduktionsbeweise für Unentscheibarkeit, Satz von Rice
Komplexität von Problemen: Klassen P und NP, NP-Vollständigkeit

Stefan Milius (Dozent)

Stefan Milius ist Professor am Lehrstuhl für Theoretische Informatik an der FAU Erlangen-Nürnberg. Er studierte Informatik in Braunschweig und Mathematik in Toronto. Er promovierte 2005 an der TU Braunschweig, war dann in der Industrie tätig und habilitierte sich 2012 ebenfalls an der TU Braunschwei...