Theoretische Informatik

In diesem Modul werden die folgenden Themengebiete behandelt:

  • Grundbegriffe: Wörter, Alphabete, formale Sprachen, Entscheidungsprobleme, (effiziente) Lösungsalgorithmen für Entscheidungsprobleme
  • Formale Sprachen/Automatentheorie: Chomsky-Grammatiken, Chomsky-Hierarchie, Wortproblem, entscheidbare und effektiv aufzählbare Sprachen, rechtslineare Sprachen, endliche Automaten, nichtdeterministische Automaten, Nerode-Relation und Nerode-Index, Minimierungsalgorithmus für deterministische Automaten, kontextfreie Sprachen, Chomsky-Normalform, CYK-Algorithmus, PumpingLemma für kontextfreie Sprachen, Kellerautomaten, deterministische Kellerautomaten
  • Berechnungstheorie: unlösbare algorithmische Probleme

Steffen Lange (Dozent)

Steffen Lange promovierte 1988 an der Humboldt-Universität zu Berlin mit einer Arbeit zur induktiven Programmsynthese. Im Jahr 2000 habilitierte er an der Universität Leipzig mit einer Arbeit zum induktiven Lernen von rekursiven Sprachen.

Er war Senior Researcher am Deutschen Forschungszentrum fü...

Björn Kinscher (Tutor)