Modulcode:	Inf-TGIE
Englische Bezeichnung:	Theory of Computation - Introduction
Modulverantwortliche(r):	Prof. Dr. Dirk Nowotka
Turnus:	jedes Jahr im SS (SS18 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:	A (BSc WInf (15)) WI (MSc WInf (15))
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

• 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,
• wenden grundlegende Algorithmen zur Manipulation von der Repräsentation regulärer Sprachen an, z.B. Potenzmengenkonstruktion,
• wenden formale Sätze an.

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 oder Inf-I1-2FNF aufgeführten Lernziele werden vorausgesetzt.

Prüfungsleistung:

Die Prüfung zum Modul TGIE 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: