Formale Sprachen und Komplexität

Vorlesungsskript

• skript.pdf

Folien

• 01-begruessung-grundlagen: [Bildschirmversion | Druckversion]
• 02-grammatiken-chomsky-hierarchie: [Bildschirmversion | Druckversion]
• 03-grammatiken-beispiele-epsilon-produktionen: [Bildschirmversion | Druckversion]
• 04-grammatiken-probleme-eigenschaften: [Bildschirmversion | Druckversion]
• 05-dfas: [Bildschirmversion | Druckversion]
• 06-wortproblem-typ1: [Bildschirmversion | Druckversion]
• 07-dfas-regulaer-nfas: [Bildschirmversion | Druckversion]
• 08-determinisierung: [Bildschirmversion | Druckversion]
• 09-nfa-epsilon: [Bildschirmversion | Druckversion]
• 10-regulaere-ausdruecke: [Bildschirmversion | Druckversion]
• 11-satz-von-kleene: [Bildschirmversion | Druckversion]
• 12-pumping-lemma: [Bildschirmversion | Druckversion]
• 13-myhill-nerode: [Bildschirmversion | Druckversion]
• 14-dfa-minimierung: [Bildschirmversion | Druckversion]
• 15-abschlusseigenschaften-entscheidbarkeiten-typ3: [Bildschirmversion | Druckversion]
• 16-cfl-chomsky-normalform: [Bildschirmversion | Druckversion]
• 17-cfl-greibach-nf-und-abschlusseigenschaften: [Bildschirmversion | Druckversion]
• 18-pumping-lemma-cfl: [Bildschirmversion | Druckversion]
• 19-CYK-algorithmus: [Bildschirmversion | Druckversion]
• 20-kellerautomaten: [Bildschirmversion | Druckversion]
• 21-kellerautomaten-aequivalenz: [Bildschirmversion | Druckversion]
• 22-dpdas-und-entscheidbarkeiten: [Bildschirmversion | Druckversion]
• 23-turingmaschinen-und-typ-1-und-typ-0: [Bildschirmversion | Druckversion]
• 24-cfl-entscheidbarkeiten-und-csl-kurodanormalform: [Bildschirmversion | Druckversion]
• 25-satz-von-kuroda-lba-probleme: [Bildschirmversion | Druckversion]
• 26-intuitive-und-turing-berechenbarkeit: [Bildschirmversion | Druckversion]
• 27-tm-konstruktionen-und-loop: [Bildschirmversion | Druckversion]
• 28-while-und-goto-programme: [Bildschirmversion | Druckversion]
• 29-ackermannfunktion: [Bildschirmversion | Druckversion]
• 30-primitiv-und-my-rekursive-funktionen: [Bildschirmversion | Druckversion]
• 31-entscheidbar-unentscheidbar-halteproblem: [Bildschirmversion | Druckversion]
• 32-reduktion-und-satz-von-rice: [Bildschirmversion | Druckversion]
• 33-pcp: [Bildschirmversion | Druckversion]
• 34-p-und-np: [Bildschirmversion | Druckversion]
• 35-np-vollstaendigkeit: [Bildschirmversion | Druckversion]
• 36-satz-von-cook: [Bildschirmversion | Druckversion]
• 37-3sat: [Bildschirmversion | Druckversion]
• 38-clique-independent-set-vertex-cover: [Bildschirmversion | Druckversion]
• 39-setcover-subsetsum-knapsack-partition-binpacking: [Bildschirmversion | Druckversion]
• 40-hamiltoncycle-travellingsalesperson-graphcoloring: [Bildschirmversion | Druckversion]
• 41-wiederholung: [Bildschirmversion | Druckversion]

Videos

• Playlist im LMU Cast