25: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.02.2018

Autor

Simon Gog, Demian Hespe

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

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

Laufzeit (hh:mm:ss)

01:27:53

Serie

Algorithmen 2, Vorlesung, WS 2017/18

Publiziert am

06.02.2018

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz