Folien

  1. Motivation und Organisation (pdf)
  2. Formale Sprachen und Endliche Automaten
    1. Endliche Automaten und Reguläre Sprachen (pdf)
      • DFA und NFA
      • Äquivalenz von DFA, NFA und regulären Ausdrücken
      • Pumping-Lemma, Äquivalenzklassen, Satz von Myhill-Nerode
    2. Grammatiken und kontextfreie Sprachen (pdf)
      • Reguläre und Kontextfreie Grammatiken, CYK-Algorithmus
      • Kellerautomaten, Pumping-Lemma für CFL
  3. Berechenbarkeitstheorie
    1. Turing-Maschinen, Rekursiv aufzählbar, Entscheidbar, Church-Turing-These, Abzählbarkeit, Diagonalisierung, Ko-Aufzählbarkeit, Halteproblem, Postsches Korrespondenztheorem (pdf)
    2. Reduktion, NTM, Äquivalenz-Problem (pdf)
    3. Satz von Rice, Turing-Reduktion, Rekursionstheorem, Kolmogorov-Komplexität (pdf)
  4. Komplexitätstheorie
    1. Komplexitätsklassen (pdf)
      (08.01.2008 pdf: ein Tippfehler beseitigt - Update nicht erforderlich)
    2. P und NP, Polynomzeit-Reduktion, Clique, Subset-Sum, Satz von Cook und Levin (SAT ist NP-vollständig)
      (14.01.2008 pdf: jetzt vollständig, vorher nur 25 Seiten )
    3. NP-Vollständigkeit von Vertex-Cover, Hamilton, UHamilton, Subset-Sum, Approximationsalgorithmen für Vertex-Cover und Traveling Salesperson
      (30.01.2008 pdf: 1. Version)
    4. Platzkomplexitätsklassen, Satz von Savitch, PSPACE, QBF, Spiele
      (06.02.2008 pdf: 1. Version)
  5. Abschluss
    Chomsky-Klassifikation und Überblick
    (06.02.2008 pdf: 1. Version)
Die Folien sind damit vollständig veröffentlicht. Sie werden bei Bedarf aktualisiert.