KIT | KIT-Bibliothek | Impressum | Datenschutz

09: Algorithmen 2, Vorlesung, WS 2017/18, 20.11.2017

Gog, Simon; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:18 Range minimum queries (RMQs)
  • 0:00:43 Overview
  • 0:01:05 O(n), Olog(n)-solution 1
  • 0:01:18 O(nlogn), O solution 2
  • 0:01:38 O(nlog(logn)), O(1) solution
  • 0:02:17 O(n),O(1) solution
  • 0:02:33 LCA & +1RMQ
  • 0:02:51 O(n),O(1) solution
  • 0:08:08 LCA& +1RQM
  • 0:16:49 (O(n),O(1)) solution (4n+o(n) bits)
  • 0:34:19 (O(n),O(1)) solution (2n+0(n) bits )
  • 0:47:12 Burrows-Wheeler-Transformation: Einführung
  • 0:48:52 Wiederholung: Suffix-Array
  • 0:49:24 Transformation
  • 0:52:22 Burrows-Wheeler-Transformation: Eigenschaften
  • 0:53:52 Rücktrnasformation
  • 1:05:34 Berechnung von LF
  • 1:08:02 Ablauf der Berechnung von LF
  • 1:10:34 Was bringt die BWT?
  • 1:11:41 Kompression
  • 1:12:03 Kompression: Move-To-Front (MTF) Kodierung
  • 1:13:38 Kompression: Huffmann Kodierung
  • 1:14:37 Suche in der Burrowa-Wheeler Transformation
  • 1:15:35 Backward Search
  • 1:21:55 Backward Search: Summary
  • 1:22:37 Wavelet Tree Example: Calculate Rank
Open Access Logo


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