Grundlagen der Theoretischen Informatik III
Winter
(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: | - M.Sc. INF: Informatik - M.Sc. INGINF: Informatik - M.Sc. WIF: Informatik |
|
Kürzel GThI 3 |
CP 6 |
Semester Winter |
Fachsem. None |
Dauer 1 Semester |
Sprache deutsch |
Niveau Master |
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: