Home  | Impressum | Sitemap | KIT

Fortgeschrittene Datenstrukturen

Fortgeschrittene Datenstrukturen
Typ: Vorlesung (V) Links:
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.