Technische Universität Ilmenau

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

Die Modultafeln sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Automaten, Sprachen und Komplexität im Studiengang Bachelor Informatik 2013
Modulnummer100437
Prüfungsnummer2200342
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2241 (Automaten und Logik)
Modulverantwortliche(r)Prof. Dr. Dietrich Kuske
TurnusWintersemester
SpracheDeutsch
Leistungspunkte8
Präsenzstudium (h)67
Selbststudium (h)173
VerpflichtungPflichtmodul
Abschlussschriftliche Prüfungsleistung, 150 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen

Prüfungsgespräch (mündliche Abschlussleistung) in Distanz nach §6a PStO-AB

Dauer: 30 Minuten

Technische Voraussetzung: Webex https://intranet.tu-ilmenau.de/site/vpsl-pand/SitePages/Handreichungen_Arbeitshilfen.aspx

Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

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

Lernergebnisse und erworbene Kompetenzen

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 und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

zum Moodle-Kurs

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)

WS 2018/19 (Vorlesung, Übung)

Hospitation: