Automaten und Komplexität - Interaktive Studienpläne der TU Ilmenau

Umgang mit mengentheoretischen Begriffen und Notationen (z.B. erworben in "Mathematik 1")

Die Studierenden

• kennen die Stufen 0, 2 und 3 der Chomsky-Hierarchie, ihre automatentheoretischen Charakterisierungen und können die Umwandlungen ausführen,
• sind in der Lage, Nachweise der Nicht-Regularität zu führen,
• sind mit Abschluss- und algorithmischen Eigenschaften der regulären und kontextfreien Sprachen vertraut.

Die Studierenden

• kennen die Klassen der semi-entscheidbaren und der entscheidbaren Probleme mit wesentlichen Beispielen,
• sind in der Lage, die Church-Turing These zu formulieren, ihre Bedeutung darzustellen und Argumente zu ihrer Begründung anzugeben.

Die Studierenden

• kennen die Komplexiätsklassen P und NP und einige NP-vollständige Probleme,
• können erläutern, warum die NP-schweren Probleme nicht effizient lösbar sind.

• reguläre Sprachen: deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, effektiver Abschluss unter Booleschen Operationen, Verkettung und Iteration, Entscheidbarkeit von Leerheit, Inklusion und Äquivalenz, Pumping-Lemma
• kontextfreie Sprachen: Kellerautomaten, Parsing, effektiver Abschluss unter positiven Booleschen Operationen, Verkettung und Iteration, Entscheidbarkeit der Leerheit, Pumping-Lemma, Nichtabschluss unter Schnitt
• semi-entscheidbare Sprachen: Turing-Maschine
• Berechenbarkeit: Church-Turing These, Unentscheidbarkeit des Halteproblems und der Universalität von kontextfreien Sprachen
• Komplexitätstheorie: die Klassen P und NP, NP-Vollständigkeit, 3-SAT, graphentheoretische Probleme

Tafel, Übungsblätter

Schöning "Theoretische Informatik kurzgefasst"

weitere, alternative Prüfungsform: mündliche Prüfung