gehaltene Vorlesungen über Grundlagen der theoretischen Informatik, SoSe 2012

• Mittwoch, den 11. 04. 2012
  • Administrativa
  • Einleitung
    • Was ist theoretische Informatik?
    • Geschichte, Motivation und Fragestellungen
• Montag, den 16. 04. 2012
  • Alphabete, Wörter, Sprachen
  • Operationen auf Sprachen
  • reguläre Ausdrücke und reguläre Sprachen
  • deterministische endliche Automaten
• Mittwoch, den 18. 04. 2012
  • Beispiele für deterministische endliche Automaten
  • nichtdeterministische endliche Automaten
• Montag, den 23. 04. 2012
  • Interpretation von NEAs
  • Äquivalenz von NEAs und DEAs
  • Potenzmengenkonstruktion
• Mittwoch, den 25. 04. 2012
  • Endliche Automaten und reguläre Ausdrücke
    • Konstruktion eines NEA für einen regulären Audsruck
    • Konstruktion eines regulären Ausdrucks für einen DEA (Algorithmus von Kleene)
• Montag, den 30. 04. 2012
  • Konstruktion eines regulären Ausdrucks für einen DEA (Algorithmus von Kleene)
  • Eigenschaften regulärer Sprachen
    • Abschluss unter Komplement und Schnitt
  • Pumping-Lemma: Einführung
• Mittwoch, den 02. 05. 2012
  • Pumping-Lemma: Beweis und Anwendungen
• Montag, den 07. 05. 2012
  • Nerode-Relation und Minimalautomaten
• Mittwoch, den 09. 05. 2012
  • Konstruktion des Minimalautomaten
  • Reguläre Sprachen im Übersetzerbau
  • Turing-Maschinen: Definition
    • Die LEGO-Turing-Maschine
• Montag, den 14. 05. 2012
  • Turing-Maschinen: Beispiele und Varianten
• Mittwoch, den 16. 05. 2012
  • Berechenbarkeit, Church-Turing These
  • Kodierung von Turing-Maschinen
  • Diagonalsprache
  • universelle Sprache und universelle Turingmaschine
• Montag, den 21. 05. 2012
  • Semientscheidbarkeit/rekursive Aufzählbarkeit
  • Halteproblem
  • Reduktionskonzept
  • Abschlusseigenschaften von entscheidbaren und semientscheidbaren Sprachen
• Mittwoch, den 23. 05. 2012
  • Weitere unentscheidbare Probleme:
    • Postsches Korrespondenzproblem,
    • Hilberts Entscheidungsproblem und Gödelscher Unvollständigkeitssatz,
    • diophantische Gleichungen,
    • Erkennen von Computerviren
  • Rekursionssatz und sich-fortpflanzende Programme
  • Fazit Berechenbarkeitstheorie
• Montag, den 28. 05. 2012 (Pfingstmontag)
  • keine Vorlesung
• Mittwoch, den 30. 05. 2012
  • Grammatiken: Definition und Beispiele
• Montag, den 04. 06. 2012
  • Chomsky-Hierarchie: Definition und Eigenschaften
  • Die Chomsky-Hierarchie ist echt
  • Kontextfreie Grammatiken: Syntaxbäume
• Mittwoch, den 06. 06. 2012
  • Kontextfreie Grammatiken: Eindeutigkeit und inhärente Mehrdeutigkeit
  • Chomsky-Normalform
• Montag, den 11. 06. 2012
  • CYK-Algorithmus
  • Pumping-Lemma für kontextfreie Sprachen
• Mittwoch, den 13. 06. 2012
  • Pumping-Lemma für kontextfreie Sprachen
  • Beispielanwendungen des Pumping-Lemmas
• Montag, den 18. 06. 2012
  • Probeklausur
• Mittwoch, den 20. 06. 2012
  • Gastvorlesung von Christoph Benzmüller
    • Folien
• Montag, den 25. 06. 2012
  • Abschlusseigenschaften kontextfreier Sprachen
  • Kellerautomaten
• Mittwoch, den 27. 06. 2012
  • Kellerautomaten: formale Definition und Beispiel
  • Zusammenfassung und Ausblick
• Montag, den 02. 07. 2012
  • Klausur
• Freitag, den 05. 10. 2012, 14–16 Uhr
  • Nachklausur