Technische Universit├Ąt Ilmenau

Formal Languages and Complexity - Modultafeln of TU Ilmenau

The Modultafeln have a pure informational character. The legally binding information can be found in the corresponding Studienplan and Modulhandbuch, which are served on the pages of the course offers. Please also pay attention to this legal advice (german only). Information on place and time of the actual lectures is served in the Vorlesungsverzeichnis.

subject properties Formal Languages and Complexity in major Master Wirtschaftsinformatik 2011
ATTENTION: not offered anymore
subject number1752
examination number2200069
departmentDepartment of Computer Science and Automation
ID of group 2241 (Automata and Logics Group)
subject leaderProf. Dr. Dietrich Kuske
term Sommersemester
languageDeutsch
credit points3
on-campus program (h)34
self-study (h)56
Obligationobligatory elective
examwritten examination performance, 90 minutes
details of the certificate
maximum number of participants
previous knowledge and experience

Fach "Algorithmen und Programmierung" und "Mathematik 1-2"

learning outcome

Fachkompetenz: Die Studierenden kennen die Grundkonzepte der Theorie der Formalen Sprachen und der Automaten. Sie kennen die grundlegenden Methoden zur Konstruktion von Automaten und das Konzept eines Äquivalenzbeweises. Sie kennen verschiedene Maschinenmodelle, das Konzept der Simulation. Sie kennen Berechenbarkeit / Entscheidbarkeit und das Phänomen der Nicht-Berechenbarkeit, und sind mit den einschlägigen Beispielen vertraut. Sie kennen Grundkonzepte der Komplexitätstheorie wie die in polynomieller Zeit lösbaren Probleme, das Konzept der NP-Vollständigkeit und der Reduktion zwischen Problemen. Sie kennen typische NP-vollständige Probleme und verstehen die Relevanz dieser Eigenschaft.

Methodenkompetenz: Die Studierenden sind in der Lage, die behandelten Algorithmen und Konstruktionsverfahren an Beispieleingaben auszuführen (Automaten-, Grammatiktransformationen, TM-Simulationen). Sie können Nicht-Regularitätsbeweise an einfachen Beispielen durchführen. Sie können für vorgegebene Sprachen / Probleme Automaten und/oder Grammatiken konstruieren. Sie können die zentralen Sätze der Unentscheidbarkeitstheorie anwenden, um die Unentscheidbarkeit semantischer Fragen zu Programmen zu demonstrieren. Sie können einfache Reduktionen zum Beweis der NP-Vollständigkeit von Problemen angeben und erläutern.

content
  1. Formale Sprachen - Deterministische endliche Automaten - reguläre Sprachen, lexikalische Analyse - Nichtdeterministische endliche Automaten - Reguläre Ausdrücke - Erkennen von Nichtregularität - Kontextfreie Grammatiken und kontextfreie Sprachen - Normalformen - EBNF-Formalismus - Ableitungsbäume und Ableitungen - Kellerautomaten - Parsing
  2. Komplexität - Maschinenmodelle, Äquivalenz der Modelle, Church-Turing-These - Entscheidbarkeit und Berechenbarkeit - Unentscheidbarkeit des Halteproblems - Unentscheidbarkeit von semantischen Fragen zu Programmen - Laufzeitschranken - Die Klasse NP und NP-Vollständigkeit - Erfüllbarkeitsproblem für Boolesche Formeln - Beispiele NP-vollständiger Probleme
media of instruction

Vorlesung: Folien

Übung: Übungsblätter (Online) Allgemein: Webseite

literature / references
  • Schöning "Theoretische Informatik kurzgefasst"
  • Asteroth, Baier "Theoretische Informatik"
evaluation of teaching

Pflichtevaluation:

SS 2010 (Fach)

Freiwillige Evaluation:

SS 2011 (Vorlesung, Übung)

SS 2012 (Vorlesung)

SS 2013 (Vorlesung)

Hospitation: