Datenstrukturen (SS 2018)

Vorlesung

Prof. Dr. Ulrich Meyer

Dienstag 08:00 - 10:00
Hörsaal H VI (Jügelhaus/Hörsaalgebäude)

Sprechstunde: Nach Vereinbarung

Freiwillige Zusatzveranstaltung: Datenstrukturen in C++ Programmieren

Manuel Penschuck

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 1Mo12 - 14NM 113Andreas Scholl(ungerade Kalenderwochen)
Gruppe 2Mo12 - 14NM 113Andreas Scholl(gerade Kalenderwochen)
Gruppe 3Mo14 - 16NM 102Anh Duong Vo(ungerade Kalenderwochen)
Gruppe 4Mo14 - 16NM 102Anh Duong Vo(gerade Kalenderwochen)
Gruppe 5Mo16 - 18NM 102Adrian Kretz(ungerade Kalenderwochen)
Gruppe 6Mo16 - 18NM 102Adrian Kretz(gerade Kalenderwochen)
Gruppe 7Di12 - 14H 9Jaro Eichler(ungerade Kalenderwochen)
Gruppe 8Di12 - 14H 9Jaro Eichler(gerade Kalenderwochen)
Gruppe 9Di14 - 16NM 102Marco Schmalhofer(ungerade Kalenderwochen)
Gruppe 10Di14 - 16NM 102Marco Schmalhofer(gerade Kalenderwochen)
Gruppe 11Mi12 - 14H 9Lukas Maurer(ungerade Kalenderwochen)
Gruppe 12Mi12 - 14H 9Lukas Maurer(gerade Kalenderwochen)
Gruppe 13Do12 - 14H 9Vincent Kühn(ungerade Kalenderwochen)
Gruppe 14Do12 - 14H 9Vincent Kühn(gerade Kalenderwochen)
Gruppe 15Do12 - 14NM 102Ehud Cseresnyès(ungerade Kalenderwochen)
Gruppe 16Do12 - 14NM 102Ehud Cseresnyès(gerade Kalenderwochen)
Gruppe 17Do14 - 16NM 102Stephan Gardoll(ungerade Kalenderwochen)
Gruppe 18Do14 - 16NM 102Stephan Gardoll(gerade Kalenderwochen)

Hinweise zu den Übungsabgaben

  • Die Abgabe der Übungen hat stets bis zu Beginn der Vorlesung zu erfolgen.
  • Jedes(!) Blatt ist mit dem vollständigen Namen, Matrikelnummer und Gruppennummer zu versehen.
  • Bei Abgabe im Briefkasten muss auch die Veranstaltung auf das Blatt geschrieben werden.
  • Wer eine falsche Gruppennummer auf dem Blatt angibt und deshalb nicht bei seinem Tutor landet, bekommt auf die Abgabe keine Punkte.
  • Eine Abgabe via E-Mail ist nur in Ausnahmefällen (z.B. Krankheit) und nur als PDF Datei möglich.
    • Bitte keine Fotos! Verwendet am besten LaTeX oder zur Not ein anderes Textsatzprogramm.
    • Nur im äußersten Notfall werden Fotos akzeptiert. Achtet darauf: keine dunklen/schwarzen Ränder oder Hintergrund, richtig gedreht, gut lesbar und als eine PDF Datei.
    • Abgaben, die nicht als PDF eingereicht werden, werden ohne Antwort ignoriert.
  • Der Tutor ist nicht verpflichtet schwer lesbare Abgaben zu korrigieren.
  • Wenn eine Aufgabe nicht lesbar ist, dann gibt es auf die Aufgabe keine Punkte.
  • Wir stellen eine LaTeX Vorlage zur Verfügung.
  • Abgaben ohne vollständigen Namen, Matrikelnummer und Gruppennummer werden nicht korrigiert.
  • Mehrseitige Übungsabgaben sind zu tackern.
  • Wenn festgestellt wird, dass eine Aufgabe abgeschrieben wurde, dann…
    • … gibt es beim ersten Mal für alle Beteiligten 0 Punkte auf das Blatt.
    • … wird beim zweiten Mal allen Beteiligten die Bonifikation sowohl für die Erst- als auch die Zweitklausur aberkannt. Außerdem werden keine weiteren Abgaben der Beteiligten mehr korrigiert.
  • Sie dürfen in Gruppen über die Aufgaben diskutieren und zusammen Lösungswege erarbeiten (es ist sogar empfohlen). Jedoch muss jeder Student in der Abgabe die Lösung selbst schreiben und somit erkennbar machen, dass der Lösungsweg verstanden wurde. Im Zweifelsfall kann der Tutor verlangen, dass Sie eine Lösung vorrechnen. Sind Sie im Tutorium gar nicht anwesend, so kann der Tutor die Punkte vom Übungsblatt aberkennen.

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.
  • M. T. Goodrich, R. Tamassia und D. Mount: Data Structures and Algorithms in C++, Wiley & Sons, 2004.

Klausurtermine

Hauptklausur: 03.08.2018 9:00 s.t.
Nachklausur: 11.10.2018 9:00 s.t.
Weitere Informationen werden zu rechtzeitig bekannt gegeben.

Materialien

Beamer-Folien

Videoaufzeichnungen

Die Videoaufzeichnungen der Vorlesung stehen hier zur Verfügung.

Altklausuren

Altklausuren finden Sie hier.

Übungsblätter

Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt, jedoch müssen Sie Ihre Lösungen eigenständig aufschreiben.

Die Übungsblätter werden so entworfen, dass ihre Bearbeitung mit den Kenntnissen aus der Vorlesung und aus vorangegangenen Übungsblättern möglich ist. Sollten Sie in Ihrer Lösung dennoch andere Quellen (Bücher, Skripte, Internetforen, soziale Netzwerke, Lösungen anderer Studenten, etc.) verwenden, so müssen Sie die entsprechenden Stellen als direkte oder indirekte Zitate kennzeichnen. Orientieren Sie sich hierfür einfach an den Hinweisen zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. Darüber hinaus muss Ihre persönliche Leistung stets deutlich erkennbar sein. Bei direkten Zitaten oder fast unverändert übernommenen Passagen liegt keine persönliche Leistung vor.

Betrugsversuche bzw. Plagiate führen beim erstmaligen Verstoß dazu, dass bei allen Beteiligten die Bonuspunkte des gesamten Übungsblattes verfallen („gelbe Karte“). Beim zweiten Verstoß werden keinerlei Bonuspunkte für die Klausur angerechnet („rote Karte“) und der Vorfall wird dem Prüfungsamt angezeigt. Bitte beachten Sie, dass auch das Ermöglichen von Plagiaten („abschreiben lassen“) einen Betrugsversuch darstellt und geahndet wird.

  • Übung 0 Ausgabe: 10.04.18 Abgabe: keine
  • Übung 1 Ausgabe: 17.04.18 Abgabe: 02.05.18 bis 08:00 (morgens) im Briefkasten neben Raum 312 (RM 11-15)
  • Übung 2 Ausgabe: 01.05.18 Abgabe: 15.05.18 bis 08:10 (vor der Vorlesung)
  • Übung 3 Ausgabe: 15.05.18 Abgabe: 29.05.18 bis 08:10 (vor der Vorlesung)
  • Übung 4 Ausgabe: 29.05.18 Abgabe: 12.06.18 bis 08:10 (vor der Vorlesung)
  • Übung 5 Ausgabe: 12.06.18 Abgabe: 26.06.18 bis 08:10 (vor der Vorlesung)
  • Übung 6 Ausgabe: 26.06.18 Abgabe: 03.07.18 bis 08:10 (vor der Vorlesung)
    Achtung: Nur eine Woche Bearbeitungszeit.

Skript

Es steht das Skript von Herrn Prof. Dr. G. Schnitger zum download bereit, an dem sich diese Veranstaltung orientiert.

Zusatzveranstalung