Institut für Theoretische Informatik, Algorithm Engineering

Fortgeschrittene Datenstrukturen

  • Typ: Vorlesung (V)
  • Semester: SS 2016
  • Zeit: 21.04.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


    28.04.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    12.05.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    19.05.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    02.06.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    09.06.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    16.06.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    23.06.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    30.06.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    07.07.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    14.07.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    21.07.2016
    09:45 - 11:15 wöchentlich
    50.34 Raum 236 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


  • Dozent: Dr. Simon Gog
  • SWS: 2/1
  • ECTS: 5
  • LVNr.: 2400078
BeschreibungIn 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
ArbeitsbelastungVorlesung 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

ZielDie 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.