Technische Universität Ilmenau

Automaten, Sprachen und Komplexität - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Automaten, Sprachen und Komplexität im Studiengang Bachelor Informatik 2013
Fachnummer100437
Prüfungsnummer2200342
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2241 (Automaten und Logik)
Fachverantwortliche(r)Prof. Dr. Dietrich Kuske
TurnusWintersemester
SpracheDeutsch
Leistungspunkte8
Präsenzstudium (h)67
Selbststudium (h)173
VerpflichtungPflicht
Abschlussschriftliche Prüfungsleistung, 150 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Vorkenntnisse

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

Lernergebnisse

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.
Inhalt

(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.

Medienformen

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

Literatur
  • 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"
Lehrevaluation

Pflichtevaluation:

WS 2011/12 (Fach)

WS 2017/18 (Fach)

Freiwillige Evaluation:

WS 2012/13 (Vorlesung)

WS 2013/14 (Vorlesung, Übung)

WS 2014/15 (Vorlesung)

WS 2015/16 (Vorlesung, Übung)

SS 2016 (Vorlesung)

WS 2016/17 (Vorlesung, Übung)

SS 2017 (Vorlesung)

WS 2017/18 (Übung)

Hospitation:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.