| INFM Informatiktheorie | SG | INF | |
|---|---|---|---|
| Dozent : |
Prof. Dr. Matthias Homeister
eMail
|
Semester | 3 |
| Einordnung : | Informatik Master | 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 kennen 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. Sie kennen die Zeitkomplexität und die Klassen P und NP, sowie mehrere NP-vollständige Probleme und können NP-Schwere beweisen. Die Studierenden verstehen das Vorgehen von wichtigen Approximationsalgorithmen und sind in der Lage deren Einsatz situationsbezogen zu beurteilen. Sie verstehen den Einsatz probabilistischer Methoden für den Algorithmenentwurf. | ||
| Lehrinhalte : | • Theorie der formalen Sprachen (Automaten, Grammatiken, Chomsky-Hierarchie) | ||
| Literatur : | Socher R.: Theoretische Grundlagen der Informatik, Hanser Verlag, 3. Auflage, 2007. Sipser M.: Introduction to the Theory of Computation, Cengage Learning, 2nd edition, 2005. Schöning U.: Theoretische Informatik kurzgefasst, Spektrum Akademischer Verlag; 5. Auflage, 2008. Hromkovic J.: Theoretische Informatik, Vieweg+Teubner, 3. Auflage, 2007. | ||