KIT | KIT-Bibliothek | Impressum | Datenschutz

16: Algorithmen II, Vorlesung und Übung, WS 2018/19, 04.12.2018

Sanders, Peter; Lamm, Sebastian; Maier, Tobias; KIT | Webcast [Hrsg.]

  • 0:00:00 Start
  • 0:00:57 Naive tiefenbeschränkte Suche
  • 0:01:20 Naive tiefenbeschränkte Suche - Laufzeit
  • 0:02:29 Kernbildung für Vertex Cover
  • 0:03:01 Kernbildung für Vertex Cover - Korrektheit
  • 0:03:47 Kernbildung für Vertex Cover - Laufzeit
  • 0:05:05 Kernbildung für Vertex Cover - Beispiel
  • 0:07:02 Reduktionsregeln
  • 0:09:36 Verbesserte tiefenbeschränkte Suche
  • 0:14:06 Weitere Verbesserungen
  • 0:15:52 Zusammenfassung
  • 0:19:41 Parallele Algorithmen
  • 0:20:21 Warum Parallelverarbeitung
  • 0:28:49 Modell - Nachrichtengekoppelte Parallelrechner
  • 0:30:07 Kostenmodell für Nachrichtenaustausch
  • 0:34:05 Warum kein Multicore Modell
  • 0:36:37 Formulierung paralleler Algorithmen
  • 0:39:53 Analyse paralleler Algorithmen
  • 0:40:16 Dynamic Space Efficient Hashing
  • 0:41:01 Basics - Hash Tables
  • 0:42:18 Classic Space Efficient Hashing
  • 0:43:20 Final Size Not Known A Priori
  • 0:45:18 Resizing
  • 0:47:07 Secondary Contribution - Efficient Growing
  • 0:50:47 Multi Table Approach
  • 0:52:08 Cuckoo Displacement
  • 0:53:14 Cintribution - Dynamic Space Efficient Cuckoo Table
  • 0:55:51 Result - Insertion into Growing Table
  • 0:56:28 Result - Word Count Benchmark
  • 0:57:03 Result - Load Bound
  • 0:57:40 Conclusion
  • 0:59:30 Übung
  • 0:59:59 Approximtionsalgorithmen


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 06.12.2018
Erstellungsdatum 04.12.2018
DOI 10.5445/DIVA/2018-943
Identifikator KITopen-ID: 1000116126
Serie Algorithmen II, Vorlesung, WS 2018/19
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page