Logbuch: Theoretische Informatik 2
Vorlesung im SoSe 2012
Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.
- Do, 12.04.2012
-
Eröffnungsveranstaltung.
Kapitel 1: Einführung ins Thema. Organisatorisches. Einige
Grundbegriffe zum Thema Worte und Sprachen.
Beginn mit Kapitel 2: Endliche Automaten und reguläre Sprachen - heute: DFAs, NFAs und Mealy Automaten.- Material:
-
Skript "Diskrete
Modellierung": Kapitel 7 (Endliche Automaten zur Modellierung
von Abläufen)
Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 1 (Einführung) und Kapitel 2 (Endliche Automaten) - Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
- Weitere Lektüre:
- Kapitel 1 sowie Kapitel 2.1-2.3 und 2.7-2.8 in [HU], Kapitel 1.2.1-1.2.3 in [S-Theo], Kapitel 4.1 und 4.4 in [W-Theo], Kapitel 4 in [W-Komp]
- Übungsaufgaben:
- Übungsblatt 1 wurde ausgeteilt. Zusätzlich dazu kann ein Blatt mit Präsenzaufgaben, deren Lösung in der ersten Übungsstunde besprochen wird, hier heruntergeladen werden.
- Do, 19.04.2012
-
Weiter mit Kapitel 2: Endliche Automaten und reguläre
Sprachen - heute: Minimierung von DFAs; insbesondere: der Äquivalenzklassenautomat
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
- Vortragsfolien und ein Beispiel zur Konstruktion des Äquivalenzklassenautomaten (Tafelanschrieb)
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 3.4 in [HU], Kapitel 1.2.5 in [S-Theo], Kapitel 4.2 in [W-Theo], Kapitel 4 in [W-Komp]
- Übungsaufgaben:
-
Übungsblatt 2
wurde ausgeteilt.
Anmerkung: Aufgabe 2 wird von Blatt 2 gestrichen, da die darin verwendeten Begriffe in der Vorlesung vom 19.04.2012 noch nicht behandelt wurden. Die Punkte für die verbleibenden Aufgaben werden wie folgt verteilt: Aufgabe 1: 34 Punkte, Aufgabe 3: 26 Punkte, Aufgabe 4: 20 + 20 = 40 Punkte.
- Do, 26.04.2012
-
Weiter mit Kapitel 2: Endliche Automaten und reguläre
Sprachen - heute: Der Satz von Myhill und Nerode, das Pumping Lemma
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 3.4 und 3.1 in [HU], Kapitel 1.2.5 und 1.2.4 in [S-Theo], Kapitel 4.2 und 4.3 in [W-Theo], Kapitel 4 in [W-Komp]
- Übungsaufgaben:
- Übungsblatt 3 wurde ausgeteilt.
- Do, 03.05.2012
-
Weiter mit Kapitel 2: Endliche Automaten und reguläre
Sprachen - heute: Beispiele für die Anwendung (und das Scheitern)
des Pumping Lemmas, untere Schranken für die Größe von NFAs,
NFAs mit epsilon-Übergängen, Abschlusseigenschaften
der Klasse aller regulären Sprachen
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
-
Kapitel 3.1, 2.4 und 3.2
in [HU],
Kapitel 1.2.4 und 1.2.6
in [S-Theo],
Kapitel 4.2 und 4.3 in [W-Theo],
Kapitel 4
in [W-Komp].
Die "Fooling Set Methode" zum Nachweis unterer Schranken an die Größe von NFAs wird in der folgenden Arbeit beschrieben: I. Glaister, J. Shallit, A lower bound technique for the size of nondeterministic finite automata, Information Processing Letters 59, pages 75-77, 1996. - Übungsaufgaben:
- Übungsblatt 4 wurde ausgeteilt.
- Do, 10.05.2012
-
Weiter mit Kapitel 2: Endliche Automaten und reguläre
Sprachen - heute: Homomorphismen, Beispiele für die Anwendung der Abschlusseigenschaften
der Klasse aller regulären Sprachen, Entscheidungsprobleme, reguläre Ausdrücke
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 3.2, 3.3 und 2.5 in [HU], Kapitel 1.2.6, 1.2.7 und 1.2.3 in [S-Theo], Kapitel 4.6 und 5.3 in [W-Theo], Kapitel 4 in [W-Komp].
- Übungsaufgaben:
- Übungsblatt 5 wurde ausgeteilt.
- Do, 24.05.2012
-
Abschluss von Kapitel 2: Endliche Automaten und reguläre
Sprachen - heute: Der Satz von Kleene, reguläre Ausdrücke für
Komplement und Durchschnitt, reguläre Grammatiken, Zusammenfassung
der in Kapitel 2 behandelten Themen
Beginn mit Kapitel 3: Kontextfreie Sprachen - heute: Beispiele für kontextfreie Grammatiken- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 2 (Endliche Automaten) und Kapitel 3 (Kontextfreie Sprachen)
- Vortragsfolien und Beweis, dass eine in der Vorlesung entwickelte KFG die Sprache aller Worte mit gleich vielen Nullen wie Einsen erzeugt (Tafelanschrieb)
- Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
- Weitere Lektüre:
-
Kapitel 2.5, 9.1, 4.1 und 4.2
in [HU],
Kapitel 1.2.3 und 1.3
in [S-Theo],
Kapitel 5.3 und 6.1 in [W-Theo],
Kapitel 4 und 6
in [W-Komp].
Die unteren Schranken für die Größe von regulären Ausdrücken für Komplement und Durchschnitt finden sich in in der folgenden Arbeit: W. Gelade, F. Neven, Succinctness of the Complement and Intersection of Regular Expressions. ACM Transactions on Computational Logic, Volume 13, Issue 1, Article No. 4, 2012. - Übungsaufgaben:
- Übungsblatt 6 wurde ausgeteilt.
- Do, 31.05.2012
-
Weiter mit Kapitel 3: Kontextfreie Sprachen - heute:
kontextfreie Grammatiken für Programmiersprachen; Ableitungsbäume
und eindeutige Grammatiken; Pumping Lemma und Ogden's Lemma;
Chomsky Normalform
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 3 (Kontextfreie Sprachen)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 4.3, 4.5 und 6.1 in [HU], Kapitel 1.3.1 und 1.3.2 in [S-Theo], Kapitel 6.1, 6.2, 6.4 in [W-Theo], Kapitel 6 in [W-Komp].
- Übungsaufgaben:
- Übungsblatt 7 wurde ausgeteilt.
- Do, 14.06.2012
-
Weiter mit Kapitel 3: Kontextfreie Sprachen - heute:
Beweis von Ogden's Lemma; Abschlusseigenschaften der Klasse aller
kontextfreien Sprachen; Kellerautomaten (PDAs)
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 3 (Kontextfreie Sprachen)
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 6.1, 6.2, 5.1, 5.2 in [HU], Kapitel 1.3.2, 1.3.3, 1.3.5 in [S-Theo], Kapitel 6.4, 6.5, 7.2 in [W-Theo], Kapitel 6 in [W-Komp].
- Übungsaufgaben:
- Übungsblatt 8 wurde ausgeteilt.
- Do, 21.06.2012
-
Abschluss von Kapitel 3: Kontextfreie Sprachen - heute:
Äquivalenz zwischen Kellerautomaten und
kontextfreien Sprachen (u.a.: die Tripelkonstruktion); deterministisch kontextfreie
Sprachen; das Wortproblem für kontextfreie Sprachen (der CYK-Algorithmus)
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 3 (Kontextfreie Sprachen)
- Vortragsfolien und ein Beispiellauf des CYK-Algorithmus (Tafelanschrieb)
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 5.3, 10.1-10.3, 6.3 in [HU], Kapitel 1.3.5, 1.3.6, 1.3.4 in [S-Theo], Kapitel 6 und 7 in [W-Theo], Kapitel 6 in [W-Komp].
- Übungsaufgaben:
- Übungsblatt 9 wurde ausgeteilt.
- Do, 28.06.2012
-
Beginn mit Kapitel 4: Berechenbarkeit - heute:
Das Halteproblem, Entscheidbarkeit, Semi-Entscheidbarkeit,
Rekursive Aufzählbarkeit,
Berechenbarkeit, der Satz von Rice, (Einleitung zum Thema) Turingmaschinen
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 5 (Berechenbarkeit)
- Turingmaschinen in Aktion (auf YouTube): A Turing Machine In The Classic Style und The LEGO Turing Machine
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 7 und 8 in [HU], Kapitel 2 in [S-Theo], Kapitel in [W-Theo], Kapitel 2 in [W-Komp].
- Übungsaufgaben:
- Übungsblatt 10 wurde ausgeteilt.
- Do, 05.07.2012
-
Weiter mit Kapitel 4: Berechenbarkeit - heute:
Turingmaschinen, die Church-Turing-These,
Mehrband-Turingmaschinen, Gödelnummern, universelle
Turingmaschine, Reduktionen, Unentscheidbarkeit der
Diagonalsprache D und der universellen Sprache U
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 5 (Berechenbarkeit)
- Turingmaschinen in Aktion (auf YouTube): A Turing Machine In The Classic Style und The LEGO Turing Machine
- Vortragsfolien
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Kapitel 7 und 8 in [HU], Kapitel 2 in [S-Theo], Kapitel in [W-Theo], Kapitel 2 in [W-Komp].
- Übungsaufgaben:
- Übungsblatt 11 wurde ausgeteilt.
- Do, 12.07.2012
-
Abschluss von Kapitel 4: Berechenbarkeit - heute:
Unentscheidbarkeit des Halteproblems H und des speziellen
Halteproblems Hε, das Postsche
Korrespondenzproblem PKP, unentscheidbare Grammatik-Probleme
(u.a. "leerer Schnitt", "Subsumption", "Äquivalenz",
"Mehrdeutigkeit" und "Regularität" für KFGs,
sowie "leerer Schnitt" und "Äquivalenz" für DPDAs).
Kapitel 5: Die Chomsky Hierarchie - heute: allgemeine Grammatiken (Typ 0), kontextsensitive Grammatiken (Typ 1), kontextfreie Grammatiken (Typ 2), reguläre Grammatiken (Typ 3), Charakterisierung der Typ 0-Sprachen als die semi-entscheidbaren Sprachen, Charakterisierung der kontextsensitiven Sprachen als die durch linear beschränkte Automaten (nichtdeterministische linear Platzbeschränkte Turingmaschinen) erkennbaren Sprachen.- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011): Kapitel 5 (Berechenbarkeit) und Kapitel 6 (Komplexitätsklassen und die Chomsky Hierarchie)
- Vortragsfolien
-
Videoaufzeichnung
der Vorlesung: Die E-Lectures zu den Themen
- Unentscheidbarkeit des Halteproblems und des speziellen Halteproblems, Unentscheidbarkeit des Postschen Korrespondenzproblems, unentscheidbare Grammatik-Probleme [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 12.07.2012)
- Die Chomsky Hierarchie [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 12.07.2012)
- Weitere Lektüre:
- Kapitel 8 und 9 in [HU], Kapitel 2.6, 2.7, 2.8 und 1.1.2 und 1.3.7 und 1.4 und 1.5 in [S-Theo], Kapitel 2.6, 2.7, 2.8 und 6.6 und 5 in [W-Theo], Kapitel 2, 6 und 5 in [W-Komp].
- Do, 19.07.2012
-
Hilfestellungen zur Klausurvorbereitung. Insbes.: Details zum
Ablauf der Klausur, Zusammenfassung der wichtigsten in Vorlesung
und Übung behandelten Themen,
Durcharbeiten von Teilen
der zweiten
Klausur aus dem
Sommersemester 2010.
- Material:
- Prof. Schnitgers Skript "Formale Sprachen und Berechenbarkeit" (SoSe 2011)
- "offiziell erlaubter Spickzettel", der bei der Klausur ausgeteilt wird
- Klausuren aus früheren Semestern: die Klausuren aus dem SoSe 2002, die erste Klausur aus dem SoSe 2010, die zweite Klausur aus dem SoSe 2010.
- Videoaufzeichnung der Vorlesung: Die E-Lecture zum Thema
- Weitere Lektüre:
- Das komplette Buch [W-Komp], Kapitel 9 in [W-Theo], Kapitel 1.5 in [S-Theo].