Lehrstuhl Automatentheorie
Prof. Dr-Ing. Franz Baader

In der Vorlesung Grundlagen der Theoretischen Informatik I werden Automaten und Grammatiken vorgestellt, die formale Sprachen - d.h. Mengen von Wörtern - erkennen bzw. erzeugen. Je nach Typ des Automaten oder der Grammatik erhält man verschieden starke Ausdrucksmittel zur Beschreibung von Klassen formaler Sprachen. Die wichtigsten dieser Klassen sind in der sogenannten Chomsky-Hierarchie zusammengefaßt. Insbesondere die regulären und die kontextfreien Sprachen sind wichtige Hilfsmittel bei der Beschreibung syntaktischer Strukturen z.B. von Programmen. Ihre formale Untersuchung bildet daher die Grundlage für die Übersetzung von Programmiersprachen und die Konstruktion zahlreicher Software-Werkzeuge.

Neben der Vermittlung von Wissen über formale Sprachen, Grammatiken und Automaten ist ein weiteres Ziel der Vorlesung, die Studierenden mit der Arbeitsweise in der Theoretischen Informatik vertraut zu machen.

In der Vorlesung Grundlagen der Theoretischen Informatik II werden formale Berechnungsmodelle eingeführt, die es ermöglichen, den intuitiven Begriff der "berechenbaren Funktion" formal zu definieren. Dies ist insbesondere wichtig, wenn man zeigen will, daß es nicht-berechenbare Funktionen gibt. In der Vorlesung werden Turing-Maschinen, While-Programme und µ-rekursive Funktionen als derartige Berechnungsmodelle eingeführt und es wird gezeigt, daß diese Modelle äquivalent sind, d.h. dieselbe Klasse von Funktionen berechnen. Diese Äquivalenz stützt die These von Church, welche besagt, daß die Turing-berechenbaren Funktionen genau die intuitiv berechenbaren Funktionen sind.

Auch wenn eine Funktion im Prinzip berechenbar ist, kann der Aufwand für ihre Berechnung so hoch sein, daß das Berechnungsverfahren in der Praxis nicht einsetzbar ist. Im zweiten Teil der Vorlesung wird daher ein formaler Rahmen eingeführt, mit dessen Hilfe man die Berechnungskomplexität von Funktionen abschätzen kann. Insbesondere erlaubt dies die Lokalisierung von harten Berechnungsproblemen, d.h. Problemen die (wahrscheinlich) nicht in polynomieller Zeit gelöst werden können.

Hier geht es zu einer ausführlichen Lehrveranstaltungsbeschreibung.

Organisation

Die Vorlesung findet montags in der 3. DS im Hörsaal HSZ/002/H statt und beginnt in der ersten Lehrveranstaltungswoche des Semesters. Das offizielle Vorlesungsskript (Stand März 2007) liegt für die Studenten auf dieser Seite bereit. Die Einschreibung in die einzelnen Übungsgruppen erfolgt über jExam und ist verbindlich. Die Übungen beginnen in der Woche vom 7.04. bis 11.04.08, d.h. mit einer ungeraden Woche (15. Kalenderwoche). In dieser Woche finden die Übungen für Gruppen mit dem Vermerk 1. Woche statt.

Es besteht die Möglichkeit, inhaltliche und organisatorische Fragen zur Lehrveranstaltung innerhalb einer Mailingliste zu diskutieren. Dabei ist zu beachten, dass bei Nutzung der Adresse, die bei der Anmeldung eingesetzt wurde, keine zeitliche Verzögerung wegen Moderation entsteht. Ansprechpartner für den Übungsbetrieb ist Dr. Monika Sturm.

Skript und Folien zur Vorlesung

• Skript (Stand März 2007)

Übungsaufgaben

Übungsaufgaben sind im Vorfeld der jeweiligen Übung auf dieser Seite zu finden und selbständig auszuarbeiten. In den Übungen erfolgt die Diskussion der studentischen Lösungen.

Ab sofort findet die Übung dienstags 1.DS (ungerade Woche) nicht mehr im Raum SCH/A185 statt, sondern im Raum E07.

Ab sofort wird zusätzlich dienstags 5.DS (gerade Woche) eine Übung angeboten. Eine Einschreibung ist seit 10.04.08 über jExam möglich.

Am 18.04.2008 findet leider die Übung in der 4.DS nicht statt (wegen der Veranstaltung OUTPUT). Ersatztermin: Freitag, 25.04.2008, 5.DS, Raum E06. Es wird das 1.Übungsblatt besprochen.

Am 23.04.2008 findet die Übung in der 1.DS letztmalig im Raum SCH/A107 statt. Mit dem 30.04. beginnend werden alle Übungen mittwochs in der 1.DS im Raum E08 durchgeführt.

1. Übungsblatt 115K,
2. Übungsblatt 103K,  Musterlösung A4b)
3. Übungsblatt 309K,
4. Übungsblatt 116K,
5. Übungsblatt 115K,
6. Übungsblatt 99K,
7. Übungsblatt 101K,

Im Mai finden einige Übungen wegen Feiertag bzw. lehrveranstaltungsfreier Zeit nicht statt. Jede Übungsgruppe erhält durch den jeweiligen Übungsleiter die Information, wie und wann ein zusätzlicher Termin für eine Übung anberaumt werden muss, d.h. jeder Student bleibt weiterhin in seiner (entsprechend jExam) eingeschriebenen Gruppe und die Übungsblätter werden in ganz normaler Folge weiter bearbeitet.

Repetitorien

Ziel des Repetitoriums ist es, ausgewählte Kapitel der Vorlesung zu wiederholen, indem den Teilnehmern die auf den Übungsblättern mit *) gekennzeichneten Aufgaben vorgerechnet werden (auch frühere Klausuraufgaben), auf Schwerpunkte der Vorlesung eingegangen wird und Fragen dazu diskutiert werden können.

1. Repetitorium I  (anstelle der Vorlesung am 14.07.2008 in der 3. DS. im Raum HSZ/002)

Literatur

Die hier aufgeführte Literatur kann über den WebOPAC der SLUB gefunden werden.

• Ingo Wegener, Theoretische Informatik, Teubner-Verlag, 1993
• Uwe Schöning, Theoretische Informatik - kurzgefaßt, Spektrum Akademischer Verlag, 1999