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: |
|
| 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 |
|
| Voraussetzungen nach Prüfungsordnung: | Empfohlene Voraussetzungen: |
|
keine |
Grundlagen der Theoretischen Informatik I + II (Bachelor) |
| Medienformen: | Literatur: |
|
|
|
Hinweise: