Grundlagen der Theoretischen Informatik III

(engl. Introduction to the Theory of Computation III)
Modulnummer: FIN-INF-110464
Link zum LSF:
LSF
Verantwortung:
Prof. Dr. Stefan Schirra
Dozent:in:
Prof. Dr. Stefan Schirra
Lehrveranstaltungen:
Vorlesung Grundlagen der Theoretischen Informatik III
Übung Grundlagen der Theoretischen Informatik III
Verwendbarkeit:
Kürzel
GThI 3
CP
6
Semester
Winter
Fachsem.
ab 1.
Dauer
1 Semester
Sprache
deutsch
Niveau
Master
Angestrebte Lernergebnisse:
Studierende lernen, formale Sprachen in die Chomsky-Hierarchie einzuordnen und beurteilen zu können. Sie verstehen algebraische Zugänge zu Formalen Sprachen. Ferner lernen sie Optionen kennen, mit schweren Problemem umzugehen, und diese anzuwenden.
Inhalt:
Weiteres zu regulären und kontextfreien Sprachen,
Kleene Algebren,
Exakte Exponentialzeitalgorithmen,
Algorithmen für spezielle Graphklassen,
Festparameterhandhabbarkeit,
Approximationsalgorithmen und Nichatapproximierbarkeit
Elementare Komplexitätstheorie.
Arbeitsaufwand:
56h Präsenzzeit + 124h selbstständige Arbeit
Studien-/Prüfungsleistungen:
Lehrform / SWS:
Klausur 120 Minuten
Vorlesung (3 SWS)
Übung (1 SWS)
Voraussetzungen nach Prüfungsordnung:
Empfohlene Voraussetzungen:
keine
Grundlagen der Theoretischen Informatik I + II (Bachelor)
Medienformen:
Literatur:
Sipser; Theory of Computation
Kozen; Automata and Computability
Shallit; A Second Course on Automata and Computability Theory
Hinweise: