Datenstrukturen

Vorlesung im SoSe 2012

Gehalten von Dr. Mariano Zelke

Aktuelles

 Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und gelegentlich ergänzende Bemerkungen.

Einführung

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.

Kürzel laut Studienordnung: B-DS.  Creditpoints: 5.  SWS: 2V, 1Ü.

Logbuch

 Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien und gelegentlich ergänzende Bemerkungen.

E-Lectures

 Im Sommersemester 2012 wurden die Vorlesungen von studiumdigitale, der E-Learning-Einrichtung der Goethe-Universität, auf Video aufgezeichnet. Die einzelnen Aufzeichnungen finden Sie hier:

Termine
ZeitOrtLeitung
Vorlesung Dienstag 8:00-10:00
(vom 10.04.-13.07.)		 Magnus-Hörsaal in der Informatik, Robert-Mayer-Str. 11-15 Dr. Mariano Zelke
Übung 1 Montag 12:00-14:00
(14-tägl. ab 16.04.)		 NM 126 Maziar Behdju
Übung 2 Montag 12:00-14:00
(14-tägl. ab 23.04.)		 NM 126 Maziar Behdju
Übung 3 Mittwoch 12:00-14:00
(14-tägl. ab 18.04.)		 NM 103 Christian Neumann
Übung 4 Mittwoch 12:00-14:00
(14-tägl. ab 25.04.)		 NM 103 Christian Neumann
Übung 5 Donnerstag 08:00-10:00
(14-tägl. ab 19.04.)		 NM 126 Hannes Seiwert
Übung 6 Donnerstag 08:00-10:00
(14-tägl. ab 26.04.)		 NM 126 Hannes Seiwert
Übung 7 Freitag 08:00-10:00
(14-tägl. ab 20.04.)		 NM 126 Edgardo Deza
Übung 8 Freitag 08:00-10:00
(14-tägl. ab 27.04.)		 NM 126 Edgardo Deza
Übung 9 Mitwoch 12:00-14:00
(14-tägl. ab 18.04.)		 AfE 104b Jens Keppeler
Übung 10 Mittwoch 12:00-14:00
(14-tägl. ab 25.04.)		 AfE 104b Jens Keppeler
Übung 11 Montag 12:00-14:00
(14-tägl. ab 16.04.)		 AfE 104b Dr. Annamaria Kovacs
Übung 12 Montag 12:00-14:00
(14-tägl. ab 23.04.)		 AfE 104b Dr. Annamaria Kovacs

Übungsblätter

Es wird regelmäßige Übungsaufgaben geben. Die Teilnahme an den Übungsstunden und das Bearbeiten der Übungsaufgaben ist für das Verständnis der Vorlesung und eine erfolgreiche Prüfung unbedingt empfohlen. Insbesondere kann durch die in den Übungen gesammelten Punkte ein Bonus für die Klausur erworben werden (Details siehe Klausur).

Das aktuelle Übungsblatt ist jeweils 14-tägig spätestens dienstags nach der Vorlesung an dieser Stelle zu finden und wird außerdem dienstags in gedruckter Form am Ende der Vorlesung ausgeteilt. Die Abgabe der bearbeiteten Übungsaufgaben erfolgt jeweils 2 Wochen später dienstags, bis spätestens 8:15 Uhr vor Beginn der Vorlesung. Achtung: Auf dem abgegebenen Übungsblatt müssen Name, Matrikelnummer und Übungsgruppe vermerkt sein. Mehrseitige Abgaben sind zusammenzuheften. Die Abgabe erfolgt in Papierform (eine elektronische Abgabe ist aus logistischen Gründen leider nicht möglich).

Obwohl es sicherlich sinnvoll ist, über die Aufgaben mit Kommilitonen/innen gemeinsam zu reden und nachzudenken, sollte jede/r Student/in seine eigene Lösung aufschreiben und abgeben.

Anleitung für die Übungsgruppen-Anmeldung im LSF

 Falls Sie an den Übungen teilnehmen wollen, müssen Sie sich im Zeitraum vom 1. bis 13. April (11:59 Uhr) über HIS-LSF für die Übung anmelden.
Zur Anmeldung für die Übungen verfahren Sie am besten wie folgt:

Klausur
Termin:
Die Klausur (= Modulabschlussprüfung Datenstrukturen) dauert 100 Minuten und findet am Freitag, den 27. Juli 2012 um 9:00 Uhr in Hörsaal V (Jügelhaus) statt.
Anmeldung:
Zur Teilnahme an der Klausur ist eine vorherige Anmeldung erforderlich. Bachelor-Studierende müssen sich beim für den jeweiligen Studiengang zuständigen Prüfungsamt anmelden. Bitte stellen Sie sicher, dass Sie die Anmeldefristen nicht verpassen! Die Frist ist abhängig von Ihrem Studiengang! Informationen zur Anmeldung für Informatik-Bachelor-Studierende finden sich auf den Webseiten des Prüfungsamts Informatik (insbesondere hier).
Nicht-Bachelor-Studierende melden sich bitte (1) ggf. beim für sie zuständigen Prüfungsamt und (2) per E-Mail bei Mariano Zelke mit den folgenden Informationen an: Name, Vorname, Matrikelnummer, Geburtsdatum, Studiengang.
 
Benotung:
Durch die in den Übungen gesammelten Punkte kann ein Bonus für die Klausur erworben werden. Zur Benotung werden neben dem Klausurergebnis Bonuspunkte mit einem Maximalgewicht von 10% eingehen. Achtung: Die Bonuspunkte werden Ihnen für die Klausur nur unter der Bedingung gutgeschrieben, dass Sie mindestens einmal im Tutorium vorgerechnet haben.
Die Klausur ist bestanden, wenn mit dem Bonus mindestens 50% der in der Klausur erzielbaren Punkte erreicht werden.

Bei einem Ergebnis von x% aus der Klausur und y% aus den Übungen werden die folgenden Noten vergeben, wobei   z = x + (y/10):

 

Note   Prozentpunkte
1.0 95% <= z
1.3 90% <= z < 95%
1.7 85% <= z < 90%
2.0 80% <= z < 85%
2.3 75% <= z < 80%
2.7 70% <= z < 75%
3.0 65% <= z < 70%
3.3 60% <= z < 65%
3.7 55% <= z < 60%
4.0 50% <= z < 55%
 
Details zum Ablauf der Klausur:
 
Checkliste — zur Klausur müssen Sie mitbringen:
  • einen dokumentenechten Schreibstift
  • einen gültigen Lichtbildausweis (z.B. Ihre Goethe-Card oder Ihren Personalausweis)
  • Ihren Studierendenausweis (... es sei denn, Sie sind als "Schülerstudent" für die Veranstaltung angemeldet)

Literatur
[S] Prof. Dr. G. Schnitger Skript zur Vorlesung "Datenstrukturen"
[IA] T. H. Cormen, C. E. Leiserson, R. L. Rivest und C. Stein. Introduction to Algorithms, Second Edition, MIT Press, 2001.
[DSA] M. T. Goodrich, R. Tamassia und D. M. Mount. Data Structures and Algorithms in C++, John Wiley, 2003.
[AD] J. Kleinberg und E. Tardos. Algorithm Design, Addison-Wesley, 2005.
zuletzt geändert: Mon Feb 18 14:44:55 2013 von Lucas Heimberg