Fortgeschrittene Datenstrukturen

  • Typ: Weiterführende Vorlesung
  • Lehrstuhl: Prof. Dr. Peter Sanders
  • Ort:

    SR 236, Geb. 50.34 (Informatikhauptgebäude)
  • Zeit:

    Donnerstag, 11.30-13.00
  • Beginn: 20.10.2011
  • Dozent:

    Peter Sanders
    Johannes Fischer
  • SWS: 3
  • LVNr.: 24178
  • Prüfung:

    ja

Inhalte

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
- Computational geometry: orthogonal range queries
- Data Structures for Strings: Suffix Arrays and String-B Trees

Als Ersatz für Präsenzübungen wird von jedem Studierenden erwartet, in mindestens einer doppelstündigen Vorlesung als Schriftführer zu agieren und ein allen anderen Studierenden zugängliches Skript in digitaler Form zu produzieren. Zur Erleichterung dieser Aufgabe werden dem/der Schriftführer(in) selbstverständlich die Materialien des Vortragenden zur Verfügung gestellt.

Vorlesungsmaterialien

Allgemeine Hinweise

  • The not so short introduction to Latex2e [pdf]
  • Jeffrey Scott Vitter's Miscellaneous Tips for Writing and Formatting [pdf]
  • Mathematical Writing by Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts [pdf]
  • Latex Vorlage [tex]

Folien und Skript