Vorlesung: Datenstrukturen (DS) (SS 2008)

Vorlesung über 2 SWS mit Übungen über 1 SWS

Pflichtveranstaltung des Moduls B-DS

Vorlesung

Prof. Dr. Ulrich Meyer
Dienstag 8:00 - 10:00 (erste Vorlesung findet am 01.04.08 statt)
Magnus-Hörsaal (R-M-S 11-15)

Die Klausurergebnisse finden Sie im geschützten Bereich.

Übungsbetrieb

Dipl-Inf. Andrei Negoescu (E-Mail: negoescu@cs.uni-frankfurt.de)
Raum 311
Sprechzeiten: Immer, wenn im Büro anzutreffen und nach Vereinbarung.

Das Lösen von Übungsaufgaben ist für eine erfolgreiche Teilnahme an der Vorlesung unbedingt zu empfehlen.
Die Aufgaben der Klausur werden sich an Übungsaufgaben orientieren. Der Übungsbetrieb ist im zweiwöchentlichen Rhythmus organisiert.

Inhalt

Die Vorlesung behandelt die Laufzeitanalyse, fundamentale Datenstrukturen und allgemeine Methoden für den Entwurf und die Analyse von Datenstrukturen. Die Analyse von Datenstrukturen im Hinblick auf Laufzeit und Speicherplatzbedarf wird motiviert. Die asymptotische Notation wird eingeführt, und Methoden zur Lösung von Rekursionsgleichungen werden besprochen.
Elementare Datenstrukturen wie Listen, Keller und Warteschlangen werden beschrieben und analysiert. Weiter werden die Darstellung von Bäumen und allgemeinen Graphen im Rechner und Algorithmen zur systematischen Durchmusterung von Graphen diskutiert.
Der Begriff des abstrakten Datentyps wird eingeführt und motiviert, und effiziente Realisierungen der Datentypen des Wörterbuchs und der Prioritätswarteschlange unter Benutzung von Bäumen (beispielsweise AVL-, Splay-Bäume und B-Bäume) und Hashing (auch verteiltes Hashing und Bloom-Filter) werden besprochen. Außerdem werden effiziente Datenstrukturen für das Union-Find-Problem behandelt.

Lernziele: Die Kenntnis fundamentaler Datentypen sowie die Fähigkeit, den Prozess des Entwurfs und der Analyse von Datenstrukturen eigenständig durchführen zu können.

Literatur

T. H. Cormen, C. E. Leiserson, R.L. Rivest und Clifford Stein: Introduction to Algorithms, Second Edition, MIT Press, 2001.

Klausurtermine (Achtung Raumänderung !)

Hauptklausur: 09.07.08, 14:00 Uhr, Hörsaal H III
Nachklausur : 29.09.08, 14:00 Uhr, Hörsaal H III

Ressourcen

Materialien für Studierende befinden sich hier.