Die Vorlesung umfasst zwei inhaltliche Blöcke:

1. Automatentheorie, formale Sprachen und Logik

   Logikkalküle sind Grundlage für eine formale Semantik von sprachlichen Beschreibungen wie auch von Anweisungen in Programmier-, Spezifikations-, und Repräsentationssprachen. In der Vorlesung werden grundlegende Anteile der Aussagenlogik behandelt. Automaten dienen als einfache mathematische Modelle von Computern oder auch Algorithmen. Formale Sprachen dienen der Beschreibung des prinzipiellen, strukturellen Aufbaus von Programmier- und Spezifikationssprachen.

2. Berechenbarkeit und Komplexität

   Die Theorie der Berechenbarkeit untersucht, in Verbindung mit der formalen Beschreibung von Komplexität, die Abgrenzung zwischen effektiv Ausführbarem und prinzipiell niemals Möglichem. Beweisverfahren sind ein grundlegendes Verfahren in diesem Bereich, das grundlegend eingeführt und behandelt wird.

Im Zentrum der Vorlesung steht insbesondere auch die mathematische Beschäftigung mit den oben genannten Themen, d.h. das Aufstellen und formale Beweisen von Behauptungen.

Allgemeine Informationen

Veranstalter: Prof. Dr. Petra Berenbrink und Dr. Daniel Moldt

Organisation: Felix Biermeier

Bedingungen für den Übungsschein:

• Mindestens drei Aufgaben erfolgreich an der Tafel vorrechnen
• Erfolgreiches Kreuzen (50 % Regel)
• Bestehen der OpenOlat-Tests (Alle bis auf 2)

Materialien 

Vorlesungsfolien und Aufgabenblätter werden in OpenOLAT hochgeladen.

Repetitorium:

An den folgenden Terminen werden eingereichte Fragen der Studierenden jeweils im Raum B-201 beantwortet:

• Freitag, 12.7, 14:00 - 18:00 Uhr
• Montag, 15.7, 8:00 - 12:00 Uhr
• Dienstag, 16.7, 14:00 - 18:00 Uhr

An den folgenden Terminen werden eingereichte Fragen der Studierenden jeweils im Raum G-021/022 beantwortet:

• Mittwoch, 4.9, 8:00 - 12:00 Uhr
• Freitag, 6.9, 14:00 - 18:00 Uhr 

Literatur

Vorlesungsmaterialien sind zum Teil auf Deusch und zum Teil auf Englisch. Die Vorlesung stützt sich insbesondere auf das Buch:

• Sipser, Michael. Introduction to the Theory of Computation.

Weitere Literatur zur Vertiefung sind z.B.

• Schöning, Uwe (2000). Logik für Informatiker.
• Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation.
• Hromkovic, Juraj. Theoretische Informatik.