Datenstrukturen (B-DS) – Sommersemester 2015

Im Logbuch finden Sie Informationen zum Inhalt der einzelnen Vorlesungsstunden.

Aktuelles

  • 06.10.2015
    Die Ergebnisse der Klausur vom 5. Oktober 2015 sind online.

    Die Klausureinsicht findet am Donnerstag 8. Oktober 2015 von 10:00 ‒ 12:00 Uhr in SR 307 statt.     Da wir nur eine begrenzte Anzahl von Studenten gleichzeitig betreuen können, bitten wir Sie, nicht alle auf einmal zu erscheinen. Danke :-)

Inhalt der Vorlesung

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.

Literaturhinweise

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest und C. Stein, „Introduction to Algorithms“ (2nd edition)
  • M.T. Goodrich, R. Tamassia und D.M. Mount, „Data Structures and Algorithms in C++“
  • M. Dietzfelbinger, K. Mehlhorn und P. Sanders, „Algorithmen und Datenstrukturen, die Grundwerkzeuge“, Springer Vieweg 2014. (Kapitel 1-4,6,8,9)
  • R. Sedgewick „Algorithmen in C++“ (9. Auflage, Kapitel 1 – 7 im Grundlagenteil)
  • J. Kleinberg und E. Tardos, „Algorithm Design“ (fortgeschritten)
Für die mathematischen Grundlagen empfehlen wir

Termine

Vorlesung: Dienstag, 8:15 – 10:00 in H V (Jügelhaus)
Übungen: siehe Abschnitt Übungsgruppen

Material

  • Skript als PDF (Stand: 17.04.2015) (Changelog)
  • Die Beamer-Folien zur Vorlesung werden im Laufe des Semesters im Logbuch ergänzt.
  • Vorlesungsvideos werden ebenfalls im Logbuch ergänzt. (Zusätzlich gibt es hier eine Übersicht aller Videos, die bisher online sind.)

  • Auf der Seite des Informatik Vorsemesterkurses finden sich Folien zu den Themen
    • Beweistechniken,
    • Rekursion & Induktion sowie
    • Asymptotik & Laufzeitanalyse.

Kontakt

Bei Fragen helfen Bert Besser, Hannes Seiwert und natürlich auch alle Tutoren gerne weiter.

Übungsbetrieb

Die Teilnahme an den Übungen und das Bearbeiten der Übungsaufgaben wird für eine erfolgreiche Prüfung unbedingt empfohlen. Die Abgabe bearbeiteter Blätter erfolgt

  • am Abgabetag
  • vor Vorlesungsbeginn
  • im Hörsaal.

Falls ein Erscheinen nicht einzurichten ist, ist eine frühere Abgabe im Briefkasten vor Raum 312 ebenfalls zulässig. Dieser Briefkasten wird am Abgabetag vor Vorlesungsbeginn geleert. Später eingeworfene Abgaben werden nicht gewertet.

Damit ein reibungsloser Ablauf gewährleistet werden kann, muss jede Abgabe im Kopf der Titelseite gut leserlich mit den folgenden Angaben versehen sein:

  • der Name und die Matrikelnummer der/des Abgebenden,
  • die Nummer sowie der/die Tutor/in der Übungsgruppe.

Abgaben, die mehrere Blätter umfassen, müssen mittels eines Tackers zusammengefügt sein. An der Ecke zusammengefaltete Blätter, Büroklammern, o.Ä. ersetzen keine Tackernadel! Für nicht getackerte Abgaben kann nicht gewährleistet werden, dass sie den Tutor vollständig erreichen.

Übungsgruppen

Die Übungen finden im zwei-wöchigen Rhythmus statt. In der ersten Vorlesungswoche (KW 16) erscheint ein Präsenzblatt, welches in den Gruppentreffen der ersten beiden Vorlesungswochen gemeinsam besprochen wird. Beginnend mit der zweiten Vorlesungswoche (KW 17) erscheinen in ungeraden Kalenderwochen Übungsblätter zur selbstständigen Bearbeitung; in ungeraden Kalenderwochen (beginnend mit KW 19) werden die bearbeiteten Übungsblätter eingesammelt. Die Bearbeitungszeit eines Übungsblattes beträgt also zwei Wochen. Das sechste und letzte Blatt wird bereits nach einer Bearbeitungszeit von einer Woche wieder eingesammelt.

Gerade Übungsgruppen finden in geraden Kalenderwochen statt. Ungerade Übungsgruppen finden in ungeraden Kalenderwochen statt.

Die Einteilung in die Tutorien ist hier verfügbar. (Bitte ignorieren Sie die Informationen im Anmeldesystem bzgl. Datenstrukturen, es haben sich noch Änderungen ergeben.)

Mo Di Mi Do Fr
08-10
Vorlesung
gerade & ungerade
Kalenderwochen

Dozent
Prof. Dr.
Georg Schnitger

Ort
H (röm.) V
10-12
Gruppe 01
Magenta
ungerade

Tutor
Robert
Jabs

Ort
NM 126
Gruppe 02
Magenta
gerade

Tutor
Robert
Jabs

Ort
NM 126
Gruppe 09
Blau
ungerade

Tutor
Jens
Donart

Ort
NM 123
Gruppe 10
Blau
gerade

Tutor
Jens
Donart

Ort
NM 114
Gruppe 12
Gelb
gerade

Tutor
Mario
Holldack

Ort
H (arab.) 1
Gruppe 14
Cyan
gerade

Tutor
Felix
Weiglhofer

Ort
H (arab.) 2
Gruppe 16
Braun
gerade

Tutor
Julian
Wüschner

Ort
NM 116
Gruppe 13
Cyan
ungerade

Tutor
Felix
Weiglhofer

Ort
H (arab.) 5
Gruppe 17
Weiß
ungerade

Tutor
Philipp
Tertel

Ort
SR 307
12-14
Gruppe 05
Rot
ungerade

Tutor
Lea
Berty

Ort
H (arab.) 5
Gruppe 06
Rot
gerade

Tutor
Lea
Berty

Ort
H (arab.) 5
Gruppe 07
Grün
ungerade

Tutor
Rafael
Franzke

Ort
H (arab.) 9
Gruppe 08
Grün
gerade

Tutor
Rafael
Franzke

Ort
H (arab.) 9
Gruppe 15
Braun
ungerade

Tutor
Julian
Wüschner

Ort
SR 11
14-16
Gruppe 03
Orange
ungerade

Tutor
Hung The
Tran

Ort
SR 11
Gruppe 04
Orange
gerade

Tutor
Hung The
Tran

Ort
SR 11
Gruppe 18
Weiß
gerade

Tutor
Philipp
Tertel

Ort
H (arab.) 9
Gruppe 11
Gelb
ungerade

Tutor
Mario
Holldack

Ort
H (arab.) 5
16-18
Fragestunde
 
KW 18, 20, 22

Dozent
Prof. Dr.
Georg Schnitger

Ort
H (röm.) V

Diese Feiertage liegen im Semester, Besprechungen für entsprechende Blätter werden verlegt:

  • Erster Mai: Fr., 1.5., KW 18
    Dieses Treffen entfällt.
  • Pfingstmontag: Mo., 25. Mai, KW 22
    Die Treffen der Gruppen 02 bzw. 04 in KW 22 werden eine Woche nach hinten verschoben und in KW 23 mit den Gruppen 01 bzw. 03 gemeinsam stattfinden.
  • Fronleichnam: Do., 04. Juni, KW 23
    Die Treffen der Gruppen 11, 13 bzw. 17 werden eine Woche nach hinten auf Dienstag, 09.06.2015, verschoben und mit den Gruppen 12, 14 bzw. 18 gemeinsam stattfinden.

Übungsblätter

Prüfungsklausur

Termine

  • Klausur: 04.08.2015, 9:00 s.t. (Ort: H VI im Jügelhaus)
  • Wiederholungsklausur: 05.10.2015, 9:00 s.t. (Ort: H VI im Jügelhaus)

Als Hilfsmittel für die Klausur ist ein beidseitig handbeschriebenes, nicht kopiertes DIN A4 Blatt zugelassen. Bitte Studienausweis (falls das keine Goethe-Card ist, dann zusätzlich einen amtlichen Lichtbildausweis) mitbringen. Die Klausur dauert 100 Minuten.

Zur Teilnahme an der Klausur ist eine vorherige Anmeldung erforderlich.

Fristen

Die Anmeldung zur Klausur muss spätestens zwei Wochen vor der Klausur erfolgen.

Anmeldung

Die Art der Anmeldung hängt von Ihrem Studiengang ab:
  • Informatik, Bio-Informatik, Wirtschaftsinformatik, Physik mit Nebenfach Informatik, Mathematik, Geografie: Die Anmeldung erfolgt per QIS/LSF.
  • Lehramt: Die Anmeldung erfolgt per E-Mail an Hannes Seiwert. Die Mail muss die folgenden Informationen enthalten: Name, Vorname, Matrikelnummer, Geburtsdatum, Studiengang. Bei erfolgreicher Anmeldung erhalten Sie eine Bestätigungsmail.
  • Sonstige: Die Anmeldung erfolgt durch dieses Formular beim Prüfungsamt Informatik (Einwurf im Briefkasten des Prüfungsamts genügt, alternativ kann das Formular direkt im Prüfungsamt oder in der Professur abgegeben werden).

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 20% eingehen. Die Klausur ist mit Sicherheit 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 wird folgende Note vergeben (z = x + y/5):

Note Prozentpunkte
1.0 z ≥ 95%
1.3 95% > z ≥ 90%
1.7 90% > z ≥ 85%
2.0 85% > z ≥ 80%
2.3 80% > z ≥ 75%
2.7 75% > z ≥ 70%
3.0 70% > z ≥ 65%
3.3 65% > z ≥ 60%
3.7 60% > z ≥ 55%
4.0 55% > z ≥ 50%
  • Um Bonuspunkte für die Klausur gutgeschrieben zu bekommen, muss im zugewiesenen Tutorium die Lösung zu einer Abgabe vorgestellt worden sein.
  • Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt; Lösungen müssen jedoch eigenständig aufgeschrieben werden, damit die erreichten Punkte anerkannt werden können!
  • Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet; jedem „Wiederholungstäter“ werden keinerlei Bonuspunkte für die Klausur angerechnet. Diese Regeln gelten auch für aus dem Internet abgeschriebene Lösungen.