Lehrstuhl Automatentheorie
Prof. Dr-Ing. Franz Baader

ERGEBNISSE GTHI-KLAUSUR 24.07.2009

Die Klausur ist korrigiert. Die Ergebnisse liegen dem Prüfungsamt vor. Eine Einsichtnahme in die Prüfungsklausur ist am 23.10.2009 möglich. Für eine Teilnahme ist eine Anmeldung erforderlich. Die Uhrzeit, die mit der Anmeldung dem Studenten zugeordnet wird, ist verbindlich. Die Einsicht findet im Raum INF/3027 statt. Anmeldefrist ist abgelaufen und die Anmeldeliste wurde geschlossen.

Zum Inhalt der Lehrveranstaltung

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 donnerstags in der 4. DS im Hörsaal HSZ / 03/ 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 13.10. bis 17.10.08, d.h. mit einer geraden Woche (42. Kalenderwoche). In dieser Woche finden die Übungen für Gruppen mit dem Vermerk 2. 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.

ACHTUNG: Der Übungsbetrieb im Wintersemester startet vor der ersten Vorlesung, d.h. ab dem 13.10.2008, mit dem 8. Übungsblatt. Der Inhalt der Übung bezieht sich auf den Vorlesungsstoff aus dem Sommersemester 2008.

ACHTUNG: Ab sofort wird dienstags in der 1. DS nur noch in der geraden Woche eine Übung angeboten. Die Übung dienstags in der 1. DS in der ungeraden Woche entfällt wegen fehlenden Bedarfs.

1. Übungsblatt 115K,
2. Übungsblatt 103K,  Musterlösung A4b)
3. Übungsblatt 309K,
4. Übungsblatt 116K,
5. Übungsblatt 115K,
6. Übungsblatt 99K,
7. Übungsblatt 101K,
8. Übungsblatt 99K,
9. Übungsblatt 104K,
10. Übungsblatt 97K,  Definition von A'
11. Übungsblatt 89K,
12. Übungsblatt 103K,
13. Übungsblatt 82K,
14. Übungsblatt 96K,

Am 16.01.09 in der 5. DS, E023 wird die krankheitsbedingt ausgefallene Übung von Marcel Lippmann (vom 15.12.08, 2. DS, HSZ 304) nachgeholt.

Am 23.01.09 ist in der 5. DS, E023 das Repetitorium III geplant.

Am 31.10.08 und 19.11.08 finden Übungen wegen Feiertagen 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

ACHTUNG: Das Repetitorium III findet am 23.01.2009 in der 5. DS im Raum INF/E023 statt.

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)
2. Repetitorium II  14.11.2008 in der 5. DS. im Raum INF/E023
3. Repetitorium III  23.01.2009 in der 5. DS. im Raum INF/E023
4. Musterklausur  5.02.2009 in der 4. DS (Vorlesung)

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