Algorithmen 2, Vorlesung, WS17/18

26 |

0:00:00 Starten

0:00:09 Seminar: Proofs from the book

0:04:48 Theses 2018: External, Parallel, and Distributed Sorting

0:11:12 Graph Generators

0:17:23 High Quality Hypergraph Partitioning

0:23:59 Kernbildung in der Praxis

0:38:53 Start Vorlesung

0:40:33 Randomisierte Algorithmen

0:43:44 Approximationsalgorithmen

0:49:41 Online Algorithmen

24 |

0:00:00 Starten

0:00:09 highest level preflow push

0:06:51 Example

0:13:50 Proof of Lemma 12

0:17:30 Claims

0:28:47 Heuristic Improvements

0:33:32 Experimental results

0:33:39 Timings: Random Graphs

0:36:16 Timings

0:36:40 Asymptotics

0:36:43 Zusammenfassung Flows und Matchings

0:49:53 Sortieren durch Mehrwege-Mischen

0:50:00 Das Sekundärspeichermodell

0:51:59 Externe Stapel

1:08:30 Externes (binäres) Mischen

1:08:56 Run Formation

1:10:11 Sortieren durch Externes Binäres Mischen

1:12:01 Zahlenbeispiel

1:14:11 Mehrwegmischen

1:20:53 Mehr zu externem Sortieren

1:21:31 Externe Prioritätslisten

1:21:57 Minimale Spannbäume

1:23:36 Externe MST-Berechnung

1:24:14 Beispiel, Sibeyn's algorithm

1:24:19 Mehr zu externen Algorithmen - Basic Toolbox

25 |

0:00:00 Starten

0:00:15 Highest Level Preflow Push

0:00:55 Claims

0:01:07 Proof of Lemma 12

0:02:32 Claims

0:12:13 Anfang der Übung

0:12:27 Themenübersicht

0:13:08 Preflow-push Algorithmus

0:20:44 FIFO preflow-push Algorithmus

0:42:37 Matching

0:44:31 Bipartite-Matching

0:46:40 Speichermodell

0:48:26 Latenzen

0:49:47 I/O-efffizientes Design

0:51:12 Blockgrößen

0:55:33 Externes Sortieren

1:02:00 Strings Sortieren

1:02:56 Stringology (Zeichenkettenalgorithmen)

1:05:15 Suche in Suffix Arrays

1:05:21 LCP-Array: Berechnung

1:06:18 Datenkompression

1:06:23 Verlustfreie Textkompression

1:06:34 Lempel-Ziv Kompression (LZ)

1:07:33 Range minimum queries (RMQs)

1:07:44 Overview

1:09:43 Burrows-Wheeler-Transformation

1:10:36 Wavelet Tree Example: Calculate Rank

1:12:39 O(n) space /constant query time

1:13:19 Typische Fragenstellungen

1:14:28 Datenstrukturen für Punktmengen

1:14:40 Plane-Sweep-Algorithmen

1:15:57 Konvexe Hülle

1:16:04 Kleinste einschließende Kugel

1:16:37 2D Bereichssuche

1:16:48 Reduktion

1:17:10 Wavelet Tree Dominance Counting Query

1:18:08 Orthogonal range searching

1:18:44 Adressierbare Prioritätslisten

1:18:56 Grundlegende Datenstrukturen

1:19:27 Pairing Heaps

1:19:52 Binomialbäume

1:20:13 Kaskadierende Schnitte

1:20:27 Fortgeschrittene Graphenalgorithmen

1:20:42 Allgemeine Definition

1:21:25 Monotone ganzzahlige Prioritätslisten

1:21:59 Bucket-Queue

1:22:20 Operationen

1:23:25 All-Pairs Shortest Paths

1:23:49 Knotenpotentiale

1:24:23 Ideen für Routenplanung

1:24:42 Distanz zu einem Zielknoten t

1:25:15 Starke Zusammenhangskomponenten

1:26:52 Maximum Flows and Matchings

23 |

0:00:00 Starten

0:07:03 Flüsse und Ford Fulkerson

0:08:39 Max Flow - Min Cut

0:12:42 Dinitz: Distanz Label

0:14:37 Dinitz: Schichtgraph

0:15:45 Dinitz: Blockierender Fluss

0:17:21 Dinitz: Blockierender Fluss Operationen

0:20:36 Dinitz: Kosten pro Blockierender Fluss

0:24:14 Dinitz: Laufzeit

0:25:37 Dinitz: Kosten pro Phase, Unit Capacity Network

0:30:24 Maximum Cardinality Bipartite Matching

0:31:35 Preflow-Push Algorithms

0:34:00 Level Function

0:36:49 Procedure genericPreflowPush

1:21:53 Searching for Eligible Edges

1:23:50 Satz 11. Arbitrary Preflow Push finds a maximum flow in time O (n²m)

22 |

0:00:00 Starten

0:00:09 Algorithms 1956-now

0:00:47 Residual Graph

0:02:25 A Bad Example for Ford Fulkerson

0:03:19 Blocking Flows

0:04:57 Dinitz Algorithm

0:06:11 Blocking Flows Analysis

0:07:39 Dinitz Analysis

0:17:14 Matching

0:20:28 Maximum Cardinality Bipartite Matching

0:23:44 Disadvantage of augmenting paths algorithms

0:45:52 Übung 11

0:46:25 Kürzeste-Wege-Suche

0:48:11 Suche in Graphen

0:51:22 Dijikstras Algorithmus

0:53:19 Bidirectionale Suche

1:00:03 A*-Suche

21 |

0:00:00 Starten

0:00:18 Maximum Flows and Matchings

0:00:37 Definitions: Network

0:02:23 Flows

0:06:45 Applications

0:07:19 Applications in our Group

0:14:39 Option 1: linear programming

0:16:09 Algorithms 1956-now

0:19:49 Example

0:24:55 Residual Graph

0:31:33 Ford Fulkerson Algorithm

0:43:36 Übung

0:44:35 SCC

0:55:06 Floyd Warshall: SCC als Speedup Technik

0 |

0:00:00 Starten

0:00:18 Anwendungen von DFS

0:05:13 Tiefensuchschema für G= (V,E)

0:09:29 Starke Zusammenhangskomponenten

0:12:53 SCCs generischer Algorithmus

0:20:12 Ziel: Effizienter Algorithmus

0:27:20 Invarianten

0:39:53 Invarianten von Gc

0:53:47 traverseNonTreeEdge(v,w)

0:56:47 Backtrack(u, v)

1:01:52 Beispiel

1:11:28 Zusammenfassung: SCC Berechnung

1:14:09 Mehr DFS-basierte Linearzeitalgorithmen

19 |

0:00:00 Starten

0:00:09 Erinnerung

0:21:19 Radix-Heaps

0:35:25 Radix-Heap-Invariante

0:40:45 Radix Heap: deleteMin

0:45:28 Kosten der deleteMin-Operationen

1:07:04 all-pair-shortest-path (APSP)

1:23:03 Definition der Potentiale

18 |

0:00:00 Starten

0:00:09 Fortgeschrittene Graphenalgorithmen

0:04:34 Allgemeine Definition

0:06:17 Kante relaxieren

0:07:11 Dijkstra's Agorithmus

0:08:40 Beispiel

0:09:00 Laufzeit

0:14:55 Lineare Laufzeit für dichte Graphen

0:26:30 Präfixminima einer Zufallsfolge

0:27:32 Monotone ganzzahlige Prioritätslisten

0:31:28 Bucket-Queue

0:34:22 Operation

0:35:17 Laufzeit Dijkstra mit Bucket-Queues

0:36:35 Übung8

0:36:41 Amortisierte Analyse

0:39:57 Legende

0:41:59 Fibonacci Heaps - Insert

0:44:09 Fibonacci Heaps - Delete Min

0:56:33 Fibonacci Heaps - Decrease Key

1:02:11 Fibonacci Heaps

17 |

0:00:00 Starten

0:00:46 Aufgabenvarianten

0:01:16 Verteilte Eigenschaften

0:01:30 Theoretiker-Quicksort

0:06:08 Fortgeschrittene Datenstrukturen

0:10:27 Adressierbare Prioritätslisten

0:34:55 Adressierbare Prioritätslisten: Anwendungen

0:38:27 Grundlegende Datenstruktur

0:39:29 Wälder bearbeiten

0:40:59 Pairing Heaps (Paarungs-Haufen??)

0:46:39 Pairing Heaps - Repräsentationen

0:48:35 Pairing Heaps - Analyse

0:49:51 Fibonacci Heaps

0:53:27 Repräsentation

0:54:09 deleteMin mit Union-by-Rank

0:55:46 Schnelles Union-by-Rank

0:59:15 Amortisierte Analyse von deleteMin

1:03:06 Warum ist maxRank logarithmisch? - Binomialbäume

1:07:19 Kaskadierende Schnitte

1:13:30 Auftritt Herr Fibonacci

1:18:39 Beweis

1:23:23 Addressable Priority Queues: Mehr

1:25:24 Zusammenfassung: Datenstrukturen