Vorlesungs-Folien

    H. Peter Gumm: Theoretische Informatik

    Vorlesungsfolien Sommer 2008

    1. Organisatorisches
      • Inhalt
      • Literatur
      • Organisatorisches
      • Übungen, Klausur, Credits
    2. Überblick
      • Der Aufbau von Sprachen
      • Compiler
      • Berechenbarkeit
      • Komplexität
    3. Alphabete, Worte, Sprachen
      • Alphabete, Worte
      • Sprachen
      • Spracherkennung
      • Entscheidbarkeit
    4. Reguläre Sprachen
      • Reguläre Ausdrücke
      • Gleichungen
      • Syntaxdiagramme
      • Erweiterungen und Anwendungen
    5. Deterministische Automaten (Druckversion)
      • Akzeptoren
      • Homomorphismen, Faktoren
      • Trennbarkeit, Nerode Kongruenz
      • Pumping Lemma, Grenzen von Automaten
      • Minimierung
    6. Nichtdeterministische Automaten (Druckversion)
      • Nichtdeterminismus
      • Epsilon-Transitionen
      • Akzeptanz
      • Vom NFA zum DFA
    7. Äquivalenz
      • Regulärer Ausdruck ==> NFA
      • DFA ==> Regulärer Ausdruck
      • Äquivalenzsatz
      • flex
    8. Kontextfreie Sprachen und Parser
      • Grammatiken und Parser
      • Stack-Automaten
      • Parserstrategien
      • Recursive Descent Parser und LR-Parser
    9. Berechenbarkeit
      • Turingmaschinen
      • LOOP, While, Goto-Programme
      • Primitive Rekursion, µ-Rekursionm
      • Halteproblem, Satz von Rice
    10. Komplexitätstheorie
      • Nichtdeterministisch polynomiale Probleme
      • SAT ist NP-hart
      • Polynomiale Reduzierbarkeit
      • NP-vollständige Probleme