Modulcode:	A4.1
Englische Bezeichnung:
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	jedes Jahr im SS (SS07 SS08 SS09 SS10)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	240 Std.
Dauer:	ein Semester
Modulkategorien:	A (Sonstige)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Lernziele:

Dieses Modul dient dazu, auf mathematisch präzise Weise Antworten auf die folgenden Fragen zu vermitteln: Was können Computer berechnen und was nicht? Wie klassifiziert und vergleicht man Berechnungsprobleme gemäß des zu ihrer Lösung notwendigen Aufwands? Wie definiert man die Syntax von textuellen Objekten? Wie definiert man ihre Semantik? Was bedeutet Korrektheit und wie weist man sie nach?

Lehrinhalte:

Das Modul behandelt die Grundzüge der Rekursionstheorie, der Komplexitätstheorie, der Theorie der formalen Sprachen, der Automatentheorie und der Korrektheitstheorie. Zentrale Begriffe sind Berechenbarkeit, Entscheidbarkeit und Semi-Entscheidbarkeit, Reduzierbarkeit, Komplexitätsklassen, Vollständigkeit, Schwerlösbarkeit, Automaten, Grammatiken, Ausdrücke, Korrektheitsaussagen, Kalküle und (relative) Vollständigkeit.

Weitere Voraussetzungen:

G1.1, G2.1

Prüfungsleistung:

schriftliche Teilprüfungen und Abschlussprüfung

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Michael Sipser, Introduction to the Theory of Computation, 2nd Ed., Boston: PWS, 2005.

Verweise:

Kommentar: