Fortgeschrittene Datenstrukturen

Übersicht

Inhalt

In dieser Vorlesung beschäftigen wir uns mir modernen Datenstrukturen für fundamentale Objekte wie Bäume, Graphen, Integers und Strings. Diese Datenstrukturen sind Grundlage für viele Anwendungen und ein wichtiger Bestandteil von effizienten Algorithmen. In dieser Vorlesung betrachten wir die Highlights aus verschiedenen Forschungsbereichen und werden dabei Techniken zur Lösung unterschiedlichster Probleme kennen lernen. Neben der theoretischen Analyse der Datenstrukturen werden wir uns auch mit der praktischen Performance der verschiedenen Datenstrukturen und ihren Einsatzgebieten beschäftigen.

Wichtige Information

  • Deadline-Extension: Das Projekt kann bis zum 18.07.2022 um 23:59 Uhr abgegeben werden.
  • Am 04.07.2022 wird die Veranstaltung evaluiert
  • Die Veranstaltung am 27.06.2022 fällt krankheitsbedingt aus.
  • Die Veranstaltung am 23.05.2022 findet nicht live vor Ort statt. Es wird nur die Videoaufnahme der Veranstaltung geben. Diese wird zur gewohnten Vorlesungszeit veröffentlicht. Am 30.05. wird es von 9:15 Uhr bis 9:45 Uhr die Möglichkeit geben, Fragen zu der Vorlesung zu stellen.

Prüfungstermine

Die mündlichen Prüfungen finden am 10.08.2022 und 19.09.2022 statt. Sie können per E-Mail an blancani∂kit.edu einen Termin vereinbaren. Bitte nennen Sie dabei Ihren vollständigen Namen, die Matrikelnummer, Ihr Studienfach und die Prüfungsordnung, nach der Sie studieren.

Sie müssen sich sowohl für die mündliche Prüfung als auch für die Zusatzleistung (Projekt/Experiment) am Studierendenportal anmelden.

Folien und Videos

Kapitel 00 Einführung: Folien und Video
Kapitel 01 Bit Vektoren: Folien und Video
Kapitel 02 Succincte Bäume: Folien, Folien ohne Animationen, Handout und Video
Kapitel 03 Dynamische Bitvektoren und Succincte Bäume: Folien, Folien ohne Animationen und Video
Kapitel 04 Succincte Graphen und Range Min-Max Bäume: Folien, Folien ohne Animationen und Video
Kapitel 05 Successor und Range Minimum Queries: Folien, Folien ohne Animationen und Video
Kapitel 06 Suffix Array und String B-Tree: Folien und Folien ohne Animationen
Kapitel 07 Komprimiertes Suffix Array: Folien und Folien ohne Animationen
Kapitel 08 Temporäre Datenstrukturen: Folien und Folien ohne Animationen
Kapitel 09 Temporäre Datenstrukturen 2: Folien und Folien ohne Animationen
Kapitel 10 Orthogonal Range Search: Folien und Folien ohne Animationen
Kapitel 11 Binary Space Partitions: Folien und Folien ohne Animationen

Projekt

Die Projektbeschreibung kann hier (English version here) heruntergeladen werden. Bitte beachten, dass die Indizes der Knoten im Baum mit 1 beginnen.