| Videoinhalt | |
|---|---|
| Begrüßung | 0:00 |
| Themenübersicht | 1:17 |
| Sprachen in der Informatik | 1:36 |
| Programmiersprachen | 3:00 |
| Grammatiken | 3:20 |
| Maschinen | 3:42 |
| Sprachen und Automaten | 4:29 |
| Berechenbarkeit | 6:00 |
| Qualifikationsziele | 7:10 |
| Videoinhalt | |
|---|---|
| Online-Vorlesungen per Video | 0:00 |
| Quizfragen | 0:41 |
| Fragestunde 10:15-11:00 | 0:59 |
| Fragen im Forum | 1:23 |
| Betrachtung der Videos | 2:06 |
| Prüfungstermin voraussichtlich in der vorletzten Semesterwoche | 2:25 |
| Quiz | 2:25 |
| Prüfungsformat | 2:58 |
| Übungsbeginn in der ersten Woche | 3:36 |
| Videoinhalt | |
|---|---|
| endliches Alphabet | 0:00 |
| Wörter | 0:54 |
| Länge |x| eines Wortes | 1:42 |
| das leere Wort | 1:52 |
| Hintereinanderschreiben | 2:59 |
| Assoziativität | 5:16 |
| keine Kommutativität | 6:02 |
| Quiz | 6:43 |
| Monoid (Halbgruppe mit Einselement) | 6:44 |
| Potenz von Wörtern | 7:45 |
| Videoinhalt | |
|---|---|
| Formale Sprachen | 0:00 |
| Beispiele von Sprachen | 0:45 |
| algorithmische Probleme als Sprachen | 2:46 |
| Operationen mit Sprachen, Mengenoperationen | 6:42 |
| Verkettung von Sprachen | 7:08 |
| Monoid aller Sprachen | 8:39 |
| Rechenregeln | 9:17 |
| Potenz von Sprachen | 9:37 |
| *-Operation | 10:10 |
| Videoinhalt | |
|---|---|
| *-Operation | 0:00 |
| Format von Dezimalzahlen | 0:09 |
| +-Operation | 2:30 |
| Quiz | 3:11 |
| regulärer Ausdruck | 5:54 |
| Anwendung regulärer Ausdrücke | 6:57 |
| Kodierung regulärer Ausdrücke | 7:20 |
| Anwendungsbeispiel | 9:13 |
| reguläre Sprachen | 13:31 |
| Videoinhalt | |
|---|---|
| Rückblick auf formale Sprachen | 0:00 |
| deterministischer endlicher Automat | 0:50 |
| Getränkeautomat | 1:15 |
| Folge von Eingaben | 1:42 |
| innerer Zustand | 2:18 |
| Arbeitsweise des Automaten | 2:40 |
| Verarbeitung eines Eingabebeispiels | 3:34 |
| Ergebnis der Verarbeitung | 5:48 |
| formale Definition | 6:37 |
| endliche Zustandsmenge | 6:42 |
| Eingabealphabet | 7:14 |
| Startzustand | 7:34 |
| Übergangsfunktion | 7:55 |
| Übergangstabelle | 9:30 |
| Menge F der akzeptierenden Zustände | 10:51 |
| 5 Dinge bestimmen einen DEA | 11:38 |
| Quintupel | 11:55 |
| Zustandsdiagramm | 12:11 |
| Determinismus | 13:20 |
| DEA zur Beschreibung des Verhaltens | 14:00 |
| Videoinhalt | |
|---|---|
| Arbeitsweise eines endlichen Automaten | 0:00 |
| von einem Automaten akzeptierte Sprache | 1:20 |
| Beispiel | 1:40 |
| erweiterte Übergangsfunktion δ* | 2:42 |
| Quiz | 3:34 |
| induktive Definition von δ* | 3:51 |
| formale Definition von L(A) | 6:34 |
| Analyse eines kleinen Beispielautomaten | 7:40 |
| Quiz | 10:15 |
| Vergleich verschiedener Darstellungen einer Sprache | 11:17 |
| Videoinhalt | |
|---|---|
| Programmieren mit endlichen Automaten | 0:00 |
| 1. gerade und ungerade Anzahl an Symbolen | 0:21 |
| 2. erster und letzter Buchstabe verschieden | 3:44 |
| Quiz | 5:23 |
| 3. gegebenes Anfangsmuster 011 | 5:25 |
| 4. Muster am Ende | 7:09 |
| 5. Muster im Inneren | 10:20 |
| Teilwortproblem | 12:36 |
| genauere Charakterisierung der Zustände | 15:25 |
| Präfix, Suffix | 15:53 |
| 6. gleiche Anzahl an Nullen und Einsen | 19:38 |
| Videoinhalt | |
|---|---|
| Berechnungsweg eines endlichen Automaten | 0:00 |
| Quiz | 2:51 |
| nichtdeterministischer Automat (NEA) | 3:25 |
| Übergangsrelation δ | 3:43 |
| Gegenüberstellung zu DEA | 4:19 |
| Nichtdeterminismus | 5:47 |
| Zustandsdiagramm | 6:02 |
| Verarbeitung eines Eingabewortes | 8:43 |
| ERZEUGUNG von Wörtern durch einen NEA | 9:13 |
| Beispiel: Verkehrsmittel in einem Verkehrsnetz | 9:36 |
| Berechnungsweg für einen NEA | 14:07 |
| formale Definiton, wann ein Wort akzeptiert wird | 16:16 |
| willkürliche Festlegung bei nicht eindeutiger Antwort | 16:37 |
| die von A akzeptierte Sprache L(A) | 18:21 |
| Videoinhalt | |
|---|---|
| Beispiele mit FLACI | 0:00 |
| Simulation des Ablaufs | 1:44 |
| akzeptierte Sprache | 2:48 |
| Übergangstabelle | 9:24 |
| Alternative: Übergangsfunktion in die Potenzmenge der Zustände | 11:37 |
| Beziehung zwischen den beiden Definition | 12:37 |
| kleine Sprachkunde: automaton, automata | 15:11 |
| das Paradoxon | 16:50 |
| Videoinhalt | |
|---|---|
| Simulation eines NEA | 0:00 |
| erreichbare Zustandsmenge Ri nach i Schritten | 0:46 |
| Beispiel | 1:35 |
| Akzeptanztest | 4:43 |
| Grundidee des Algorithmus | 5:50 |
| Algorithmus | 6:28 |
| Videoinhalt | |
|---|---|
| Äquivalente Definitionen regulärer Sprachen | 0:00 |
| NEA als Verallgemeinerung von DEA | 1:44 |
| äquivalente Automaten | 2:25 |
| äquivalente reguläre Ausdrücke | 2:38 |
| Idee der Konstruktion | 3:05 |
| Potenzmengenkonstruktion | 5:08 |
| Beispiel | 9:19 |
| Aufstellen der Übergangsfunktion | 9:38 |
| systematisches Aufstellen der Tabelle | 11:44 |
| bedarfsorientiertes Ausfüllen der Tabelle | 12:51 |
| exponentielles Wachstum der Zustandsmenge | 14:22 |
| DEA mit neuen Namen | 15:14 |
| Startzustand und akzeptierende Zustände | 16:33 |
| Analyse des entstandenen DEA | 17:56 |
| der Simulationsalgorithmus im Lichte des DEA | 18:26 |
| DEA mit allen 2^n Zuständen | 19:57 |
| unerreichbare Zustände | 21:42 |
| Zusammenfassung | 22:51 |
| Videoinhalt | |
|---|---|
| reguläre Sprachen | 0:00 |
| Syntaxdiagramme für reguläre Ausdrücke | 1:22 |
| graphische Darstellung eines regulären Ausdrucks | 4:35 |
| Erzeugen eines Wortes | 5:45 |
| Ähnlichkeit mit einem NEA | 6:28 |
| Unterschiede zu einem NEA | 7:28 |
| Einfügen von Zustandsknoten | 7:51 |
| Auflösen von längeren Wörtern | 8:58 |
| ε-Übergänge | 9:21 |
| NEA mit ε-Übergängen | 10:35 |
| Berechnungsweg | 11:44 |
| Ausblick | 13:53 |
| Videoinhalt | |
|---|---|
| induktiver Aufbau eines regulären Ausdrucks | 0:00 |
| reduziertes Repertoire an Bausteinen | 1:03 |
| endliche Sprachen | 1:39 |
| Konstruktion des NEA-ε | 2:35 |
| Produkt | 4:49 |
| Vereinigung | 7:28 |
| *-Operation | 9:39 |
| Abschluss des Beweises | 11:14 |
| Videoinhalt | |
|---|---|
| Notwendigkeit der ε-Übergänge | 0:00 |
| Vermischung der Berechnungswege | 1:20 |
| Gegenmaßnahmen | 1:54 |
| Vereinigung | 2:39 |
| *-Operation | 3:34 |
| Elimination der ε-Übergänge | 5:15 |
| Betrachtung eines Berechnungsweges | 5:59 |
| Gruppieren der ε-Übergänge | 7:02 |
| Behandlung der abschließenden ε-Übergänge | 8:20 |
| Erweiterung der akzeptierenden Zustände F | 8:48 |
| Notation für ε-Erreichbarkeit | 9:35 |
| Allgemeine Bedeutung von * | 10:14 |
| Modifikation des Automaten | 10:30 |
| 1) Gruppieren mit dem nachfolgenden Übergang | 10:35 |
| 2) Erweiterung von F | 12:35 |
| 3) Weglassen der ε-Übergänge | 13:42 |
| Äquivalenz zum ursprünglichen Automaten | 14:38 |
| Einfügen am Ende | 17:41 |
| umgekehrte Richtung | 19:13 |
| Alternative Gruppierung | 20:39 |
| Symmetrische Variante eines NEA | 21:45 |
| Bestimmung der Erreichbarkeit | 23:38 |
| Erreichbarkeit in Graphen | 24:05 |
| Zusammenfassung und Zwischenstand | 27:47 |
| Videoinhalt | |
|---|---|
| Algorithmus von Kleene | 0:00 |
| Nummerierung der Zustände | 1:32 |
| Berechnungswege mit beliebigem Ausgangszustand | 2:34 |
| Verkettung von Berechnungswegen | 4:28 |
| Quiz | 6:32 |
| Definition der Sprachen R_ij^(k) | 6:33 |
| Quiz | 9:36 |
| Berechnungswege ohne Zwischenzustände | 11:18 |
| Induktionsanfang k=0 | 12:00 |
| Rekursionsgleichung | 13:47 |
| Zerlegung an den Stellen, wo der Zustand q_k besucht wird | 14:57 |
| zentrale Rekursionsformel | 16:39 |
| Vereinfachungen für i=k oder j=k | 18:18 |
| Beweis über reguläre Ausdrücke | 21:16 |
| vollständige Induktion nach k | 22:01 |
| Induktionsbasis: Die Sprachen R_ij^(0) sind endlich. | 22:06 |
| Induktionsschritt | 22:46 |
| Beweisschluss: akzeptierte Sprache L(A) | 23:31 |
| DEA oder NEA? | 25:20 |
| Videoinhalt | |
|---|---|
| Algorithmische Querverbindungen | 0:00 |
| dynamische Programmierung | 0:47 |
| Definition der Teilprobleme | 1:50 |
| Wegeprobleme in Graphen | 3:29 |
| Algorithmus von Warshall für Erreichbarkeit | 4:45 |
| Algorithmus von Floyd für kürzeste Wege | 7:01 |
| Größen, mit denen der Algorithmus hantiert | 7:52 |
| Wachsen der regulären Ausdrücke | 8:01 |
| transitive Hülle einer Relation | 8:55 |
| Gauß-Jordan-Elimination zur Matrizeninversion | 10:20 |
| Laufzeit O(n^3) | 12:53 |
| Videoinhalt | |
|---|---|
| Abschlussoperationen | 0:00 |
| Bedeutung von abgeschlossen | 1:24 |
| Äquivalente Charakterisierungen der regulären Sprachen | 2:12 |
| die "regulären Operationen" | 3:17 |
| Komplement | 4:21 |
| Produktautomat | 6:09 |
| Aufwand | 8:13 |
| Spiegelung | 9:32 |
| strukturelle Induktion | 10:42 |
| Videoinhalt | |
|---|---|
| Abschluss unter Spiegelung | 0:00 |
| induktive Definition regulärer Ausdrücke | 0:19 |
| induktive Konstruktion der Spiegelung | 0:41 |
| formale Definiton eines regulären Ausdrucks | 4:14 |
| Grundregeln und Aufbauregeln | 5:38 |
| Beispiel | 6:35 |
| regulärer Ausdruck als Zeichenkette | 9:47 |
| Grammatik | 10:45 |
| Semantik: die dargestellte Sprache | 12:07 |
| strukturelle Induktion | 15:49 |
| Vergleich mit vollständiger Induktion | 16:25 |
| Basisfälle | 17:46 |
| Vereinigung | 18:45 |
| Multiplikation | 21:27 |
| *-Operation | 23:39 |
| Zusammenfassung | 24:17 |
| strukturelle Induktion in der Informatik | 26:49 |
| praktisches Top-Down-Vorgehen | 27:46 |
| Beispiel | 28:27 |
| Videoinhalt | |
|---|---|
| Homomorphismen als strukturerhaltende Abbildungen | 0:00 |
| Homomorphismen zwischen Sprachen | 0:46 |
| Folgerungen | 2:09 |
| Bestimmt durch die Werte an den Einzelsymbolen | 4:20 |
| Freiheit der Wahl | 4:52 |
| Beispiel: Code | 5:05 |
| Beispiel: Löschen von Symbolen | 5:57 |
| Anwendung von Homomorphismen | 7:16 |
| inverser Homomorphismus | 8:42 |
| Abschluss unter Homomorphismen | 9:31 |
| Videoinhalt | |
|---|---|
| inverser Homomorphismus | 0:00 |
| Simulation eines DEA für das Bild unter h | 0:22 |
| erweiterte Übergangsfunktion | 2:49 |
| Konstruktion des neuen DEA | 4:39 |
| Korrektheitsbeweis | 7:03 |
| Videoinhalt | |
|---|---|
| Konstruktion regulärer Sprachen | 0:00 |
| nicht reguläre Sprachen | 1:19 |
| Pumping-Lemma | 2:21 |
| Formulierung des Pumping-Lemmas | 3:10 |
| Beispiel L | 3:57 |
| Zerlegung des Wortes w in xyz | 4:29 |
| Pumpen | 4:42 |
| andere Zerlegungen von w | 6:03 |
| leeres Wort | 7:02 |
| Längenschranke n | 7:40 |
| endlich viele Ausnahmen vom Pumpen | 10:49 |
| Beispiel L' | 11:39 |
| Quiz | 12:10 |
| Beispiel L" | 13:00 |
| Quiz | 13:17 |
| Zusammenfassung: Aussage des Lemmas | 14:37 |
| Videoinhalt | |
|---|---|
| Pumping-Lemma als notwendige Bedingung | 0:00 |
| Geschachtelte Quantoren | 0:54 |
| Einführen von Begriffen | 1:52 |
| Vergleich: Stetigkeit einer Funktion | 2:24 |
| formale Formulierung | 3:07 |
| Verneinung der Schlussfolgerung | 4:59 |
| Formulierung in Worten | 7:52 |
| Verwendung von Begriffen | 8:26 |
| zusammengefasste Formulierung | 10:18 |
| Beispielanwendung | 11:03 |
| Wörter, die man aufpumpen kann | 11:31 |
| Schlussfolgerung | 15:47 |
| Videoinhalt | |
|---|---|
| Anwendungen der Pumping-Lemmas | 0:00 |
| Primzahlen | 1:26 |
| Beweis des Pumping-Lemmas | 5:28 |
| Wiederholung eines Zustands | 8:03 |
| Überprüfung der Bedingungen | 10:01 |
| Videoinhalt | |
|---|---|
| Kombination von Pumpinglemma mit Abschlusseigenschaften | 0:00 |
| Beispiel: die Dyck-Sprache | 0:48 |
| ausgeglichene Klammerausdrücke | 1:07 |
| Quiz | 3:10 |
| Charakterisierung ausgeglichener Klammerfolgen | 3:11 |
| Mitführen eines Zählers | 3:28 |
| Schnitt mit einer regulären Sprache | 4:57 |
| Homomorphismus zum Umbenennen | 6:31 |
| Beispiel 2: Kette von Homomorphismen | 8:25 |
| Zusammenfassen von Buchstabenpaaren | 11:30 |
| Videoinhalt | |
|---|---|
| Klassifikation der Wörter nach erreichtem Zustand | 0:00 |
| die Nerode-Relation | 3:09 |
| Anil Nerode | 4:29 |
| Beispiel | 5:10 |
| gleicher Zustand -> Nerode-äquivalent | 9:09 |
| Äquivalenzrelation | 9:55 |
| reflexiv | 10:22 |
| symmetrisch | 10:32 |
| transitiv | 10:40 |
| verschiedene Äquivalenzbegriffe | 11:17 |
| Nerode-Klassen | 12:19 |
| Videoinhalt | |
|---|---|
| Zerlegung nach erreichtem Zustand | 0:00 |
| nicht erreichbare Zustände | 1:37 |
| Beziehung zwischen den Klasseneinteilungen | 1:59 |
| Verfeinerung einer Klasseneinteilung | 4:30 |
| Anzahl der Nerode-Klassen | 5:04 |
| endlich viele Nerode-Klassen | 5:45 |
| unendliche viele Nerode-Klassen | 6:19 |
| Beispiel | 6:29 |
| Satz von Myhill-Nerode | 8:24 |
| Videoinhalt | |
|---|---|
| Satz von Myhill-Nerode | 0:00 |
| notwendige Bedingung | 0:12 |
| Beispiel: keine Einzelblöcke | 0:53 |
| Blocklängen > 1 | 1:49 |
| verbotene Muster | 2:05 |
| Quiz | 4:09 |
| Nerode-Klassen | 5:02 |
| Welche Frage muss man stellen? | 10:44 |
| Konstruktion des Automaten aus den Nerode-Klassen | 12:16 |
| Videoinhalt | |
|---|---|
| Konstruktion des Automaten aus den Nerode-Klassen | 0:00 |
| Übergangsfunktion | 3:01 |
| allgemeine Konstruktion des DEA | 4:31 |
| Zustandsmenge Q | 4:52 |
| unendliche Mengen als Zustände? | 5:17 |
| Übergangsfunktion | 8:07 |
| Wahl eines Repräsentanten w | 9:32 |
| wohldefiniert | 9:46 |
| unabhängig von der Wahl des Repräsentanten | 10:46 |
| Lemma 1 (Wohldefiniertheit) | 11:09 |
| Anfangszustand | 11:48 |
| akzeptierende Zustände | 11:56 |
| Korrektheit | 12:42 |
| Beweis von Lemma 2 durch vollständige Induktion | 14:58 |
| Induktionsschritt | 15:37 |
| Beweis von Lemma 1 (Wohldefiniertheit) | 17:33 |
| Beweiszusammenfassung | 19:34 |
| Folgerung über den Minimalautomaten | 20:17 |
| Eindeutigkeit des Minimalautomaten | 21:22 |
| Minimierung von Automaten | 24:45 |
| Videoinhalt | |
|---|---|
| Minimierung eines DEA | 0:00 |
| Grundidee | 0:33 |
| nicht erreichbare Zustände weglassen | 0:57 |
| äquivalente Zustände | 2:06 |
| Äquivalente Zustände sind austauschbar | 4:09 |
| Lemma 3 | 4:38 |
| Verfeinerungsalgorithmus | 7:36 |
| schrittweise Verfeinerung | 8:29 |
| Zielkriterien | 9:33 |
| 1. Unterscheidung zwischen akzeptieren und nicht akzeptierenden Zuständen | 9:42 |
| 2. Verträglichkeit mit der Übergangangsfunktion | 10:34 |
| Überblick über den Algorithmus | 11:57 |
| Videoinhalt | |
|---|---|
| Beispiel für Minimierung | 0:00 |
| Was musss sich der Automat merken? | 0:19 |
| Anfangszerlegung in zwei Klassen | 0:48 |
| 1. Verfeinerungsschritt | 1:48 |
| Aufspaltung | 4:15 |
| 2. Verfeinerungsschritt | 7:16 |
| 3. Verfeinerungsschritt | 9:58 |
| Schleifenende | 11:07 |
| Identifikation äquivalenter Zustände | 12:26 |
| Konsistenz der Übergänge | 13:27 |
| Bestimmung des Startzustandes | 14:28 |
| akzeptierende Zustände | 14:38 |
| Formulierung des Verfeinerungsalgorithmus | 15:05 |
| Schleifenende | 17:11 |
| Definition des Automaten | 17:35 |
| Zustände | 17:49 |
| Übergangsfunktion | 18:18 |
| Startzustand | 19:17 |
| verbleibende Überlegungen | 19:56 |
| Terminierung des Algorithmus | 20:28 |
| Videoinhalt | |
|---|---|
| Die Übergangsfunktion ist wohldefiniert. | 0:00 |
| Die gleiche Sprache wird akzeptiert. | 1:10 |
| Die beiden Automaten erreichen ensprechende Zustände. | 1:45 |
| entsprechende akzeptierende Zustände | 2:45 |
| Induktion nach der Länge von x | 4:08 |
| Induktionsbasis | 4:43 |
| Induktionsschritt von x zu xa | 5:52 |
| Induktionsannahme | 6:15 |
| Induktionsbehauptung | 6:38 |
| Induktionsschluss | 6:59 |
| Betrachtung zum Induktionsbeweis | 9:27 |
| Ende des Induktionsbeweises | 10:35 |
| unterscheidendes Wort für Zustände in verschiedenen Klassen | 11:16 |
| Formulierung einer Invariante | 11:55 |
| Invariante zu Beginn | 13:21 |
| Invariante bei Verfeinerung | 13:48 |
| Minimalität | 16:01 |
| Zusammenhang zu den Nerode-Klassen | 16:07 |
| Beweisstrategie | 16:33 |
| ein Wort w_i für jede Klasse | 17:41 |
| Wörter in verschiedenen Klassen sind nicht äquivalent. | 18:19 |
| Betrachtung des Minimalitätsbeweises | 21:32 |
| Videoinhalt | |
|---|---|
| Laufzeit des Minimierungsalgorithmus | 0:00 |
| Daten des gegebenen Automaten | 1:15 |
| Darstellung der Klassenzerlegung | 1:56 |
| Verfeinerungsschritt | 4:40 |
| Gesamtlaufzeit | 9:00 |
| Konstruktion des Minimalautomaten | 9:38 |
| schnellere Alternative | 11:56 |
| Tabellenausfüllalgorithmus | 12:45 |
| Videoinhalt | |
|---|---|
| Minimierung eines NEA? | 0:00 |
| Anwendung des Minimierungsalgorithmus auf einen NEA | 0:53 |
| akzeptierte Sprache L(A) | 2:22 |
| Minimierung von NEA ist schwierig. (PSPACE-vollständig) | 4:00 |
| Videoinhalt | |
|---|---|
| Eindeutigkeit des Minimalautomaten | 0:00 |
| Nerodeklassenautomat A | 0:26 |
| Zerlegung der Wörter in Zustandsklassen | 2:05 |
| Verfeinerung der Nerodeklassen | 2:43 |
| bildliche Darstellung | 3:00 |
| Abbildung f der Zustände | 3:39 |
| (**) Bewahrung der Übergangsfunktion | 5:15 |
| schematische Darstellung als Diagramm | 6:04 |
| Beispiel | 7:23 |
| Beweis von (**) | 8:12 |
| f ist surjektiv | 11:10 |
| Fall des Minimalautomaten | 12:12 |
| Umbenennung der Zustände | 12:38 |
| Startzustand und Menge F | 13:20 |
| Zusammenfassung | 14:04 |
| anderer Beweis | 14:28 |
| Videoinhalt | |
|---|---|
| Startzustand | 0:00 |
| akzeptierende Zustände F | 0:39 |
| Videoinhalt | |
|---|---|
| Entscheidungsprobleme für reguläre Sprachen | 0:00 |
| Äquivalenzfrage | 1:31 |
| Zusammenfassung über reguläre Sprachen | 2:48 |
| 1. verschiedene Darstellungsformen | 3:02 |
| 2. Abschlusseigenschaften | 3:48 |
| Anwendung der Abschlusseigenschaften | 4:26 |
| 3. Minimalautomat | 4:59 |
| 4. Satz von Myhill-Nerode | 5:14 |
| 5. Pumpinglemma | 5:29 |
| Anwendung: lexikalische Analyse | 5:47 |
| flex und JFlex | 7:31 |
| summe.lex | 8:38 |
| Java-Version | 12:26 |
| Variante: Automaten mit Ausgabe | 14:02 |
| Markoffketten | 14:59 |
| Videoinhalt | |
|---|---|
| endliche Automaten | 0:00 |
| Turingmaschinen | 0:12 |
| unendliches Band | 0:47 |
| Schreib-/Lesekopf | 1:08 |
| Steuerung mit endlich vielen Zuständen | 1:21 |
| Computer in den 30er-Jahren | 1:59 |
| eindimensionaler Bandspeicher | 3:11 |
| Eingabeband | 3:39 |
| Operationen der Turingmaschine | 4:25 |
| Beispiel: Addition von zwei Binärzahlen | 4:54 |
| Rechnung von Hand | 5:52 |
| Hin- und Herfahren, Bandpositionen markieren | 7:31 |
| Ablauf der Addition | 7:52 |
| aktuelles Bandsymbol Z | 11:58 |
| Formulierung des Programms | 12:17 |
| Variable mit endlich vielen möglichen Werten | 13:35 |
| Aufräumen am Ende | 17:44 |
| Leerzeichen B am Rand des Bandes | 18:19 |
| Markierung des Eingabeendes | 19:12 |
| Höhere Programmiersprache für Turingmaschinen | 22:24 |
| Grundoperationen der Turingmaschine | 22:36 |
| Turingmaschine programmieren, wozu? | 23:38 |
| Turingmaschine = Algorithmus | 23:51 |
| Church-Turing'sche These | 24:43 |
| Videoinhalt | |
|---|---|
| Übergangsfunktion | 0:00 |
| Abschluss: Löschen der Markierungen | 12:30 |
| Haltezustände | 14:29 |
| Übergangstabelle | 15:12 |
| Halten der Maschine | 16:28 |
| Definition einer Turingmaschine M | 17:23 |
| endliche Zustandsmenge Q | 17:54 |
| Eingabealphabet Sigma | 17:59 |
| Bandalphabet Gamma | 18:02 |
| Leerzeichen B | 18:14 |
| Übergangsfunktion delta | 18:51 |
| Startzustand q0 | 18:55 |
| akzeptierende Zustandsmenge F | 19:03 |
| Turingmaschine zur Berechnung | 19:10 |
| Turingmaschinen zur Entscheidung | 19:36 |
| Konfiguration einer Turingmaschine | 20:35 |
| Notation für Konfigurationen | 21:13 |
| Startkonfiguration | 24:26 |
| Übergang in einem Schritt | 24:41 |
| Übergang in beliebig vielen Schritten | 24:52 |
| Videoinhalt | |
|---|---|
| Church-Turingsche These | 0:00 |
| Algorithmen der künstlichen Intelligenz | 2:06 |
| andere Definitionen von Algorithmus | 3:03 |
| Einwände | 3:36 |
| Mächtigkeit von Turingmaschinen | 4:53 |
| adressierbarer Speicher | 5:03 |
| Einschränkung bezüglich der Laufzeit | 6:04 |
| Turingmaschinen zu mächtig? | 6:45 |
| Quiz | 7:04 |
| Computer als endlicher Automat | 7:57 |
| berechenbare Funktionen | 9:18 |
| nicht berechenbare Funktionen | 10:55 |
| Videoinhalt | |
|---|---|
| Programmiertricks | 0:00 |
| Unterprogramme | 0:17 |
| Schnittstellen | 1:06 |
| Programmbibliotheken | 1:20 |
| Daten in einer Tabelle | 1:55 |
| adressierbarer Speicher | 4:39 |
| Variablen mit endlichem Wertebereich | 5:40 |
| Band mit mehreren Spuren | 8:14 |
| Turingmaschinen mit mehreren Bändern | 10:34 |
| Simulation auf einer klassischen 1-Band-Turingmaschine | 12:33 |
| Videoinhalt | |
|---|---|
| Einschränkungen | 0:00 |
| Eingabealphabet {0,1} | 0:32 |
| Gruppieren der Felder | 1:30 |
| Kodierung einer Turingmaschine als Bitfolge | 2:36 |
| Reduktion des Bandalphabets | 3:09 |
| Die Zustandsmenge wird größer. | 4:01 |
| Reduktion der Zustandsmenge | 4:23 |
| universelle Turingmaschine | 4:51 |
| fleißige Biber | 5:14 |
| Videoinhalt | |
|---|---|
| Berechenbare Funktionen | 0:00 |
| Entscheidungsprobleme | 0:31 |
| formale Sprache als Entscheidungsproblem | 1:05 |
| Wortproblem für L | 1:41 |
| von einer Turingmaschine M akzeptierte Sprache L(M) | 2:57 |
| entscheidbare Sprachen | 5:19 |
| rekursiv aufzählbare Sprachen | 5:51 |
| andere Bezeichnungen | 6:47 |
| Unterschied: abzählbare Mengen | 7:28 |
| das Halteproblem H | 8:23 |
| Quiz | 9:36 |
| Turingmaschine als Eingabe für eine Turingmaschine | 11:32 |
| selbstbezüglich | 12:04 |
| Kodierung einer Turingmaschine | 12:32 |
| Simulationsprogramm | 15:06 |
| universelle Turingmaschinen | 16:49 |
| universelle Turingmaschinen für Berechnungsprobleme | 19:37 |
| kleine universelle Turingmaschinen | 20:34 |
| die universelle Sprache U | 21:10 |
| Quiz | 22:27 |
| Verhalten bei ungültiger Eingabe | 22:28 |
| Videoinhalt | |
|---|---|
| Unentscheidbare Probleme | 0:00 |
| Programme als Daten | 0:22 |
| Diagonalsprache D | 1:33 |
| Programme, die ihren eigenen Quelltext lesen | 3:58 |
| Selbstbezüglichkeit | 4:27 |
| Exkurs: selbstreproduzierende Programme | 4:41 |
| Definition von D | 5:34 |
| D ist nicht rekursiv aufzählbar | 5:48 |
| Russell'sche Antinomie | 8:28 |
| Lügnerparadoxon | 10:05 |
| Diagonalisierung | 10:56 |
| Aufzählung aller Turingmaschinen | 11:11 |
| andere Diagonalisierungsargumente: Die reellen Zahlen sind nicht abzählbar | 16:32 |
| Potenzmenge jeder Menge ist mächtiger als die Menge selbst | 16:55 |
| Videoinhalt | |
|---|---|
| Es gibt unentscheidbare Probleme | 0:00 |
| Der Gödelsche Unvollständigkeitssatz | 1:25 |
| Unentscheidbarkeit des Halteproblems | 2:47 |
| D auf H zurückführen | 4:07 |
| Quiz | 6:20 |
| Problemreduktion: A≤B | 7:23 |
| Unentscheidbarkeit durch Problemreduktion | 9:01 |
| Vergleich der Schwierigkeit | 9:29 |
| Reduktion als informatisches Grundprinzip | 10:43 |
| Aufruf eines Unterprogramms für B | 11:23 |
| Videoinhalt | |
|---|---|
| Komplement einer Sprache | 0:00 |
| Abschluss unter Komplementbildung | 0:23 |
| rekursiv aufzählbare Sprachen | 1:59 |
| semientscheidbar | 3:41 |
| L und -L sind rekursiv aufzählbar | 5:25 |
| Parallelverarbeitung | 7:37 |
| verbal beschriebene Algorithmen | 8:50 |
| nicht rekursive aufzählbare Sprache | 10:16 |
| universelle Sprache U | 10:48 |
| Übersicht über Sprachklassen | 13:38 |
| Probleme ohne Eingabe | 15:18 |
| Videoinhalt | |
|---|---|
| Abschlusseigenschaften | 0:00 |
| Produkt | 1:52 |
| exponentielles Wachstum | 4:05 |
| alle Zerlegungen für * | 5:48 |
| Aufzählen der Wörter | 6:46 |
| Videoinhalt | |
|---|---|
| Weitere unentscheidbare Probleme | 0:00 |
| Pflasterung der Ebene | 0:26 |
| Kodierung der Eingabe? | 3:36 |
| Wang-Kacheln | 4:28 |
| Regeln für Wangkacheln: 1) keine Drehung | 5:06 |
| 2) Seite an Seite | 5:14 |
| 3) Aneinanderstoßende Farben müssen gleich sein. | 5:41 |
| Kodierung der Eingabe | 6:34 |
| Reduktion auf geometrische Kachelung | 7:48 |
| Ausstülpungen und Aussparungen | 8:43 |
| Seite-an-Seite | 10:02 |
| Legespiele | 10:44 |
| festgelegte Ausgangskonfiguration | 12:34 |
| Berechnungsweg einer Turingmaschine | 13:08 |
| neutrale Beschriftung | 17:11 |
| Ausgangskonfiguration | 17:44 |
| Kopierkacheln | 17:59 |
| Kacheln für die Übergangsfunktion | 18:24 |
| Bewegungskacheln | 18:54 |
| Haltezustand | 19:40 |
| Blankokacheln | 21:55 |
| Füllkacheln | 23:03 |
| Reduktion | 24:31 |
| Ergänzung: Lösbare Spezialfälle | 26:47 |
| Beschleunigung durch Backtracking | 28:03 |
| periodische Kachelungen | 29:53 |
| aperiodische Kachelmengen | 30:48 |
| Videoinhalt | |
|---|---|
| Postsches Korrespondenzproblem (PKP) | 0:00 |
| Beispiel 1 | 1:09 |
| Beispiel 2 | 2:25 |
| Beispiel 3 | 5:03 |
| PKP ist unentscheidbar | 6:31 |
| Simulation einer Turingmaschine | 6:39 |
| Lösung = Folge von Konfigurationen | 6:59 |
| Ausgangssituation | 7:30 |
| Schritt nach links | 14:08 |
| Schreiben über den Rand | 14:21 |
| Terminieren | 15:57 |
| Löschen des Bandes am Ende | 16:20 |
| Abschlusspaar | 18:02 |
| triviale Lösbarkeit | 19:02 |
| Modifiziertes PKP (MPKP) | 20:12 |
| spezielles Anfangspaar | 20:39 |
| Schritt 1: H ≤ MPKP | 21:00 |
| Schritt 2: MPKP ≤ PKP | 22:42 |
| Einfügen von *-Symbolen | 23:37 |
| Extra * für a1 | 25:02 |
| Wortpaar ($,*$) für den Abschluss | 25:20 |
| Zusammenfassung der Reduktion | 26:53 |
| Videoinhalt | |
|---|---|
| Nicht berechenbare Funktionen | 0:00 |
| Schranke s(k,l) für die Lösungslänge | 0:31 |
| schnelles Wachstum | 2:06 |
| Beweis, dass f nicht berechenbar ist | 3:15 |
| verwandte Funktion: fleißige Biber | 6:00 |
| Videoinhalt | |
|---|---|
| Diophantische Gleichungen | 0:00 |
| Polynomgleichung in ganzzahligen Variablen | 0:27 |
| Beispiel 1: pythagoräische Zahlentripel | 1:03 |
| Beispiel 2: Systeme mehrerer Gleichungen | 1:48 |
| Beispiel 3: Fermatscher Satz | 2:35 |
| 10. Hilbertsches Problem | 3:11 |
| Lösbarkeit in reellen oder rationalen Werten | 4:04 |
| Erkennen von Schadsoftware | 4:24 |
| Videoinhalt | |
|---|---|
| Eigenschaften der von M akzeptierten Sprache | 0:00 |
| Satz von Rice | 1:19 |
| triviale Ausnahmen | 1:33 |
| Eigenschaften von Turingmaschinen | 3:45 |
| nichttriviale Eigenschaft einer Sprache | 5:37 |
| Satz von Rice: Formulierung | 6:40 |
| Ist L(M) leer? | 7:21 |
| Reduktion die universellen Sprache U auf Leerheit | 7:54 |
| Konstruktion von M' | 10:00 |
| zwei Möglichkeiten für L(M') | 12:06 |
| Konstruktion der Turingmaschine für M' | 13:08 |
| M' hängt von w ab | 14:12 |
| Turingmaschine M' | 14:48 |
| ohne universelle Turingmaschine | 15:56 |
| Videoinhalt | |
|---|---|
| Anpassung des Beweises | 0:00 |
| Sprache L0 im positiven Fall statt der vollen Sprache Sigma* | 1:23 |
| Fall 1 | 2:25 |
| Erklärung von M' | 4:05 |
| Charakterisierung von L(M') | 5:20 |
| Endgültige Entscheidung | 6:40 |
| Fall 2 | 7:58 |
| Negation von P | 9:11 |
| Turingmaschine für M' | 9:30 |
| Videoinhalt | |
|---|---|
| Folgerungen aus Unentscheidbarkeit | 0:00 |
| Lösung von einzelnen Beispielen | 1:40 |
| Softwareentwicklung: Korrektheit | 3:18 |
| Korrektheitsbeweis | 4:41 |
| kritische Anwendungen | 5:11 |
| formale Methoden | 5:55 |
| Videoinhalt | |
|---|---|
| Grammatiken | 0:00 |
| Struktur von Sprache | 0:32 |
| rudimentäre Beispielgrammatik | 1:25 |
| Regeln (Produktionen) | 4:21 |
| Ableitung | 4:29 |
| Ableitungsschritt: => | 5:01 |
| Variablen (Nichtterminalsymbole) | 5:09 |
| Terminalsymbole | 5:24 |
| Beschreibung eines Ableitungsschritts | 5:51 |
| alternative Regeln für eine Variable | 6:19 |
| Sätze der Sprache | 7:27 |
| Startsymbol | 7:59 |
| andere Ableitungen | 8:18 |
| Ableitung in mehreren Schritten: =>* | 8:31 |
| Angemessenheit der grammatikalischen Kategorien | 9:02 |
| Videoinhalt | |
|---|---|
| Definition einer kontextfreien Grammatik | 0:00 |
| Terminalsymbole | 0:10 |
| Variablen | 0:21 |
| Regeln | 0:56 |
| linke und rechte Seite | 1:14 |
| Zusammenfassen mehrerer Regeln | 2:30 |
| Die Regeln reichen aus. | 3:47 |
| Satzformen und Sätze | 4:07 |
| Sätze und Wörter | 4:44 |
| Definition Ableitungsschritt | 7:18 |
| Ableitung | 8:00 |
| Wahl der Variablen ist frei. | 8:33 |
| Wahl der Variablen hat keinen Einfluss. | 9:03 |
| Linksableitung | 10:01 |
| Rechtsableitung | 11:17 |
| Die von G erzeugte Sprache L(G) | 11:26 |
| Quiz | 13:10 |
| Quiz | 13:30 |
| Ableitungsbaum (Syntaxbaum, parse tree) | 13:32 |
| Videoinhalt | |
|---|---|
| kontextfreie Sprachen | 0:00 |
| Beispiel 2: 0^n 1^n | 0:28 |
| Beispiel 3: Palindrome | 2:12 |
| Beispiel 4: Wörter gerader Länge | 5:50 |
| Beispiel 5: ausgeglichene Wörter | 7:50 |
| Beweis | 11:18 |
| umgekehrte Inklusion | 11:48 |
| vollständige Induktion nach |w| | 12:04 |
| Induktionsschritt | 12:37 |
| kürzester ausgeglichener Präfix | 15:59 |
| Fall 1: w fängt mit 0 an | 16:40 |
| u muss mit 1 aufhören | 17:40 |
| Existenz eines geeigneten Präfixes | 18:25 |
| Fall 2: w fängt mit 1 an | 21:12 |
| Variante | 21:49 |
| Zusammenfassung | 22:08 |
| Videoinhalt | |
|---|---|
| Syntax von Programmiersprachen | 0:00 |
| erweiterte Backus-Naur-Form (EBNF) | 0:20 |
| Syntax von Java | 1:23 |
| Elimination der Erweiterungen | 3:20 |
| Beispiel: Methodenaufruf in Java | 3:53 |
| Metasymbole | 6:35 |
| Videoinhalt | |
|---|---|
| Anwendungen kontextfreier Grammatiken | 0:00 |
| Syntax von Programmiersprachen | 0:13 |
| kontextfreie Datenformate | 0:28 |
| HTML für Netzseiten | 0:39 |
| Quelltext einer Netzseite | 1:04 |
| XML als strukturiertes Datenformat | 2:55 |
| Beispiel einer XML-Datei | 3:21 |
| Baumstruktur | 4:39 |
| Videoinhalt | |
|---|---|
| mehrdeutige Grammatiken | 0:00 |
| bedingte Anweisung, "if" | 3:02 |
| nachhängendes "else" | 4:21 |
| Unterscheidung der Variablen | 6:35 |
| if-else in Python | 8:11 |
| Priorität bei arithmetischen Ausdrücken | 8:29 |
| eindeutige und mehrdeutige Grammatik | 10:05 |
| Syntaxanalysealgorithmen | 11:42 |
| inhärent mehrdeutige Sprachen | 12:48 |
| Mehrdeutigkeit im Deutschen | 15:25 |
| Videoinhalt | |
|---|---|
| allgemeine Form einer Regel | 0:00 |
| Ableitungsschritt | 1:24 |
| Typ-0-Grammatiken | 2:25 |
| Typ 1: kontextsensitive Grammatiken | 2:33 |
| Typ 2: kontextfreie Grammatiken | 2:58 |
| Typ 3: rechtslineare Grammatiken | 3:14 |
| Typ-0/1/2/3-Sprachen | 3:56 |
| Typ-3-Sprachen sind reguläre Sprachen | 4:29 |
| linkslineare Grammatiken | 5:05 |
| Typ-0-Sprachen sind rekursiv aufzählbare Sprachen. | 5:32 |
| Noam Chomsky, geb. 1928 | 6:11 |
| die Chomsky-Hierarchie | 8:33 |
| Ausnahme für das leere Wort | 9:43 |
| Videoinhalt | |
|---|---|
| kontextsensitive Sprache: 0^n 1^n 0^n | 0:00 |
| Bezeichnung "kontextsensitiv" | 4:49 |
| Vergleich mit einer Turingmaschine | 6:51 |
| Videoinhalt | |
|---|---|
| Kontextsensitive Sprachen sind entscheidbar. | 0:00 |
| das Wortproblem | 0:25 |
| Ausnahme für das leere Wort | 1:11 |
| endlich viele Satzformen | 1:24 |
| Algorithmus | 2:00 |
| Erreichbarkeit in einem Graphen | 3:01 |
| Nicht jede entscheidbare Sprache ist kontextsensitiv. | 3:15 |
| [linear platzbeschränkte Turingmaschinen] | 3:34 |
| [nichtdeterministische Turingmaschinen] | 4:11 |
| [Das Komplement einer kontextsensitiven Sprache ist kontextsensitiv.] | 5:07 |
| Videoinhalt | |
|---|---|
| Typ-0-Sprachen und rekursiv aufzählbare Sprachen | 0:00 |
| Typ-0-Grammatik => Turingmaschine | 0:18 |
| Turingmaschine M => Grammatik | 2:19 |
| Ableitung in umgekehrter Reihenfolge | 2:48 |
| Zustände entsprechen Variablen | 3:42 |
| Start mit akzeptierendem Zustand | 5:36 |
| Ende mit Startzustand und akzeptiertem Wort | 6:21 |
| Einfügen und Löschen von Blankosymbolen | 8:59 |
| Quiz | 10:44 |
| Videoinhalt | |
|---|---|
| Chomsky-Normalform | 0:00 |
| Ausnahme für das leere Wort | 1:08 |
| Terminalsymbole und Variablen getrennt | 2:49 |
| zu lange und zu kurze rechte Seite | 3:05 |
| Beweisübersicht | 3:51 |
| Folgerung: kontextfreie Sprachen sind auch kontextsensitiv | 4:40 |
| Beweis: Transformation der Grammatik | 5:34 |
| Schritt 1: Trennung von Variablen und Terminalsymbolen | 5:53 |
| Beispiel | 6:43 |
| Schritt 2: zu lange Regeln | 8:24 |
| neue Variablen W für jede Regel | 9:07 |
| Alternativen | 11:30 |
| Schritt 3: ε-Regeln | 12:29 |
| Schritt 3a: Bestimmen der Variablen, aus denen ε abgeleitet werden kann | 14:47 |
| Schritt 3b: Regeln kürzen | 18:47 |
| Beweis der Äquivalenz | 20:35 |
| Darstellung der ε-Regel im Ableitungsbaum | 23:28 |
| Videoinhalt | |
|---|---|
| Terminalregeln, Paarregeln, Einheitsregeln | 0:00 |
| Schritt 4: Elimination der Einheitsregeln | 0:46 |
| Einreitsregeln im Ableitungsbaum | 0:54 |
| neue Regeln | 2:35 |
| Die Sprache ändert sich nicht. | 4:24 |
| Ketten von Einheitsregeln | 5:33 |
| maximale Kette | 6:15 |
| Bestimmen der Ketten aus Einheitsregeln | 7:47 |
| Erreichbarkeit in einem Graphen | 8:20 |
| Tiefensuche, Breitensuche | 9:39 |
| Videoinhalt | |
|---|---|
| Beispiel 1 | 0:00 |
| Schritt 1: Trennung von Variablen und Terminalsymbolen | 0:19 |
| Schritt 2: Elimination zu langer Regeln | 1:21 |
| Schritt 3: Elimination der ε-Regeln | 2:23 |
| Sonderbehandlung von S | 6:29 |
| Schritt 4: Elimination der Einheitsregeln | 6:41 |
| Ersatz für Terminalregeln | 8:30 |
| Ersatz für Paarregeln | 10:19 |
| Videoinhalt | |
|---|---|
| Beispiel 2: arithmetische Ausdrücke | 0:00 |
| Ausdruck als Summe von Termen | 1:00 |
| Syntaxbaum für einen Ausdruck | 2:29 |
| Zusammensetzung mehrerer Terme von links nach rechts | 3:03 |
| Term als Produkt von Faktoren | 3:40 |
| Der Sinn von Einheitsregeln | 5:24 |
| Schritt 1: Trennung der Variablen und Terminalsymbole | 6:07 |
| Schritt 2: zu lange Regeln | 7:07 |
| keine ε-Regeln | 7:49 |
| Schritt 4: Elimination der Einheitsregeln | 7:53 |
| Graph der Einheitsregeln | 8:05 |
| Übersichtlichkeit geht verloren. | 10:03 |
| CNF als Vorverarbeitung für Beweise | 10:52 |
| CNF als Vorverarbeitung für Algorithmen | 11:21 |
| Das Wortproblem | 11:26 |
| Videoinhalt | |
|---|---|
| Nachtrag: Turing-Reduktion und Karp-Reduktion | 0:00 |
| Turing-Reduktion: Definition | 0:28 |
| Karp-Reduktionen | 1:05 |
| fehlerhafte Aufgabe bei Übung 85c | 1:22 |
| Reduktion D≤U | 1:41 |
| formale Definition mit Reduktionsfunktion f | 2:33 |
| Karp-Reduktion ist stärker als Turing-Reduktion | 6:29 |
| Karp-Reduzierbarkeit und rekursiv aufzählbare Sprachen | 6:55 |
| Zusammenfassung | 9:41 |
| Komplexitätstheorie, P, NP-vollständig | 10:05 |
| Videoinhalt | |
|---|---|
| Das Wortproblem | 0:00 |
| Grammatik in Chomsky-Normalform | 0:39 |
| Bestimmen eines Ableitungsbaums | 0:51 |
| Beispiel | 1:15 |
| Anfangsüberlegungen | 1:38 |
| Teilprobleme | 4:25 |
| dynamische Programmierung | 6:24 |
| systematisches Lösen von Teilproblemen | 6:38 |
| Rückgriff auf kleinere Teilprobleme | 7:23 |
| Rekursionsanker: Wörter der Länge 1 | 9:37 |
| Andere Notation: Variablenmenge Vij | 10:31 |
| systematische Reihenfolge | 12:52 |
| Lösung des ursprünglichen Wortproblems | 13:28 |
| Beispiel | 14:03 |
| Videoinhalt | |
|---|---|
| Beispiel | 0:00 |
| Hauptdiagonale: Terminalregeln | 0:24 |
| zweite Diagonale | 1:48 |
| dritte Diagonale | 3:48 |
| vierte Diagonale | 6:33 |
| allgemeines Vorgehen | 7:26 |
| Analogie zur Matrizenmultiplikation | 8:49 |
| Lösung: w gehört zu L(G). | 9:58 |
| untypisches Beispiel | 10:21 |
| den Ableitungsbaum konstruieren | 10:51 |
| Zurückverfolgen der Lösung | 11:54 |
| eindeutiger Ableitungsbaum | 15:01 |
| Laufzeit: O(n^3) | 15:38 |
| höchstens n^2 Mengen V_ij | 15:53 |
| höchstens n Möglichkeiten für k | 15:59 |
| Grammatik wird als konstant betrachtet | 16:12 |
| CYK-Algorithmus | 17:22 |
| praktische Bedeutung | 17:36 |
| bester bekannter Algorithmus für allgemeine kontextfreie Grammatiken | 18:02 |
| schnelle Matrizenmultiplikation | 18:33 |
| Wichtigkeit der Chomsky-Normalform | 19:12 |
| Videoinhalt | |
|---|---|
| Pumpinglemma | 0:00 |
| Sprache { 0^n 1^n 0^n } | 0:29 |
| Punmpinglemma für reguläre Sprachen | 0:55 |
| Zusatzbedingungen | 1:37 |
| Pumpmöglichkeit | 2:01 |
| Pumpinglemma für kontextfreie Sprachen | 2:12 |
| nichttriviale Pumpmöglichkeit | 3:18 |
| Längenschranke | 3:40 |
| Beweisidee: Variablenwiederholung im Ableitungsbaum | 4:07 |
| Ersetzen von Teilbäumen für die Variable A | 5:24 |
| herausschneiden | 5:38 |
| einsetzen | 6:36 |
| Eigenschaft einer kontextfreien Grammatik | 8:16 |
| Beweisidee | 9:16 |
| Grundidee: nur endlich viele Variablen | 9:53 |
| Beweis: Chomsky-Normalform | 10:42 |
| Lemma: Anzahl der Blätter ist durch Höhe h begrenzt. | 10:54 |
| Länge eines Pfades | 11:22 |
| Höhe h eines Baumes | 12:09 |
| vollständige Induktion nach h | 14:01 |
| Induktionsbasis h=1 | 14:07 |
| Induktionsschritt für h>1 | 14:29 |
| Bestimmung der Schranke n = 2^m | 16:02 |
| längster Pfad | 17:09 |
| Länge |yzu| | 19:19 |
| Videoinhalt | |
|---|---|
| Anwendung des Pumpenlemmas | 0:00 |
| Sprachen mit Blöcken gleicher Länge | 0:24 |
| L = { 0^n 1^n 2^n | n>=0 } | 1:56 |
| Zerlegung w=xyzuv | 3:11 |
| x y^0 z u^0 v liegt nicht in L | 5:33 |
| Beweis ohne Längenschranke für das Pumpen | 6:59 |
| Palindrome | 7:29 |
| verdoppelte Wörter | 8:49 |
| Bestimmen des Wortes w | 9:17 |
| Zerlegung xyzuv | 10:21 |
| Fallunterscheidungen | 10:53 |
| Abpumpen | 12:44 |
| Lemma über Wörter 0^p 1^q 0^r 1^s | 15:02 |
| Beweis des Lemmas | 17:16 |
| Videoinhalt | |
|---|---|
| Abschlusseigenschaften kontextfreier Sprachen | 0:00 |
| Vereinigung | 0:21 |
| disjunkte Variablenmengen | 1:05 |
| Produkt | 3:03 |
| *-Operation | 3:18 |
| Homomorphismen | 3:28 |
| inverse Homomorphismen | 4:05 |
| kein Abschluss unter Schnitt | 4:16 |
| Komplement | 6:46 |
| de Morgan'sche Regeln | 7:00 |
| Schnitt mit einer regulären Sprache | 7:56 |
| Videoinhalt | |
|---|---|
| Entscheidungsfragen für kontextfreie Sprachen | 0:00 |
| leere Sprache | 0:17 |
| unendliche Sprache | 0:24 |
| Wortproblem | 0:29 |
| unentscheidbare Fragen | 0:56 |
| Ist eine Grammatik mehrdeutig? | 1:10 |
| Ist eine Sprache inhärent mehrdeutig? | 1:31 |
| Ist der Schnitt zweier kontextfreier Sprachen leer | 2:37 |
| Reduktion vom MPKP | 3:06 |
| Mehrdeutigkeit einer Grammatik | 9:09 |
| Videoinhalt | |
|---|---|
| Die Dycksprache | 0:00 |
| mehrere Klammerpaare | 1:51 |
| ausgeglichene Klammerfolgen | 2:27 |
| die Mutter aller kontextfreien Sprachen | 3:43 |
| Videoinhalt | |
|---|---|
| passende Automaten zu verschiedenen Sprachklassen | 0:00 |
| Beispiel einer Linksableitung | 1:02 |
| Ende des Beispiels | 3:31 |
| Betrachtung des Ablaufs | 3:33 |
| Stapel | 4:25 |
| Erzeugen aller Wörter mit einem Stapel | 5:25 |
| Keller | 6:48 |
| Patiencen | 7:00 |
| Erzeugen im Gegensatz zu Lesen | 7:36 |
| nichtdeterministisch | 8:15 |
| Arbeitsweise eines Kellerautomaten | 8:50 |
| Eingabeband | 8:56 |
| Keller | 9:22 |
| Steuerung | 9:46 |
| ein Schritt eines Kellerautomaten | 10:09 |
| Bestandteile eines Kellerautomaten | 11:39 |
| 1. Eingabealphabet Σ | 11:46 |
| 2. Kelleralphabet Γ | 11:50 |
| 3. endliche Zustandsmenge Q | 12:00 |
| 4. Kellergrundsymbol Z_0 | 12:12 |
| 5. Startzustand q_0 | 12:57 |
| 6. Übergangsrelation δ | 13:05 |
| 7. akzeptierende Zustandmenge F | 13:43 |
| Kellerautomat K ist ein 7-Tupel | 13:57 |
| Bedeutung der Übergangsrelation | 14:28 |
| nichtdeterministisch | 16:05 |
| engl. pushdown automaton (PDA) | 16:52 |
| Beispiel | 17:36 |
| Kelleralphabet | 19:04 |
| Übergangsrelation | 19:13 |
| Zustand q0: Kopiermodus | 19:24 |
| Übergang zu q1 | 21:20 |
| Zustand q1: Vergleichsmodus | 22:20 |
| Zustand q2: Akzeptieren | 23:11 |
| F={q2} | 23:45 |
| nichtdeterministisch | 24:30 |
| Akzeptierungsregel | 25:06 |
| steckenbleiben | 26:14 |
| weitere Übergänge nach dem Lesen der Eingabe | 26:53 |
| kompakte Schreibweise für die Übergangsrelation | 27:14 |
| Ausblick | 28:55 |
| Videoinhalt | |
|---|---|
| Konfigurationsbeschreibung eines Kellerautomaten | 0:00 |
| Konfiguration (q,w,γ) | 0:29 |
| Zustand q | 0:43 |
| verbleibendes Eingabewort w | 0:49 |
| Kellerinhalt γ | 1:03 |
| Startkonfiguration | 1:13 |
| Nachfolgekonfiguration | 1:31 |
| 5 Elemente eines Übergangs in δ | 2:18 |
| Formale Definition der Nachfolgekonfiguration | 2:49 |
| Nachfolgerrelation in mehreren Schritten | 4:40 |
| Nachfolger ist nicht eindeutig! | 4:58 |
| von einem Kellerautomaten K akzeptierte Sprache L(K) | 5:41 |
| Akzeptieren durch leeren Keller | 6:55 |
| mit leerem Keller akzeptierte Sprache N(K) | 7:32 |
| Unterschied der beiden Akzeptanzarten | 8:24 |
| Äquivalenz zwischen den Akzeptanzarten | 8:42 |
| akzeptierender Zustand -> leerer Keller | 10:05 |
| Idee der Transformation | 10:39 |
| zusätzliche Wörter in N(K') | 12:39 |
| K darf den Keller nicht leeren. | 13:06 |
| Idee: neues künstliches Kellergrundsymbol | 14:18 |
| Beschreibung von K^ | 15:03 |
| Was passiert, wenn der Keller von K leer wird? | 16:38 |
| leerer Keller -> akzeptierender Zustand | 17:52 |
| Idee | 18:07 |
| Schutz vor "wirklich" leerem Keller | 18:24 |
| ergänzende Übergänge | 19:26 |
| Akzeptanzkriterium ist Geschmackssache | 21:15 |
| Videoinhalt | |
|---|---|
| Kellerautomaten und kontextfreie Sprachen | 0:00 |
| Grammatik G -> Kellerautomat K | 0:34 |
| Beispiel einer Linksableitung | 0:50 |
| Idee: Nachvollziehen der Linksableitung | 1:25 |
| Unterscheidung erzeugen <-> lesen | 1:37 |
| Übergänge von K | 2:49 |
| Behandlung der Paarregeln | 2:59 |
| Behandlung der Terminalregeln | 4:10 |
| K braucht kein Gedächtnis. | 5:25 |
| nur ein einziger Zustand | 5:44 |
| Startsymbol S | 6:12 |
| Akzeptieren bei leerem Keller | 6:34 |
| Kellergrundsymbol = S | 6:40 |
| Eingabealphabet | 6:56 |
| Bandalphabet = V | 7:06 |
| Zustandsmenge Q = {q0} | 7:13 |
| Folge der Konfigurationen | 7:51 |
| kein Gedächtnis | 9:25 |
| Definition der Übergänge | 9:36 |
| Bedeutung der CNF | 9:49 |
| Übergangsrelation | 10:18 |
| ε-Regeln | 11:31 |
| Videoinhalt | |
|---|---|
| Kellerautomat -> Grammatik | 0:00 |
| Elimination der Zustände | 1:18 |
| Idee: Zustand auf dem Keller speichern | 1:50 |
| Problem beim Löschen im Keller | 3:17 |
| Raten der richtigen Zustands | 4:55 |
| Folge eines falschen Rateversuchs | 6:06 |
| Kontrollzustände | 6:39 |
| Kelleralphabet des gedächtnislosen Automaten | 8:12 |
| Entsprechung zum Keller im Automaten K | 8:52 |
| genaue Entsprechung | 9:22 |
| Ziel der Konstruktion | 11:55 |
| Beschreibung der Übergänge | 13:54 |
| Übergänge mit Kellerinhalt | 14:07 |
| Kellersymbol wird gelöscht | 18:25 |
| Anfangsübergänge für den ersten Schritt | 20:25 |
| Wiederholung der Grundidee | 22:58 |
| Abschluss des Beweises | 23:48 |
| Zusammenfassung | 24:25 |
| Akzeptieren über Zustand | 24:48 |
| Videoinhalt | |
|---|---|
| Konstruktion der Grammatik G | 0:00 |
| Definition der Regeln | 0:51 |
| Variablenmenge V = Kelleralphabet | 1:20 |
| Startsymbol | 2:00 |
| Struktur der entstehenden Regeln | 2:49 |
| Ausblick auf Anwendung | 3:28 |
| Videoinhalt | |
|---|---|
| Schnitt einer kontextfreien Sprache mit einer regulären Sprache | 0:00 |
| Kellerautomat für L | 0:38 |
| Kellerautomat für die Schnittmenge | 1:42 |
| Zustandsmenge: kartesisches Produkt | 2:43 |
| unveränderte Kelleroperationen | 3:02 |
| Startzustand | 3:16 |
| nichtdeteministischer Kellerautomat | 3:51 |
| Übergänge in K | 4:25 |
| Nachfolgezustand | 5:05 |
| Übergänge ohne Eingabesymbol | 6:13 |
| akzeptierende Zustände | 7:44 |
| Rückblick auf die Konstruktion | 8:37 |
| 2. Beweis: Tripelkonstruktion | 9:16 |
| Videoinhalt | |
|---|---|
| Konstruktion ausgehend von Grammatik G | 0:00 |
| Grammatik in Chomsky-Normalform | 0:33 |
| Tripelkonstruktion | 1:00 |
| Regeln | 1:20 |
| Behandlung von Paarregeln | 1:23 |
| Grundidee | 2:11 |
| Zusammenpassen wie Dominosteine | 3:22 |
| Behandlung von Terminalregeln | 4:27 |
| Anfangsregeln | 5:47 |
| Regel für das leere Wort | 7:51 |
| Videoinhalt | |
|---|---|
| deterministischer Kellerautomat | 0:00 |
| deterministische kontextfreie Sprachen | 2:18 |
| Beispiel { 0^n 1^n } | 2:48 |
| Beispiel Dycksprache | 3:37 |
| Palindrome mit markierter Mitte | 4:17 |
| Palindrome ohne Mittelmarkierung | 5:02 |
| Definition mit Akzeptieren durch leeren Keller | 5:45 |
| Mit leerem Keller muss der Automat abbrechen. | 6:20 |
| präfixfreie Sprachen | 7:46 |
| Beispiel { 0^n 1^n } + { 0^n 1^(2n) } | 8:27 |
| Beweisidee | 9:02 |
| nicht abgeschlossen unter Umkehrung | 10:17 |
| eindeutige Grammatik | 11:19 |
| keine Umkehrung | 12:22 |
| inhärent mehrdeutige Sprachen | 13:14 |
| Anwendung auf Programmiersprachen | 13:38 |
| Werkzeuge: bison (yacc), und flex | 14:54 |
| Videoinhalt | |
|---|---|
| Ergänzung: Anwendung der theoretischen Informatik | 0:00 |
| Vorlesung Algorithmen, Datenstrukturen, Datenabstraktion (3. Semester) | 0:18 |
| deterministischer 2-Wege-Kellerautomat | 0:54 |
| Eingabebegrenzungssymbole | 1:45 |
| Teilwortproblem | 2:17 |
| Suchen des Musters x im Text b | 2:49 |
| grundlegende Aufgabe der Textverarbeitung | 3:09 |
| det. 2W-Kellerautomat für das Teilwortproblem | 3:20 |
| quadratische Laufzeit | 4:01 |
| Simulation in linearer Zeit | 4:25 |
| Linearzeitalgorithmus für das Teilwortproblem | 5:17 |
| Videoinhalt | |
|---|---|
| Anwendungen kontextfreier Grammatiken | 0:00 |
| Syntax von Programmiersprachen | 0:13 |
| kontextfreie Datenformate | 0:28 |
| HTML für Netzseiten | 0:39 |
| Quelltext einer Netzseite | 1:04 |
| XML als strukturiertes Datenformat | 2:55 |
| Beispiel einer XML-Datei | 3:21 |
| Baumstruktur | 4:39 |
| Videoinhalt | |
|---|---|
| Zusammenfassung und Rückblick | 0:00 |
| Sprache | 0:24 |
| Automat | 0:46 |
| Algorithmus, Turingmaschine | 1:03 |
| Querverbindung zwischen Sprachen und Automaten | 1:26 |
| algorithmische Fragen über Sprachen und Automaten | 1:46 |
| Algorithmen in der Vorlesung | 2:04 |
| duale Rolle von Algorithmen | 3:41 |
| Algorithmen über Algorithmen | 4:29 |
| Unentscheidbarkeit | 4:58 |
| Primitive Maschinen können mächtig sein. | 5:35 |
| Nichtdeterminismus | 6:52 |
| Selbstbezüglichkeit: Programme und Daten | 8:59 |
| Reduktion zwischen Problemen | 10:10 |
| Ausblick: weiterführende Lehrveranstaltungen | 10:53 |