Home  | Impressum | Sitemap | KIT

Fortgeschrittene Datenstrukturen (Advanced Data Structures)

Fortgeschrittene Datenstrukturen (Advanced Data Structures)
Typ: Vorlesung (V) Links:
Semester: WS 12/13
Zeit: 18.10.2012
11:30-13:00
50.34 Raum 236


25.10.2012
11:30-13:00
50.34 Raum 236

08.11.2012
11:30-13:00
50.34 Raum 236

15.11.2012
11:30-13:00
50.34 Raum 236

22.11.2012
11:30-13:00
50.34 Raum 236

29.11.2012
11:30-13:00
50.34 Raum 236

06.12.2012
11:30-13:00
50.34 Raum 236

13.12.2012
11:30-13:00
50.34 Raum 236

20.12.2012
11:30-13:00
50.34 Raum 236

27.12.2012
11:30-13:00
50.34 Raum 236

03.01.2013
11:30-13:00
50.34 Raum 236

10.01.2013
11:30-13:00
50.34 Raum 236

17.01.2013
11:30-13:00
50.34 Raum 236

24.01.2013
11:30-13:00
50.34 Raum 236

31.01.2013
11:30-13:00
50.34 Raum 236

07.02.2013
11:30-13:00
50.34 Raum 236

Dozent: Johannes Fischer
SWS: 2
ECTS: 5
LVNr.: 24178
Prüfung:

ja

Vorlesungsbeschreibung

Datenstrukturen sind der grundlegende Baustein für effiziente Algorithmen. Aufgrund der stetig anwachsenden Datenmengen (Internet, digitale Bibliotheken, Bioinformatik, etc.) besteht ein grundlegender Bedarf an kleinen, aber leistungsfähigen Datenstrukturen. In dieser Vorlesung wollen wir uns mit modernen Datenstrukturen für fundamentale Objekte wie Bäume, Graphen, Integers und Strings beschäftigen. Ein besonderer Fokus wird hierbei auf die mathematische Analyse dieser Datenstrukturen gelegt; es wird aber auch immer wieder die praktische Seite (Implementierung) angesprochen werden. Die Vorlesung ist so ausgelegt, dass wiederkehrende Techniken anhand von konkreten Problemen gelehrt werden.

Wir behandeln voraussichtlich die folgenden Themen:

- Predecessor data structures: van-Emde-Boas trees, y-fast trees, fusion trees
- Integer sorting
- Dictionaries: cuckoo hashing, FKS dictionary
- Data structures for graphs: distance oracles, spanners, distance labels
- Data structures for trees: lowest common ancestors, level ancestors
- Data structures for arrays: range minima and other kind of range queries
- Succinct data structures: bit vectors, succinct tree navigation
- Data Structures for Strings: Compressed Suffix Arrays

Folien und Skript