RUB » LMI » Lehre » Datenstrukturen SS 2018

Datenstrukturen SS 2018

LVR-Nr: 150 322
Veranstaltung: Datenstrukturen
4-std.
Di, 14-16 Uhr, HNC 30
Do, 14-16 Uhr, HNC 30
Dozent: Hans U. Simon
Übungsgruppen: Gruppe 1: Di, 12-14 Uhr, NC 2/99 Daniel Pasler
Gruppe 2: Di, 12-14 Uhr, NB 3/99 - Rouven Lemmerz
Gruppe 3: Di, 16-18 Uhr, NA 2/99 - Lars Schlieper
Korrekteure: Rouven Lemmerz
Björn Hahn

Aktuelles

  • 05.02.2019: Die Ergebnisse der Nachklausur liegen vor. Sie sind bis zum 13. Februar abrufbar. Die Einsicht findet am 13. Februar um 13 Uhr in IB 3/147 statt (Voranmeldung bei Daniel Pasler).

    Sie haben das Recht, nach Ablauf der Aufbewahrungsfrist von 2 Jahren die Klausur ausgehändigt zu bekommen. Wenn Sie davon Gebrauch machen wollen, melden Sie Ihr Interesse innerhalb der sechs Monate vor Ablauf der Frist per Mail an Katharina.Weissman@rub.de mit dem Betreff „Klausurrückgabe“. Bitte nennen Sie in der Mail die Veranstaltung und das Datum, an dem die Klausur geschrieben wurde. Sie werden nach Ablauf der Aufbewahrungsfrist per Mail kontaktiert. Bitte beachten Sie, dass es nach Rücknahme der Klausur nicht erlaubt ist, diese zu veröffentlichen.

  • 25.10.2018: Die Nachschreibeklausur im Winter 2018/2019 findet am 4. Februar 2019 ab 10 Uhr in NB 02/99 statt. Für die Anmeldung zur Klausur gilt das Entsprechende wie für jene im Sommersemester.
  • 06.09.2018: Es wurden Anmerkungen zur Klausur hochgeladen, die sich auf häufige Fehler beziehen, die aufgetreten sind. Dadurch kann auch in Eurem Interesse der Klärungsbedarf bei der Einsicht am Montag möglicherweise reduziert werden.
  • 21.08.2018: Die Klausureinsicht findet am 10. September um 13 Uhr in NA 1/24 statt. Eventuell werden noch Anmerkungen zur Klausur hochgeladen, um häufige Fragen vorab zu klären.
  • 17.08.2018: Aus organisatorischen Gründen wird die Klausureinsicht wahrscheinlich doch schon im September stattfinden. Schaut regelmäßig nach, ob es hier eine Ankündigung gibt. Die PDF mit den Ergebnissen wird in der kommenden Woche offline sein. Die Ergebnisse sind weiterhin am Aushang auf NA 1 zu finden.
  • 14.08.2018: Die Klausurergebnisse liegen nun vor (Aushang auf NA 1). Ein Termin für die Einsicht wird demnächst noch bekanntgegeben. Diese wird aber auf jeden Fall in der ersten Semesterwoche des Wintersemesters 18/19 stattfinden.
  • 24.07.2018: Die Korrekturen zu Blatt 11 können nun bei Daniel in NA 1/69 abgeholt werden (für alle Übungsgruppen). Auch alle restlichen Abgaben befinden sich nun in NA 1/69. Bitte beachtet, dass wegen einer Klausuraufsicht am heutigen Dienstag das Büro NA 1/69 nur selten garantiert besetzt ist. Daher ist es empfehlenswert, erst am morgigen Mittwoch zu versuchen, die Abgaben abzuholen.
  • 13.07.2018: Aufgabe 11.3 war fehlerhaft formuliert. Dies ist nun korrigiert.
  • 10.07.2018: Statt der Übungen am 17. Juli bieten die Übungsgruppenleiter Sprechstunden zu den Zeiten in ihren Räumen an (s. Info-PDF). Die korrigierten Blätter 10 können ebenfalls ab dann beim jeweiligen Gruppenleiter abgeholt werden. Wann die korrigierten Blätter 11 abgeholt werden können, wird noch bekannt gegeben. Ebenfalls bieten die Übungsgruppenleiter bis zur Klausur am 27. Juli weiter ihre Sprechstunden an (s. Info-PDF). Auch Korrekteur Björn Hahn bietet seine Sprechstunden weiterhin an.
  • 06.07.2018: Die Vorlesung am 10. Juli ist die letzte, die stattfindet. Für Fragen zur Vorlesung steht Prof. Simon während der Vorlesungszeiten an den weiteren Terminen im Semester in seinem Büro zur Verfügung. Die Übung am 10. Juli ist ebenfalls die letzte, die stattfindet.
  • 04.07.2018: Das Zusatzmaterial zu Bucketsort/Radixsort wurde ergänzt.
  • 27.06.2018: Bei Blatt 9 hat es kleine sprachliche Verbesserungen gegeben.
  • 20.06.2018: Bei Aufgabe 8.1 gab es einen Fehler bzgl. der Grafik. Dieser ist nun korrigiert.
  • 13.06.2018: Hinweis zu Aufgabe 7.3: Bei beiden Explorationstechniken werden solange neue Suchen auf unbesuchten Knoten kleinster Markierung gestartet, bis alle Knoten besucht wurden. (s. S. 2/3 im Zusatzmaterial, "Im Hauptprogramm")
  • 07.06.2018: Bei Aufgabe 6.2 wurde ein Wortfehler korrigiert.
  • 17.05.2018: Bei Aufgabe 4.3 hat es eine Anpassung gegeben.
  • 25.04.2018: Die mündlichen Prüfungstermine für Mathematikstudierende sind nun ergänzt.
  • 24.04.2018: Die Sprechstunde von Rouven Lemmerz am 26. April fällt aus.
  • 20.04.2018: Eine Themenübersicht wurde nun angelegt. Zudem wurden Informationen zur Klausur ergänzt. Der Termin ist nun verfügbar.
  • 19.04.2018: Die Informationen zur Übung wurden nun aktualisiert. Beachtet, dass durch die Verlegung der Übung um 10 Uhr auch die Abgabeuhrzeit eine andere ist (12 Uhr statt 10 Uhr).
  • 16.04.2018: Die Übung von 10-12 Uhr findet ab dem 24. April von 12-14 Uhr in NC 2/99 statt. Am 17. April findet die Übung zum ursprünglichen Termin (s.o.) statt. Die Informationen zu den Übungen werden demnächst aktualisiert.

Materialien

Hier gibt es im laufenden Semester die Übungsblätter und weitere Materialien zur Vorlesung.

Hausaufgaben

Präsenzaufgaben

Folien zur Vorlesung und Ergänzungen der Literatur

Themenliste

Die Kapitelangaben beziehen sich, falls nicht anders angegeben, auf das Buch von Güting und Dieker. Die Java-Implementierungen spielen in der Vorlesung keine Rolle und können beim Selbststudium weggelassen werden.

  • 1. Woche : RAM, sowie allgemeine Einführung, Datentypen (Kapitel 1 und 2 + Skriptteil, außer 2.2)
  • 2. Woche : Zeigertypen, Listen, Stacks, Queues (Kapitel 2.2, 3.1-3.3)
  • 3. Woche : Abbildungen, binäre Bäume, allgemeine Bäume, Dictionaries (Rest Kapitel 3, dazu bis 4.2.1)
  • 4. Woche : Hashing (4.2.2 mit Ausnahme der Analyse des idealen, geschlossenen Hashings)
  • 5. Woche : Analyse des idealen Hashings (Kapitel 4.2.2)
  • 6. Woche : Binäre Suchbäume / AVL Bäume (Kapitel 4.2.3-4.2.4)
  • 7. Woche : Priority Queues / Mengenpartitionen, Merge-Find-Strukturen (Kapitel 4.3,4.4 (a))
  • 8. Woche : Fortsetzung Merge-Find-Strukturen / Graphexploration (Kapitel 4.4 (b), 5.1.1, 5.1.2 + Zusatzmaterial)
  • 9. Woche : Kürzeste Pfade (Kapitel 5.4,5.5), Transitive Hülle (Kapitel 5.6), Starke Komponenten (Kapitel 5.7)
  • 10. Woche: Ungerichtete Graphen, Minimaler Spannbaum, Einfache Sortierverfahren, Mergesort, Quicksort (Kapitel 5.8,5.9,6.1,6.2)
  • 11. Woche: Heapsort, Untere Schranke für allg. Sortierverfahren, Bucketsort/Radixsort (Kapitel 6.3, 6.4, 6.5 + Zusatz)
  • 12. Woche: Fortsetzung Bucketsort (Zusatz), Externes Suchen (Kapitel 8.1)
  • 13. Woche: Externes Sortieren (Kapitel 8.2)
  • 14. Woche: -

    • Klausurrelevant sind die Themen bis einschließlich Woche 12.

Informationen

Kommentar aus dem Vorlesungsverzeichnis

Für Studierende der Mathematik mit Nebenfach Informatik ist diese Vorlesung ein obligatorischer Bestandteil des B.Sc.. Bei Wahl des Schwerpunkts Informatik ist sie im B.Sc. zu empfehlen, da andere Vorlesungen auf ihr aufbauen. Weiterhin ist die Vorlesung in den Studiengängen "Angewandte Informatik" und "IT-Sicherheit" vorgesehen.

Nach einer Besprechung grundlegender Datentypen (wie Listen, Stacks, Queues und Bäume) werden zunächst Datenstrukturen diskutiert, die zur Repräsentation von Mengen geeignet sind und dabei bestimmte Mengenoperationen unterstützen (wie zum Beispiel Dictionaries, Priority Queues und UNION-FIND-Datenstruktur). Weiterhin gehen wir auf Repräsentationen von Graphen ein, behandeln diverse Graphalgorithmen (wie zum Beispiel Tiefen- und Breitensuche, kürzeste Wege, transitive Hülle, starke Komponenten und minimaler Spannbaum) sowie diverse Sortierverfahren (Mergesort, Heapsort, Quicksort, Bucketsort, Radixsort). Die Vorlesung soll die Fähigkeit schulen, bekannte Datenstrukturen professionell einzusetzen, neue Datenstrukturen bei Bedarf selbst zu entwerfen, die Korrektheit eines Algorithmus sauber zu begründen und seine Laufzeit zu analysieren.

Voraussetzungen

Die Kenntnis einer höheren Programmiersprache ist hilfreich, aber nicht im engeren Sinne erforderlich.

Literatur

Die Vorlesung orientiert sich hauptsächlich an der folgenden Quelle:
Güting & Dieker. Datenstrukturen und Algorithmen. Teubner.

Außerdem empfohlen:
Aho, Hopcroft & Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley.

Zu den Übungsaufgaben

Während der Vorlesungszeit wird jeden Dienstag ein neues Übungsblatt auf dieser Seite bereitgestellt. Die bearbeiteten Aufgaben sind am darauffolgenden Dienstag spätestens bis 12:00 Uhr abzugeben. Die Abgabekästen befinden sich auf NA 02 gegenüber von Raum 257. Die Abgabe soll nach Aufgaben getrennt erfolgen. Bitte auf jedes Blatt die Namen und die Übungsgruppe schreiben! Die korrigierten Blätter werden in den Übungen zurückgegeben.

Die Blätter können in Gruppen bis zu maximal drei Personen bearbeitet und abgegeben werden.

Einen Übungsschein erhält, wer mindestens die Hälfte der Punkte erreicht, mindestens einmal bei einem Übungsgruppenleiter vorrechnet und regelmäßig an den Übungen teilnimmt.

Die durch Übungsaufgaben erreichten Punkte werden anteilig auf die Abschlussklausur als Bonus angerechnet, wobei 100% der bei den Übungen maximal vergebenen Punkte 10% der bei der Abschlussklausur maximal vergebenen Punkten entsprechen. Dabei kann die maximal erreichte Punktezahl in der Abschlussklausur 100% nicht übersteigen. Dieser Bonus gilt nur für die Klausur im Sommersemester 2018 und nicht für Klausuren in späteren Semestern.

Zur Klausur

Die Abschlussprüfung wird in Form einer Semesterabschlussklausur erbracht. Dies gilt für alle Studierende, abgesehen von Studierenden, die die Vorlesung im Hauptfach des B.Sc. Mathematik belegen (s.u.: Mündliche Prüfungen). An der Klausur teilnehmen kann nur, wer sich fristgemäß bei dem für ihn zuständigen Prüfungsamt anmeldet. Bei Fragen hierzu wenden Sie sich direkt an Ihr zuständiges Prüfungsamt.

Die dreistündige Klausur wird am Freitag, den 27. Juli 2018 ab 14 Uhr in HZO 10 geschrieben. Als Hilfsmittel sind nur die unter Literatur angegebenen Bücher zugelassen, sowie alle zusätzlichen Materialien zur Vorlesung. Nicht gestattet sind Übungs-/Präsenzblätter oder Lösungen zu diesen.

Mündlichen Prüfungen (nur relevant für B.Sc. in Mathematik)

Für die Studierenden, die "Datenstrukturen" im Hauptfach des Bachelor of Science in der Mathematik belegen, wird am Ende des Semesters eine mündliche Prüfung angeboten. Hierfür stehen die folgenden beiden Termine zur Wahl:

  • 16.07.2018
  • 08.10.2018

Achtung: Bitte vereinbaren Sie vor der Prüfungsanmeldung zunächst mit Daniel Pasler Ihren Prüfungstermin mit Uhrzeit.

Die Anmeldung muss mindestens zwei Wochen vor der jeweiligen Prüfung per VSPL erfolgen. Ein Rücktritt von einer angemeldeten Prüfung muss mindestens drei Tage vor der Prüfung in schriftlicher Form ohne Angabe von Gründen im Prüfungsamt (Container N-Süd OG/37) erfolgen.

Kontakt