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
- Übungsblatt 01
- Übungsblatt 02
- Übungsblatt 03
- Übungsblatt 04
- Übungsblatt 05
- Übungsblatt 06
- Übungsblatt 07 (Aufgabe 7.1 aktualisiert: UNION(1,2,1) statt UNION(1,2,2))
- Übungsblatt 08
- Übungsblatt 09
- Übungsblatt 10
- Übungsblatt 11
- Übungsblatt 12
- Übungsblatt 13
Präsenzzettel
- Präsenzblatt 01
- Präsenzblatt 02
- Präsenzblatt 03
- Präsenzblatt 04
- Präsenzblatt 05
- Präsenzblatt 06
- Präsenzblatt 07
- Präsenzblatt 08
- Präsenzblatt 09
- Präsenzblatt 10
- Präsenzblatt 11
Folien zur Vorlesung/Ergänzungen zum Buch
- Algorithmen aus Kapitel 3 (Sorting and Order Statistics)
- Beispiele aus Kapitel 4 (Hashing, aus Datenstrukturen und Algorithmen)
Algorithmus aus Abschnitt 4.5 (Optimal binary search trees)- Algorithmus aus Abschnitt 4.5 (Optimal binary search trees) (aktualisiert)
- Implementierung aus Abschnitt 4.6 (UNION-FIND)
- Restliche Abbildungen/Algorithmen aus Kapitel 4
- Algorithmen aus Abschnitt 5.1, 5.2, 5.4
- Algorithmen aus Abschnitt 5.3 und 5.10
- Kürzeste Pfade
- Beispiele aus den Abschnitten 5.7 bis 5.10
- Algorithmus aus Abschnitt 9.3 (Recognition of substrings)
- Algorithmus und Beweis aus Kapitel 6 (Matrix Multiplication and Related Operations)
Ü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
- Hans U. Simon, NA 1/73
- Marius Konitzer, NA 1/35
- Sören Köpping, NA 1/36
- Sandra Pasucha
- Henrik Sie
- Jan Tekülve