Audio/Video

Mitschnitte der Veranstaltung mittels des Lecturnity-Systems (2. Übersicht)

  1. 26.10.2006 (lecturnity, flash): Motivation, Organisation, Endliche Automaten
  2. 27.10.2006 (lecturnity, flash): Reguläre Operatoren, Nichtdeterministische endlichen Automaten
  3. 02.11.2006 (lecturnity, flash): Umwandlung DFA zu NFA, Äquivalenz von NFA und regulären Ausdrücken
  4. 03.11.2006 (lecturnity, flash):  Äquivalenz von DFA und NFA und regulären Ausdrücken
    (Fortsetzung) Pumping-Lemma
  5. 09.11.2006 (lecturnity): Äquivalenzklassen, Satz von Myhill-Nerode, kontextfreie Sprachen
  6. 10.11.2006 (lecturnity, flash): Umwandlung in Chomsky-Normalform, Der Algorithmus von Cocke-Younger-Kasami (CYK), Lösung des Wortproblems der kontextfreien Sprachen
  7. 16.11.2006 (lecturnity, flash): Äquivalenz von PDA und CFG (Kontextfreie Grammatiken)
  8. 17.11.2006 (lecturnity, flash): Äquivalenz von PDA und CFG (Kontextfreie Grammatiken), Pumping-Lemma für kontextfreie Sprachen
  9. 23.11.2006: (lecturnity, flash): Turing-Maschinen (DTM), Mehr-Band-Turing-Maschinen, Rekursiv aufzählbare Sprachen, Entscheidbare Sprachen
  10. 24.11.2006: (lecturnity, flash): Church-Turing-These, Wort-, Leerheits und Äquivalenzproblem für reguläre und kontextfreie Sprachen
  11. 30.11.2006: (lecturnity, flash): Abzählbarkeit, Diagonalisierung, Ko-Aufzählbarkeit
  12. 01.12.2006: (lecturnity, flash): Halteproblem, Postsches Korrespondenzproblem, Reduktion
  13. 07.12.2006: (lecturnity): Nichtdeterministische Turing-Maschine
  14. 08.12.2006: (lecturnity, flash): ein nicht-aufzählbares und nicht-ko-aufzählbares Problem, der Satz von Rice
  15. 14.12.2006: (lecturnity, flash): Orakel-TM, Turing-Reduktion, Brainfuck, Die SELBST-Maschine, Selbstreproduzierende Quines, Reduktionstheorem
  16. 15.12.2006: (lecturnity, flash): Kolmogorov-Komplexität, Optimale Komprimierbarkeit
  17. 21.12.2006: (lecturnity, flash): Komplexitätsklassen, 1-Band-NTM versus DTM, k-Band-DTM versus 1-Band-DTM
  18. 22.12.2006: (lecturnity, flash): P und NP
  19. 11.01.2007: (lecturnity, flash): Verifizierier, Subset-Sum
  20. 12.01.2007: (lecturnity, flash): Abbildungsreduktion, Clique, 3-SAT, NP-schwierig, NP-vollständig
  21. 18.01.2007: (lecturnity, flash): Theorem von Cook/Levin (I)
  22. 19.01.2007: (lecturnity, flash): Theorem von Cook/Levin (II)
  23. 25.01.2007: (lecturnity, flash): NP-vollständigkeit von Vertex-Cover, Hamilton
  24. 26.01.2007: (n/a: Es puffte und qualmte der Pultcomputer und wollte nicht mehr hören, was gesagt werden musste. Die Aufzeichnung wurde nach /dev/null gespeichert. Leider.)
  25. 01.02.2007: (lecturnity, flash): ApproxTSP, ApproxVertexCover, Platzkompexitätsklassen
  26. 02.02.2007: (lecturnity, flash): Satz von Savitch, PSPACE, QBF
  27. 08.02.2007: (lecturnity, flash): PSPACE und Komplexität von Spielen
  28. 09.02.2007: (lecturnity, flash): Chomsky-Typen, Zusammenfassung