Aktueller Eintrag

Logbuch: Theoretische Informatik 2

Vorlesung  im SoSe 2014

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


  1. Mi, 16.04.2014
  2. Eröffnungsveranstaltung. Kapitel 1: Einführung ins Thema. Organisatorisches.
    Kapitel 2: Grundbegriffe zum Thema Wörter und Sprachen. Klassen, Abschlusseigenschaften, Klasse FIN, Abschlusseigenschaften von FIN
    Beginn mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: DFAs, Klasse REG, Pumping-Lemma
    Material:
    Skript "Diskrete Modellierung": Kapitel 7 (Endliche Automaten zur Modellierung von Abläufen)
    Im Skript Kapitel 2 und Kapitel 3.1 (bis einschließlich 3.1.1.)
    Videoaufzeichnung der Vorlesung:
    Übungsaufgaben:
    Übungsblatt 1 wurde ausgeteilt. (In Aufgabe 3 war das echte Teilmengenzeichen zuerst fälschlicherweise ein echtes Obermengenzeichen.)
  3. Mi, 23.04.2014
  4. weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Komplement- und Produktautomat, Abschlusseigenschaften, Nerode-Relation
    Material:
    Im Skript Kapitel 2 und Kapitel 3.1 (bis einschließlich 3.1.3., aber noch nicht den Beweis des Myhill-Nerode-Satzes)
    Videoaufzeichnung der Vorlesung:
    Übungsaufgaben:
    Übungsblatt 2 wurde ausgeteilt.
  5. Mi, 30.04.2014
  6. weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Satz von Myhill-Nerode fertig bewiesen, Minimierung von DFAs
    Material:
    Im Skript Kapitel 3.1 (bis einschließlich 3.1.5). Schwerpunkt auf dem Minimierungs-Algorithmus.
    Videoaufzeichnung der Vorlesung:
    Weitere Lektüre
    Kapitel 3.10 in [S-Sec],
    Diese Veröffentlichung, in der mehrere Algorithmen zur Minimierung von DFAs verglichen werden.
    Übungsaufgaben:
    Übungsblatt 3 wurde ausgeteilt.
  7. Mi, 07.05.2014
  8. weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: NFAs, NFAs mit nichtdeterministischem Startzustand, NFAs mit ε-Übergängen, Brzozowskis Algorithmus, Reversal-Konstruktion.
    Material:
    Im Skript Kapitel 3.2 (bis einschließlich 3.2.3).
    Videoaufzeichnung der Vorlesung:
    Übungsaufgaben:
    Übungsblatt 4 wurde ausgeteilt.
  9. Mi, 14.05.2014
  10. weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Abschluss der Klasse REG unter Vereinigung, Konkatenation und Kleene-Stern anhand von ε-NFAs, reguläre Ausdrücke, erweiterte NFAs, sowie Substitution, Homomorphismus und inverser Homomorphismus.
    Material:
    Im Skript von Kapitel 3.2.4 bis einschließlich 3.3.2). Beachten Sie besonders den Algorithmus ENFA2RegEx und die Beispiele in Kapitel 3.3.2.
    Videoaufzeichnung der Vorlesung:
    Weitere Lektüre
    In der Vorlesung wurde kurz über die Programmbibliotheken für reguläre Ausdrücke gesprochen, die stark automatentheoretisch geprägt sind:
    • RE2: Die Webseite des Projekts finden Sie dort. Besonders relevant ist dieser Text zu den theoretischen Hintergründen.
    • redgrep: Auf der Webseite habe ich nicht viel dazu gefunden, aber es gibt ein Video (YouTube), das ein wenig den Hintergrund erläutert. Die regular expression derivatives, von denen dort die Rede ist, sind ähnlich zu den Ableitungen von regulären Sprachen definiert, die wir bereits aus der Vorlesung kennen.
    Übungsaufgaben:
    Übungsblatt 5 wurde ausgeteilt.
  11. Mi, 21.05.2014
  12. weiter mit Kapitel 3: Endliche Automaten und reguläre Sprachen - heute: Entscheidungsprobleme, reguläre Grammatiken. Einstieg in Kapitel 4: Kontextfreie Sprachen - heute: Kontextfreie Grammatiken, Abschlusseigenschaften, Ableitungsbäume.
    Material:
    Im Skript von Kapitel 3.4 bis einschließlich 4.1.
    Videoaufzeichnung der Vorlesung
    Weitere Lektüre
    In der Vorlesung wurde wieder kurz über die Programmbibliotheken für reguläre Ausdrücke gesprochen, die stark automatentheoretisch geprägt sind. Damit Sie nicht scrollen müssen hier noch einmal die Links:
    • RE2: Die Webseite des Projekts finden Sie dort. Besonders relevant ist dieser Text zu den theoretischen Hintergründen.
    • redgrep: Auf der Webseite habe ich nicht viel dazu gefunden, aber es gibt ein Video (YouTube), das ein wenig den Hintergrund erläutert. Die regular expression derivatives, von denen dort die Rede ist, sind ähnlich zu den Ableitungen von regulären Sprachen definiert, die wir bereits aus der Vorlesung kennen.
    Übungsaufgaben:
    Übungsblatt 6 wurde ausgeteilt.
  13. Mi, 28.05.2014
  14. weiter mit Kapitel 4: Kontextfreie Sprachen - heute: Das Pumping-Lemma für Kontextfreie Sprachen, (Nicht-)Abschlusseigenschaften, Chomsky-Normalform.
    Material:
    Im Skript Kapitel 4.1.1 und 4.1.2.
    Videoaufzeichnung der Vorlesung
    Übungsaufgaben:
    Übungsblatt 7 wurde ausgeteilt.
  15. Mi, 04.06.2014
  16. weiter mit Kapitel 4: Kontextfreie Sprachen - heute: Der CYK-Algorithmus und Mehrdeutigkeit.
    Material:
    Im Skript Kapitel 4.1.3 und 4.1.4.
    Videoaufzeichnung der Vorlesung
    Übungsaufgaben:
    Übungsblatt 8 wurde ausgeteilt. Leider hatten sich ein paar Fehler eingeschlichen; beachten Sie bitte die Hinweise auf der Seite zur Vorlesung (unter Aktuelles).
  17. Mi, 11.06.2014
  18. weiter mit Kapitel 4: Kontextfreie Sprachen - heute: Kellerautomaten (und der Abschluss der Klasse der kontextfreien Sprachen unter inversen Homomorphismen).
    Material:
    Im Skript Kapitel 4.2 bis einschließlich 4.2.1.
    Videoaufzeichnung der Vorlesung
    Übungsaufgaben:
    Übungsblatt 9 wurde ausgeteilt.
  19. Mi, 18.06.2014
  20. weiter mit Kapitel 4: Kontextfreie Sprachen - heute: deterministische Kellerautomaten (und deterministisch kontextfreie Sprachen), Entscheidungsprobleme für kontextfreie Sprachen (und das Postsche Korrespondenz Problem).
    Material:
    Im Skript Kapitel 4.2.2 und 4.3
    Videoaufzeichnung der Vorlesung
    Bonus-Material
    Dort können Sie ein Programm zum Lösen von (manchen) PCP-Instanzen herunterladen.
    Übungsaufgaben:
    Übungsblatt 10 wurde ausgeteilt.
  21. Mi, 25.06.2014
  22. Wiederholung der Tripelkonstruktion. Einstieg in Kapitel 5: Jenseits der kontextfreien Sprachen. Kontextsensitive Sprachen (kontextsensitive und monotone Grammatiken, LBAs) und die Chomsky-Hierarchie.
    Material:
    Im Skript Kapitel 4.2.1, 5.1 und 5.2
    Videoaufzeichnung der Vorlesung
    • Die E-Lecture V11 [HTML5 | Flash | Quicktime | mobile | audio]
      Aus technischen Gründen wurden die Folien bei dieser Vorlesung nicht mit aufgezeichnet. Wir bedauern dies zutiefst, weisen aber gleichzeitig auch darauf hin, dass wir auf die technische Seite der Aufzeichnungen keinen Einfluss haben.
    Übungsaufgaben:
    Übungsblatt 11 wurde ausgeteilt.
  23. Mi, 02.07.2014
  24. Weiter Kapitel 5: Jenseits der kontextfreien Sprachen. Patternsprachen und erweiterte reguläre Ausdrücke.
    Material:
    Im Skript Kapitel 5.3
    Videoaufzeichnung der Vorlesung
    Weitere Lektüre
    In der Vorlesung wurde kurz erwähnt, dass mit erweiterten regulären Ausdrücken Sudoku gelöst werden kann. Eine Skizze der (nicht wirklich praktischen) Herangehensweise findet sich dort.
    Übungsaufgaben:
    Übungsblatt 12 wurde ausgeteilt.
  25. Mi, 09.07.2014
  26. Einstieg Kapitel 6: Anwendungen. Heute: XML, deterministische reguläre Ausdrücke und Glushkov-Automaten.
    Material:
    Im Skript Kapitel 6.1
    Videoaufzeichnung der Vorlesung
    Übungsaufgaben:
    Heute wurde kein Übungsblatt ausgeteilt. Zum Abschluss des Semesters wird es noch ein unbepunktetes Bonusblatt geben (ohne Abgabe, Besprechung oder Korrektur; aber mit Lösungshinweisen).
  27. Mi, 16.07.2014
  28. Weiter mit Kapitel 6: Anwendungen. Heute: Pattern-Matching.
    Material:
    Im Skript Kapitel 6.2
    Videoaufzeichnung der Vorlesung
    Übungsaufgaben:
    Übungsblatt 13 wurde ausgeteilt. Dieses Blatt wird nicht abgegeben und auch nicht korrigiert. Lösungshinweise zu diesen Aufgaben sind hier verfügbar.