Folien

Powerpoint-Folien der Veranstaltung

  1. 26.10.2006: ppt/pdf: Organisation, Motivation,  Determinische Automaten
  2. 27.10.2006: ppt/pdf: Nichtdeterministische Automaten
  3. 02.11.2006: ppt/pdf: Äquivalenz von DFA und NFA und regulären Ausdrücken
  4. 03.11.2006: ppt/pdf: Äquivalenz von DFA und NFA und regulären Ausdrücken
    (Fortsetzung) Pumping-Lemma
  5. 09.11.2006: ppt/pdf: Äquivalenzklassen, Satz von Myhill-Nerode, kontextfreie Sprachen
  6. 10.11.2006: ppt/pdf: Umwandlung in Chomsky-Normalform, Der Algorithmus von Cocke-Younger-Kasami (CYK), Lösung des Wortproblems der kontextfreien Sprachen
  7. 16.11.2006: ppt/pdf: Der Algorithmus von Cocke-Younger-Kasami (CYK), Keller-Automaten (PDA), Äquivalenz von PDA und CFG (Kontextfreien Grammatiken)
  8. 17.11.2006: ppt/pdf:  Äquivalenz von PDA und CFG (Kontextfreien Grammatiken), Pumping-Lemma für kontextfreie Sprachen
  9. 23.11.2006: ppt/pdf:  Turing-Maschinen (DTM), Mehr-Band-Turing-Maschinen, Rekursiv aufzählbare Sprachen, Entscheidbare Sprachen
  10. 24.11.2006: ppt/pdf: Church-Turing-These, Wort-, Leerheits und Äquivalenzproblem für reguläre und kontextfreie Sprachen
  11. 30.11.2006: ppt/pdf: Abzählbarkeit, Diagonalisierung, Ko-Aufzählbarkeit
  12. 01.12.2006: ppt/pdf: Halteproblem, Postsches Korrespondenzproblem, Reduktion
  13. 07.12.2006: ppt/pdf: Nichtdeterministische Turing-Maschine
  14. 08.12.2006: ppt/pdf: ein nicht-aufzählbares und nicht-ko-aufzählbares Problem, der Satz von Rice
  15. 14.12.2006: ppt/pdf: Orakel-TM, Turing-Reduktion, Brainfuck, Die SELBST-Maschine, Selbstreproduzierende Quines, Reduktionstheorem
  16. 15.12.2006: ppt/pdf: Kolmogorov-Komplexität, Optimale Komprimierbarkeit
  17. 21.12.2006: ppt/pdf: Komplexitätsklassen, 1-Band-NTM versus DTM, k-Band-DTM versus 1-Band-DTM
  18. 22.12.2006: ppt/pdf: P und NP
  19. 11.01.2007: ppt/pdf: Verifizierier, Subset-Sum
  20. 12.01.2007: ppt/pdf: Clique, Subset-Sum, Polynom-Abbildungsreduktion, Reduktion zwischen zwei NP-Problemen, NP-schwierig, NP-vollständig
  21. 18.01.2007: ppt/pdf: Beweis des Satzes von Cook/Levin (SAT ist NP-vollständig)
  22. 19.01.2007: ppt/pdf: Beweis des Satzes von Cook/Levin (SAT ist NP-vollständig),  3-SAT ist NP-vollständig, Clique ist NP-vollständig
  23. 25.01.2007: ppt/pdf: NP-vollständigkeit von Vertex-Cover, Hamilton,
  24. 26.01.2007: ppt/pdf: UHamilton, Subset-Sum, Approximationsalgorithmen für Vertex-Cover und Traveling Salesman
  25. 01.02.2007: ppt/pdf: Approx-TSP, Approx-Vertex-Cover, Platzkomplexitätsklassen, Satz von Savitch
  26. 02.02.2007: ppt/pdf: Platzkomplexitätsklassen, Satz von Savitch, PSAPCE, QBF
  27. 08.02.2007: ppt/pdf: PSPACE und Komplexität von Spielen
  28. 09.02.2007: ppt/pdf: Chomsky-Typen, Zusammenfassung
  29. 15.02.2007: pdf: Probeklausur
  30. 16.02.2007: ppt/pdf: Wunschvorlesung: Die Theorie der Peer-to-Peer-Netzwerke (nicht prüfungsrelevant)
Die Folien werden im MS Powerpoint-Format und als PDF kurz vor der jeweiligen Vorlesung hier veröffentlicht.