Claim OwnershipTheoretische Grundlagen der Informatik, Vorlesung, WS15/16
Subscribed: 26Played: 62
Subscribe
Description
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
27 Episodes
Reverse
26: Übung|
0:00:00 Starten
0:00:12 Vorbereitung Klausur: 1. Übungsblatt
0:05:44 2. Übungsblatt
0:06:34 3. Übungsblatt
0:08:49 4. Übungsblatt
0:18:32 5. Übungslbatt
0:25:58 6. Übungsblatt
0:30:05 7. Übungsblatt
0:34:44 8. Übungsblatt
0:41:35 Weihnachtsblatt
0:42:46 10. Übungsblatt
0:45:17 Weiterführende Vorlesungen
0:52:01 11. Übungsblatt
0:55:22 12. Übungsblatt
0:59:14 13. Übungsblatt
1:03:44 14. Übungsblatt
25: Vorlesung und Übung |
0:00:00 Starten
0:02:07 Caesar-Chiffre
0:05:07 Monoalphabetische Verschiebungschiffre
0:06:57 Vigenère-Verschlüsselung
0:20:34 Set Cover
0:27:01 Set Cover Beispiel 1
0:27:37 Set Cover ist NP-vollständig
0:27:53 Beweis ""Set Cover ist NP-hart""
0:35:36 Set Cover Beispiel 2
0:37:40 Beweis F erfüllbar
0:41:18 Bewies ""3SAT ist NP-hart""
0:42:14 Negation in die Blätter drücken
0:43:25 Nichtblattknoten -> Neue Variablen
0:47:21 Clique
0:47:43 Clique Beispiel
0:50:22 Subset Sum
0:50:50 Die Subset Sum Instanz
0:52:51 Integer Linear Programming (ILP)
0:53:30 Directed Hamilton Cycle (DHC)
0:56:23 Umgang mit NP-harten Problemen
24: Vorlesung und Übung |
0:00:00 Starten
0:00:18 Übung: Gedächtnislose Quellen
0:02:16 Übung: Entropiemaximierung
0:06:59 Übung: Decodierbarkeit
0:11:32 Übung: Theoretische Grenzen der Kompression
0:15:27 Übung: Fakten zur Kolmogorov Koplexität
0:20:03 Übung: Einige Beispiele für obere Schranken
0:23:46 Vorlesung: Elias-Fano Kodierung
0:24:37 Vorlesung: Elias-Fano Kodierung - Funktionsweise
0:33:53 Vorlesung: Elias-Fano Kodierung - Anwendung
0:37:15 Vorlesung: Wechselseitiger und bedingter Informationsgehalt
0:47:22 Vorlesung: Verbundentropie und bedingte Entropie
0:49:10 Vorlesung: Übertragungsmodell
0:49:35 Vorlesung: Der Symmetrische Binärkanal
0:53:31 Vorlesung: Transinformation (mutual information)
0:57:41 Vorlesung: Kanalkapazität
1:02:19 Vorlesung: Codierung zum Schutz gegen Übertragungsfehler
1:03:47 Vorlesung: Paritätscodes
1:13:56 Vorlesung: Beispiel ISBN-10
1:14:27 Vorlesung: Block-Codes
20: Vorlesung und Übung |
0:00:00 Starten
0:00:11 Directed Hamilton Cycle (DHC)
0:01:35 Beweis von »DHC ist NP-hart«
0:02:03 Reduktionen
0:02:43 DHC
0:03:34 Beweis von »DHC ist NP-hart«
0:05:07 Ein Knoten pro Variable
0:05:47 Gadget Kj mit 6 Knoten je Klausel
0:08:35 »Vorgesehene« Hamiltonkreise
0:12:12 Unmögliche Hamiltonkreise
0:14:16 Verbindungen der Gadgets
0:18:35 Beispiel
0:27:46 F erfüllbar - Instanz lösbar
0:29:28 Instanz lösbar - F erfüllbar
0:30:41 DHC - Hamilton Circle
0:34:32 Exkurs: Euler-Tour
0:36:11 Gesehene Reduktionen
0:36:53 Komplexität (verallgemeinerter) klassischer Spiele
0:43:48 10. Übung
0:44:23 Integer Linear Programming
0:44:51 ILP: 0-1-Belegung erzwingen
0:45:29 Beispiel: KNAPSACK
0:47:01 Pseudo-polynomieller Knapsack Algorithmus
0:56:04 Approximation von Knapsack
1:01:16 Domino
1:03:34 Domino: Probleme
1:04:00 2-Player Cooperative Dominoes
1:08:19 Weitere Domino-Varianten
1:09:28 Portal 2
1:12:14 3Sat - Super Mario World
23: Vorlesung|
0:00:00 Starten
0:00:42 Thema dieses Kapitels
0:04:32 Information
0:09:03 Wiederholung: Rechenregeln Logarithmus
0:11:49 Entropie
0:13:45 Bemerkungen zur Entropie
0:15:22 Entropie einer Münze mit Wkt p für Zahl
0:16:01 (Platzsparende) Codierungen
0:16:48 Codierungsbäume
0:19:51 Beispiel
0:20:57 Präfix-Codes
0:21:43 Beispiel
0:23:16 Quellencodierungstheorem
0:24:48 Quellencodierungstheorem-Beweis
0:34:37 Shannon-Fano Codierung
0:37:33 Codierungsbaum Shannon-Fano
0:37:46 Bemerkung
0:38:17 Beispiel: Shannon-Fano Codierung
0:38:36 Beispiel: Huffman-Codierung
0:40:41 Huffman-Codierung
0:41:28 Optimalität der Huffman-Codierung
0:41:37 Vorbereitendes Lemma
0:42:44 Vorbreitendes Lemma: Beweis
0:47:00 Beweis-Induktionsschluss
0:51:00 Nachteile der Huffman-Codierung
0:52:49 Lauflängenkodierung
0:59:53 Succinct Datenstrukturen
1:05:59 Bitvektoren mit Zugriff und Rank Operation
1:14:23 Komprimierte Datenstrukturen
1:16:32 Komprimierte Datenstrukturen: Wavelet Tree
1:26:49 Elias-Fano Kodierung
22: Vorlesung und Übung|
0:00:00 Starten
0:00:10 2: Berechenbarkeitstheorie | 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These
0:00:41 Berechenbarkeit Hauptergebnis
0:01:26 2.2 Intuitiver Berechenbarkeitsbgegriff
0:01:48 Beispiel
0:07:15 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit
0:08:41 LOOP-Programme
0:10:29 Äquivalenz von Maschinenmodellen
0:12:04 Markov-Algorithmen
0:14:08 Zellularautomaten
0:15:16 2.4 Primitiv rekursive Funktionen
0:16:11 2.5 Die Ackermannfunktion
0:18:06 Mehr schnell wachsende Funktionen
0:19:06 Wissen über Fleißige Biber
0:20:12 2.6 Halterproblem, Unentscheidbarkeit, Reduzierbarkeit
0:21:05 Paradoxien und Selbstbezüglichkeit
0:22:07 Semi-Entscheidbarkeit
0:24:02 Rekursive Aufzählbarkeit
0:24:51 Äquivalente Aussagen
0:25:30 2.7 Nicht-entscheidbare Probleme
0:26:32 Gödelnummer einer Turingmaschine
0:26:52 Diagonalsprache
0:28:34 Universelle Turingmaschine
0:30:35 Halteproblem
0:31:48 Das beschränkte Halteproblem
0:31:57 Mehr unentscheidbare Probleme
0:32:46 Unentscheidbarkeit von Leerheit
0:33:50 Postsches Korrespondenzproblem (PKP)
0:34:32 Hilberts 10. Problem - Diophantische Gleichungen
0:35:05 Abgeschlossenheit entscheidbarer Sprachen
0:35:31 Nebenläufige Ausführung
0:36:11 Terminologie und Konventionen
0:36:26 Komplexitätsmaße
0:37:37 Obere Schranken
0:37:53 Untere Schranken: Lösungsansätze
0:38:43 Eine Komplexitätsklasse
0:41:07 Polynomiale Reduzierbarkeit
0:43:20 Beispiel
0:48:02 Weitere NP-vollständige Probleme
0:48:31 11. Übung
0:49:09 NP-Schwere Reduktionen
21: Vorlesung |
0:00:00 Starten
0:03:23 1.1 Allgemeines
0:04:18 1.1.1 Grammatiken
0:05:19 1.1.2 Chomsky-Hierachie
0:11:12 1.1.3 Wortproblem
0:12:17 1.1.4 Syntaxbäume
0:13:02 1.2 Reguläre Sprachen
0:14:03 1.2.1 (Deterministische) endliche Automaten
0:14:30 1.2.2 Nichtderterministische (endliche) Automaten
0:19:52 1.2.3 Reguläre Ausdrücke
0:27:01 1.2.4 Das Pumping Lemma (für reguläre Sprachen)
0:33:11 1.2.5 Äquivalenzrelationen und Minimalautomaten
0:46:13 1.2.6 Abschlusseigenschaften
0:58:50 1.3 Kontextfreie Sprachen
0:59:11 1.3.1 Normalformen
1:01:14 1.3.2 Das Pumping Lemma
19: Vorlesung |
0:00:00 Starten
0:03:08 Beweis SUBSET SUM
0:03:31 Beweis ""SUBSET SUM ist NP-hart""
0:03:34 SUBSET SUM
0:06:04 Die SUBSET SUM Instanz
0:10:08 Beispiel
0:13:55 Beweisidee
0:18:29 F erfüllbar -> Instanz lösbar
0:20:42 Instanz lösbar -> F erfüllbar
0:23:44 Beispiel Rucksackproblem
0:24:29 Rucksackproblem
0:26:11 Reduktionen
0:26:56 PARTITION
0:28:30 Beweis SUBSET SUM <= pPARTITION
0:38:39 Integer Linear Programming (ILP)
0:40:14 Beweis von ""ILP ist NP-hart""
0:41:18 Ist ILP in NP ?
0:44:52 Umgang mit NP-harten Probleme
0:55:29 Optimierungsprobleme
0:56:11 NP vollständig
0:57:26 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP)
1:00:20 alpha-Approximation von TSP
1:01:13 HamiltonCycle<=palpha-Approximation von TSP
1:05:45 Pseudopolynomielle Algorithmen
1:07:56 Beispiel Rucksackproblem
18: Vorlesung und Übung|
0:00:00 Starten
0:00:10 Wiederholung: Satz: 3SAT ist NP-vollständig
0:02:06 Wiederholung: Beweis ""3SAT ist NP-hart""
0:02:47 Wiederholung: Negationen in die Blätter drücken
0:03:07 Wiederholung: Nichtblattknoten --> Neue Variablen
0:03:37 Wiederholung: Erfüllbarkeitsäquivalenz
0:05:05 Exkurs: 2SAT ∈ P
0:10:27 CLIQUE
0:14:22 Beweis Clique ∈ NP
0:15:01 Beweis von ""CLIQUE ist NP-hart""
0:19:57 Beispiel
0:29:19 VERTEX COVER (Knotenüberdeckung)
0:31:14 Beweis VERTEX COVER ∈ NP
0:31:32 Beweis von ""VERTEX COVER ist NP-hart""
0:39:11 Gesehene Reduktionen
0:39:39 Beweistechniken für A ≤p B: Spezialfälle
0:43:36 Beweistechniken für A ≤p B: Uminterpretation
0:44:28 Beweistechniken für A ≤p B: Gadgets
0:46:27 Beweistechniken für A ≤p B: Randbedingungen
0:47:33 9. Übung
0:47:35 Komplexitätsklassen - Einführung
0:56:38 Komplexitätsklassen - Fortführung
1:03:57 3SAT ≤p 3COLOR - Einführung
1:05:16 3SAT ≤p 3COLOR - Fortführung
1:09:00 3SAT ≤p 3COLOR - mit Gadget
1:14:08 1-aus-3SAT
1:20:37 XOR-(3)SAT
1:23:07 Einige weitere Varianten
1:26:08 PLANAR 3SAT
1:28:05 Knapsack und Subset Sum
17: Vorlesung|
0:00:00 Starten
0:00:53 Wiederholung Komplexitätstheorie
0:08:54 Polynominale Reduzierbarkeit
0:09:55 Beispiel
0:10:57 NP-harte und Np-Vollständige Probleme
0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ?
0:13:50 SAT: Das Erfüllbarkeitsproblem
0:17:03 Beweis von SAT
0:17:31 Beweis das SAT-NP-hart ist.
0:19:45 Variablen für F
0:24:53 Die Architektir von F=
0:27:08 Beweis w gehört zu der Sprache L, was daraus folgt das F erfüllbar ist
0:31:44 Es kann nur einen geben
0:33:05 Randbedingung
0:37:00 Anfangsbedingung
0:38:46 Übergangsbedingung Ü1, t->t+1
0:42:01 Übergangsbedingung Ü2, t->t+1
0:42:42 Endebedingung E
0:43:56 Gesamtgröße von F
0:48:06 Weitere NP-vollständige Probleme
0:55:04 3SAT (KNF)
0:56:56 Satz: 3SAT ist NP-vollständig
0:58:29 Beweis ""3SAT ist NP-hart""
1:00:12 Negation in die Blätter drücken
1:01:23 Beispiel
1:03:04 Nichtblattknoten -> Neue Variablen
1:05:52 Beispiel
1:06:34 Erfüllbarkeitsäquivalenz von F1
1:07:57 Beispiel
1:10:15 F1 -> 3KNF
16: Übung und Vorlesung|
0:00:00 Starten
0:00:56 Rückblick: Chomsky-3
0:05:29 Rückblick: Chomsky-3 Verfahren
0:16:18 Rückblick: Chomsky-2
0:19:33 Rückblick: Chomsky-2 Verfahren
0:27:23 Rückblick: Chomsky-0/1
0:30:41 Rückblick: Entscheidbarkeit
0:36:54 Ausblick: Komplexitätstheorie
0:38:54 Video: Game of Life Automat
0:43:27 Video: Variante von Game of Life mit realen Werten
0:45:23 Vorlesung
0:46:03 Kapitel 2: Komplexitätstheorie
0:46:34 Obere Schranken
0:46:54 Untere Schranken
0:47:23 Untere Schranken: Lösungsansätze
0:49:08 Eine Komplexitätsklasse
0:50:00 Komplexitätsklasse P
0:50:31 P für verschiedene Maschinenmodelle
0:52:33 Komplexitätsklasse NP
0:53:29 Beispiel: Rucksackproblem
0:54:05 Alternative Definition von NTIME: Orakel
0:55:26 Äquivalenz von NTIME und OTIME
0:55:47 Die 1 000 000 $ Frage
0:57:09 Eine Komplexitätshierarchie
0:59:59 Polynomiale Reduzierbarkeit
1:02:10 Beispiel
1:09:05 NP-harte und NP-vollständige Probleme
1:15:09 Ein einfacher Weg zu Ruhm und Reichtum?
1:20:16 SAT: Das Erfüllbarkeitsproblem
1:23:34 Beweis von SAT ∈ NP
15: Vorlesung|
0:00:00 Starten
0:01:24 Halteproblem
0:02:27 Das beschränkte Halteproblem
0:02:57 Mehr unentscheidbare Probleme
0:03:15 Unentscheidbarkeit von Leerheit
0:09:13 Unentscheidbarkeit von Vollständigkeit
0:09:31 Metaprogrammierung
0:11:03 Postsches Korrespondenzproblem (PKP)
0:12:16 Beispiel
0:19:04 PCP ist semientscheidbar
0:20:25 PCP ist unentscheidbar
0:22:56 Hilberts 10. Problem- Diophantische Gleichungen
0:25:32 Abgeschlossenheit entscheidbarer Sprachen
0:27:58 Anwendung der nebenläufigen Ausführung
0:30:05 Nebenläufige Ausführung
0:33:51 2 Kompexitätstheorie
0:35:04 Terminologie und Konventionen
0:35:47 Komplexitätsmaße
0:38:34 Beispiel: Hamiltonkreisproblem
0:41:42 Beispiel Rucksackproblem
0:43:32 Beispiel: Handlungsreisendenproblem
0:46:08 Obere Schranken
0:47:05 Untere Schranken
0:51:19 Untere Schranken: Lösungsansätze
0:53:32 Eine Komplexitätsklasse
0:55:14 Polynom
0:56:00 Komplexitätsklasse P
0:57:02 P für verschiedene Maschinenmodelle
0:59:19 Transformation Optimierungsproblem -> Entscheidungsproblem
1:02:22 Noch eine Komplexitätsklasse
1:05:15 Komplexitätsklasse NP
1:05:50 Beispiel: Rucksackproblem
1:06:49 Alternative Definition von NTIME: Orakel
1:07:56 Äquivalenz von NTIME und OTIME
1:08:35 Die 1.000.000$ Frage
14: Vorlesung und Übung|
0:00:00 Starten
0:00:10 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit
0:00:44 Paradoxien und Selbstbezüglichkeit
0:01:28 Entscheidbarkeit
0:01:47 Äquivalente Aussagen
0:02:37 2.7 Nicht-entscheidbare Probleme
0:03:04 Normierung von Turing-Maschinen
0:04:24 Gödelnummer (M) einer Turingmaschine M
0:09:01 Gödelnummer
0:09:59 Beispiel
0:10:39 Diagonalsprache
0:12:09 Kapitel 12
0:12:33 Satz: Diagonalsprache ist unentscheidbar
0:15:53 Korollar
0:16:20 Universelle Turingmaschine
0:25:00 Universelle Turingmaschine: 3Band - 1Band
0:28:18 Halteproblem
0:34:09 Das beschränkte Halteproblem
0:35:10 Mehr unentscheidbare Probleme
0:36:42 Unentscheidbarkeit von Leerheit
0:39:44 7. Übung
0:39:44 Universelle Turingmaschinen
0:41:18 Quines
0:43:17 Unentscheidbarkeit
0:44:24 Der Satz von Rice
0:47:14 Es gibt keine perfekten Virenscanner
0:48:11 Beweis über das Halteproblem
0:52:15 Einschub: Rekursionssatz
0:53:26 Beweis mit Rekursionssatz
13: Vorlesung|
0:00:00 Starten
0:00:10 LOOP-Programme
0:01:22 2.5 Die Ackermannfunktion
0:04:23 Totalität der Ackermannfunktion
0:07:53 Wie große Zahlen berechnet ein Loop Programm?
0:10:35 Die Ackermann Funktion ist nicht Loop-berechenbar
0:12:30 Beispiele
0:14:46 Monotonie der Ackermann Funktion
0:15:41 Beweis
0:34:56 Mehr schnell wachsende Funktionen
0:37:13 Wissen über Fleißige Biber
0:38:36 Rekordhalter
0:40:47 Langsam wachsende Funktionen
0:41:34 Union-Find Datenstruktur
0:44:30 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit
0:47:49 Paradoxien und Selbstbezüglichkeit
0:51:34 Entscheidbarkeit
0:52:51 Semi-Entscheidbarkeit
0:57:53 Rekursive Aufzählbarkeit
0:59:41 Rekursiv aufzählbar -> semi-entscheidbar
1:01:37 Semi-entscheidbar -> rekursiv aufzählbar
1:08:25 Äquivalente Aussagen
12: Vorlesung und Übung |
0:00:00 Starten
0:00:10 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit
0:01:04 LOOP-Programme
0:09:28 While-Programm
0:11:26 Äquivalenz von Maschinenmodellen
0:13:55 Turingmaschine emuliert k-Band-TM
0:20:07 k-Band-TM emuliert Registermaschine
0:22:40 Registermaschine emuliert RAM
0:27:59 Markov-Algorithmen
0:36:03 Semi-Thue-Systeme
0:37:16 Zellularautomaten
0:44:32 Quantencomputer
0:49:16 2.4 Primitiv rekursive und µ-rekursive Funktionen
0:50:02 2.5 Die Ackermannfunktion
0:50:24 6. Übung
0:50:36 Turingvollständigkeit
0:52:47 Brainfuck
0:56:20 Lego Mindstorms
0:59:08 Game of Life
1:04:26 Game of Life - Videoeinlage
1:10:18 Magic the Gathering
11: Vorlesung |
0:00:00 Starten
0:00:09 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These
0:00:43 2.2 Intuitiver Berechenbarkeitsbegriff
0:02:41 Beispiel
0:04:51 Exkurs: einige Nährungen für Pi
0:07:47 Beispiel
0:13:09 Nichtberechenbare Funktionen
0:17:58 Church´sche These
0:18:56 Turingmaschinen berechnen Funktionen
0:22:07 Turingmaschinen berechnen numerische Funktionen
0:23:17 Akzeption -> Funktion
0:24:44 Beispiel
0:32:02 Funktionsweise
0:35:24 Beispiel: Die überall undefinierte Funktion
0:35:58 Programmiertechniken für Turingmaschinen
0:40:24 Lokale Variablen
0:41:00 Hintereinanderschalten
0:44:04 Spuren
0:46:11 While-Schleifen
0:48:54 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit
0:50:06 RAM: Random Access Machine
0:56:38 Registermaschine
0:59:52 Registermaschinen-Berechenbarkeit
1:03:10 RAM-Berechenbarkeit
1:04:50 Höhere Programmiersprachen
1:08:16 LOOP-Programme
10: Vorlesung |
0:00:00 Starten
0:00:08 Abschlusseigenschaften Typ 1
0:01:39 Abschluss Vereinigung Typ 0/1
0:03:19 Abschluss Produkt Typ 0/1
0:05:11 Abschluss Komplement Typ 1
0:12:39 Berechnung
0:20:02 Typ 0 Sprachen
0:22:49 Überblick Chomsky-Hierarchie
0:27:54 Abschlusseigenschaften
0:30:09 Entscheidbarkeitsprobleme
0:31:02 Komplexität des Wortproblemes
0:32:27 Überblick Chomsky-Hierarchie
0:33:43 Chomsky-Hierarchie: Eine Kritik
0:37:29 2 Berechenbarkeitstheorie, 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These
0:38:16 Berechenbarkeit Hauptergebnis
0:39:17 2.2 Intuitiver Berechenbarkeitsbegriff
0:40:42 Beispiel
0:42:04 5. Übung
0:42:26 Vereinigung von Sprachen
0:45:01 Zusatzaufgabe 2
0:49:54 Zusatzaufgabe 2 - Exkurs
0:52:43 Zusatzaufgabe 2 - Häufige Fehler
0:54:55 Turingmaschinen Konstruktion und Funktionsweise
08-02: Vorlesung |
0:00:00 Starten
0:00:07 1.3.2 Das Pumping Lemma
0:00:41 Beweis Pumping Lemma
0:01:03 Konsturktion von Wiederholungen:
0:01:24 Faustregeln für Beweise mit dem Pumping Lemma
0:01:47 Abgeschlossenheit von KFG unter U
0:02:07 Nichtabgeschlossenheit von KFG unter U
0:02:30 Beispiel
0:02:56 1.3.5 Kellerautomaten
0:04:08 Konfiguration einer Kellermaschine
0:04:30 Funktionsweise einer Kellermaschine
0:04:54 Kellermaschine als Akzeptor
0:05:19 Beispiel
0:06:04 Satz: L ist kontextrei
0:06:42 Beweis: L ist kontextfrei
0:17:30 1.3.6 Deterministisch kontextfreie Sprachen
0:20:51 Satz
0:22:04 Compiler
0:24:59 Abgeschlossenheitseigenschaften für DKellerA
0:26:16 1.3.7 Entscheidbarkeit für kontextfreie Sprachen
0:26:40 Unentscheidbare Probleme für KFG
0:27:01 Entscheidbare Probleme für DKellerA
0:27:33 4. Übung
0:27:59 CYK-Algorithmus (Chomsky-NF)
0:32:03 CYK-Algorithmus (1. Bsp.)
0:43:12 CYK-Algorithmus (2. Bsp.)
0:46:20 Kellerautomaten
0:55:55 Pumpinglemma kontextfreie Sprachen
0:57:50 Pumpinglemma für CFL: Beispiel
1:07:06 Chomsky-Normalform
09: Vorlesung |
0:00:00 Starten
0:00:08 1.4 Kontextsensitive und Typ 0-Sprachen
0:00:35 Kuroda Normalform
0:02:10 Turing Maschine
0:03:32 Deterministische Einband-Turingmaschine
0:06:23 Nichtdeterministische Turingmaschine
0:07:21 Warum Turingmaschine?
0:10:39 Ursprüngliche Motivation
0:13:23 Potentiell unendlicher Speicher?
0:15:32 Konfiguration einer TM
0:16:47 Funktionsweise DTM
0:18:12 Funktionsweise NTM
0:18:24 Wann hält eine DTM?
0:19:30 Wann hält eine NTM?
0:20:06 Graphinterpretation
0:22:24 Turingmaschine als Akzeptor
0:23:14 Beispiel: Akzeptor für L=1(0,1)*
0:25:14 Vervollständigung
0:27:15 Beispiele
0:39:14 Varianten von Turingmaschinen
0:41:16 Linear Beschränkte Nichtdet. Turingmaschinen
0:49:21 Unterprogramm: Passende linke Seite suchen
0:51:18 Unterprogramm: Ersetzung für AB -> CD
0:51:48 Unterprogramm: Ersetzung für AB -> C
0:58:21 Phase 1: generiere Wort aus Summe*
0:59:57 Phase 2: simuliere Berechnung der TM
1:02:13 Phase 3: regeneriere Eingabewort
1:03:24 Abschlusseigenschaften Typ 1
1:04:22 Überblick Chomsky-Hierarchie
1:04:27 Chomsky-Hierarchie: Eine Kritik
08: Vorlesung |
0:00:00 Starten
0:00:07 Wiederholung
0:01:05 1.3.2 Das Pumping Lemma
0:03:48 Beweis Pumping Lemma
0:13:10 Hilfs Lemma
0:14:39 Anwendung Pumping Lemma
0:22:02 Faustregeln für Beweise mit dem Pumping Lemma
0:26:21 Abschlusseigenschaften
0:27:26 Abgeschlossenheit von KFG unter Vereinigungsmengen
0:29:37 Abgeschlossenheit von KFG unter Produktbildungen
0:30:38 Abgeschlossenheit von KFG unter *
0:33:25 Nichtabgeschlossenheit von KFG
0:38:23 1.3.4 Der CYK-Algorithmus ( Das Wortproblem für kontextfreie Sprachen )
0:41:07 CYK Algorithmus
0:44:29 Beispiel
0:52:24 Impementierung durch dynamische Programmierung
0:55:01 Analyse
1:00:32 1.3.5 Kellerautomaten
1:06:20 Konfiguration einer Kellermaschine
1:06:48 Funktionsweise einer Kellermaschine
1:09:07 Kellermaschine als Akzeptor
1:13:09 Beispiel
Comments
Download from Google Play
Download from App Store
United States