Grundlagen der Theoretischen Informatik III
Winter
(engl. Introduction to the Theory of Computation III )
Modulnummer: FIN-INF-110464 |
|
Kürzel GThI 3 |
CP 6 |
Semester Winter |
Fachsem. starting at 1. |
Dauer 1 Semester |
Sprache deutsch |
Niveau Master |
| Link zum LSF: | LSF |
| Zugang beschränkt: | |
| Verantwortung: | Prof. Dr. Stefan Schirra |
| Dozent:in: | Prof. Dr. Stefan Schirra |
| Lehrveranstaltungen: |
|
| Verwendbarkeit: | - M.Sc. INF: Informatik - M.Sc. INF: Informatik Wahlpflicht (SPO 2027) - M.Sc. INGINF: Informatik - M.Sc. WIF: Informatik - M.Sc. WIF: Informatik Wahlpflicht (SPO 2027) |
Angestrebte Lernergebnisse:
Students learn to classify and evaluate formal languages in the Chomsky hierarchy. They understand algebraic approaches to formal languages. They will also learn about options for dealing with serious problems and how to apply them.
Inhalt:
- More about regular and context-free languages,
- Kleene Algebras,
- Exact exponential time algorithms,
- Algorithms for special graph classes,
- Fixed-parameter tractability,
- Approximation algorithms and non-approximability
- Elementary complexity theory.
Arbeitsaufwand:
56h attendance time + 124h independent work
| Prüfungsvorleistungen: | Studien-/Prüfungsleistungen: | Lehrform / SWS: |
|
Written exam 120 Minuten
|
|
| Voraussetzungen nach Prüfungsordnung: | Empfohlene Voraussetzungen: |
|
none
|
Grundlagen der Theoretischen Informatik I + II (Bachelor)
|
| Medienformen: | Literatur: |
|
|
|
Hinweise: