Algorithmen 2, WS2016/17, Vorlesung
By Karlsruher Institut für Technologie (KIT)
Um dir einen Audio-Podcast anzuhören, fahre mit der Maus über den Titel und klicke auf "Wiedergabe". Öffne iTunes, um Podcasts zu laden und zu abonnieren.
Beschreibung
Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt. Literaturhinweise: - K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox - K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie - R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows - M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications - G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press - R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006. Dozenten: Prof. Dr. Peter Sanders, Dr. Christian Schulz, Dr. Simon Gog, M.Sc. Michael Axtmann | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
| Name | Beschreibung | Erschienen | Preis | ||
|---|---|---|---|---|---|
| 1 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 07.02.2017, 26 | 26 | 0:00:00 Starten 0:01:13 Fortgeschrittene Graphenalgorithmen: 2 Kürzeste Wege 0:02:31 Monotone ganzzahlige Prioritätslisten 0:03:05 Radix-Heaps 0:04:38 All-Pairs Shortest Paths 0:06:18 3 Anwendungen von DFS 0:08:27 Algorithms 1956-now 0:11:39 Preflow-Push Algorithms 0:13:38 5 Externe Algorithmen 0:15:04 6 Fixed-Parameter-Algorithmen 0:16:16 Fixed parameter tractable 0:16:49 Beispiel: VERTEX COVER 0:17:46 Naive tiefenbeschränkte Suche 0:18:38 7 Parallele Algorithmen 0:18:41 Warum Parallelverarbeitung 0:19:30 Kostenmodell für Nachrichtenaustausch 0:20:12 7.2 Beispiel: Assoziative Operationen (=Reduktion) 0:21:17 7.3 Sortieren 0:21:59 8 Stringology (Zeichenkettenalgorithmen) 0:22:25 Knuth-Morris-Pratt (1977) 0:27:42 9 Geometrische Algorithmen 0:27:54 9.1 Streckenschnitt (line segment intersection) 0:28:42 Verallgemeinerung 0:29:38 9.3 Kleinste einschließende Kugel 0:30:08 9.4 2D Bereichssuche (range search) 0:32:55 10 Onlinealgorithmen 0:33:33 Competitive analysis | 16.2.2017 | Gratis | In iTunes ansehen |
| 2 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 31.01.2017, 25 | 25 | 0:00:00 Starten 0:00:24 Wavlet Tree 0:08:46 Allgemeine Reporting Query 0:09:02 Bitvektoren 0:15:34 Suffix Array 0:15:45 Backward Search 0:20:37 Wavelet Tree Example: Calculate Rank 0:24:21 Index size comparison 0:26:55 Beginn Übung 13 0:27:01 Themenübersicht 0:28:27 Geometrische Algorithmen 0:32:55 Geometrische Methoden 0:35:13 Sweep-Line 0:39:04 One-Dimensional Problem 0:39:26 Skyline 0:56:58 Linienschnitt 1:02:03 Punktorientierung | 3.2.2017 | Gratis | In iTunes ansehen |
| 3 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 25.01.2017, 24 | 24 | 0:00:00 Starten 0:00:14 Verallgemeinerung 0:10:21 Überlappungen finden 0:11:52 Platzverbrauch 0:12:45 Mehr Linienschnitt 0:13:34 9.2 2D Konvexe Hülle 0:17:35 Graham's Scan 0:23:22 3D Konvexe Hülle 0:25:05 9.3 Kleinste einschließende Kugel 0:31:29 Kleinste einschließende Kugel - Korrektheitm 0:35:57 Kleinste einschließende Kugel - Analyse 0:49:17 9.4 2D Bereichssuche 0:52:14 1D Bereichssuche 0:58:43 Reduktion auf 1...n x 1...n 1:01:19 Beispiel 1:02:05 Walvelet Tree | 2.2.2017 | Gratis | In iTunes ansehen |
| 4 | CleanVideoAlgorithmen II, Übung und Vorlesung, WS 2016/17, 24.01.2017, 23 | 23 | 0:00:00 Starten 0:00:07 Übung 12 - Online Algorithmen 0:02:44 Grundlagen 0:04:19 Gütemaß 0:05:21 Ski Rental Problem 0:06:46 Randomisierte Ski Rental Strategie 0:18:02 Doubling Strategie 0:18:52 Online Bidding 0:40:30 Zusammenfassung 0:41:39 Vorlesung: Kapitel 9 - Geometrische Algorithmen 0:45:17 Elementare Geometrische Objekte 0:49:22 Typische Fragestellungen 0:53:29 Verweissensitive Grafik (Wikipedia) 0:54:30 Datenstrukturen für Punktemengen 0:54:42 Mehr Fragestellungen 0:59:47 9.1 Streckenschnitt (line segment intersection) 1:01:02 Streckenschnitt: Anwendungen 1:01:44 Streckenschnitt: Naiver Algorithmus 1:02:18 Streckenschnitt: Untere Schranke 1:04:17 Idee: Plane-Sweep-Algorithmen 1:04:54 Plane-Sweep für orth. Streckenschnitt 1:10:02 Analyse orth. Streckenschnitt 1:12:03 Verallgemeinerung - aber erstmal ""nicht ganz"" 1:12:55 Verallgemeinerung - Grundidee 1:16:48 Verallgemeinerung - Korrektheit 1:17:46 Verallgemeinerung - Implementierung 1:23:05 Verallgemeinerung - Beispiel 1:24:05 Verallgemeinerung - Analyse | 2.2.2017 | Gratis | In iTunes ansehen |
| 5 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 18.01.2017, 22 | 22 | 0:00:00 Starten 0:00:42 13 Onlinealgorithmen 0:05:35 Examples 0:08:09 Competitive analysis 0:09:19 A typical online problem: ski rental 0:11:31 Upper bound for ski rental 0:14:33 Lower bound for ski rental 0:18:07 Paging 0:20:16 Definitions 0:21:49 Paging algorithms 0:25:11 Longest Forward Distance is optimal 0:27:34 Using the claim 0:29:01 Proof the claim 0:29:44 Comparison of algorithms 0:34:33 A general lower bound 0:38:53 Resource augmentation 0:40:14 Conservative algorithms 0:43:26 Competitive ratio 0:46:50 Counting the faults of OPT 0:47:32 Conclusion 0:48:30 Competitive analysis 0:49:57 Notes 0:51:02 New results 0:54:25 Randomized algorithms 0:55:38 Three types of adversaries 1:00:46 Markig Algorithm 1:04:28 Analysis of REMARk 1:06:21 Lower bound for OPT 1:07:42 Discussion 1:08:50 Why competitive analysis? 1:16:24 Disadvantages of competetive analysis | 20.1.2017 | Gratis | In iTunes ansehen |
| 6 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 11.01.2017, 21 | 21 | 0:00:00 Starten 0:00:07 Burrows-Wheeler-Transformation 0:12:23 Datenkompression 0:18:42 Verlustfreie Textkompression 0:30:39 Wörterbuchbasierte Textkompression 0:33:02 Lempel-Ziv Kompression 0:33:45 Naive Lempel-Ziv Kompression 0:43:15 Naive LZ Dekompression 0:45:08 LZ Beispiel 0:45:16 LZ-Verfeinerung 0:46:37 Begin Übung 11 0:48:29 Suche mit Suffix-Arrays (1) 0:56:41 LCP-Array 1:03:46 Schnelle Suche mit Suffix-Arrays 1:10:29 Suche mit Suffix-Arrays (2) | 19.1.2017 | Gratis | In iTunes ansehen |
| 7 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 10.01.2017, 20 | 20 | 0:00:00 Starten 0:00:07 Wiederholung: Asymmetrisches Divide-and-Conquer 0:03:50 Implementierung 0:06:04 Verallgemeinerung: Differenzenüberdeckungen 0:10:34 Verbesserungen / Verallgemeinerungen 0:11:23 Suffixtabellenkonstruktion: Zusammenfassung 0:12:00 Suche in Suffix Arrays 0:14:13 LCP-Array 0:15:56 Beispiel 0:32:42 LCP-Array: Berechnung 0:39:53 Suffix-Baum aus SA und LCP 0:41:20 Beispiel 0:53:45 Suche in Suffix-Bäumen 0:55:41 Datenkompression 0:55:55 Burrows-Wheeler-Transformation | 19.1.2017 | Gratis | In iTunes ansehen |
| 8 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 21.12.2016, 19 | 19 | 0:00:00 Starten 0:00:09 Wiederholung: Suffix Tree und Suffix Array 0:02:28 Kapitel 8 - Stringology (Zeichenkettenalgorithmen) 0:03:37 Etwas ""Stringology""-Notation 0:05:26 Suffixe Sortieren 0:05:59 Anwendungen 0:07:05 Volltextsuche 0:07:28 Suffix-Baum 0:08:33 Alphabet-Modell 0:09:24 Geordnetes --> ganzzahliges Alphabet 0:10:30 Verallgemeinerung: Lexikographische Namen 0:11:20 Ein erster Teile-und-Herrsche-Ansatz 0:15:17 SA1 berechnen 0:17:08 Berechne SA0 aus SA1 0:19:50 Asymmetrisches Divide-and-Conquer 0:23:22 Beispiel 0:50:06 Rekursion, Beispiel 0:50:41 Least Significant Digit First Radix Sort 0:51:11 Stabiles Ganzzahliges Sortieren 0:51:44 Analyse 0:53:31 Übung 10 0:53:36 Themenübersicht 0:53:44 Parametrisierte Algorithmen 1:02:24 in-place Multikey Quicksort 1:16:25 Beispiel | 12.1.2017 | Gratis | In iTunes ansehen |
| 9 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 20.12.2016, 18 | 18 | 0:00:00 Starten 0:00:07 Stringology (Zeichenkettenalgorithmen) 0:00:59 Top 10 query completion (Suchvolumina) 0:04:18 Weitere Anwendungen 0:10:19 Naives Pattern Matching 0:17:29 Besserer Algorithmus 0:27:53 Fallanalyse Palindrome 0:41:09 Berechnung der Verschiebetabelle 1:00:26 Multi Key Quicksort for Strings 1:11:00 Matching von k pattern gegen einen Text der Länge n 1:12:46 Suffix Tree und Suffix Array | 12.1.2017 | Gratis | In iTunes ansehen |
| 10 | CleanVideoAlgorithmen II, Übung, WS 2016/17, 14.12.2016, 17 | 17 | 0:00:00 Starten 0:00:07 Übung 9 – Algorithmen 2 0:00:27 Themenübersicht 0:02:21 Parallelverabeitung 0:06:11 PRAM 0:08:27 Verbindungsnetzwerke 0:14:26 Anwendungen 0:33:58 Parallele Programmierung 0:35:53 Übung 8 – Algorithmen 2 0:36:07 Anwendungen 0:38:33 Themenübersicht 0:40:20 Approximationsalgorithmen 1:06:46 Parametrisierte Algorithmen | 20.12.2016 | Gratis | In iTunes ansehen |
| 11 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 13.12.2016, 16 | 16 | 0:00:00 Starten 0:00:09 Wiederholung 0:11:01 9 Fixed-Parameter-Algorithmen 0:30:14 10 Parallele Algorithmen 0:35:16 10.1 Modell Nachrichtengekoppelte Parallelrechner 0:46:53 10.2 Beispiel: Assoziative Operationen (=Reduktion) 0:59:16 Präfixsummen 1:04:46 10.3 Sortieren | 20.12.2016 | Gratis | In iTunes ansehen |
| 12 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 07.12.2016, 15 | 15 | 0:00:00 Starten 0:00:09 Wiederholung: Job Scheduling 0:03:14 Wiederholung: List Scheduling 0:10:08 Wiederholung: TSP 0:13:43 Wiederholung: Metric TSP 0:19:21 Pseudopolynomielle Algorithmen 0:22:08 Rucksack Problem 0:25:21 Dynamic Programming 0:33:09 Fully Polynomial Time Approximation Scheme 0:34:50 Beispielschranken 0:36:22 FPTAS für Knapsack 0:47:18 Lemma 21 0:48:43 Das beste bekannte FPTAS 0:49:06 Optimale Algorithmen für das Rucksackproblem 0:49:37 9 Fixed-Parameter-Algorithmen 0:50:57 Beispiel: VERTEX COVER (Knotenüberdeckung) 0:52:56 Fixed parameter tractable 0:55:23 Beispiel: VERTEX COVER 0:57:02 Naive tiefenbeschränkte Suche 1:00:33 Fortsetzung Beispiel: VERTEX COVER 1:04:29 Kernbildung für Vertex Cover | 20.12.2016 | Gratis | In iTunes ansehen |
| 13 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 06.12.2016, 14 | 14 | 0:00:00 Starten 0:00:10 Wiederholung 0:09:49 8 Approximationsalgorithmen 0:12:39 Job Scheduling 0:26:47 Approximationsfaktor 0:38:22 Traveling Salesman Problem 0:51:22 Metric TSP 0:53:54 Euler-Tour/Kreis 0:59:01 Algorithmus | 13.12.2016 | Gratis | In iTunes ansehen |
| 14 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 29.11.2016, 12 | 12 | 0:00:00 Starten 0:01:10 Wiederholung 0:17:28 Randomisierter Algorithmus 0:33:34 Barabasi Albert Graph Generation 0:52:54 7 Externe Algorithmen 0:53:01 7.1 Das Sekundärspeichermodell 1:07:02 7.2 Externe Stabel 1:11:38 Run Formation 1:13:03 Sortieren durch Externes Binäres Mischen | 6.12.2016 | Gratis | In iTunes ansehen |
| 15 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 30.11.2016, 13 | 13 | 0:00:00 Starten 0:00:09 Wiederholung 0:10:06 Externe Algorithmen 0:13:21 7.2 Externe Stapel 0:15:56 Run Formation 0:16:33 Sortieren durch Externes Binäres Mischen 0:17:16 Zahlenbeispiel: PC 2010 0:18:01 Mehrwegmischen 0:22:06 Sortieren durch Mehrwege-Mischen 0:23:30 Mehr zu externem Sortieren 0:25:47 Mehrwegmischen – Analyse 0:26:16 Externe Prioritätsliste 0:27:28 Sequence Heaps 0:33:30 Analyse 0:35:03 Große Queues 0:35:47 Experiments 0:36:54 Minimale Spannbäume 0:38:04 Externe MST-Berechnung 0:38:43 Beispiel, Sibeyn's algorithm 0:38:51 Mehr zu externen Algorithmen – Basic Toolbox? 0:39:23 8 Parallele Algorithmen 0:40:28 Beginn Übung 5 Abschluss 0:40:32 FIFO preflow-pussh Algorithmus 0:40:59 preflow-pussh Algorithmus 0:56:35 Matching 0:59:17 Bipartite - Matching 1:04:22 Beginn Übung 6 1:05:38 Randomizierte Algorithmen 1:19:10 Matrix-Matrix Multiplikation | 6.12.2016 | Gratis | In iTunes ansehen |
| 16 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 23.11.2016, 11 | 11 | 0:00:00 Starten 0:01:51 Wiederholung 0:10:59 Example 0:23:53 Searching for Eligibla Edges 0:27:29 FIFO Preflow push 0:29:07 Highest Level Preflow Push 0:31:15 Proof of Lemma 13 0:33:26 Claims 0:44:27 Heuristic Improvements 0:47:01 Experimental results 0:50:36 Zusammenfassung Flows und Matchings 0:51:54 Übung 6 0:53:51 Potentialmethode 1:00:25 preflow-push Algorithmus 1:12:37 FIFO preflow-push Algorithmus | 1.12.2016 | Gratis | In iTunes ansehen |
| 17 | CleanVideoAlgorithmen II, Übung, WS 2016/17, 22.11.2016, 10 | 10 | 0:00:00 Starten 0:00:09 Wiederholung L8 0:15:30 Dinics Alogorithmus 0:32:19 Matching 0:34:41 Maximum Cardinality Bipartite Matching 0:35:37 Similar Performance for Weighted Graphs? 0:36:51 Disadvantage of augmenting paths algorithms 0:39:10 Preflow-Push Algorithmen 0:42:47 Procedure Push 0:49:32 Procedure genericPreflowPush | 1.12.2016 | Gratis | In iTunes ansehen |
| 18 | CleanVideoAlgorithmen II, Übung, WS 2016/17, 16.11.2016, 09 | 09 | 0:00:00 Starten 0:00:36 Themenübersicht 0:01:47 Nachklausur 0:02:16 Ford Fulkerson 0:02:20 Flüsse und Ford Fulkerson 0:07:45 Residualgraph 0:11:40 Flüsse und Ford Fulkerson 0:14:02 Max Flow - Min Cut 0:17:12 Dinitz Algorithmus 0:18:52 Dinitz - Distanz Label 0:22:38 Dinitz - Schichtgraph für Graph G = (V, E) 0:25:02 Dinitz - Blockierender Fluss 0:28:25 Dinitz - Blockierender Fluss: Operationen 0:33:25 Dinitz - Kosten pro Blockierender Fluss 0:38:12 Dinitz - Laufzeit 0:40:05 Dinitz - Kosten pro Phase - Unit Capacity Network 0:42:40 Dinitz - Anzahl Phasen - Unit Capacity Network 0:46:36 SCC (Widerholung) 1:03:07 Floyd Warshall: SCC als Speedup Technik 1:15:14 Floyd Warshall und SCC | 22.11.2016 | Gratis | In iTunes ansehen |
| 19 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 15.11.2016, 08 | 08 | 0:00:00 Starten 0:00:18 Wiederholung Starke Zusammenhangskomponenten 0:05:26 Wiederholung Tiefensuchschema 0:13:12 5 Maximum Flows and Matchings 0:14:57 Definitions: Network 0:16:04 Definitions: Flows 0:18:46 Definitions: (Minimum) s-t Cuts 0:20:12 Duality Between Flows and Cuts 0:21:21 Applications 0:22:11 Applications in our Group 0:22:34 Exkurs: Balanced Bipartitioning 0:27:24 Example 0:28:58 Option 1: linear programming 0:32:33 Algorithms 1956-now 0:34:00 Augmenting Paths (Rough Idea) 0:34:59 Example 0:35:49 Residual Graph 0:38:51 Augmenting Paths 0:39:40 Ford Fulkerson Algorithm 0:59:36 A Bad Example for Ford Fulkerson 1:00:35 An Even Worse Example for Ford Fulkerson 1:03:05 Dinitz Algorithmus 1:19:41 Example 1:20:38 Block Flows Analysis 1 1:22:59 Blocking Flows Analysis 2 1:23:23 Blocking Flows Analysis 3 1:23:49 Dinitz Analysis 1 1:24:09 Dinitz Analysis 2 | 22.11.2016 | Gratis | In iTunes ansehen |
| 20 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 09.11.2016, 07 | 07 | 0:00:00 Starten 0:00:57 1 Algorithm Engineering 0:05:04 (Caricatured) Traditional View: Algorithm Theory 0:07:43 Gaps Between Theory & Practice 0:12:14 Algorithmics as Algorithm Engineering 0:18:43 Bits of History 0:25:30 Realistic Models 0:28:11 Design 0:30:03 Analysis 0:31:05 Implementation 0:33:47 Experiments 0:37:14 Algorithm Libraries - Challenges 0:42:58 Problem Instances 0:43:45 Example: Sorting Benchmark (Indy) 0:45:41 GraySort 0:45:41 JouleSort 0:46:46 Applications tha ""Change the World"" 0:51:07 Conclusion: Algorithm Engineering Algorithm Theory 0:52:28 More On Experimental Methodology 0:53:24 Quality Criteria 0:58:20 Not Here but Important 1:00:47 The Starting Point 1:01:46 The Process 1:07:31 Of Risks and Opportunities 1:08:36 Übung 4 1:08:41 Themen 1:09:47 Starke Zusammenhangskomponenten 1:10:39 SCC (Wiederholung) | 21.11.2016 | Gratis | In iTunes ansehen |
| 21 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 08.11.2016, 06 | 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 Note / backtrack (u,v) | 21.11.2016 | Gratis | In iTunes ansehen |
| 22 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 02.11.2016, 05 | 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 – Landmarken | 10.11.2016 | Gratis | In iTunes ansehen |
| 23 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 26.10.2016, 04 | 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 für Routenplanung 0:38:22 Bidirektionale Suche 0:39:50 A-Suche 0:42:52 Benötige Eigenschaften von f(v) 0:44:59 Wie finden wir f(v)? 0:46:01 Landmarks 0:46:44 Zusammenfassung Kürzeste Wege 0:47:32 Übung: Inhalt 0:48:31 KaHIP: Implementierung einer BFS 0:56:22 Spezielle Priority Queues 0:58:25 Bucket Queues 1:02:36 Radix Heaps 1:24:08 Average case Analyse für MST | 10.11.2016 | Gratis | In iTunes ansehen |
| 24 | CleanVideoAlgorithmen II, Vorlesung und Übung, WS 2016/17, 19.10.2016, 02 | 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 Herr Fibonacci 0:46:52 Beweis 0:48:32 Addressable Priority Queues: Mehr 0:49:35 Zusammenfassung Datenstrukturen 0:50:40 Übung 1 – Algorithmen II 0:51:17 Organisatorisches – Übungsbetrieb 0:53:56 Amortisierte Analyse 0:56:46 Legende 0:58:19 Fibonacci Heaps – Insert 1:00:09 Fibonacci Heaps – Delete Min 1:21:35 Fibonacci Heaps – Decrease Key 1:30:15 Fibonacci Heaps | 3.11.2016 | Gratis | In iTunes ansehen |
| 25 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 25.10.2016, 03 | 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: deleteMin 1:10:57 Buckets j>i bei Änderungen von min 1:11:42 Bucket B(i) bei Änderung von min 1:13:16 Kosten der deleteMin-Operation 1:14:09 Laufzeit der Dijkstra mit Radix-Heaps 1:15:06 Lineare Laufzeit für zufällige Kantengewichte 1:17:04 Analyse | 3.11.2016 | Gratis | In iTunes ansehen |
| 26 | CleanVideoAlgorithmen II, Vorlesung, WS 2016/17, 18.10.2016, 01 | 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 Heaps – Analyse | 27.10.2016 | Gratis | In iTunes ansehen |
| 26 Artikel |
