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

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

  • Die Erstklausur wird am 03.08.2018 um 9:00 Uhr (s.t.) beginnnen und in den Hörsälen IV (römisch 4), V (römisch 5) und VI (römisch 6) stattfinden.
  • Bitte beachten Sie die vorgegebene Sitzordnung.
  • Bitte denken Sie daran, sich rechtzeitig beim zuständigen Prüfungsamt anzumelden. Bitte registrieren Sie sich zusätzlich mit Name und Matrikelnummer per Mail an ds18@ae.cs.uni-frankfurt.de sofern Sie sich nicht im QIS/LSF anmelden müssen. Das betrifft hauptsächlich Lehramtsstudenten.
  • Die maximale Bearbeitungszeit der Klausur beträgt 100 Minuten.
  • Für die Klausur ist als einziges Hilfsmittel ein einseitig handschriftlich beschriebener DIN-A4 Zettel zugelassen.
  • Es dürfen nur dokumentenechte Stifte in den Farben blau und schwarz verwendet werden.
  • Tipp-Ex und andere Korrekturwerkzeuge sind nicht erlaubt!!! Wenn Textstellen nicht gewertet werden sollen, so sind diese mit einem zugelassenen Stift durchzustreichen.
  • Sicher bestanden hat, wer mindestens 50% der maximalen Klausurpunkte (inklusive Bonus) erreicht.

Vorlesung

Prof. Dr. Ulrich Meyer
E-Mail: umeyer@ae.cs.uni-frankfurt.de
Dienstag 08:00 - 10:00
Hörsaal H VI (Jügelhaus/Hörsaalgebäude)
LSF
Sprechstunde: Nach Vereinbarung

Freiwillige Zusatzveranstaltung: Datenstrukturen in C++ Programmieren

Manuel Penschuck
E-Mail: manuel@ae.cs.uni-frankfurt.de (nur für Zusatzveranstaltung)
Freitag 10:00 - 12:00
Magnus Hörsaal (Robert-Mayer-Str. 11-15)
Sprechstunde: Nach Vereinbarung

Übungsbetrieb

Alex Schickedanz
E-Mail: ds18@ae.cs.uni-frankfurt.de
Sprechstunde: Nach Vereinbarung

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 zweiwöchentlichen Rhythmus organisiert. Die Abgabe des Blattes erfolgt normalerweise zwei Wochen später vor Beginn der Vorlesung. Für eine frühere Abgabe benutzen Sie bitte den großen Briefkasten neben Raum 312 (Robert-Mayer-Str. 11-15). Der Briefkasten wird am Tag der Abgabe um 8:00 geleert.

Sie können durch Teilnahme an den Übungen bis zu 10 Bonuspunkte, durch die Teilname an der zusätzlichen Programmierveranstaltung bis zu 3 Bonuspunkte erlangen, in Summe jedoch nicht mehr als 10.

Termine der Übungsgruppen

Gruppe 01 Mo 12 - 14 NM 113 Andreas Scholl (ungerade Kalenderwochen)
Gruppe 02 Mo 12 - 14 NM 113 Andreas Scholl (gerade Kalenderwochen)
Gruppe 03 Mo 14 - 16 NM 102 Anh Duong Vo (ungerade Kalenderwochen)
Gruppe 04 Mo 14 - 16 NM 102 Anh Duong Vo (gerade Kalenderwochen)
Gruppe 05 Mo 16 - 18 NM 102 Adrian Kretz (ungerade Kalenderwochen)
Gruppe 06 Mo 16 - 18 NM 102 Adrian Kretz (gerade Kalenderwochen)
Gruppe 07 Di 12 - 14 H 9 Jaro Eichler (ungerade Kalenderwochen)
Gruppe 08 Di 12 - 14 H 9 Jaro Eichler (gerade Kalenderwochen)
Gruppe 09 Di 14 - 16 NM 102 Marco Schmalhofer (ungerade Kalenderwochen)
Gruppe 10 Di 14 - 16 NM 102 Marco Schmalhofer (gerade Kalenderwochen)
Gruppe 11 Mi 12 - 14 H 9 Lukas Maurer (ungerade Kalenderwochen)
Gruppe 12 Mi 12 - 14 H 9 Lukas Maurer (gerade Kalenderwochen)
Gruppe 13 Do 12 - 14 H 9 Vincent Kühn (ungerade Kalenderwochen)
Gruppe 14 Do 12 - 14 H 9 Vincent Kühn (gerade Kalenderwochen)
Gruppe 15 Do 12 - 14 NM 102 Ehud Cseresnyès (ungerade Kalenderwochen)
Gruppe 16 Do 12 - 14 NM 102 Ehud Cseresnyès (gerade Kalenderwochen)
Gruppe 17 Do 14 - 16 NM 102 Stephan Gardoll (ungerade Kalenderwochen)
Gruppe 18 Do 14 - 16 NM 102 Stephan Gardoll (gerade Kalenderwochen)

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: 03.08.2018 9:00 s.t.
Nachklausur: 11.10.2018 9:00 s.t.
Weitere Informationen werden zu rechtzeitig bekannt gegeben.

Ressourcen

Materialien für Studierende befinden sich hier.