| INFMW Informatiktheorie | SG | INF | |
|---|---|---|---|
| Dozent : |
Prof. Dr. Matthias Homeister
eMail
|
Semester | 3 |
| Einordnung : | Master Informatik (Winter-Immatrikulation) | SWS | 4 |
| Sprache : | Deutsch | Art | VÜS |
| Prüfungsart : | PL | Credits | 6 |
| Prüfungsform : | Klausur 120 min | ||
| Voraussetzungen : | |||
| Querverweise : | |||
| Vorkenntnisse : | |||
| 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. 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. Die Studierenden verstehen das Vorgehen von wichtigen Approximationsalgorithmen und sind in der Lage deren Einsatz situationsbezogen zu beurteilen. | ||
| Lehrinhalte : | • Theorie der formalen Sprachen (Automaten, Grammatiken, Chomsky-Hierarchie) | ||
| Literatur : | Sipser M.: Introduction to the Theory of Computation, Cengage Learning, 3nd edition, 2013. Socher R.: Theoretische Grundlagen der Informatik, Hanser Verlag, 3. Auflage, 2008. Hoffmann D. W.: Theoretische Informatik, Hanser Verlag; 3. Auflage, 2015. Mertens S., Moore C.: The Nature of Computation oretische Informatik, Oxford University Press, 2011. | ||