Automata, languages and complexity - Interactive curriculae of TU Ilmenau

sicherer Umgang mit mengentheoretischen Begriffen und Notationen (z.B. erworben in "Grundlagen und Diskrete Strukturen")

Die Studierenden

• kennen die Stufen der Chomsky-Hierarchie, ihre  automatentheoretischen Charakterisierungen, können die Umwandlungen ausführen und die für die gegebene Problemstellung adäquate Darstellung wählen,

• sind in der Lage, Nicht-Regularitäts- und Nicht-Kontextfreiheitsbeweise zu führen,
• sind mit Abschlusseigenschaften und Entscheidbarkeits- und Komplexitätsaspekten insbesondere der regulären und kontextfreien Sprachen vertraut.

Die Studierenden

• kennen die Klassen der semi-entscheidbaren und der entscheidbaren Probleme,
• sind in der Lage, die Church-Turing These zu formulieren, ihre Bedeutung darzustellen und sie zu begründen,
• können durch Reduktionen die Unentscheidbarkeit neuer Probleme beweisen.

Die Studierenden

• kennen Zeit- und Platzkomplexiätsklassen (insbes. P und NP) und einige vollständige Probleme in diesen Klassen,
• können die Komplexität neuer Probleme beurteilen und ihre effiziente (Un)Lösbarkeit begründen.

(A) Chomsky-Hierarchie:

(1) reguläre Sprachen und ihre Beschreibung mittels deterministischer und nichtdeterministischer endlicher Automaten, regulärer Ausdrücke und rechtslinearer Grammatiken, algorithmische Umformung dieser Beschreibungsmethoden, Entscheidungsverfahren für Leerheit, Inklusion und Äquivalenz, Nicht-Regularitätsbeweise mittels Myhill-Nerode und mittels Pumping-Lemma, Minimalautomat.

(2) kontextfreie Sprachen und ihre Beschreibung durch nichtdeterministische Kellerautomaten und kontextfreie Grammatiken in Normalform, algorithmische Umformung (Parsing), deterministische Kellerautomaten, Nicht-Kontextfreiheitsbeweise mittels Pumping-Lemma, Nicht-Abschluss unter Schnitt und Komplement, Entscheidungsverfahren für Leerheit.

(3) kontextsensitive Sprachen: linear beschränkte Automaten

(4) rekursiv aufzählbare Sprachen: nichtdeterministische Turingmaschinen

(B) Berechenbarkeitstheorie

Turing-, LOOP-, WHILE- und GOTO-Berechenbarkeit, (primitiv) rekursive Funktionen, Ackermann-Funktion, Church-Turing These, Unentscheidbarkeit des Halteproblems, der Universalität von kontextfreien Sprachen und des Post'schen Korrespondenzproblems

(C) Komplexitätstheorie

Komplexitätsklassen P, NP, PSPACE und EXPTIME, NP-Vollständigkeit von 3CNF-SAT und von ausgewählten graphentheoretischen Problemen (durch polynomielle Reduktionen), PSPACE-Vollständigkeit von QBF.

Folien, Mitschnitte der Vorlesungen,Übungsblätter (online)

• Schöning "Theoretische Informatik kurzgefaßt"
• Hopcroft, Motwani, Ullman "Einführung in die Automatentheorie, Formale Sprachen und Komplexität"
• Asteroth, Baier "Theoretische Informatik"
• Wegener "Theoretische Informatik"