Grundlagen der Theoretischen Informatik II

Sommer
 
(engl. Introduction to the Theory of Computation II
)
Modulnummer: FIN-INF-110118
Kürzel
GThI 2
CP
5
Semester
Sommer
Fachsem.
ab 4.
Dauer
1 Semester
Sprache
deutsch
Niveau
Bachelor
Link zum LSF:
 LSF
Zugang beschränkt:
Verantwortung:
Prof. Dr. Stefan Schirra
Dozent:in:
Prof. Dr. Stefan Schirra
Lehrveranstaltungen:
Vorlesung Grundlagen der Theoretischen Informatik II
Übung Grundlagen der Theoretischen Informatik II
Verwendbarkeit:
- B.Sc. INF: Mathematik / Theoretische Informatik
- B.Sc. INF: Aufbaumodule (SPO 2027)
- B.Sc. CV: Informatik - Wahlpflicht
- B.Sc. CV: Computervisualistik Wahlpflicht (SPO 2027)
- B.Sc. INGINF: Informatik - Wahlpflicht
- B.Sc. INGINF: Informatik Wahlpflicht (SPO 2027)
- B.Sc. WIF: Verstehen und Gestalten - Wahlpflicht
- B.Sc. WIF: Informatik Wahlpflicht (SPO 2027)
- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik
- B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)
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)
Vorlesung (2 SWS)
Übung (2 SWS)
Voraussetzungen nach Prüfungsordnung:
Empfohlene Voraussetzungen:
keine
Grundlagen der Theoretischen Informatik
Medienformen:
Literatur:
Sipser; Theory of Computation
Kozen; Automata and Computability
Hinweise:
Auch dieses Modul ist zwei Lehrstühlen zugeordnet, die es abwechselnd bedienen