Vorlesung: Datenstrukturen (B-DS) (SS 2016)

Vorlesung über 2 SWS mit Übungen über 1 SWS
Die Veranstaltung DS ist Pflichtveranstaltung des Basis-Moduls B-DS

Vorlesung

Dr. Ignaz Rutter
E-Mail: rutter@ae.cs.uni-frankfurt.de
Dienstag 08:00 - 10:00
Hörsaal H VI (Jügelhaus/Hörsaalgebäude)
LSF
Sprechstunde: Dienstag 10:00 - 12:00 in Raum 115 (R-M-S 11-15)

Übungsbetrieb

Dipl-Math. Mahyar Behdju
E-Mail: ds16-support@ae.cs.uni-frankfurt.de
Sprechzeiten: Immer, wenn im Büro anzutreffen und nach Vereinbarung.

Die Übungsgruppen beginnen ab Dienstag, den 19.04.2016, mit Blatt 0.

Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe "Hinweise zu den Übungsabgaben").

Der Übungsbetrieb ist im wöchentlichen Rhythmus organisiert. Die Abgabe des Blattes erfolgt am Dienstag in der Folgewoche vor Beginn der Vorlesung. Für eine frühere Abgabe benutzen Sie bitte den Briefkasten neben Raum 312.

Termine der Übungsgruppen

Hinweise zu den Übungsabgaben

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

Klausurtermine

Hauptklausur: 28.07.2016, 09:00 - 11:00 Uhr, Jügelhaus - H V
Nachklausur : 10.10.2016, 09:00 - 11:00 Uhr, Jügelhaus - H V
Weitere Räume und Informationen werden zu gegebener Zeit bekannt gegeben.

Ressourcen

Materialien für Studierende befinden sich hier.