Algorithmen 1, SS2019, Vorlesung

23 |

0:00:00 Start

0:00:13 Übung: Überblick

0:03:26 Dijkstras Algorithmus

0:07:19 Bellmann Ford Algorithmus

0:14:50 Minimale Spannbäume

0:20:31 Steinerbäume

0:27:20 Problem des Handlungsreisenden (TSP)

22 |

0:00:00 Start

0:00:23 Generische Optimierungsansätze

0:05:36 Rucksackproblem

0:09:28 Maximierungsprolem

0:12:42 Black-Box-Löser

0:17:38 Lineare Programmierung

0:24:53 Kürzeste Wege

0:29:29 Tierfutter

0:35:21 Algorithmen und Implementierungen

0:39:09 Ganzzahlige Lineare Programmierung

0:53:05 Greedy-Algorithmen

1:00:00 Dynamische Programmierung

1:17:32 Algorithmenentwurf mittels dynamischer Programmierung

1:23:01 Systematische Suche

21 |

0:00:00 Start

0:00:10 Rückblick

0:01:58 Heutige Vorlesung

0:03:31 Minimale Spannbäume

0:08:34 MST-Kanten auswählen und verwerfen

0:22:22 Jarnik-Prim-Algorithmus

0:37:10 Analyse - Jarnik-Prim-Algorithmus

0:38:04 Kruskals-Algorithmus

0:45:14 Kruskals Algorithmus - Korrektheit

0:49:51 Union-Find Datenstruktur

1:03:25 Pfadkompression

1:08:34 Union by Rank

1:10:11 Analyse - nur Union by Rank

1:11:33 Analyse - nur Pfadkompression

1:12:05 Analyse - Pfadkompression und Union by Rank

1:15:21 Ackermannfunktion - Beispiele

1:15:44 Kruskal mit Union-Find

1:21:09 Vergleich Jarnik-Prim vs. Kruskal

1:23:00 Mehr MST-Algorithmen

1:25:11 Zusammenfassung

20 |

0:00:00 Start

0:01:21 Kürzeste Wege: Definition

0:02:23 Dijkstras Algorithmus. Pseudocode

0:08:12 Dijkstra: negative Kantengewichte

0:17:02 Monotone ganzzahlige Prioritätslisten

0:19:49 Negative Zyklen

0:21:55 Zurück zu Basiskonzepten

0:26:31 Allgemeines Korrektheitskriterium

0:31:09 Bellman-Ford-Algorithmus

0:39:29 Beispiel

0:43:57 Bellman-Ford: Laufzeit

0:45:30 Azyklische Graphen

0:49:38 Von überall nach überall

0:52:15 Kürzeste Wege: Zusammenfassung

0:57:10 Exkurs: Routing in Straßennetzwerken

1:01:56 Ideen für Routenplanung

1:03:47 Ansatz: Transit-Node Routing

1:09:15 Zweite Beobachtung

1:17:04 Offene Fragen

1:18:36 Minimale Spannbäume (MST)

1:23:59 Minimal aufspannende Wälder (MSF)

19 |

0:00:00 Start

0:00:11 Rückblick: Kürzeste Wege

0:02:00 Dijkstras Algorithmus

0:02:54 Allgemeine Definition

0:07:38 Kante relaxieren

0:13:02 Dijkstras Algorithmus: Pseudocode

0:16:44 Beispiel

0:23:52 Korrektheit

0:37:29 Implementierung

0:40:10 Prioritätsliste

0:46:50 Beispiel

0:49:18 Dijkstra: Laufzeit

0:58:32 Analyse im Mittel

0:59:32 Monotone ganzzahlige Prioritätslisten

1:01:18 Negative Kosten

1:03:38 Zurück zu Basiskonzepten

1:06:34 Allgemeines Korrektheitskriterium

1:08:46 Bellman-Ford Algorithmus

18 |

0:00:00 Start

0:07:02 Graph-Traversierung

0:11:13 Breitensuche

0:13:13 Tiefensuche

0:21:56 DFS-Baum

0:28:14 DFS-Nummerierung

0:38:39 Topologische Sortierung

0:43:27 Topologisches Sortieren mittels DFS

0:55:01 Begriff Zusammenhang

1:02:26 BFS vs DFS

1:07:16 Kürzeste Wege : Definition

1:17:22 Dijkstras Algorithmus

17 |

0:00:00 Start

0:00:05 Rückblick und Überblick

0:01:35 Graphen

0:02:12 Repräsentation von Graphen

0:02:33 Kantenfolgenrepräsentation

0:03:31 Adjazenzfelder

0:05:59 Kantenliste -> Adjazenzfeld

0:07:29 Adjazenzlisten

0:13:10 Customization (Zuschneiden)

0:13:53 Beispiel: DAG-Erkennung

0:23:23 Adjazenz-Matrix

0:31:24 Pfade zählen mittels linearer Algebra (LA)

0:35:54 Beispiel, wo Graphentheorie bei LA hilft

0:38:56 Implizite Repräsentation

0:40:53 Zusammenhangstest für Intervallgraphen

0:43:46 Beispiel

0:45:13 Graphpräsentation: Zusammenfassung

0:52:00 Graph-Traversierung

0:58:59 Breitensuche

1:07:32 Repräsentation des Baums

1:16:41 Repräsentation von Q und Q' mittels FIFO

1:19:17 Tiefensuche

1:24:26 DFS-Baum

16 |

0:00:00 Start

0:00:11 Wiederholung

0:11:16 Locate

0:19:22 Einfügen-Algorithmenskizze

0:50:36 Zusammenfassung

0:53:43 Graphen

0:58:43 Graphen-Anwendung

1:05:15 Operationen

1:10:05 Kantenfolgenrepräsentation

1:13:28 Adjazenzfelder

15 |

0:00:00 Start

0:00:08 Übungsblatt 7, Pseudocode

0:02:49 4. Übung

0:02:52 Roadmap, Bucket Sort Spezial, Bucket Queue, Binary Radix Heap

0:03:14 Erinnerung: Bucketsort

0:06:46 Bucket Sort Spezial

0:13:55 Spezielle Priority Queues

0:14:55 Bucket Queue

0:17:40 Binary Radix Heap

0:22:52 Binary Radix Heap: deleteMin

0:24:06 Binary Radix Heap

0:25:54 Möglichkeit Ternärer Radix Heaps

14 |

0:00:00 Start

0:00:05 Rückblick und Überblick

0:02:06 Sortierte Folgen

0:07:56 Statisch: Sortiertes Feld mit binärer Suche

0:18:14 Dynamisch sortierte Folgen

0:26:49 Abgrenzung

0:32:27 Sortierte Folgen - Anwendungen

0:46:39 Binäre Baumsuche

0:52:08 locate (k)

1:00:15 Laufzeit von locate (k)

1:03:05 Naives Einfügen

1:08:07 Naives Einfügen - Beispiel

1:11:25 Suchbäume balancieren

1:16:25 Items

1:20:24 Initialisierung

1:22:27 Locate