KIT | KIT-Bibliothek | Impressum | Datenschutz

02: Algorithmen 2, Vorlesung, WS 2017/18, 23.10.2017

Worsch, Thomas; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:01:08 Erinnerung an W-Theorie
  • 0:02:22 Randomisierter Quicksort
  • 0:04:34 randQS: Anzahl Vergleiche
  • 0:11:40 randQS: Anzahl Vergleiche mit hoher Wkt.
  • 0:28:25 Chernoff-Schranken
  • 0:29:04 Einfache Schranken
  • 0:32:19 Chernoff-Schranken
  • 0:38:03 Chernoff-Schranken: Beweis von Teil 1
  • 0:44:26 Chernoff-Schranken: Verienfachungen
  • 0:45:47 Chernoff-Schranken: Korollare
  • 0:47:14 Auswertung von Und-Oder-Bäume
  • 0:51:13 Satz
  • 0:53:50 Beweis
  • 1:00:35 Zwischenüberlegung
  • 1:04:58 Algorithmus: randomisierte UOB-Auswertung
  • 1:07:20 Satz
  • 1:09:19 Beweis
  • 1:18:58 Satz

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 24.10.2017
Erstellungsdatum 23.10.2017
Sprache Deutsch
DOI 10.5445/DIVA/2017-542
Identifikator KITopen-ID: 1000114936
Lizenz KITopen-Lizenz
Serie Algorithmen 2, Vorlesung, WS 2017/18
Folge 2
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page