| Videoinhalt | |
|---|---|
| Begrüßung | 0:00 |
| Qualifikationsziele | 1:00 |
| Was? | 1:38 |
| Wie? | 1:45 |
| Wozu? | 4:21 |
| Wie spezifizieren? | 4:51 |
| Korrektheit einer Implementierung | 5:35 |
| Effizienz | 8:52 |
| NP-Vollständigkeit | 9:37 |
| Inhalte | 10:14 |
| Videoinhalt | |
|---|---|
| Sortierverfahren | 0:00 |
| Bubblesort | 0:11 |
| Sortieren durch Auswahl | 2:01 |
| Sortieren durch Einfügen | 3:23 |
| Quicksort | 7:14 |
| Sortieren durch Verschmelzen | 15:32 |
| Teile und herrsche | 19:46 |
| Videoinhalt | |
|---|---|
| O-Notation | 0:00 |
| Quiz | 3:27 |
| Omega-Notation | 5:52 |
| Theta-Notation | 6:40 |
| Beispiel | 9:01 |
| Videoinhalt | |
|---|---|
| Analyse von Quicksort | 0:00 |
| zufällige Pivotauswahl | 1:25 |
| Quiz | 1:43 |
| Rekursion für den Erwartungswert | 3:03 |
| Quiz | 12:21 |
| Rückblick auf den Beweis | 14:22 |
| Laufzeit bei zufälliger Eingabe | 15:42 |
| Quiz | 17:18 |
| Videoinhalt | |
|---|---|
| Topologisches Sortieren | 0:00 |
| Problemdefinition | 2:46 |
| Algorithmus | 5:05 |
| Formulierung des Algorithmus | 9:10 |
| Korrektheit | 11:11 |
| Abbruch ohne Lösung | 11:52 |
| Charakterisierung der Existenz einer topologischen Sortierung | 13:23 |
| Videoinhalt | |
|---|---|
| Implementierung | 0:00 |
| Ganz naive Implementierung | 0:42 |
| naive Implementierung | 3:09 |
| getrennte Listen der Abhängigkeiten | 4:56 |
| Vorgängerzähler | 8:15 |
| Liste der freien Aufgaben | 13:03 |
| Videoinhalt | |
|---|---|
| Endgültiger Algorithmus | 0:00 |
| mitgeführte Daten | 0:16 |
| verbesserter Algorithmus | 0:56 |
| Initialisierung | 3:31 |
| Methodische Überlegungen zu Varianten | 4:56 |
| Speichern oder ausrechnen? | 5:28 |
| Vergleich von Varianten | 7:21 |
| Modellierung als Graphenproblem | 10:19 |
| Videoinhalt | |
|---|---|
| Auswahl der Datenstrukturen | 0:00 |
| Java-Programm | 4:49 |
| Hauptprogramm | 7:22 |
| Initialisierung | 9:49 |
| Testlauf | 12:04 |
| Python-Programme | 13:12 |
| Laufzeitanalyse | 14:05 |
| Videoinhalt | |
|---|---|
| Abstrakte Datentypen | 0:00 |
| Befehle und Abfragen | 2:03 |
| Spezifikation abstrakter Datentypen | 4:32 |
| Abstraktion in der Informatik | 9:57 |
| Videoinhalt | |
|---|---|
| Mengen | 0:00 |
| Definition der Gleichheit | 0:17 |
| Multimengen | 1:58 |
| Gleichheit von Elementen | 2:27 |
| veränderliche Objekte | 2:43 |
| veränderliche und unveränderliche Typen in Python | 6:26 |
| Mengen in Java | 7:26 |
| Namen und Parameter der Operationen | 9:03 |
| Videoinhalt | |
|---|---|
| Was ist Algebra? | 0:00 |
| Quiz | 2:42 |
| Quiz | 3:26 |
| Axiome | 4:23 |
| Vollständigkeit und Konsistenz | 7:28 |
| Beispiel eines Umformungsbeweises | 10:21 |
| Videoinhalt | |
|---|---|
| Referenzimplementierung in Haskell | 0:00 |
| algebraische Datentypen in Haskell | 0:50 |
| Haskell-Programm | 1:52 |
| Programmlauf | 5:04 |
| automatische Erzeugung der Implementierung | 8:16 |
| Videoinhalt | |
|---|---|
| Stückweise konstante Funktionen | 0:00 |
| Anwendungsbeispiele | 1:15 |
| Darstellung durch Fallunterscheidung | 1:51 |
| Intervallgrenzen | 2:45 |
| halboffene Intervalle | 3:48 |
| Definitionsbereich | 4:09 |
| Operationen | 6:03 |
| Daten zur Darstellung | 8:11 |
| Videoinhalt | |
|---|---|
| Implementierung in Python | 0:00 |
| Darstellung als Folge | 0:21 |
| Berechnen der Funktion | 1:38 |
| Addition zweier Funktionen | 3:49 |
| Aufgabe bei der Addition | 5:28 |
| Verschmelzen | 6:09 |
| Die yield-Anweisung in Python | 6:28 |
| Generatorfunktionen | 12:20 |
| Die Schleifeninvariante | 16:15 |
| Videoinhalt | |
|---|---|
| Python-Programm zur Addition | 0:00 |
| Darstellung der leeren Funktion | 3:27 |
| Quiz | 5:17 |
| Eindeutigkeit der Darstellung | 5:55 |
| Beispieldaten | 6:49 |
| Ablaufbeispiel | 7:44 |
| Videoinhalt | |
|---|---|
| offene und geschlossene Intervallgrenzen | 0:00 |
| Definition der erweiterten Zahlen | 1:40 |
| eine Klasse für erweiterte Zahlen | 4:54 |
| Totalordnung | 5:54 |
| Quiz | 12:43 |
| Videoinhalt | |
|---|---|
| Analyse von Quicksort | 0:00 |
| randomisierter Quicksort-Algorithmus | 0:24 |
| zufällige Eingabe | 1:00 |
| Analyse im schlimmster Fall | 2:04 |
| durchschnittlicher Fall | 2:48 |
| ausgabeabhängige etc. Analyse | 4:13 |
| andere Modelle | 5:38 |
| Verhalten in der Praxis | 6:23 |
| randomisierte Algorithmen | 8:11 |
| Videoinhalt | |
|---|---|
| Modellierende Spezifikation | 0:00 |
| Namen der Operationen und Typen der Parameter | 0:46 |
| Vorbedingungen und Nachbedingungen | 1:57 |
| Quiz | 7:59 |
| Gleichungen, keine Zuweisungen | 8:12 |
| Zusammenfassung | 8:51 |
| Spezifikation als Vertrag | 9:31 |
| Videoinhalt | |
|---|---|
| Implementierung vom Mengen | 0:00 |
| Quiz | 0:25 |
| SmallIntSet.java | 0:27 |
| Darstellung einer Menge | 1:24 |
| Abstraktionsfunktion | 4:45 |
| Eindeutigkeit | 7:43 |
| Zusammenfassung: Abstraktionsfunktion | 11:30 |
| Videoinhalt | |
|---|---|
| Darstellungsinvariante | 0:00 |
| Nebenbedingungen (Zusatzrestriktionen) | 1:52 |
| Korrektheit einer Implementierung | 3:29 |
| Übersetzung mit Hilfe der Abstraktionsfunktion | 5:27 |
| Beweis der Eigenschaften | 9:18 |
| Aufstellen der Schleifeninvariante | 10:26 |
| Beweis der einzelnen Schritte mit dem Hoare-Kalkül | 13:56 |
| Zusammenfassung | 16:36 |
| Videoinhalt | |
|---|---|
| Schnittstellen (interfaces) in Java | 0:00 |
| abstrakte Klassen | 1:44 |
| Vor- und Nachbedingungen in Eifel | 2:49 |
| design by contract | 4:20 |
| Videoinhalt | |
|---|---|
| Wörterbücher | 0:00 |
| Wörterbuchoperationen | 3:49 |
| Wörterbücher in Python | 6:39 |
| Wörterbücher und Mengen | 9:11 |
| Videoinhalt | |
|---|---|
| Binärer Baum | 0:00 |
| Suchbaum | 0:28 |
| Suchen in einem Suchbaum | 1:25 |
| Höhe und Tiefe | 1:57 |
| Einfügen | 3:26 |
| Löschen | 4:02 |
| Laufzeit | 7:01 |
| ausgeglichene und entartete Bäume | 7:47 |
| Videoinhalt | |
|---|---|
| AVL-Bäume | 0:00 |
| AVL-Bedingung | 0:37 |
| Quiz | 2:36 |
| Höhe eines AVL-Baums | 3:10 |
| Beweis der Höhenschranke | 4:50 |
| Videoinhalt | |
|---|---|
| Veränderung der Baumstruktur | 0:00 |
| Rotationen | 0:19 |
| Ausführung der Rotation | 1:42 |
| Veränderung der Höhen | 2:27 |
| Doppelrotation | 3:09 |
| Veränderung der Höhen | 5:09 |
| Einfügen in einen AVL-Baum | 5:56 |
| Wiederherstellung der AVL-Eigenschaft | 10:57 |
| Fall 2: Wachstum in der Mitte | 12:31 |
| Zusammenfassung für das Einfügen | 16:16 |
| Videoinhalt | |
|---|---|
| Löschen in einem Binärbaum | 0:00 |
| Änderung der Gestalt beim Löschen | 1:40 |
| Quiz | 3:59 |
| Quiz | 4:51 |
| Fall2: E hat geringere Tiefe | 8:12 |
| Zusammenfassung | 11:21 |
| Implementierung, Speicherung der Höhe | 12:12 |
| Videoinhalt | |
|---|---|
| Erweiterte Abfragen | 0:00 |
| Rangabfragen und inverse Rangabfragen | 0:43 |
| Zusätzliche Attribute | 1:38 |
| einfache rekursive Neuberechnung | 5:18 |
| Zusammenfassung | 6:27 |
| Videoinhalt | |
|---|---|
| Skiplisten | 0:00 |
| Suchen | 4:15 |
| Einfügen | 5:11 |
| Randomisierte Höhenbestimmung | 5:42 |
| Quiz | 7:58 |
| Quiz | 10:10 |
| Quiz | 11:01 |
| Einfügen | 11:42 |
| Beispiel für Einfügen | 12:45 |
| Quiz | 13:08 |
| Laufzeit für das Einfügen | 14:13 |
| Löschen | 16:03 |
| Analyse der Löschzeit | 18:09 |
| Zusammenfassung | 19:17 |
| Videoinhalt | |
|---|---|
| Erwartungswert der Höhe H | 0:00 |
| Beweis der Höhenschranke | 1:43 |
| Umformulierung des Erwartungswertes | 5:23 |
| Videoinhalt | |
|---|---|
| a-b-Bäume | 0:00 |
| Gestaltregeln | 1:59 |
| Ausnahme für die Wurzel | 3:39 |
| Werte nur in den Blättern | 4:15 |
| Aufbau eines inneren Knotens | 4:56 |
| Suchen | 7:14 |
| Videoinhalt | |
|---|---|
| Einfügen | 0:00 |
| Notwendigkeit der Bedingung für a und b | 1:44 |
| Ausbessern der Schlüssel | 3:40 |
| Löschen | 4:13 |
| Quiz | 4:56 |
| ausborgen | 5:03 |
| vereinigen | 5:51 |
| Elimination der Wurzel | 6:42 |
| Ausbessern der Schlüssel | 7:04 |
| Zusammenfassung | 8:28 |
| Implementierung der Knoten | 8:51 |
| Nebenbemerkungen: | 9:38 |
| 1. Rot-Schwarzbäume | 9:39 |
| 2. Umstrukturierungen in amortisiert konstanter Zeit | 10:09 |
| 3. Sortiern einer vorsortierten Liste | 12:03 |
| 4. Fingerbäume | 14:07 |
| Videoinhalt | |
|---|---|
| B-Bäume | 0:00 |
| externer Speicher | 0:39 |
| große Knoten | 0:57 |
| interne Verwaltung der Knoten | 3:20 |
| Videoinhalt | |
|---|---|
| Untere Schranken | 0:00 |
| vergleichsbasierte Algorithmen | 0:15 |
| Bitvektoren | 0:36 |
| beschänkte Grundgesamtheit | 1:52 |
| durchlaufen oder zählen | 4:52 |
| Bits als Markierung | 5:19 |
| Schlüssel als Adresse | 6:25 |
| Hashtabellen | 7:19 |
| Videoinhalt | |
|---|---|
| Entscheidungsbaum | 0:00 |
| Untere Schranke für das Sortieren | 5:45 |
| Entscheidungsbaum als Modell für untere Schranken | 7:39 |
| Untere Schranke für Wörterbuchoperationen | 8:22 |
| Videoinhalt | |
|---|---|
| Digitale Suchbäume | 0:00 |
| Beispiel | 0:23 |
| Markierung der Knoten | 2:01 |
| Suchen | 3:40 |
| Einfügen | 4:16 |
| Löschen | 4:58 |
| Laufzeit | 5:44 |
| Größe des Alphabets | 6:40 |
| Anwendungen | 9:07 |
| Speicherbedarf | 10:34 |
| Der Name "trie" | 11:54 |
| Videoinhalt | |
|---|---|
| Knoten vom Grad 1 | 0:00 |
| komprimierte digitale Suchbäume | 0:48 |
| Regeln | 2:29 |
| Suchen, Einfügen und Löschen | 3:42 |
| Speichervergleich | 5:27 |
| Anzahl der Knoten | 6:38 |
| Beweis der Knotenschranke | 8:08 |
| Quiz | 9:20 |
| Quiz | 9:51 |
| Quiz | 10:56 |
| Videoinhalt | |
|---|---|
| Suffixbäume | 0:00 |
| Definition | 0:35 |
| Beispiel | 1:10 |
| Betrachtung | 4:35 |
| Speicherbedarf | 6:21 |
| Alle Vorkommen eines Teilworts | 6:32 |
| Quiz | 8:30 |
| Funktion von $ | 8:59 |
| Teilwortproblem | 10:01 |
| Aufbau | 11:02 |
| Suffixfelder | 11:51 |
| Zusammenfassung | 12:23 |
| Videoinhalt | |
|---|---|
| Das Teilwortproblem | 0:00 |
| naiver Algorithmus | 1:52 |
| Laufzeit | 3:35 |
| Verbesserung mit der Verschiebefunktion | 5:19 |
| Verschiebefunktion | 9:11 |
| Quiz | 13:49 |
| Definitionsbereich der Verschiebefunktion | 14:43 |
| Bedeutung von j und k=f(j) | 15:28 |
| weiteres Beispiel | 16:27 |
| Sonderfall | 17:12 |
| Verschiebefunktion für das ganze Wort | 18:36 |
| Quiz | 19:08 |
| Verschiebetabelle | 19:16 |
| Videoinhalt | |
|---|---|
| Der Algorithmus von Knuth, Morris und Pratt | 0:00 |
| Laufzeit | 5:28 |
| Python-Programm | 8:11 |
| Verschiebefunktion | 10:15 |
| Videoinhalt | |
|---|---|
| Berechnen der Verschiebefunktion | 0:00 |
| Illustrativer Fall | 2:35 |
| Zusammenfassung | 6:13 |
| Python-Programm | 7:12 |
| Speicherbedarf | 9:05 |
| Videoinhalt | |
|---|---|
| Der Rabin-Karp-Algorithmus | 0:00 |
| Interpretation der Zeichen als Ziffern | 0:51 |
| Wert einer Zifferndarstellung | 2:36 |
| inkrementelle Berechnung | 4:58 |
| Wortvergleich und Wertvergleich | 8:06 |
| lineare Laufzeit | 9:11 |
| Vergleich mit den anderen Algorithmen | 11:09 |
| Videoinhalt | |
|---|---|
| Rechenoperationen auf m-stelligen Zahlen | 0:00 |
| Reduktion modulo Q | 1:59 |
| Quiz | 2:03 |
| Anpassung der Rekursion | 3:42 |
| Kontrolle auf Überlauf | 4:51 |
| Initialisierung | 6:40 |
| falscher Alarm | 7:27 |
| Wahl des Moduls Q | 9:45 |
| Videoinhalt | |
|---|---|
| Q als große Primzahl | 0:00 |
| Primzahlsatz | 1:22 |
| Abschätzung für Fehlalarm | 2:53 |
| Quiz | 5:32 |
| Zusammenfassung | 8:29 |
| Fingerabdruck | 8:42 |
| Bestimmen zufälliger Primzahlen | 9:55 |
| zweidimensionale Mustersuche | 13:03 |
| Videoinhalt | |
|---|---|
| Endliche Automaten | 0:00 |
| Beispiel | 1:45 |
| Konstruktion des Automaten | 5:10 |
| Speicherbedarf | 6:10 |
| Flexibiität | 7:08 |
| Videoinhalt | |
|---|---|
| Graphen in der Informatik und in Anwendungen | 0:00 |
| Wiederholung der Grundbegriffe | 0:25 |
| Kantengewichte | 1:16 |
| gerichtete und ungerichtete Graphen | 2:33 |
| Weg | 3:10 |
| Kreis | 3:45 |
| einfache Wege und Kreise | 4:00 |
| Abstand | 4:30 |
| Erreichbarkeit | 4:45 |
| Darstellung von Graphen im Computer | 5:23 |
| Adjazenzmatrix | 5:29 |
| Adjazenzlisten | 6:49 |
| Grundoperation | 10:06 |
| Vergleich Adjazenzmatrix und Adjazenzliste | 10:26 |
| dünn besetzte Graphen | 12:08 |
| Videoinhalt | |
|---|---|
| Breitensuche | 0:00 |
| Aufteilung in Schichten V_i | 0:34 |
| Ablauf | 1:27 |
| Initialisierung | 2:40 |
| Abbruchbedingung | 6:05 |
| Korrektheit | 6:26 |
| Invariante über die Mengen V_i | 6:31 |
| Vollständige Induktion nach k | 7:59 |
| Vorgängerzeiger | 15:16 |
| Breitensuchbaum | 16:50 |
| Organisation der Schichten | 18:17 |
| gemeinsame Warteschlange Q | 18:57 |
| Zusammenfassung | 22:27 |
| Videoinhalt | |
|---|---|
| Tiefensuche | 0:00 |
| Markierung der besuchten Knoten | 1:11 |
| Strategie | 2:13 |
| Tiefensuchbaum | 4:08 |
| rekursive Formulierung | 5:45 |
| Programm T(u) | 6:03 |
| Vorgängerzeiger | 7:12 |
| Implementierung der Markierungen und Vorgängerzeiger | 7:24 |
| Korrektheit | 8:28 |
| Induktionsbeweis | 9:37 |
| Laufzeit | 11:38 |
| Programm Tiefensuche.py | 12:37 |
| Tiefensuchnummern | 12:44 |
| Anwendungen der Tiefensuche | 13:34 |
| Testbeispiel | 15:21 |
| abstrakter Zugriff auf den Graphen | 16:06 |
| Ablauf für das Testbeispiel | 16:44 |
| Zusammenfassung | 19:09 |
| Videoinhalt | |
|---|---|
| Der kürzeste Weg | 0:00 |
| nichtnegative Kantengewichte | 0:42 |
| Algorithmus von Dijkstra | 1:11 |
| Simulation von Breitensuche | 1:42 |
| Unterteilung der Kanten | 2:01 |
| Ameisenüberfall | 6:02 |
| Abkürzung der Simulation | 6:49 |
| Welcher Knoten wird als nächster erreicht? | 8:14 |
| Beispiel | 12:44 |
| Vorgängerzeiger und kürzester-Wege-Baum | 16:10 |
| Videoinhalt | |
|---|---|
| Formulierung des Algorithmus (1. Fassung) | 0:00 |
| Abbruchbedingung | 1:18 |
| Korrektheit | 2:43 |
| Invariante | 3:07 |
| Terminierung | 6:44 |
| Videoinhalt | |
|---|---|
| Beschleunigung | 0:00 |
| inkrementelle Bestimmung der Spaltenminima | 3:03 |
| vorläufige kürzeste Weg | 4:28 |
| verbesserter Algorithmus | 8:02 |
| Initialisierung | 12:38 |
| Laufzeit | 14:44 |
| Vermeidung unendlicher Werte | 16:38 |
| Videoinhalt | |
|---|---|
| Betrachtung der notwendigen Operationen | 0:00 |
| Operationen mit den Markierungen | 1:26 |
| Ereignissimulation | 3:46 |
| decreasekey | 4:59 |
| Prioritätswarteschlange als abstrakter Datentyp | 5:15 |
| Implementierung durch Suchbäume | 5:41 |
| Untere Schranke für Prioritätswarteschlangen durch Sortieren | 6:23 |
| Halden | 7:19 |
| Fibonacci-Halden | 8:07 |
| Zusammenfassung | 9:39 |
| Videoinhalt | |
|---|---|
| Halden | 0:00 |
| Haldeneigenschaft | 0:35 |
| Einfügen | 1:47 |
| Gestalt des Baumes | 2:05 |
| EntferneMin | 5:27 |
| Speicherung in einem Feld | 7:52 |
| Pythonprogramm | 9:32 |
| Funktion zuklein | 10:57 |
| Funktion zugroß | 11:32 |
| Funktion decreaseKey | 13:21 |
| Quiz | 14:34 |
| Zusammenfassung | 14:34 |
| implizite Datenstrukturen | 15:26 |
| Videoinhalt | |
|---|---|
| Prioritätswarteschlange als abstrakter Datentyp | 0:00 |
| Zugriffsproblematik | 1:30 |
| Problem liegt in der Spezifikation | 4:28 |
| Henkelobjekte | 5:21 |
| Inhalt eines Henkelobjekts | 6:31 |
| Halde mit Henkeln | 7:14 |
| die Klasse Halde | 7:53 |
| die Klasse Henkel | 8:02 |
| entferneMin | 9:49 |
| verkleinereSchlüssel | 10:34 |
| Algorithmus von Dijkstra mit Prioritätswarteschlange | 12:12 |
| 2. Version, mit Attributen von Objekten | 16:00 |
| Testdaten | 16:31 |
| Zusammenfassung: Zugriff über ein Henkelobjekt | 17:35 |
| Höhere Effizienz durch eingebaute Implementierung | 18:22 |
| Videoinhalt | |
|---|---|
| kürzestes Verbindungsnetz | 0:00 |
| Anwendungen | 0:56 |
| Aufgabenstellung | 1:30 |
| Zusammenhang | 1:40 |
| Zielfunktion | 1:57 |
| zusammenhängende Graphen | 3:08 |
| Kreise | 3:24 |
| kreisfreie Graphen | 4:05 |
| Bäume | 4:31 |
| Spannbäume | 4:59 |
| Annahmen über die Anwendung | 5:52 |
| Quiz | 8:19 |
| Annahmen über die Kosten | 9:23 |
| Zusammenfassung der Problemstellung | 10:00 |
| Videoinhalt | |
|---|---|
| Bäume in verschiedenen Bedeutungen | 0:00 |
| Baum als Graph | 0:32 |
| Charakterisierung von Bäumen | 1:12 |
| eindeutiger Kreis | 1:43 |
| Bäume als Datenstrukturen | 2:08 |
| Grad eines Knotens | 3:24 |
| Quiz | 4:27 |
| Zeiger zwischen Eltern und Kindern | 5:07 |
| Quiz | 5:25 |
| Videoinhalt | |
|---|---|
| Gierige Algorithmen | 0:00 |
| Algorithmus von Kruskal | 0:29 |
| Formulierung des Algorithmus | 1:55 |
| gierige Entscheidungen | 3:22 |
| notwendige Operationen | 4:27 |
| Test auf Kreisfreiheit | 5:25 |
| Korrektheit | 5:49 |
| Beweis des Hilfssatzes | 7:03 |
| Videoinhalt | |
|---|---|
| 1. Zusammenhangskomponenten | 0:00 |
| 2. Äquivalenzklassen bezüglich Erreichbarkeit | 1:12 |
| 3. Test auf Kreisfreiheit | 1:45 |
| 4. Entwicklung der Komponenten | 3:51 |
| 5. Korrektheitsbeweis | 4:45 |
| 6. Korrektheit der Kante uv | 5:20 |
| Videoinhalt | |
|---|---|
| gleiche Kantenkosten | 0:00 |
| beliebige Auflösung von untentschiedenen Vergleichen | 0:37 |
| Störung der Kosten | 1:03 |
| Schlussfolgerung | 6:14 |
| Eindeutigkeit | 6:23 |
| Nachbemerkung: Behandlung von Sonderfällen | 6:52 |
| Videoinhalt | |
|---|---|
| Verwalten von Komponenten | 0:00 |
| UNION-FIND | 1:19 |
| FIND | 1:51 |
| UNION | 1:58 |
| Abstrakte Mengen | 2:20 |
| Mögliche Darstellung der Mengen | 3:34 |
| Anwendung im Algorithmus von Kruskal | 4:46 |
| Darstellung der Mengen als Bäume | 5:57 |
| Höhe logarithmisch beschränkt | 8:59 |
| Videoinhalt | |
|---|---|
| Pfadkompression | 0:00 |
| Analyse der Pfadverkürzung | 3:11 |
| Die Ackermannfunktion | 3:45 |
| Umkehrfunktionen | 5:51 |
| Untere Einhüllende von Strecken | 11:11 |
| Videoinhalt | |
|---|---|
| Algorithmus von Prim | 0:00 |
| Beispiel | 2:46 |
| Implementierung | 4:47 |
| Invariante | 6:37 |
| Initialisierung | 8:59 |
| Verwendung einer Prioritätswarteschlange | 10:43 |
| Laufzeit | 12:05 |
| Vergleich mit dem Algorithmus von Dijkstra | 12:18 |
| Videoinhalt | |
|---|---|
| 1. Der Algorithmus von Borůvka | 0:00 |
| 2. Anzahl der Iterationen | 2:43 |
| 3. Implementierung der Schleifen | 3:52 |
| 4. gleiche Kosten | 5:28 |
| 5. Entscheidung durch sekundäre Merkmale | 6:30 |
| Videoinhalt | |
|---|---|
| Hashtabellen | 0:00 |
| Hashfunktion | 2:09 |
| feste Länge | 3:21 |
| Kollisionen | 4:13 |
| gute Hashfunktion | 5:54 |
| Verhalten wie eine zufällige Funktion | 6:52 |
| Zusammenfassung | 7:51 |
| Kollisionsbehandlung | 8:06 |
| Verkettung | 8:14 |
| offene Adressierung | 8:37 |
| Videoinhalt | |
|---|---|
| multiplikatives Hashing | 0:00 |
| Beispiel | 1:39 |
| Eigenschaften der Hashfunktion | 3:19 |
| Quiz | 4:24 |
| Belegungsfaktor | 6:11 |
| erwartete Listenlänge | 7:39 |
| Laufzeit | 10:15 |
| Suchen, Einfügen, und Löschen | 10:48 |
| Videoinhalt | |
|---|---|
| Offene Adressierung | 0:00 |
| Clusterbildung | 0:58 |
| Löschen | 2:32 |
| erwartete Laufzeit | 3:29 |
| quadratisches Sondieren | 4:52 |
| Videoinhalt | |
|---|---|
| Kuckuckshashing | 0:00 |
| Speicherung der Schlüssel | 0:58 |
| Suchen in konstanter Zeit | 1:24 |
| Einfügen | 1:44 |
| Kette von Verschiebungen | 3:05 |
| Neuaufbau der Tabelle | 4:22 |
| Zusammenfassung | 4:53 |
| Videoinhalt | |
|---|---|
| Multiplikative Hashfunktion | 0:00 |
| Kollisionswahrscheinlichkeit | 1:08 |
| Zeitpunkt der zufälligen Wahl von z | 1:37 |
| Hilfssatz über multiplikative Bijektion | 2:23 |
| Experimentelle Überprüfung | 3:19 |
| Beweis des Lemmas | 4:36 |
| Formulierung als Zufallsaussage | 7:28 |
| Beweis des Satzes | 8:28 |
| Interpretation einer Kollision | 8:55 |
| zwei unpassende Bitmuster | 11:44 |
| Überlappung der Zufallsbits mit dem Fenster | 15:05 |
| Videoinhalt | |
|---|---|
| längere Schlüssel | 0:00 |
| Hashcodes | 1:06 |
| Berechnung des Hashcodes in 2 Stufen | 2:32 |
| Kollisionswahrscheinlichkeit | 4:39 |
| Beweis | 5:50 |
| Videoinhalt | |
|---|---|
| Hashcodes mit Primzahlen | 0:00 |
| Schlüssel variabler Länge | 0:48 |
| Unabhängigkeit der zufälligen Multiplikatoren | 1:06 |
| Fingerabdrücke beim Rabin-Karp-Algorithmus zur Teilwortsuche | 2:24 |
| hashCode() in Java | 4:28 |
| böswille Wahl der Schlüssel | 7:27 |
| kryptographische Hashfunktionen | 9:04 |
hashCode() in Java, siehe Java-Spezifikation, Funktion hash() in Python| Videoinhalt | |
|---|---|
| Kuckuckshashing | 0:00 |
| Tabelle der Hashwerte zufällig gleichverteilt | 1:24 |
| Anzahl der notwendigen Bits | 2:58 |
| Quiz | 3:10 |
| Belegungsfaktor | 3:40 |
| Kuckucksgraph | 4:22 |
| zulässige Orientierung | 5:29 |
| Unabhängigkeit von der Einfügereihenfolge | 7:28 |
| Einfügealgorithmus | 7:51 |
| Hindernisse | 10:22 |
| Hindernisse und Orientierungen | 11:13 |
| Quiz | 12:36 |
| Codierungsargument | 13:00 |
| Parameter für die Gestalt des Hindernisses | 16:24 |
| Schlüssel und Hashwerte im Hindernis | 17:35 |
| Hashwerte für die Schlüssel außerhalb des Hindernisses | 18:45 |
| Gesamtzahl der Möglichkeiten | 20:38 |
| Zusammenfassung | 24:34 |
| Videoinhalt | |
|---|---|
| Erfolgreiches Einfügen | 0:00 |
| Ablauf des Einfügens | 0:31 |
| hohe Erfolgswahrscheinlichkeit | 3:19 |
| erwartete Einfügezeit | 3:50 |
| Zusammenfassung der Laufzeit | 5:52 |
| Implementieren des Einfügens | 8:01 |
| Markierung | 8:35 |
| ohne Markierungen | 8:58 |
| Draufgängertum | 10:10 |
| Verhalten bei Kreisen | 13:29 |
| Videoinhalt | |
|---|---|
| erweiterter Euklidischer Algorithmus | 0:00 |
| Existenz einer Inversen | 0:41 |
| Notwendigkeit der Bedingung | 1:25 |
| Zwischenergebnisse durch u und v ausgedrückt | 3:06 |
| Invarianten | 3:30 |
| Beispiel | 4:00 |
| Quiz | 4:23 |
| Ergebnis | 7:10 |
| Folgerung für x und m | 7:31 |
| Berechnung der Inversen | 8:49 |
| Anwendungen | 9:07 |
| Videoinhalt | |
|---|---|
| Durchprobieren aller Möglichkeiten | 0:00 |
| Spektrum verschiedener Laufzeiten | 0:28 |
| Acht-Damenproblem | 1:39 |
| Lösungsbaum | 4:47 |
| rekursives Durchlaufen | 6:51 |
| Testen auf Konflikt | 9:13 |
| Videoinhalt | |
|---|---|
| Effiziente Lösbarkeit von Problemem | 0:00 |
| Algorithmische Probleme | 0:28 |
| Eingabe | 0:37 |
| Eingabelänge | 2:33 |
| Ausgabe | 3:02 |
| Laufzeit | 4:27 |
| Definition der Klasse P | 5:51 |
| Beispiele | 6:56 |
| Videoinhalt | |
|---|---|
| Rechnermodelle | 0:00 |
| RAM-Modell (Registermaschine) | 0:35 |
| Turingmaschine | 2:40 |
| Modelle sind für negative Aussagen notwendig | 4:19 |
| Church-Turing'sche These | 5:09 |
| Robustheit der Definition von P | 6:04 |
| Simulation einer RAM auf einer Turingmaschine | 8:03 |
| Videoinhalt | |
|---|---|
| Reduktion eines Problems auf ein anders | 0:00 |
| Reduktion in der Informatik | 2:13 |
| Witz | 3:33 |
| Argument für Schwierigkeit | 5:10 |
| Transitivität der Redukzierbarkeit | 6:23 |
| Laufzeit einer Reduktion | 6:46 |
| polynomielle Reduktion | 7:22 |
| Hauptsatz über polynomielle Reduktion | 7:44 |
| Beweis | 8:10 |
| Quiz | 12:29 |
| Transitivität | 12:30 |
| Videoinhalt | |
|---|---|
| Beispiel für eine Reduktion | 0:00 |
| Rundreiseproblem | 0:12 |
| Reduktion HAM<TSP | 3:38 |
| polynomielle Laufzeit der Reduktion | 5:23 |
| Videoinhalt | |
|---|---|
| Das Erfüllbarkeitsproblem | 0:00 |
| Bedeutung des Erfüllbarkeitsproblems | 3:00 |
| Graphenfärbung | 3:47 |
| Färbungsbeispiel | 4:42 |
| Färbungsanwendungen | 5:35 |
| Entscheidungsproblem | 6:23 |
| Reduktion auf SAT | 7:32 |
| Variablen | 8:52 |
| Bedingungen | 9:37 |
| polynomielle Laufzeit | 13:58 |
| Videoinhalt | |
|---|---|
| Entscheidungsprobleme | 0:00 |
| Entscheidungsproblem als Sprache | 0:33 |
| Karp-Reduktion für Entscheidungsprobleme | 2:15 |
| Turing-Reduktion | 4:12 |
| Videoinhalt | |
|---|---|
| Die Klasse NP | 0:00 |
| polynomielles Zertifikatskriterium | 0:59 |
| Korrektheit | 1:36 |
| polynomielle Laufzeit | 4:12 |
| Beispiele | 5:37 |
| Diskussion der Definition | 6:43 |
| Lösung durch "Raten" | 7:02 |
| nichtdeterministisch-Polynomialzeit | 8:16 |
| Videoinhalt | |
|---|---|
| Probleme in NP | 0:00 |
| polynomiell lösbare Probleme in NP | 0:25 |
| schwieriger als alle Probleme in NP | 1:48 |
| Bedeutung | 3:12 |
| Ungelöstes Problem: P=NP? | 5:35 |
| Bedeutung als Cartoon | 7:10 |
| NP-schwere Probleme | 10:08 |
| NP-Vollständigkeit | 10:26 |
| Videoinhalt | |
|---|---|
| Satz von Cook/Levin | 0:00 |
| Skizze des Beweises | 0:21 |
| NP-Schwerheit durch Reduktion | 7:36 |
| Richtung der Reduktion | 8:20 |
| Beweis | 8:48 |
| Ausblick | 9:37 |
| Videoinhalt | |
|---|---|
| 1. Graphenfärbung | 0:00 |
| 2. 3-Färbbarkeit | 0:34 |
| 3. 2-Färbbarkeit | 1:05 |
| Quiz | 2:12 |
| 4. Reduktion auf ein allgemeineres Problem | 2:29 |
| 5. Reduktion | 3:35 |
| 6. Klauseln | 5:54 |
| 7. Korrektheit der Reduktion | 8:23 |
| 8. polynomielle Laufzeit | 8:42 |
| 9. Analyse der Bausteine | 8:54 |
| 10. Fallunterscheidung | 10:11 |
| 11. Klauselvorrichtung | 11:42 |
| 12. Korrektur der Konstruktion | 12:36 |
| 13. typische Konstruktion von "Vorrichtungen" | 14:05 |
| 14. Beweis der Korrektheit | 15:16 |
| 15. Definiton der Reduktion | 17:42 |
| 16. Zusammenfassung | 19:28 |
| Videoinhalt | |
|---|---|
| 3-SAT: Klauseln der Länge 3 | 0:00 |
| Idee der Reduktion | 1:27 |
| Behandlung zu langer Klauseln | 1:44 |
| Hilfsreduktion | 3:35 |
| 2-SAT | 5:48 |
| Videoinhalt | |
|---|---|
| Felder und verkettete Listen | 0:00 |
| Dynamische Listen | 2:05 |
| amortisierte Laufzeit | 4:31 |
| Speicherbedarf | 6:39 |
| Löschen | 7:30 |
| alternative strengere Bedingungen | 10:40 |
| Abstand von den kritischen Füllständen | 11:26 |
| Anwendung auf Hashtabelen | 13:16 |
| virtueller Speicher | 14:10 |
| Zusammenfassung | 15:29 |
| Videoinhalt | |
|---|---|
| Listen in Python | 0:00 |
| Mengen und Wörterbücher in Python | 1:58 |
| Collection-Klassen der Java-Bibliothek | 2:41 |
| Videoinhalt | |
|---|---|
| 1. dynamische Speicherverwaltung | 0:00 |
| 2. automatische Verwaltung in Java oder Python | 0:15 |
| 3. Laufzeitsystem | 2:03 |
| 4. explizite Speicherfreigabe | 4:15 |
| 5. automatische Speicherfreigabe | 4:31 |
| 6. Referenzzähler | 5:24 |
| 7. Mitführen des Referenzzählers | 6:08 |
| 8. zyklische Zeigerstrukturen | 8:01 |
| 9. Müllsammlung (garbage collection) | 8:58 |
| 10. Markierungsalgorithmus | 9:39 |
| 11. Aufwand | 10:13 |
| 12. Echtzeitanwendungen | 11:26 |
| 13. explizite Speicherfreigabe | 13:09 |
| 14. Verwaltung des freien Speichers | 13:39 |
| 15. Stapel und Halde | 14:17 |
| 16. Freigabe durch Löschen der Referenzen | 15:57 |
| 17. Speicherleck | 17:08 |
| Videoinhalt | |
|---|---|
| Sortieren ohne Vergleiche | 0:00 |
| beschränktes Schlüsseluniversum | 0:09 |
| Sortieren durch Fachverteilung | 0:31 |
| Stabilität | 3:03 |
| Radixsort | 3:57 |
| Korrektheit | 6:25 |
| Sortiermaschinen | 7:45 |
| Lochkarten | 9:26 |
| Laufzeit und Speicherbedarf | 10:46 |
| Gleitkommazahlen | 13:10 |
| Videoinhalt | |
|---|---|
| optimale Codes | 0:00 |
| Quellalphabet | 0:37 |
| ASCII | 1:08 |
| eindeutig entzifferbar | 3:04 |
| präfixfrei | 4:21 |
| Codebaum | 6:13 |
| Häufigkeiten | 8:20 |
| Mittlere äußere Weglänge | 11:58 |
| Videoinhalt | |
|---|---|
| Algorithmus von Huffman | 0:00 |
| Top-Down-Ansatz | 0:17 |
| Zuordnung zwischen Längen und Häufigkeiten | 0:48 |
| Austauschargument | 2:16 |
| tiefste Geschwister | 4:24 |
| Beispiel | 10:30 |
| Erzeugung des Codes | 11:19 |
| Implementierung | 11:53 |
| Anwendungen in der Datenkompression | 13:14 |
| Videoinhalt | |
|---|---|
| Kraft-McMillan'sche Ungleichung | 0:00 |
| Satz von McMillan | 0:26 |
| Beispiel | 0:39 |
| Nachrichten der Länge k | 1:56 |
| Rekursion | 2:52 |
| Beweis durch Widerspruch | 4:22 |
| charakteristische Gleichung der Rekursion | 5:16 |
| Korrektur der Notation | 6:47 |
| vollständige Induktion | 7:31 |
| Induktionsbasis | 8:33 |
| Längen, die nicht vorkommen | 9:15 |
| größter gemeinsamer Teiler | 9:23 |
| Füllsymbole | 11:02 |
| Induktionsbeweis | 13:06 |
| eindeutige Entzifferbarkeit | 13:50 |
| Induktionsbasis | 14:04 |
| Widerspruch | 14:36 |
| Videoinhalt | |
|---|---|
| optimaler Suchbaum | 0:00 |
| Zugriffshäufigkeiten | 1:15 |
| Wahrscheinlichkeiten und erwartete Suchzei | 2:35 |
| Vergleich zum optimalen binären Code | 3:05 |
| Lücken | 4:07 |
| Dreiwegevergleiche | 5:56 |
| Aufgabenstellung | 6:52 |
| Probieren aller Bäume | 7:28 |
| Ansatz | 7:47 |
| Teilprobleme | 9:16 |
| künstliche unendliche Schlüssel | 10:01 |
| Rekursion | 10:57 |
| Anfangsbedingungen | 14:40 |
| Lösung des ursprünglichen Problems | 15:37 |
| rekursive Funktion | 16:13 |
| Videoinhalt | |
|---|---|
| Mehrfaches Lösen des gleichen Problems | 0:00 |
| Dynamische Programmierung | 0:41 |
| Definition der dynamischen Programmierung | 0:55 |
| allgemeines Algorithmenentwurfsprinzip | 1:11 |
| Bezeichnung "Dynamische Programmierung" | 1:42 |
| 1. DEFINITION DER TEILPROBLEME | 2:44 |
| 2. Rekursionsgleichung und Anfangswerte | 3:49 |
| 3. Systematische Reihenfolge | 4:45 |
| Python-Programm | 5:54 |
| Laufzeit | 7:49 |
| Speicher | 8:39 |
| Partialsummen als Vorverarbeitung | 9:36 |
| Konstruktion der optimalen Lösung | 10:10 |
| a) Speichern von Vorgängerzeigern | 10:31 |
| b) Rekonstruktion bei Bedarf | 11:47 |
| Videoinhalt | |
|---|---|
| Quiz | 6:15 |
| Videoinhalt | |
|---|---|
| 1. Algorithmus von Dantzig | 0:00 |
| 2. negative Kantengewichte | 0:46 |
| 3. keine negativen Kreise | 1:50 |
| 4. einfacher Weg | 2:24 |
| 5. kürzeste einfache Wege | 3:35 |
| 6. kürzeste Wege zwischen allen Knotenpaaren | 4:28 |
| 7. Zusammenfassung der Problembeschreibung | 4:59 |
| 8. dynamische Programmierung | 5:19 |
| 9. Simplexalgorithmus zur linearen Programmierung | 5:37 |
| 10. Definition der Teilprobleme | 6:08 |
| 11. Gesamtproblem | 8:03 |
| 12. Rekursion | 8:16 |
| 13. Distanz von einem Knoten zu sich selbst | 12:39 |
| 14. nicht vorhandene Kanten | 15:03 |
| 15. Anfangsbedingungen | 16:11 |
| 16. Gesamtlaufzeit | 16:22 |
| 17. Speicherbedarf | 16:39 |
| 18. Speicherung in einer Matrix | 17:19 |
| 19. Rekonstruktion der Wege: Zwischenknoten | 19:04 |
| 20. Feststellen negativer Kreise | 22:31 |
| 21. Andere Ansätze mit dynamischer Programmierung | 25:20 |
| 22. Algorithmus von Bellman/Ford | 25:33 |
| 23. Algorithmus von Floyd/Warshall | 26:09 |
| Videoinhalt | |
|---|---|
| Edit-Abstand | 0:00 |
| Problemstellung | 1:36 |
| gewichtete Änderungen | 3:03 |
| Ausrichten zweier Wörter aneinander | 3:26 |
| Anwendungen in der Bioinformatik | 5:03 |
| 1) Definition der Teilprobleme | 6:03 |
| 2) Rekursion | 6:53 |
| 2b) Randbedingungen | 9:47 |
| 3) Reihenfolge der Teilprobleme | 10:27 |
| Matrix der Lösungen | 11:07 |
| Ausfüllen der Tabelle | 11:29 |
| Laufzeit und Speicher | 14:06 |
| Zurückverfolgen der Lösung | 14:30 |
| Zusammenfassung | 16:16 |
| verschiedene Gewichte für verschiedene Änderungen | 16:40 |
| Reduktion des Speicherbedarfs | 18:33 |
| Quiz | 19:43 |
| Videoinhalt | |
|---|---|
| Abhängigkeitsgraph | 0:00 |
| Interpretation als kürzeste Wege | 0:41 |
| Kürzeste Wege in azyklischen Graphen | 6:22 |
| 1) Definition der Teilprobleme | 6:48 |
| 2) Rekursion | 7:03 |
| 2b) Anfangsbedingung | 7:20 |
| 3) Reihenfolge der Teilprobleme | 7:32 |
| Algorithmus | 9:23 |
| Laufzeit und Speicher | 10:27 |
| beliebige Kantengewichte | 11:37 |
| topologische Sortierung a priori | 11:51 |
| Videoinhalt | |
|---|---|
| Algorithmische Geometrie | 0:00 |
| konvexe Hülle | 1:55 |
| konvexes Polygon | 2:44 |
| konvexe Menge | 4:00 |
| Rand oder Inneres eines Polygons? | 6:04 |
| Videoinhalt | |
|---|---|
| inkrementeller Algorithmus | 0:00 |
| untere und obere konvexe Hülle | 0:25 |
| gleiche x-Koordinaten | 1:31 |
| Übergang von k-1 auf k | 3:17 |
| Veranschaulichung durch ein gespanntes Seil | 5:37 |
| Nummerieren der Hüllenpunkte | 6:20 |
| Abbruchbedingung | 9:11 |
| äußere Schleife | 10:40 |
| Grenzfall: entartete Lage | 12:08 |
| Implementierung von Q als Stapel | 13:11 |
| Videoinhalt | |
|---|---|
| Laufzeit | 0:00 |
| geschachtelte Schleifen | 0:07 |
| lineare Laufzeit | 1:09 |
| amortisierte Analyse | 2:07 |
| Zusammenfassung | 3:37 |
| Videoinhalt | |
|---|---|
| Knickrichtung | 0:00 |
| Vergleich der Winkel | 0:42 |
| Vergeich der Steigungen | 1:35 |
| Elimination der Division | 2:48 |
| Determinantenform | 3:26 |
| 3x3-Determinante | 4:39 |
| Anzahl an Multiplikationen | 5:14 |
| Umformung der Determinante | 6:18 |
| Beweis | 9:24 |
| rotierter Vektor | 10:44 |
| Rotation um 90° | 10:59 |
| geometrische Interpretation des Skalarprodukts | 11:32 |
| Lage in Bezug auf eine gerichtete Gerade | 12:56 |
| Flächeninhalt eines Dreiecks | 15:20 |
| Zusammenfassung | 17:39 |
| Videoinhalt | |
|---|---|
| Punkt in Polygon? | 0:00 |
| einfaches Polygon | 1:18 |
| Algorithmus | 1:53 |
| beliebige Richtung | 3:48 |
| lineare Laufzeit | 4:58 |
| Abfrageproblem mit Vorverarbeitung | 5:10 |
| konvexes Polygon | 5:35 |
| Quiz | 6:14 |
| Quiz | 6:14 |
| Schwierigkeiten | 6:14 |
| Anzahl der geschnittenen Kanten | 7:12 |
| Videoinhalt | |
|---|---|
| Schnitt mit einem horizontalen Strahl | 0:00 |
| Orientierungstest | 1:03 |
| Sonderfälle | 2:34 |
| Stören | 3:44 |
| erweiterte Zahlen | 6:51 |
| Zusammenfassung | 8:14 |
| Rundungsfehler | 8:32 |
| falsches Ergebnis | 10:03 |
| exakte Arithmetik | 12:30 |
| Videoinhalt | |
|---|---|
| 1. Dichtestes Punktpaar | 0:00 |
| 2. Anwendungen | 0:43 |
| 3. randomisierter Algorithmus mit Hashfunktionen | 1:27 |
| 4. Teile und herrsche | 1:38 |
| 5. Abstände zwischen L und R | 3:40 |
| 6. Beschränkung auf einen Streifen | 4:30 |
| 7. vertikale Sortierung | 5:14 |
| 8. Vereinigung der Teilprobleme | 7:21 |
| 9. Korrektheit | 8:35 |
| 10. Laufzeit | 9:58 |
| 11. Vereinigung der Teilprobleme | 10:46 |
| 12. beschränkte Anzahl an Nachbarn | 11:04 |
| 13. dichte Packung von Punkten | 12:39 |
| 14. Packungsargument | 12:58 |
| 15. disjunkte Viertelkreise | 14:15 |
| 16. Vergleich der Flächen | 15:07 |
| 17. Überblick über den Algorithmus | 19:04 |
| 18. Vorverarbeitung | 19:23 |
| 19. Zerlegung | 19:57 |
| 20. rekursive Lösung der Teilprobleme | 20:37 |
| 21. Vereinigung der Teilprobleme | 20:48 |
| 22. Rekursion für die Laufzeit | 21:56 |
| 23. Zusammenfassung | 22:54 |
| Videoinhalt | |
|---|---|
| 1. Rundreiseproblem | 0:00 |
| 2. gerichtetes Rundreiseproblem | 0:47 |
| 3. Kostenmatrix | 0:56 |
| 4. Anzahl der Lösungen | 1:32 |
| 5. Teillösungen | 3:18 |
| 6. Definition der Teilprobleme | 5:06 |
| 7. Rekursion | 6:55 |
| 8. Anfangsbedingung | 8:08 |
| 9. Lösung des Gesamtproblems | 8:34 |
| 10. systematische Reihenfolge | 9:33 |
| 11. Laufzeit und Speicherbedarf | 10:39 |
| 12. dynamische Programmierung im exponentiellen Bereich | 13:10 |
| 13. Anwendungen | 14:36 |
| Videoinhalt | |
|---|---|
| 1. Allgemeine Algorithmenentwurfsprinzipien | 0:00 |
| 2. Überblick | 1:12 |
| 3. Teile und herrsche | 2:07 |
| 4. dynamische Programmierung | 2:43 |
| 5. Definition der Teilprobleme | 3:56 |
| 6. Beispiele | 4:30 |
| 7. systematischen Durchsuchen von Lösungsbäumen | 7:12 |
| 8. gierige Algorithmen | 7:46 |
| 9. lokale Optimierung, heuristische Suchverfahren | 9:02 |
| Videoinhalt | |
|---|---|
| Sortierverfahren | 0:00 |
| Bubblesort | 0:11 |
| Sortieren durch Auswahl | 2:01 |
| Sortieren durch Einfügen | 3:23 |
| Quicksort | 7:14 |
| Sortieren durch Verschmelzen | 15:32 |
| Teile und herrsche | 19:46 |
| Videoinhalt | |
|---|---|
| Approximationsalgorithmen | 0:00 |
| Gütegarantie | 1:31 |
| Beispiel: größte Paarung | 1:40 |
| maximale Paarung | 3:12 |
| symmetrische Differenz | 3:51 |
| anternierende Wege | 4:49 |
| Heuristiken | 8:29 |
| Videoinhalt | |
|---|---|
| 1. lokale Optimierung | 0:00 |
| 2. Nachbarschaftsrelation | 0:23 |
| 3. Beispiel: Paarungen | 0:59 |
| 4. Beispiel: Rundreiseproblem | 2:43 |
| 5. 2-OPT-Nachbarschaft | 4:42 |
| 6. Optimierungsproblem: | 5:14 |
| 7. Zielfunktion | 5:33 |
| 8. lokale Optimierung | 6:11 |
| 9. Terminierung | 7:20 |
| 10. lokales Optimum | 7:55 |
| 11. globales Optimum | 8:30 |
| 12. lokale Extrema in der Analysis | 8:44 |
| 13. konvexe Funktionen | 11:26 |
| 14. Gütegarantie bei Paarungen | 12:21 |
| 15. Größe der Nachbarschaft | 14:13 |
| 16. Startlösung | 16:04 |
| 17. steilster Abstieg | 18:18 |
| 18. Gradientenverfahren | 19:16 |
| 19. Laufzeit? | 20:48 |
| Videoinhalt | |
|---|---|
| Ausweg aus einem lokalen Optimum | 0:00 |
| Tabusuche | 0:51 |
| Ameisenalgorithmen | 1:36 |
| genetische Algorithmen | 2:16 |
| simulated annealing | 4:10 |
| Akzeptieren von Verschlechterungen | 4:54 |
| Temperatur | 6:17 |
| Akzeptanzwahrscheinlichkeit | 7:29 |
| Temperatur als Skalierungseinheit | 8:21 |
| Temperatur als Steuerungsparameter | 9:15 |
| Abkühlen | 10:36 |
| Boltzmannverteilung | 13:34 |
| Vielseitigkeit heuristischer Suchverfahren | 15:29 |
| Nebenbedingungen als Strafterme | 16:30 |
| Zusammenfassung | 18:26 |
| Videoinhalt | |
|---|---|
| Analsyse von Spielen | 0:00 |
| Stellungsspiele | 0:24 |
| künstliche Intelligenz | 0:46 |
| Planungsprobleme ohne Gegner | 1:17 |
| Modellierung als Spielgraph | 1:51 |
| 2-Personen-Nullsummenspiele | 2:02 |
| Bewertung des Spielausgangs | 2:44 |
| Spiele mit vollständiger Information | 3:08 |
| kein Zufall | 3:38 |
| Spielgraph | 4:02 |
| Beispiel:Tic-Tac-Toe | 5:37 |
| Spielgraph für Tic-Tac-Toe | 7:28 |
| grobe Abschätzung der Größe des Graphen | 9:10 |
| bessere Abschätzung der Knotenzahl | 9:54 |
| Multinomialkoeffizienten | 10:36 |
| Knotenzahl laut Wikipedia | 13:00 |
| Quiz | 13:26 |
| Videoinhalt | |
|---|---|
| Symmetrieüberlegungen | 0:00 |
| Quiz | 0:32 |
| Quiz | 0:48 |
| Größe der Äquivalenzklassen | 1:27 |
| Min-Max-Algorithmus | 2:39 |
| Wert des Spieles | 3:26 |
| 4 gewinnt | 6:08 |
| Hex | 6:33 |
| Optimale Strategie | 6:58 |
| Kreise | 10:17 |
| Zusatzregel gegen unendliches Schach | 12:14 |
| Die Ko-Regel bei Go | 12:40 |
| Videoinhalt | |
|---|---|
| Optimale Strategie für Tic-Tac-Toe | 0:00 |
| Strategie für ALLE Spielzustände? | 0:30 |
| Graph oder Baum? | 0:52 |
| Symmetrie? | 1:11 |
| Darstellung | 1:26 |
| Symmetrie | 4:05 |
| Spielgraph oder Spielbaum? | 5:25 |
| Quiz | 6:33 |
| Videoinhalt | |
|---|---|
| Heuristische Bewertungsfunktionen | 0:00 |
| Zusammenfassung | 7:27 |
| α-β-Suche | 7:52 |
| dynamische Konstruktion des Spielbaumes | 8:15 |
| Berechnungsablauf | 9:53 |
| Abkürzungen | 13:15 |
| Spezifikation der α-β-Suche | 15:22 |
| Intervalle (α,β) im Beispiel | 17:23 |
| Algorithmus | 25:26 |
| Variante der Spezifikation | 29:16 |
| Zusammenfassung | 31:39 |
| Videoinhalt | |
|---|---|
| Auswahl des k-kleinsten Elements | 0:00 |
| Rangbestimmung von 12 | 0:48 |
| Median | 1:13 |
| Median in der Statistik | 1:41 |
| Ausreißer | 1:53 |
| Mittelwert | 2:28 |
| Robustheit des Medians | 2:39 |
| Einkommensverteilung | 2:45 |
| Quartile | 3:20 |
| Bestimmung des k-kleinsten Elements | 3:35 |
| Quickselect | 4:01 |
| deterministischer Algorithmus | 4:11 |
| Zerlegung | 4:30 |
| Rang und inverse Rangbestimmung | 5:43 |
| rekursive Suche | 6:50 |
| Beziehung zu Quicksort | 9:03 |
| Basis der Rekursion | 9:38 |
| schlechtester Fall | 9:54 |
| bester Fall | 11:02 |
| zufällige Auswahl des Pivotelementes | 11:35 |
| Videoinhalt | |
|---|---|
| Analyse | 0:00 |
| Rang r des Pivotelementes | 0:41 |
| gleichverteilter Rang | 1:39 |
| Größe der Teile | 1:52 |
| gleiche Elemente | 2:09 |
| gutes Pivotelement | 3:24 |
| Reduktion um den Faktor 3/4 | 3:45 |
| viele gute Pivotelemente | 4:35 |
| Wahrscheinlichkeit eines schlechten Pivotelementes | 7:09 |
| erwartete Laufzeit T(n) | 7:24 |
| monotone Laufzeit | 7:44 |
| Rekursion | 8:16 |
| Lösung der Rekursion | 12:01 |
| vollständige Induktion | 12:30 |
| Induktionsschritt | 12:57 |
| Rückblick auf die Analyse | 14:08 |
| Videoinhalt | |
|---|---|
| Nachtrag zum Teilwortproblem | 0:00 |
| Überblick | 0:56 |
| deterministischer 2-Wege-Kellerautomat | 1:38 |
| Eingabeband (nur zum Lesen) | 1:43 |
| Zustandsmenge Q | 2:53 |
| Startzustand q0 | 3:00 |
| Kelleralphabet Gamma | 3:06 |
| Stapelbodensymbol Z0 | 3:36 |
| Eingabealphabet Sigma | 4:17 |
| Übergangsfunktion delta | 4:49 |
| Startkonfiguration | 6:05 |
| Beendung | 6:20 |
| akzeptierende Zustandsmenge F | 6:51 |
| unendliche Schleife | 7:21 |
| Lösung des Teilwortproblems | 7:30 |
| Programmzähler | 8:40 |
| Laufzeit | 9:14 |
| exponentielle Laufzeit: Binärzähler | 9:30 |
| Simulation in linearer Zeit | 10:06 |
| direkte Simulation | 10:32 |
| Abbruchbedingung | 10:57 |
| Ausführung eines Schrittes | 11:21 |
| Beendigung nur mit leerem Stapel | 12:44 |
| Videoinhalt | |
|---|---|
| gegliederte Simulation | 0:00 |
| Veränderung des Stapels | 1:19 |
| Ergebnis der Simulationsfunktion | 2:31 |
| rekursive Simulationsfunktion | 2:56 |
| Akzeptieren der Eingabe | 5:48 |
| Vergleich mit der direkten Simulation | 6:53 |
| Vorteil | 7:31 |
| Systematische Reihenfolge der Teilprobleme? | 8:27 |
| Merken der Ergebnisse | 8:56 |
| Unendliche Rekursion | 10:27 |
| Unendliche Schleife im Kellerautomaten | 11:15 |
| Statusabfrage zu Beginn | 12:44 |
| Statusänderung am Ende | 13:40 |
| lineare Laufzeit | 13:50 |
| Zählen der Aufrufe | 14:31 |
| Zusammenfassung und Rückblick | 16:06 |
| Videoinhalt | |
|---|---|
| Das 15-Spiel | 0:00 |
| Herkunft | 1:30 |
| Paritätsargument | 2:13 |
| Modellierung als Graphenproblem | 3:36 |
| Nachbarschaft | 4:04 |
| Anzahl der Knoten | 4:25 |
| durschnittlicher Grad = 3 | 4:44 |
| Anzahl der Kanten | 6:02 |
| kürzeste Lösung | 6:55 |
| Breitensuche | 7:44 |
| kompakter Code einer Stellung | 8:22 |
| Bestimmen der möglichen Züge | 10:29 |
| Abstand zum Ziel | 11:22 |
| Einteilung in Schichten | 11:41 |
| Berechnung des Zielabstands | 14:15 |
| gerader Abstand | 15:34 |
| Vereinfachung zur Speicherersparnis | 16:36 |
| bipartiter Stellungsgraph | 17:30 |
| Löschen unnötiger Listen | 18:35 |
| leichtere Startpositionen | 19:40 |
| Größen der Schichten | 21:58 |
| Vermeidung von Umkehrzügen | 24:06 |
| bidirektionale Suche | 24:38 |
| Videoinhalt | |
|---|---|
| Algorithmus von Dijkstra | 0:00 |
| besser als lineare Laufzeit | 0:27 |
| besuchte Knoten | 0:47 |
| Veranschaulichung auf der Karte | 1:25 |
| Abstand zum Ziel | 3:48 |
| mehrere kürzeste Wege | 5:34 |
| Quiz | 6:12 |
| Schätzung des Abstands zum Ziel | 6:26 |
| heuristische Funktion | 6:43 |
| Beispiel: Luftlinie | 6:55 |
| Korrekturfaktor | 7:51 |
| Algorithmus A* | 8:57 |
| Name des Algorithmus | 9:17 |
| A*-Platz | 9:42 |
| Veranschaulichung auf der Karte | 10:08 |
| schematische Visualisierung | 11:15 |
| Qualität der heuristischen Funktion | 11:35 |
| Algorithmus von Dijkstra: | 12:04 |
| Knotenauswahlregel | 12:10 |
| Knotenauswahl bei A* | 12:50 |
| wiederholte Behandlung von Knoten | 13:07 |
| exponentielle Laufzeit | 14:26 |
| kein korrektes Ergebnis | 15:32 |
| Videoinhalt | |
|---|---|
| Eigenschaften einer heuristischen Funktion | 0:00 |
| zulässige heuristische Funktion | 0:09 |
| konsistente heuristische Funktion | 0:27 |
| Konsistenz impliziert Zulässigkeit | 1:21 |
| Addition einer Konstanten zu h | 1:45 |
| Optimalitätsgarantie für zulässiges h | 2:11 |
| Zusammenfassung | 3:37 |
| modifizierte Kantenkosten | 4:03 |
| modifizierte Kosten eines Weges | 4:43 |
| Teleskopsumme | 6:10 |
| kürzester Weg bleibt unverändert | 7:22 |
| nichtnegative modifizierte Kosten | 8:24 |
| Reduktion auf Dijkstras Algorithmus | 9:42 |
| andere Konsequenzen | 11:58 |
| negative modifizierte Kosten | 13:14 |
| Videoinhalt | |
|---|---|
| Anwendung auf das 15-Spiel | 0:00 |
| explizite und implizite Graphen | 0:10 |
| heuristische Funktion | 0:59 |
| modifizierte Kosten | 3:38 |
| Schichten statt Prioritätswarteschlange | 3:47 |
| Ändern einer Liste, die gerade durchlaufen wird | 7:17 |
| Quiz | 8:47 |
| Qualität der heuristischen Funktion | 12:14 |
| Videoinhalt | |
|---|---|
| Längste aufsteigende Teilfolge | 0:00 |
| Anwendung: Entfernen von Ausreißern | 1:08 |
| Problemdefinition | 1:59 |
| Aufzählen aller Möglichkeiten | 2:43 |
| Greedy-Algorithmus | 3:13 |
| Dynamische Programmierung | 3:57 |
| Definition der Teilprobleme | 4:00 |
| Rekursion | 5:01 |
| Definition der Teilprobleme | 7:31 |
| Rekursion | 7:47 |
| Lösung des Ausgangsproblems | 10:55 |
| Laufzeit und Speicherbedarf | 12:04 |
| Zurückverfolgen der Lösungen | 12:34 |
| Videoinhalt | |
|---|---|
| Abfrage aus den gelösten Teilproblemen | 0:00 |
| Maximum über einem Bereich | 0:38 |
| Bereichsabfragen | 1:33 |
| Aufrechterhalten bei Rotationen | 3:35 |
| Einfügen und Löschen | 4:02 |
| Beantwortung der Abfrage | 4:25 |
| gleiche Schlüssel | 7:42 |
| Quiz | 8:05 |
| Videoinhalt | |
|---|---|
| Unterproblem | 0:00 |
| geometrische Darstellung | 0:38 |
| dominierte Punkte | 1:48 |
| Definition der Dominanz | 2:34 |
| nichtdominierte Punkte | 3:48 |
| Eingeschränkter Wertebereich 1,...,n | 3:59 |
| Umkehrung der Fragestellung | 4:36 |
| Abfragefunktion f(S) | 5:52 |
| stückweise konstante Funktion | 6:07 |
| Neue Formulierung des Algorithmus | 6:43 |
| Ausbessern der Funktion f(S) | 7:36 |
| Umkehrfunktion | 8:22 |
| Auswertung von f(S) | 9:51 |
| Ausbessern von f | 10:58 |
| Zusammenfassung | 12:49 |
| Videoinhalt | |
|---|---|
| Nonogramme | 0:00 |
| Beispiel einer Reihe | 1:23 |
| lokale Schlüsse | 2:30 |
| Betrachten einer Reihe | 5:13 |
| Fortschritt | 5:39 |
| 0-1-Muster | 6:23 |
| Problem A: Zusammenpassen | 8:09 |
| Problem B: Festlegen unbekannter Kästchen | 8:36 |
| Vereinfachung der Notation | 9:33 |
| dynamische Programmierung | 10:06 |
| Definition der Teilprobleme | 10:32 |
| Rekursion | 11:13 |
| Anfangs- und Randbedingungen | 13:46 |
| Laufzeit und Speicher | 14:38 |
| Systematische Reihenfolge | 14:50 |
| Videoinhalt | |
|---|---|
| Fortschrittsberechnung | 0:00 |
| Erweiterbarkeit | 1:07 |
| Zurückrechnen von der Gesamtlösung | 2:37 |
| mögliche Symbole an einer Position | 4:42 |
| Fortschritt: Festlegen eines ?-Symbols | 5:47 |
| Videoinhalt | |
|---|---|
| Randomisierte Algorithmen: Überblick | 0:00 |
| Quicksort | 0:25 |
| Der Zufall als Freund | 1:11 |
| deterministische Alternativen | 1:47 |
| Quickselect | 1:59 |
| Hashtabellen | 2:27 |
| Kuckuckshashing | 3:04 |
| Fingerabdrücke nach Rabin und Karp | 3:24 |
| Skiplisten | 3:51 |
| Ausblick | 4:29 |
| Primzahltest | 4:44 |
| Fehlerwahrscheinlichkeit | 5:41 |
| Videoinhalt | |
|---|---|
| Rettung der Geschenke | 0:00 |
| Wie der Grintsch Weihnachten gestohlen hat | 2:09 |
| Verfolgungsprobleme | 2:34 |
| Greedy-Strategien | 3:43 |
| kritischer Kreis | 6:15 |
| Videoinhalt | |
|---|---|
| Schwierigkeit mit gleichzeitigen Zügen | 0:00 |
| abwechselnde Züge | 0:40 |
| Vergleich mit dem ursprünglichen Problem | 1:35 |
| Wer beginnt? | 1:49 |
| Spielende | 1:58 |
| Vorteil für den Grintsch | 2:34 |
| dynamische Programmierung | 4:34 |
| Randbedingungen | 6:20 |
| Quiz | 7:00 |
| Rekursion | 7:26 |
| Gleichungssystem | 9:15 |
| Ausnützen der Symmetrie | 10:37 |
| Elimination eines Parameters | 11:10 |
| Winkelschranke für den Grintsch | 11:49 |
| Rekursion für die normalisierten Größen | 12:37 |
| Videoinhalt | |
|---|---|
| Diskretisierung im Raum | 0:00 |
| Kreisgitter | 0:37 |
| endliches Gleichungssystem | 2:43 |
| Zeitdiskretisierung | 3:37 |
| Parametrisierung in Polarkoordinaten | 4:09 |
| diskretisiertes Gleichungssystem | 5:55 |
| Randbedingungen | 7:31 |
| Existenz einer Lösung | 9:03 |
| Eindeutigkeit | 10:08 |
| unendliches Spiel | 12:08 |
| Iterationsgleichung | 12:58 |
| Videoinhalt | |
|---|---|
| Daten des Gitters | 0:00 |
| Daten des Problems | 1:06 |
| Iteration | 1:59 |
| Minimum über einem Bereich | 3:36 |
| Optimieren über den Kreis | 4:59 |
| Abstandsfunktion | 8:36 |
| zu große Zeitschritte | 9:21 |
| Verfeinerung des Gitters | 10:30 |
| Grafik der Werte mit matplotlib | 13:08 |
| Videoinhalt | |
|---|---|
| 2-Personen-Spiel | 0:00 |
| Kreise im Spielgraphen | 1:09 |
| montone Iteration | 3:19 |
| Konvergenz | 5:01 |
| Stabilisierung | 5:20 |
| Beziehung zum ursprünglichen Spiel in der Ebene | 5:57 |
| Strategie | 8:31 |
| viele gute Züge | 9:53 |
| Videoinhalt | |
|---|---|
| Spieldauer als sekundäres Kriterium | 0:00 |
| lexikographischer Vergleich | 2:18 |
| Lösungsweg | 5:03 |
| Die Lösung verfolgen | 5:55 |
| Lösungsweg in normalisierter Darstellung | 7:48 |
| Normalisierung rückgängig machen | 9:31 |
| Quiz | 11:56 |
| Videoinhalt | |
|---|---|
| Punkte nach den Zügen des Grintsches | 0:00 |
| Bewegung des Grintsches | 0:47 |
| merkwürdiges Verhalten | 4:42 |
| Überlappung der Grintschbewegung | 5:37 |
| Entzerrung der Bewegung | 5:52 |
| unerklärliches Verhalten | 8:16 |
| Videoinhalt | |
|---|---|
| merkwürdiges Verhalten | 0:00 |
| Beschleunigung des Programms | 0:09 |
| Monotonie der Werte auf den Kreisen | 1:07 |
| Symmetrie | 2:46 |
| schnelle Programmversionen | 3:00 |
| optimale Lösung | 4:06 |
| Erreichen der Ausgangslage | 10:50 |
| Begründung | 12:59 |
| Peripheriewinkelsatz | 14:35 |
| Unbestimmtheit der Richtung | 15:10 |
| Spieldauer | 16:36 |
| Herkunft der Aufgabe | 18:21 |
| Videoinhalt | |
|---|---|
| Monotonie | 0:00 |
| Symmetrie | 0:45 |
| Funktionen auf einem ebenen Bereich | 1:28 |
| Iterationsvorschrift | 1:44 |
| vollständige Induktion | 1:56 |
| Induktionsbasis | 3:01 |
| Induktionsschritt für optG | 3:25 |
| Induktionsschritt für optW | 5:26 |
| Maximum aus mehreren Intervallmaxima | 7:17 |
| Monotonie bezüglich der lexikographischen Ordnung | 8:18 |
| beschleunigte Bestimmung des Minimums und Maximums | 9:28 |
| Videoinhalt | |
|---|---|
| Fallstudien | 0:00 |
| Diskrete Ereignissimulation | 0:36 |
| Simulation | 0:51 |
| Beispiel: Supermarkt | 1:50 |
| Ereignisse | 2:57 |
| zufällige Schwankungen | 3:44 |
| Auslösen neuer Ereignisse | 4:26 |
| externe Ereignisse | 5:01 |
| Steuerung | 5:15 |
| Wahrscheinlichkeitsverteilungen | 5:35 |
| Poissonverteilung | 5:59 |
| exponentialverteilte Wartezeit | 6:26 |
| Ereigniswarteschlange | 6:49 |
| Simulationsalgorithmus | 7:20 |
| Statistiken als Simulationsergebnisse | 8:23 |
| Entscheidungsunterstützung | 8:46 |
| DISKRETE Simulation | 9:02 |
| Algorithmus von Dijkstra | 9:37 |
| Programmieraufgaben | 10:13 |
| Objektorientierung: Programmiersprache Simula | 11:10 |
| Videoinhalt | |
|---|---|
| Kraft-McMillan'sche Ungleichung | 0:00 |
| Satz von McMillan | 0:26 |
| Beispiel | 0:39 |
| Nachrichten der Länge k | 1:56 |
| Rekursion | 2:52 |
| Beweis durch Widerspruch | 4:22 |
| charakteristische Gleichung der Rekursion | 5:16 |
| Korrektur der Notation | 6:47 |
| vollständige Induktion | 7:31 |
| Induktionsbasis | 8:33 |
| Längen, die nicht vorkommen | 9:15 |
| größter gemeinsamer Teiler | 9:23 |
| Füllsymbole | 11:02 |
| Induktionsbeweis | 13:06 |
| eindeutige Entzifferbarkeit | 13:50 |
| Induktionsbasis | 14:04 |
| Widerspruch | 14:36 |
| Videoinhalt | |
|---|---|
| dynamische Programmierung | 0:00 |
| optimale "Stadt" | 0:23 |
| Manhattan-Abstand | 0:48 |
| Zielfunktion: Summe aller Abstände | 1:48 |
| kleine Beispiele | 2:26 |
| Trennung der Zielfunktion in x und y | 5:00 |
| Konvexität | 5:46 |
| Zeilen und Spalten | 7:01 |
| Axiale (Fast-)Symmetrie | 7:24 |
| Ordnung der Spalten nach Länge | 10:43 |
| Videoinhalt | |
|---|---|
| Definition der Teilprobleme | 0:00 |
| Illustration | 1:14 |
| enthaltenes Rechteck | 2:05 |
| obere und untere Kappen | 2:24 |
| spaltenweiser Aufbau der Lösung | 3:03 |
| Abstände zu den Punkten im Rechteck | 3:59 |
| Abstände zu den Punkten in den Kappen | 4:33 |
| zusätzliche Parameter | 7:59 |
| Definition der Teilprobleme | 8:33 |
| Videoinhalt | |
|---|---|
| Vorwärtsrechnung als Variante der dynamischen Programmierung | 0:00 |
| Rückwärtsmodus | 0:16 |
| Vorwärtsmodus | 0:58 |
| Zusammenhang zu kürzesten Wegen | 1:32 |
| Verarbeitung eines Teilproblems im Vorwärtsmodus | 2:46 |
| Programm | 4:20 |
| zweistufiges Wörterbuch | 4:41 |
| Lösung einer Stadt | 5:42 |
| Kostenberechnung | 5:56 |
| Vorwärtsiteration im Programm | 7:06 |
| Verkleinern von c | 7:50 |
| Laufzeit und Speicher | 9:35 |
| Bestimmung der Lösungen | 11:10 |
| Erweiterung auf verbotene Punkte | 11:30 |