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

Die Interaktiven Studienpläne 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.

Bitte beachten Sie, dass auf dieser Seite keine Aktualisierungen mehr vorgenommen werden. Alle Module und Studienpläne ab der PO-Version 2021 (Bachelor- und Master-Studiengänge) sind ab sofort im Campus-Portal erreichbar.

Modulinformationen zu Automaten und Komplexität im Studiengang Bachelor Ingenieurinformatik 2013
Modulnummer	100535
Prüfungsnummer	2200619
Fakultät	Fakultät für Informatik und Automatisierung
Fachgebietsnummer	2241 (Automaten und Logik)
Modulverantwortliche(r)	Prof. Dr. Dietrich Kuske
Turnus	Sommersemester
Sprache	Deutsch
Leistungspunkte	3
Präsenzstudium (h)	34
Selbststudium (h)	56
Verpflichtung	Pflichtmodul
Abschluss	schriftliche Prüfungsleistung, 90 Minuten
Details zum Abschluss	weitere, alternative Prüfungsform: mündliche Prüfung
Link zum Moodle-Kurs	https://moodle2.tu-ilmenau.de/course/view.php?id=2471
Lehrende
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse	Umgang mit mengentheoretischen Begriffen und Notationen (z.B. erworben in "Mathematik 1")
Lernergebnisse und erworbene Kompetenzen	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.
Inhalt	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
Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form	Tafel, Übungsblätter
Literatur	Schöning "Theoretische Informatik kurzgefasst"
Lehrevaluation