Grundlagen der Theoretischen Informatik II
Sommer
(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: | - B.Sc. INF: Mathematik / Theoretische Informatik - B.Sc. CV: Informatik - Wahlpflicht - B.Sc. INGINF: Informatik - Wahlpflicht - B.Sc. WIF: Verstehen und Gestalten - Wahlpflicht - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik |
|
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)
| Prüfungsvorleistungen: | Studien-/Prüfungsleistungen: | Lehrform / SWS: |
|
Erfolgreiche Teilnahme an den Übungen, d.h. für je 4 aufeinanderfolgende Übungsblätter 50% der Aufgaben erfolgreich votieren |
Klausur 120 Min (schriftliche Prüfung)
|
|
| 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