Fortgeschrittene Datenstrukturen

Die Vorlesung muss im Sommersemester 2020 leider entfallen.

---

---

Beschreibung

In datenintensiven Bereichen wie etwa Bioinformatik, sozialen Netzwerken oder Suchmaschinen sind effiziente Algorithmen abhängig von Datenstrukturen, welche die Grundoperationen der Algorithmen effizient unterstützen. Darüber hinaus sollen die Strukturen möglichst platzeffizient sein und schnell konstruiert oder aktualisiert werden. In dieser Vorlesungen werden wir Datenstrukturen für verschiedene fundamentale Objekte wie Bäume, Graphen und Strings vorstellen. Wir werden uns dabei auf die Highlights der verschiedener Forschungsbereiche konzentrieren. Neben der theoretischen Analyse der Strukturen werden wir uns auch mit der praktischen Performance der Strukturen beschäftigen und Einsatzgebiete erläutern.

Lehrinhalt

  • Dictionary data structures: Hashing (universal, perfect, minimum monoton, cuckoo)
  • Predecessor data structures: van-Emde-Boas trees, y-fast trees, fusion trees
  • Orthogonal range search structures
  • Range minimum queries
  • Index structures for arrays
  • Top-k document retrieval

Arbeitsbelastung

Vorlesung mit Projekt/Experiment mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davon

  • ca. 30 Std. Besuch der Vorlesung
  • ca. 60 Std. Vor- und Nachbereitung
  • ca. 30 Std. Bearbeiten des Projekts/Experiments
  • ca. 30 Std. Prüfungsvorbereitung

Ziel

Die Studierenden lernen in der Vorlesung fortgeschrittene Datenstrukturen und algorithmische Techniken kennen, welche auf dem bestehenden Wissen im Themenbereich Algorithmik aufbauen und es erweitern. Außerdem können sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungsarbeiten im Bereich Datenstrukturen interpretieren und nachvollziehen. Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen, grundlegende Problemdefinitionen und Algorithmen aus der Vorlesung erklären;
  • auswählen, welche Algorithmen und Datenstruktuen zur Lösung einer Fragestellung geeignet sind und diese ggf. den Anforderungen einer konkreten Problemstellung anpassen;
  • Algorithmen und Datenstrukturen ausführen, mathematisch präzise analysieren und die algorithmischen Eigenschaften beweisen.