| INFMS Informatiktheorie | SG | INF | |
|---|---|---|---|
| Dozent : |
Prof. Dr. Matthias Homeister
eMail
|
Semester | 2 |
| Einordnung : | Master Informatik (Sommer-Immatrikulation) | SWS | 4 |
| Sprache : | Deutsch | Art | VÜS |
| Prüfungsart : | PL | Credits | 6 |
| Prüfungsform : | Klausur 120 min | ||
| Voraussetzungen : | |||
| Querverweise : | |||
| Vorkenntnisse : | Kenntnisse über NFAs, DFAs und kontextfreie Grammatiken, wie in der Bachelor-Lehrveranstaltung „Formale Sprachen / Automatentheorie“ vermittelt. | ||
| Hilfsmittel und Besonderheiten : | Studien- und Prüfungsleistungen: Semesterbegleitende Leistungen können in die Bewertung einbezogen werden. | ||
| Lehrziele : | Die Studierenden verstehen die Theorie der formalen Sprachen und die Chomsky-Hierarchie und können formale Systeme zur exakten Modellierung und Einordnung von Problemen einsetzen. Sie kennen mehrere formale Systeme zur Beschreibung berechenbarer Probleme und verstehen ihre Äquivalenz. Sie verstehen die Äquivalenz von nichtdeterministischen linear beschränkten Automaten und kontextsensitiven Grammatiken. Die Studierenden verstehen die Struktur ausgewählter nicht entscheidbarer Probleme, die Bedeutung von Reduktionen und können einfache Reduktionen konstruieren. Sie kennen die Zeitkomplexität und die Klassen P und NP, sowie mehrere NP-vollständige Probleme und können NP-Vollständigkeit beweisen. Sie kennen und die Klassen P, NP, PSPACE und BQP und verstehen die Zusammenhänge bzgl. der P-NP-Fragestellung. Sie kennen mehrere NP-vollständige Probleme, verstehen die zugehörigen Reduktionsbeweise und können einfache Polynomialzeit-Reduktionen konstruieren. Die Studierenden verstehen das Vorgehen ausgewählter Approximationsalgorithmen und können deren Einsatz situationsbezogen beurteilen. | ||
| Lehrinhalte : | * Theorie der formalen Sprachen: Automaten, Grammatiken, Chomsky-Hierarchie. * Church-Turing-These: Äquivalenz von Turingmaschinenvarianten, von Turingmaschinen, Registermaschinen und Grammatiken, von LBAs und Typ-1-Grammatiken. * Entscheidbarkeit: Halteproblem, Postsches Korrespondenzproblem, Reduktionen * Raum- und Zeitkomplexität: die Klassen P, NP, P-SPACE und BQP * NP-Vollständigkeit: Polynomialzeitreduktionen, der Satz von Cook und verschiedene NP-vollständige Probleme * Approximationsalgorithmen für NP-schwere Optimierungsprobleme | ||
| Literatur : | Sipser M.: Introduction to the Theory of Computation, Cengage Learning, 3nd edition, 2021. Schulz, A.: Grundlagen der Theoretischen Informatik, Springer Vieweg 2022. John MacCormick: What can be computed? Princeton University Press, 2018. Mertens S., Moore C.: The Nature of Computation, Oxford University Press, 2011 Schöning U.: Theoretische Informatik kurzgefasst, Spektrum Akademischer Verlag; 5. Auflage, 2008. Hoffmann D. W.: Theoretische Informatik, Hanser Verlag; 5. Auflage, 2022 | ||