Grundlagen der Theoretischen Informatik II
(engl. Introduction to the Theory of Computation II)
Modulnummer: FIN-INF-110118 |
| Link zum LSF: | LSF |
| Verantwortung: | Prof. Dr. Stefan Schirra |
| Dozent:in: | Prof. Dr. Stefan Schirra |
| Lehrveranstaltungen: |
|
| Verwendbarkeit: |
|
Kürzel GThI 2 |
CP 5 |
Semester Sommer |
Fachsem. ab 4. |
Dauer 1 Semester |
Sprache deutsch |
Niveau Bachelor |
Angestrebte Lernergebnisse:
Die Studierenden haben erweiterte Fähigkeiten, komplexe Probleme hinsichtlich Berechenbarkeit und Komplexität beurteilen und klassifizieren zu können.
Inhalt:
- Weiterführendes zu Formalen Sprachen und Automatentheorie (Abschlusseigenschaften, deterministische Kellerautomaten, Zustandsminimierung endlicher Automaten),
- Äquivalenz verschiedener Berechnungsmodelle (beispielsweise Turingmaschinen, Registermaschinen, primitiv rekursive und mu-rekursive Funktionen, Grammatiken),
- weitere unentscheidbare und NP-vollständige Probleme.
Arbeitsaufwand:
56h Präsenzzeit + 94h selbstständige Arbeit (Bearbeiten der Übungsaufgaben Nachbereitung der Vorlesungen)
| Studien-/Prüfungsleistungen: | Lehrform / SWS: |
|
Prüfungsvorleistungen: Erfolgreiche Teilnahme an den Übungen (s. Vorlesung)
Prüfung: Klausur 120 Min |
|
| Voraussetzungen nach Prüfungsordnung: | Empfohlene Voraussetzungen: |
|
keine |
Grundlagen der Theoretischen Informatik |
| Medienformen: | Literatur: |
|
|
|
Hinweise:
Auch dieses Modul ist zwei Lehrstühlen zugeordnet, die es abwechselnd bedienen