Algorithmen 2, WS2016/17, Vorlesung

06 | 0:00:00 Starten 0:01:59 Wiederholung 0:15:02 4. Anwendungen von DFS 0:15:17 Tiefensuchschema für G=(V,E) 0:18:34 DFS Nummerierung 0:20:18 Fertigstellungszeit 0:21:05 Starke Zusammenhangskomponenten 0:29:31 Grobe Struktur 0:31:45 Nomenklatur 0:36:01 Invarianten/Eigenschaften 0:44:39 Repräsentation offener Komponenten 0:46:05 A: init 0:48:38 B: Neuer Root Knoten wird markiert 0:51:55 C: Traversierung einer Baumkante e= (v,w) 0:56:02 D: Traversiere Nicht-Baumkante e= (v,w) 1:05:34 E: finishing a

05 | 0:00:00 Starten 0:00:25 Wiederholung Lektion 4 0:14:10 Starke Zusammenhangskomponenten 0:27:12 Kreise mit Gewicht 0 0:48:01 Beginn Übung 3 0:48:03 Inhalt 0:48:16 Suche in Graphen: Kürzeste-Wege-Suche 0:49:37 Suche in Graphen: Übersicht über verschiedene Varianten 0:51:52 Suche in Graphen: Dijkstras Algorithmus 0:53:57 Suche in Graphen: Bidirektionale Suche 0:59:36 Suche in Graphen: A*-Suche 1:02:11 Suche in Graphen: A*-Suche – Potentialfunktionen 1:07:30 Suche in Graphen: A*-Suche –

04 | 0:00:00 Starten 0:00:10 Vorlesung: Fortgeschrittene Graphenalgorithmen, 3 Kürzeste Wege 0:01:16 Wiederholung 0:12:21 Definition msd (a,b) 0:13:08 Radix Heap: deleteMin 0:13:51 Bucket B(i) bei Änderung von min 0:15:01 All-Pairs Shortest Paths 0:16:15 Algorithmen Brutal – Belman-Ford-Algorithmus für beliebige Kantengewichte 0:18:32 Knotenpotenziale 0:25:00 Wie berechnen wir Potenziale? 0:31:44 Algorithmus 0:33:16 Laufzeit 0:34:36 Hilfsknoten 0:35:25 Distanz zu einem Zielknoten t 0:37:24 Ideen

02 | 0:00:00 Starten 0:00:10 2.1 Adressierbare Prioritätslisten 0:06:37 Grundlegende Datenstruktur 0:07:45 Wälder Bearbeiten 0:08:08 Pairing Heaps (Paarungs-Haufen??) 0:08:45 Pairing Heaps 0:11:21 Pairing Heaps – Repräsentation 0:11:55 Pairing Heaps – Analyse 0:13:30 Fibonacci Heaps (Fredmann Tarjan 1987) 0:15:45 Repräsentation 0:16:38 deleteMin mit Union-by-Rank 0:17:38 Schnelles Union-by-Rank 0:33:04 Warum ist maxRank logarithmisch? – Binomialbäume 0:36:03 Kaskadierende Schnitte 0:43:29 Auftritt

03 | 0:00:00 Starten 0:00:10 Übersicht 0:01:18 Wiederholung Lecture 2 0:11:18 Kürzeste Wege 0:12:55 Allgemeine Definition 0:14:45 Kante relaxieren 0:19:12 Pseudocode 0:20:31 Beispiel 0:46:31 Präfixminima einer Zufallsfolge 0:50:42 Lineare Laufzeit für dichte Graphen 0:52:37 Monotone ganzzahlige Prioritätslisten 0:56:54 Bucket-Queue 0:58:24 Operationen 1:00:42 Laufzeit Dijkstra mit Bucket-Queues 1:02:31 Radix-Heaps 1:05:03 Definition msd (a,b) 1:06:02 Radix-Heap-Invariante 1:08:22 Radix Heap:

01 |0:00:00 Starten 0:00:55 Inhaltsübersicht I 0:02:37 1 Algorithm Engineering 0:03:11 (Caricatured) Traditional View: Algorithm Theory 0:04:03 Algorithmics as Algorithm Engineering 0:09:06 2 Fortgeschrittene Datenstrukturen 0:10:23 2.1 Adressierbare Prioritätslisten 0:12:22 Adressierbare Prioritätslisten: Anwendungen 0:37:22 Grundlegende Datenstruktur 0:39:09 Wälder Bearbeiten 0:40:33 Pairing Heaps (Paarungs-Haufen??) 0:41:07 Pairing Heaps 0:47:10 Pairing Heaps – Repräsentation 0:49:03 Pairing