RUB » LMI » Lehre » Datenstrukturen SS 12

Datenstrukturen SS 2012

LVR-Nr: 150 322
Veranstaltung: Datenstrukturen
4 std.
Di 14.00-16.00, HIA
Do 14.00-16.00, HMA 20
Dozent: Hans U. Simon
Übungsgruppen: Gruppe 1: Di 12.00-14.00, NC 6/99 (Konitzer)
Gruppe 2: Di 12.00-14.00, NA 5/99 (Köpping)
Gruppe 3: Mi 08.00-10.00, NA 01/99 (Konitzer)
Gruppe 4: Mi 08.00-10.00, NA 02/99 (Köpping)
Die Übungen am 03. und 04. April finden nicht statt.
Korrektur: Sandra Pasucha, Sprechstunde Mi 14.00-15.00 NA 1/31
Henrik Sie, Sprechstunde Mi 10.00-11.00 NA 1/31
Jan Tekülve, Sprechstunde Mi 14.00-15.00 NA 1/31
Anmeldung zur Klausur: schriftlich im Prüfungsamt (bitte Fristen beachten!)

News

18.03.2013: Ergebnisse der Wiederholungsklausur

Die Ergebnisse zur Wiederholungsklausur vom 18. März 2013 sind am Schwarzen Brett einsehbar. Die Klausureinsicht findet statt am 8. April, 18:00 bis 19:00 Uhr in NA 1/58.

28.01.2013: Wiederholungsklausur

Die 90 minütige Wiederholungsklausur findet am 18. März 2013 von 9:00 bis 11:00 Uhr s.t. im HID statt. Bitte informieren Sie sich rechtzeitig bei ihrem jeweiligen Prüfungsamt über die Anmeldungsmodalitäten.

19.11.2012: Wiederholungsklausur

Die 90 minütige Wiederholungsklausur findet am 18. März 2013 statt. Raum und Zeit werden rechtzeitig hier und per Aushang bekannt gegeben.

21.08.2012: Klausurergebnisse

Die Ergebnisse zur Klausur vom 16. August 2012 sind am Schwarzen Brett einsehbar. Die Klausureinsicht findet statt am 30. August, 13:00 bis 14:00 Uhr in NA 1/58.

13.07.2012: Unbenotete Übungsscheine

Studierende, die sich in den Übungen für einen unbenoteten Übungsschein angemeldet haben, können diesen voraussichtlich ab Mitte nächster Woche bei Frau Weissmann abholen.

13.07.2012: Bonuspunkteliste

Die Bonuspunkteliste ist online. Insgesamt konnten in den Hausaufgaben 246 Punkte erreicht werden.

12.07.2012: Nichtabgeholte Übungsblätter

Noch nicht abgeholte Übungsblätter können dienstags bis freitags von 8:30 bis 12:30 Uhr im Sekretariat bei Frau Weissmann (NA 1/72) abgeholt werden.

04.07.2012: Klausuranmeldung über VSPL

Für Studierende der Mathematik kann die Anmeldung zur Klausur am 16. August ab dem 1. Juli über VSPL erfolgen. Anmeldeschluss ist der 1. August.

06.06.2012: Mündliche Prüfungen

Die mündlichen Modul-9c-Prüfungen für Mathematiker finden am 18. Juli 2012 statt. Anmeldungen sind in den Übungen am 19., 20., 26. oder 27. Juni möglich. Beachten Sie, dass zudem bis zwei Wochen vor der Prüfung eine Anmeldung im Prüfungsamt Mathematik erforderlich ist.

13.04.2012: Klausur

Die Uhrzeit und die Räume für die Klausur stehen fest.

05.04.2012: VSPL-Anmeldung zur Abgabe von Übungsblättern

Bitte melden Sie sich bis zum Abgabeschluss des ersten Übungsblatts am 17.04. über VSPL für die Übungen zu Datenstrukturen (150323) an.

Inhalt

Nach einer Beprechung grundlegender Datentypen (wie Listen, Stacks, Queues, Bäume) werden zunächst Datenstrukturen diskutiert, die zur Representation von Mengen geeignet sind und dabei bestimmte Mengenoperationen unterstützen (wie zum Beispiel Dictionaries, Priority Queues, 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 professional einzusetzen, neue Datenstrukturen bei Bedarf selber zu entwerfen, die Korrketheit eines Algorithmus sauber zu begründen, und seine Laufzeit zu analysieren.

Vorkenntnisse

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

Literatur

Als begleitende Literatur sind die folgenden Bücher sehr zu empfehlen:

  • Güting, Ralf Hartmut und Dieker, Stefan. Datenstrukturen und Algorithmen. Stuttgart [u.a.]: Teubner.
  • Aho, Hopcroft und Ullman. The design and analysis of computer algorithms. Reading, Mass. [u.a.]: Addison-Wesley.

Themenliste

Die Kapitelangaben beziehen sich meistens auf das Buch von Aho, Hopcroft und Ullman.

  • 1. Woche: ausgewählte Themen aus Kapitel 1 und 2
  • 2. Woche: Radixsort, Graphen, Bäume und Rekursion (Kapitel 2 und 3)
  • 3. Woche: Mergesort, Heapsort und Quicksort (Kapitel 3)
  • 4. und 5. Woche: Order Statistics (Abschnitt 3.6 und 3.7) und Hashing (Abschnitt 4.1 und 4.2 in Datenstrukturen und Algorithmen)
  • 6. Woche: Binary Search Trees, Optimal Binary Search Trees (Abschnitt 4.3, 4.4 und 4.5)
  • 7. Woche: Union-Find-Datenstruktur (Abschnitt 4.6 und 4.7)
  • 8. Woche: Anwendung der Union-Find-Datenstruktur (Abschnitt 4.8), 2-3-Baum und Mergeable Heap (Abschnitt 4.9 bis 4.11)
  • 9. Woche: Concatenable Queues und Partitioning (Abschnitt 4.12 und 4.13)
  • 10. Woche: Kruskal und DFS (Abschnitt 5.1, 5.2 und 5.4)
  • 11. Woche: zweifach zusammenhängende Komponenten (Abschnitt 5.3) und starke Komponenten (Abschnitt 5.7 in Datenstrukturen und Algorithmen)
  • 12. Woche: kürzeste Pfade (siehe Material) und Path problems and matrix multiplication (Abschnitt 5.9)
  • 13. Woche: String-Matching (Abschnitt 9.3) und Segmentschnittproblem (Abschnitte 7.1.1 und 7.2.1 in Datenstrukturen und Algorithmen)
  • 14. Woche: Matrix Multiplication and Related Operations (Kapitel 6)

Klausurrelevant sind die Themen der 1. bis 12. Woche.

Materialien

Hausaufgaben

Präsenzzettel

Folien zur Vorlesung/Ergänzungen zum Buch

Übungsaufgaben

Während der Vorlesungszeit wird jeden Montagnachmittag 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 2012 und nicht für Klausuren in späteren Semestern.

Klausur

Die Klausur findet am 16. August 2012 von 09:00 bis 10:30 Uhr s.t. im HNA statt.

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 und deren Lösungen nicht gestattet.

Alle Klausurteilnehmer melden sich bei dem Prüfungsamt ihrer eigenen Fakultät nach den dort geltenden Regeln und Fristen an (und ggf. ab). Bei Fragen zur Anmeldung bitte auch an das zuständige Prüfungsamt wenden.

Kontakt