Grundlagen der Theoretischen Informatik III
Winter
(M.Sc.)
(engl. Introduction to the Theory of Computation III )
Modulnummer: FIN-INF-110464 |
|
Kürzel GThI 3 |
CP 6 |
Semester Winter |
Fachsem. ab 1. |
Dauer 1 Semester |
Sprache deutsch |
Niveau Master |
| Link zum LSF: | LSF |
| Zugang beschränkt: | false |
| 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) - M.Sc. VC: Computer Science |
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
| Prüfungsvorleistungen: | Studien-/Prüfungsleistungen: | Lehrform / SWS: |
|
Aktive Teilnahme an der Veranstaltung. Im Unterschied zur B.Sc. Variante muss mindestens einmal eine eigene Lösung zu einer Übungsaufgabe vorgestellt werden. |
Klausur 120 Minuten
|
|
| Voraussetzungen nach Prüfungsordnung: | Empfohlene Voraussetzungen: |
|
keine
|
Grundlagen der Theoretischen Informatik I + II (Bachelor)
|
| Medienformen: | Literatur: |
|
|
|
Hinweise: