RUB » LMI » Lehre » Datenstrukturen SS 2015

Datenstrukturen SS 2015

LVR-Nr: 150 322
Veranstaltung: Datenstrukturen
4-std.
Di, 16-18 Uhr, HZO 60
Do, 14-16 Uhr, HNC 30
Dozent: Hans U. Simon
Übungsgruppen: Gruppe 1: Di, 12-14 Uhr, NA 3/99 - Christoph Ries
Gruppe 2: Di, 12-14 Uhr, NA 5/99 - Henrik Sie
Gruppe 3: Mi, 8-10 Uhr, NA 5/99 - Malte Darnstädt

Für den Besuch der Übungen ist eine Anmeldung via Blackboard erforderlich.
Korrekteure: Chris Scharpenberg, Sprechstunde: Do, 13-14 Uhr, NA 1/31
Svenja Patricia Wienen, Sprechstunde: Fr, 11-12 Uhr, NA 4/58

Materialien

Hausaufgaben

Präsenzaufgaben

Folien zur Vorlesung und Ergänzungen der Literatur

Themenliste

Die Kapitelangaben beziehen sich, falls nicht anders angegeben, auf das Buch von Aho, Hopcroft und Ullman (siehe "Literatur").

  • 1. Woche (KW 15): RAM und Komplexität von RAM-Programmen (Kurzfassung der Abschnitte 1.2 und 1.3), Listen, Warteschlangen, Stapel, Mengenrepräsentation, Graphen, Bäume (Abschnitte 2.1 bis 2.4)
  • 2. Woche (KW 16): Laufzeitanalyse, Rekursion (Kurzfassung des Abschnitts 2.5), Bucket Sort, Lexicographic Sort (Abschnitte 3.1 und 3.2)
  • 3. Woche (KW 17): Radix sorting, Sorting by comparisons, Heapsort (Abschnitte 3.2 bis 3.4)
  • 4. Woche (KW 18): Mergesort (Abschnitt 2.7), Quicksort, Order Statistics, Expected Time for Order Statistics (Abschnitte 3.5 bis 3.7), Data Structures for Set Manipulation Problems (ohne passende Literaturangabe)
  • 5. Woche (KW 19): Hashing (Abschnitt 4.2.2 des Buchs von Güting und Dieker)
  • 6. Woche (KW 20): Binary search, Binary search trees (Abschnitte 4.3 und 4.4), Optimal binary search trees (Erster Teil des Abschnitts 4.5)
  • 7. Woche (KW 21): Optimal binary search trees (Rest des Abschnitts 4.5), Union-Find-Datenstrukturen (Abschnitt 4.6 und 4.7)
  • 8. Woche (KW 23): Anwendungen der Union-Find-Datenstruktur (Erster Teil des Abschnitts 4.8)
  • 9. Woche (KW 24): Anwendungen der Union-Find-Datenstruktur (Rest des Abschnitts 4.8), Balanced tree schemes, Dictionaries and priority queues, Mergeable Heaps, Concatenable queues (Abschnitte 4.9 bis 4.12)
  • 10. Woche (KW 25): Partitioning, Minimum-cost spanning trees, Depth-first search (Abschnitte 4.13, 5.1 und 5.2)
  • 11. Woche (KW 26): Biconnectivity, Depth-first search of a directed graph (Abschnitte 5.3 und 5.4), Starke Komponenten (Abschnitt 5.7 des Buchs von Güting und Dieker)
  • 12. Woche (KW 27): Path-finding problems, A transitive closure algorithm, A shortest-path algorithm, Path problems and matrix multiplication (Abschnitte 5.6 bis 5.9)
  • 13. Woche (KW 28): Single Source Shortest Path (PDF "Kürzeste Pfade", siehe "Materialien"), Dominators in a directed acyclic graph (Abschnitt 5.11)
  • 14. Woche (KW 29): ---

Die Themen der 13. Woche sind nicht klausurrelevant.

Beachten Sie auch die auf Blackboard verfügbaren Videoaufzeichnungen.

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:
Aho, Hopcroft & Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley.

Außerdem empfohlen:
Güting & Dieker. Datenstrukturen und Algorithmen. Teubner.

Zu den Übungsaufgaben

Zur Teilnahme am Übungsbetrieb ist eine Anmeldung über Blackboard erforderlich. Die Anmeldung wird voraussichtlich am 08. April freigeschaltet.

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. Jedes Gruppenmitglied muss aber in der Lage sein, die Aufgaben vorzurechnen.

Einen Übungsschein erhält, wer mindestens die Hälfte der Punkte erreicht, mindestens einmal 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 2015 und nicht für Klausuren in späteren Semestern.

Zur Nachklausur

Die 180-minütige Wiederholungsklausur findet am Dienstag, den 16. Februar 2016 um 13 Uhr im Hörsaal HIC statt. Bitte beachten Sie, dass für diese Klausur keine Bonuspunkte aus Übungsaufgaben angerechnet werden!

Als Hilfsmittel sind ausschließlich die beiden unter "Literatur" genannten Bücher, eine geheftete Vorlesungsmitschrift, sowie die auf dieser Webseite veröffentlichten Ergänzungen zu den Büchern zugelassen. Insbesondere sind Taschenrechner sowie Übungsblätter, Präsenzblätter und deren Lösungen nicht gestattet.

Die Teilnahme an der Klausur ist nur nach vorheriger Anmeldung möglich. Die Anmeldung zur Klausur erfolgt nach den Regeln und Fristen des für Sie zuständigen Prüfungsamtes. Wenden Sie sich bei Fragen hierzu am besten direkt an Ihr Prüfungsamt.

Zu 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:

  • Mittwoch, der 22. Juli 2015
  • Mittwoch, der 14. Oktober 2015

Achtung: Bitte vereinbaren Sie vor der Prüfungsanmeldung zunächst mit Henrik Sie 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 (NA 02/73) erfolgen.

Kontakt