Modulcode:	Inf-TGI
Englische Bezeichnung:	Theory of Computation
Modulverantwortliche(r):	Prof. Dr. Dirk Nowotka
Turnus:	jedes Jahr (SS10 WS10/11 WS11/12 WS12/13 WS13/14 WS14/15 WS15/16 WS16/17 SS17 SS18 SS19 SS20 SS21 SS22)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	A (BSc Inf (15)) V (BSc Inf) A (BSc Inf (2-Fach)) WI (MSc WInf (15)) GU (MSc WInf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-Math-A Inf-ProgOO

Kurzfassung:

Es werden die theoretischen Grundlagen der Informatik in den Bereichn Berechenbarkeit, Komplexitätstheorie, Automaten und formale Sprachen 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 Sprachrepräsentationen und Wortproblemen an, 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 Mathematik A und Inf-ProgOO aufgeführten Lernziele werden vorausgesetzt.

Prüfungsleistung:

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

Die Abschlussklausur wird aus zwei gleichen Teilen bestehen, von denen der erste den Stoff der ersten Veranstaltungshälfte und der zweite den Stoff der restlichen Veranstaltungen umfasst.

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:

Dieses Modul entspricht dem Modul A4.1 der alten BSc-PO.