KIT | KIT-Bibliothek | Impressum | Datenschutz

30: Algorithmen II, Vorlesung, WS 2018/19, 05.02.2019

Hespe, Demian ORCID iD icon; Lamm, Sebastian ORCID iD icon; KIT | Webcast [Hrsg.]

  • 0:00:00 Start
  • 0:00:20 Schrumpfgraph
  • 0:02:39 Approximationsalgorithmen
  • 0:03:29 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen
  • 0:03:57 Viele kleine Jobs
  • 0:04:52 Untere Schranken
  • 0:05:10 Der Approximationsfaktor
  • 0:07:17 Diese Schranke ist bestmöglich
  • 0:07:49 Mehr zu Scheduling
  • 0:07:58 Nichtapproximierbarkeit des Handlungsreisendenproblems
  • 0:08:33 Hamilton Cycle
  • 0:10:07 TSP mit Dreiecksungleichung
  • 0:10:38 2-Approximstion durch minimalen Spannbaum
  • 0:11:16 Pseudopolynomielle Algorithmen
  • 0:12:26 Fully Polynomial Time Approximation Scheme
  • 0:13:31 Fixed Parameter Algorithmen
  • 0:14:49 VERTEX Cover
  • 0:15:05 Fixed parameter tractable
  • 0:16:32 Naive tiefenbeschränkte Suche
  • 0:19:19 Kernbildung für Vertex Cover
  • 0:21:45 Warum Parallelverarbeitung
  • 0:22:58 Modell Nachrichtengekoppelte Parallelrechner
  • 0:23:30 Kostenmodell für Nachrichtenaustausch
  • 0:24:56 Warum kein Multicore-Modell?
  • 0:26:18 Analyse paralleler Algorithmen
  • 0:26:49 Pseudocode
  • 0:27:41 Weniger ist mehr
  • 0:28:10 Hyperwürfel
  • 0:28:56 Hyperwürfelaulgorithmus
  • 0:31:31 Paralleles Quicksort
  • 0:32:00 Theoretiker-Parallelisierung
  • 0:34:01 Onlinealgorithmen
  • 0:34:29 Competitive analysis
  • 0:35:19 A typical online problem: Ski rental
  • 0:36:32 Paging
  • 0:37:48 Comparison of algorithms
  • 0:39:57 Discussion
  • 0:42:00 Stringology
  • 0:43:29 Strings Sortieren
  • 0:47:55 Naives Pattern Matching
  • 0:48:29 Knuth-Morris-Pratt
  • 0:50:27 Volltextsuche von Langsam bis Superschnell
  • 0:51:18 Invertierter Index
  • 0:52:13 Etwas ""Stringology""-Notation
  • 0:53:14 Suffixe Sortieren
  • 0:53:56 Volltextsuche
  • 0:54:45 Suffix-Baum
  • 0:56:22 SA mit Präfix Verdopplung
  • 0:58:05 Ein erster Teile-und-Herrsche-Ansatz
  • 0:58:52 SA berechnen
  • 1:00:42 Rekursion
  • 1:03:52 LCP-Array
  • 1:07:13 Datenkompression
  • 1:08:51 Wörterbasierte Textkompression
  • 1:09:59 Lempel-Ziv Kompression
  • 1:11:29 Burrows Wheeler Transformation
  • 1:14:47 Geometrische Algorithmen
  • 1:15:37 Plane-Sweep-Algorithmen
  • 1:18:08 Verallgemeinerung
  • 1:21:33 Mehr Linienschnitt
  • 1:22:51 Kleine einschließende Kugel

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 07.02.2019
Erstellungsdatum 05.02.2019
Sprache Deutsch
DOI 10.5445/DIVA/2019-133
Identifikator KITopen-ID: 1000116320
Lizenz KITopen-Lizenz
Serie Algorithmen II, Vorlesung, WS 2018/19
Folge 30
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page