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.

Modulinformationen zum Modul Automaten, Sprachen und Komplexität im Studiengang Bachelor Informatik 2013
ModulnameAutomaten, Sprachen und Komplexität
Modulnummer100337
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2241 (Automaten und Logik)
Modulverantwortliche(r)Prof. Dr. Dietrich Kuske
Leistungspunkte8
VerpflichtungPflicht
Voraussetzungen

Grundlagen und diskrete Strukturen

ModulabschlussEinzelleistungen
Details zum Abschluss
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.

Das Modul beinhaltet die folgenden Fächer:
Automaten, Sprachen und Komplexität
Leistungspunkte8
VerpflichtungPflicht
Fachabschlussschriftliche Prüfungsleistung, 150 Minuten
TurnusWintersemester

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