KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Gog, Simon; Hespe, Demian; 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
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 06.02.2018
Erstellungsdatum 05.02.2018
DOI 10.5445/DIVA/2018-156
Identifikator KITopen-ID: 1000115371
Serie 25
Serie Algorithmen 2, Vorlesung, WS 2017/18
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page