Automaten, Sprachen 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 zum Modul Automaten, Sprachen und Komplexität im Studiengang Bachelor Informatik 2013
Modulname	Automaten, Sprachen und Komplexität
Modulnummer	100337
Fakultät	Fakultät für Informatik und Automatisierung
Fachgebietsnummer	2241 (Automaten und Logik)
Modulverantwortliche(r)	Prof. Dr. Dietrich Kuske
Leistungspunkte	8
Verpflichtung	Pflichtmodul
Voraussetzungen	Grundlagen und diskrete Strukturen
Modulabschluss	Einzelleistungen
Details zum Abschluss
Link zum Moodle-Kurs
Lehrende
Anmeldemodalitäten für alternative PL oder SL
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.
Das Modul beinhaltet die folgenden Fächer:
Automaten, Sprachen und Komplexität
Leistungspunkte	8
Verpflichtung	Pflichtmodul
Modulabschluss	schriftliche Prüfungsleistung, 150 Minuten
Turnus	Wintersemester