RUB » LMI » Lehre » Datenstrukturen SS 2019

Datenstrukturen SS 2019

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, IA 1/53 - Christoph Ries
Gruppe 2: Di, 12-14 Uhr, NB 3/99 - Daniel Pasler
Gruppe 3: Di, 12-14 Uhr, NC 2/99 - Leonie Ryvkin
Gruppe 4: Di, 16-18 Uhr, NC 3/99 - Leonie Ryvkin
Korrekteur: Lukas Steenvoort

Aktuelles

  • 04.02.20: Die Ergebnisse der Klausur sind nun verfügbar bis zum Ende dieses Monats unter dem Link https://www.ruhr-uni-bochum.de/lmi/lehre/ds_ss19/erg/<Ziffern>.txt. Statt <Ziffern> sind die letzten fünf Ziffern der eigenen Matrikelnummer einzusetzen. Die Klausureinsicht findet am Montag, den 10.02.2020, um 11 Uhr s.t. in IB 3/147 statt. Eine Voranmeldung ist erwünscht.
  • 28.10.19: Der Termin für die Nachschreibklausur steht fest - siehe Unterpunkt "Zur Klausur".
  • 17.07.19: Um die häufigsten Fragen bei der Einsicht zu vermeiden, sind einige Hinweise zu Fehlern hier bis zum Ende dieses Monats zu finden.
  • 17.07.19: Die Ergebnisse der Klausur sind nun verfügbar bis zum Ende dieses Monats unter dem Link https://www.ruhr-uni-bochum.de/lmi/lehre/ds_ss19/ergebnisse/<Ziffern>.txt. Statt <Ziffern> sind die letzten fünf Ziffern der eigenen Matrikelnummer einzusetzen.

    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.

  • 16.07.19: Die Klausureinsicht findet am Donnerstag den 25. Juli 2019 um 13:30 Uhr in IA 1/53 statt. (An dieser Stelle wird bis Mittwoch noch ein Dokument hochgeladen, in dem einige der häufigsten Fehler aufgelistet sein werden). Zudem wird die Ergebnisliste bald hochgeladen.
  • 04.07.19: Die Vorlesung fällt in der letzten Vorlesungswoche aus.
  • 25.06.19: Zu den Präsenzblättern 11 und 12 wird es kein Übungsblatt geben.
  • 28.05.19: Die Übungsgruppen 3 und 4 entfallen heute wegen Krankheit!
  • Der Raum der Übungsgruppe 4 hat sich geändert (nun NC 3/99).
  • Auf Blatt 3 hat es zwei Fehlerkorrekturen gegeben! (Aufgaben 2 und 3)
  • Der Klausurtermin steht fest. Siehe Unterpunkt "Zur Klausur".
  • Der Termin für die mündliche Prüfung steht fest. Siehe Unterpunkt "Mündliche Prüfungen".
  • Bitte nicht vergessen den Namen, die Matrikelnummer, sowie die Übungsgruppennummer auf die Abgabenzettel zuschreiben! Die Abgabe kann in Dreiergruppen erfolgen.
  • Es wurden Angaben zur Übung ergänzt, sowie Literatur aktualisiert. Prüfungstermine werden bald festgelegt.
  • Die Vorlesung beginnt am 02. April, der Übungsbetrieb eine Woche später.

Materialien

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

Hausaufgaben

Präsenzaufgaben

Skript

Das Skript zur Vorlesung ist hier zu finden.

Themenliste

Die Abkürzungen stehen für die entsprechende Lehrliteratur (s. Punkt Literatur bzw. Folien zur Vorlesung)

1. Woche Interval Scheduling (Skriptteil + [AD] Kap. 4.1, S.116-122)
Asymptotik + RAM-Modell (Skriptteil Grundlagen 1)
2. Woche Intervall–Färbungsproblem (Skriptteil), Minimierung von Verspätungen (Skriptteil)
Fortführung RAM, Laufzeit + Listen als Arrays (Skriptteil Grundlagen 2)
3. Woche Minimierung von Cache-Fehlern (Skriptteil)
Korrektheitsnachweise (Skriptteil Grundlagen 3)
4. Woche Huffman-Code und Datenkompression (Skriptteil)
Binäre Suchbäume ohne Rebalancierung (Skriptteil Grundlagen 4)
5. Woche Mergesort (Skriptteil)
AVL-Bäume ([DA] Kap. 4.2.4)
6. Woche Paare von Punkten mit minimaler Distanz (Skriptteil)
Priority Queues ([DA], Kap. 4.3)
Union-Find-Strukturen ([CA], Kap. 4.6)
7. Woche Interval-Scheduling mit Gewichten (Skriptteil)
Union-Find (Baumimplementierung) ([CA], Kap. 4.7),
(Di-)Graphen und ihre Darstellung ([DA], Kap. 5.1,5.2)
8. Woche Minimale Spannbäume (Skriptteil)
Graphexploration (Skriptteil Grundlagen 5)
9. Woche Clustering (Skriptteil)
10. Woche Kürzeste Pfade (Skriptteil)
Starke Komponenten ([DA], Kap. 5.7)
11. Woche Sortieren mit Schlüsselvergleichsverfahren (Skriptteil)
12. Woche Sortieren durch Fachverteilung (Skriptteil)
Hashing Teil I ([DA], Kap. 4.2.2)
13. Woche Hashing Teil II ([DA], Kap. 4.4.2)

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.
Parallel werden weitere effiziente Algorithmen behandelt.

Voraussetzungen

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

Literatur

Die Vorlesung orientiert sich hauptsächlich an folgenden Quellen:

[DA] Güting & Dieker. Datenstrukturen und Algorithmen. Teubner.

[AD] Kleinberg, Tardos. Algorithm Design. Addison-Wesley.

[CA] Aho, Hopcraft, Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley.

Weitere Literaturhinweise werden in der Vorlesung gegeben.

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 Uhr (s.t.) abzugeben. Die Abgabekästen befinden sich auf IB 01 direkt rechts am Eingang. Die Abgabe soll nach Aufgaben getrennt erfolgen. Bitte auf jedes Blatt die Namen, die Matrikelnummern 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 2019 und nicht für Klausuren in späteren Semestern.

Der Korrekteur ist Lukas Steenvoort, lukas.steenvoort@rub.de (Sprechstunde: nach Vereinbarung).

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 Montag, den 08. Juli 2019, ab 12 Uhr in HZO 20 geschrieben. Als Hilfsmittel sind nur die unter Literatur angegebenen Bücher zugelassen, sowie alle zusätzlichen, auf dieser Homepage veröffentlichten Materialien zur Vorlesung. Nicht gestattet sind Übungs-/Präsenzblätter oder Lösungen zu diesen.

Die dreistündige Nachschreibklausur findet am Montag, den 03. Februar 2020, ab 10 Uhr in HZO 80 statt. Es gibt keinen Bonus. Ansonsten gelten dieselben Regeln wie bei der ersten Klausur oben beschrieben.

Mündliche 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. Der Termin ist Dienstag, der 09. Juli 2019.

Achtung: Vor der Prüfungsanmeldung ist zunächst mit Christoph Ries der Prüfungstermin mit Uhrzeit zu vereinbaren.

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 (IB 1/111) erfolgen.

Kontakt