25: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.02.2018
Gog, Simon; Hespe, Demian
; KIT | Webcast [Hrsg.]
; KIT | Webcast [Hrsg.]- 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
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 06.02.2018 |
| Erstellungsdatum | 05.02.2018 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2018-156 |
| Identifikator | KITopen-ID: 1000115371 |
| Lizenz | KITopen-Lizenz |
| Serie | Algorithmen 2, Vorlesung, WS 2017/18 |
| Folge | 25 |