Current entry

Logfile: Theoretische Informatik 2

Lecture  in Summer 2012

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.


  1. Do, 12.04.2012
  2. 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.
  3. Do, 19.04.2012
  4. 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.
  5. Do, 26.04.2012
  6. 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.
  7. Do, 03.05.2012
  8. 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
    • Untere Schranken für die Größe von NFAs, NFAs mit epsilon-Übergängen, Abschlusseigenschaften der Klasse aller regulären Sprachen [Flash | QuickTime | Mobile | MP3]
    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.
  9. Do, 10.05.2012
  10. 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
    • Homomorphismen, Anwendung der Abschlusseigenschaften der Klasse aller regulären Sprachen, Entscheidungsprobleme, reguläre Ausdrücke [Flash | QuickTime | Mobile | MP3]
    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.
  11. Do, 24.05.2012
  12. 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.
  13. Do, 31.05.2012
  14. 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
    • Kontextfreie Grammatiken für Programmiersprachen; Ableitungsbäume und eindeutige Grammatiken; Pumping Lemma und Ogden's Lemma [Flash | QuickTime | Mobile | MP3]
    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.
  15. Do, 14.06.2012
  16. 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
    • Beweis von Odgen's Lemma; Abschlusseigenschaften der Klasse aller kontextfreien Sprachen; Kellerautomaten [Flash | QuickTime | Mobile | MP3]
    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.
  17. Do, 21.06.2012
  18. 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
    • Äquivalenz zwischen Kellerautomaten und kontextfreien Sprachen; deterministisch kontextfreie Sprachen; der CYK-Algorithmus [Flash | QuickTime | Mobile | MP3]
    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.
  19. Do, 28.06.2012
  20. 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
    • Halteproblem, (Semi-)Entscheidbarkeit, Rekursive Aufzählbarkeit, Berechenbarkeit, Satz von Rice, Turingmaschinen [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 02.07.2012)
    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.
  21. Do, 05.07.2012
  22. 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
    • (Mehrband-)Turingmaschinen, Church-Turing-These, Gödelnummern, universelle Turingmaschine, Reduktionen, Unentscheidbarkeit der Diagonalsprache und der universellen Sprache [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 05.07.2012)
    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.
  23. Do, 12.07.2012
  24. 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].
  25. Do, 19.07.2012
  26. 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
    • Zusammenfassung der wichtigsten in Vorlesung und Übung behandelten Themen sowie Hilfestellungen zur Klausurvorbereitung [Flash | QuickTime | Mobile | MP3] (Aufzeichnung vom 19.07.2012)
    Weitere Lektüre:
    Das komplette Buch [W-Komp], Kapitel 9 in [W-Theo], Kapitel 1.5 in [S-Theo].