Modulcode:	Inf-TGIF
Englische Bezeichnung:	Theory of Computation - Continuation
Modulverantwortliche(r):	Prof. Dr. Dirk Nowotka
Turnus:	jedes Jahr im SS (SS19 SS20 SS21 SS22)
Präsenzzeiten:	2V 1Ü
ECTS:	4
Workload:	30 Std. Vorlesung, 15 Std. Präsenzübung, 75 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WI (MEd Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Es werden die theoretischen Grundlagen der Informatik in den Bereichn Berechenbarkeit, Komplexitätstheorie, Automaten und formale Sprachen sowie Korrektheit vermittelt.

Lernziele:

Die Studierenden beherrschen die Lernziele aus dem Modul Grundlagen der Theoretischen Informatik - Einführung (TGIE) zusätzlich zu weiteren Lernzielen. Sie

• erklären die wichtigen Begriffe (siehe Lehrinhalte) sowohl intuitiv als auch mathematisch präzise,
• unterscheiden zwischen entscheidbaren, unentscheidbaren, erkennbaren und nicht erkennbaren Mengen,
• unterscheiden zwischen effizient lösbar und nicht effizient lösbar, inbesondere ordnen sie algorithmische Probleme entsprechend ein,
• beschreiben formale Sprachen durch Grammatiken, Automaten und Ausdrücke,
• unterscheiden zwischen regulären, kontextfreien und nicht kontextfreien Sprachen,
• können grundlegende Algorithmen zur Manipulation von Sprachrepräsentationen und Wortproblemen anwenden, z.B. Potenzmengenkonstruktion, Umwandlung regulärer Ausdrücke in die Automatendarstellung und umgekehrt, Minimierung deterministische endlicher Automaten und die Entscheidung des Wortproblems für kontextreie Sprachen,
• wenden formale Sätze an und vollziehen die zugehörigen Beweise nach.

Lehrinhalte:

Das Modul behandelt die Grundzüge der Theorie der formalen Sprachen, der Automatentheorie und der der Komplexitätstheorie. Zentrale Begriffe sind Berechenbarkeit, Entscheidbarkeit und Erkennbarkeit, Reduzierbarkeit, Komplexitätsklassen, Vollständigkeit, Automaten, Grammatiken, Ausdrücke und Korrektheitsaussagen.

Weitere Voraussetzungen:

Die in der Beschreibung der Module Inf-Math-A und Inf-TGIE aufgeführten Lernziele werden vorausgesetzt.

Prüfungsleistung:

Die Prüfung zum Modul TGIF erfolgt in Form einer Abschlussklausur.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

• Michael Sipser, Introduction to the Theory of Computation, 2nd Ed., Boston: PWS, 2005.
• Dexter C. Kozen, Automata and Computability, Springer, 1997.

Verweise:

Kommentar: