Fakultät für Informatik
Lehrstuhl für Algorithm Engineering (Ls11)
Home Kontakt Deutsch English
Vorlesung SS06: Datenstrukturen, Algorithmen und Programmierung (DAP) 2

Datenstrukturen, Algorithmen und Programmierung (DAP) 2

(Vorlesung)

Sommersemester 2006

Prof. Dr. Petra Mutzel


Termine

Di 12:15 - 14:00, Campus Nord HG 3 / Audimax
Do 14:15 - 16:00, Campus Nord HG 3 / Audimax

Beginn: 04.04.2006

Klausur / Haupttermin

  • Termin: 21.07.2006, 14:00-16:00
  • Stoffumfang: Vorlesungsstoff mit Ausnahme von: externes Sortieren, Kapitel 7, Kapitel 8
  • Für die Klausur herrschte Anmeldepflicht. Die Einteilung in die verschiedenen Hörsäle erfolgte nach den Matrikelnummern.
  • Download: Klausurangabe
  • Einsichtnahme: Mittwoch, 30. August, 10:00-12:00, OH14, Seminarraum 2.02
  • SOPRA: Für die Studenten, die sich für SoPra angemeldet haben, die Klausur jedoch nicht bestanden haben findet eine zeitnahe Einsichtnahme statt: Fr. 4.August, 10:00-11:00 (Sem.Raum 2.02, OH14). Diese Einsichtnahme ist ausschliesslich für diese Studenten!
  • Klausurergebnisse:
    Von den 260 Teilnehmern haben 128 bestanden (49,2 Prozent).
    Gratulation an alle die die Klausur positiv bestanden haben, insbesondere an die beiden Studenten die uns (bei ihrem ersten Antritt!) bei der Korrektur mit 58 bzw. mit allen 60 Punkten besonders Freude gemacht haben!
    Download: Punkteschema, Ergebnisliste

Klausur / Nebentermin

  • Termin: 09.10.2006, 10:00-12:00
  • Stoffumfang: Vorlesungsstoff mit Ausnahme von Kapitel 7
  • Es herrschte Anmeldepflicht; man war nicht durch den ersten Antritt automatisch angemeldet! Die Einteilung in die verschiedenen Hörsäle erfolgte nach den Matrikelnummern.
  • Klausurangabe: Honolulu, Waikiki
  • Um bei der Einsichtnahme nicht alles vielfach erklären zu müssen: Lösungen und Anmerkungen zur Klausur. Wir möchten aber klarstellen, dass alle Angaben wie bei Lotto im Fernsehen ohne Gewähr sind ;-)
  • Klausurergebnisse:
    Von den 229 Teilnehmern haben leider nur 69 bestanden (30,1 Prozent).
    Gratulation an alle die die Klausur positiv bestanden haben; auch dieses Mal gab es zwei Studenten, die mit 58,5 und 56,5 Punkten herausragende Leistungen geboten haben.
    Download: Punkteschema, vorläufige Ergebnisliste
  • Reguläre Einsichtnahme: Die Einsichtnahme findet am Freitag, 10. November, von 10:00-12:00 in OH14, Seminarraum 2.02 statt.
  • Einsichtnahme für Zum-Dritten-Mal-Negativ: Für diejenigen, die die Klausur zum dritten Mal nicht bestanden haben (und nur für diese!) findet eine vorgezogene Einsichtnahme am Freitag, 27. Oktober, von 10:00-11:00 in OH14, Seminarraum 2.02 statt. Abhängig von eurer DPO steht euch eine mündliche Ergänzungsprüfung zu (zB bei Informatik, Physik,...). Details dazu werden ebenfalls beim Einsichtnahmetermin besprochen.
  • Mündliche Ergänzungsprüfungen: Anbei die Termine, aufgeschlüsselt nach Studiengang. Informatikstudenten werden einen Brief mit dem genauen Termin erhalten. Die betroffenen Physikstudenten mögen sich bitte, sofern sie es noch nicht getan haben, bei mir (markus.chimani (at) cs.uni-dortmund.de) melden!
    Wenn jemand seinen genauen Termin/Uhrzeit schon jetzt wissen möchte, genügt eine Mail an mich (von eurem Uni-Account aus!).
    Angewandte Informatik: Mo. 18.12. Nachmittag, Do. 21.12. Nachmittag.
    Kerninformatik: Di. 12.12., Do. 14.12., Di. 19.12., Do. 19.12. jeweils Vormittag; Mo. 11.12. Nachmittag
    Physik: Di. 19.12. Nachmittag.
    Diejenigen Studenten, die bei ihrem dritten Versuch angemeldet waren, nicht angetreten sind, und kein Attest vorgewiesen haben, mögen sich wegen ihrer Termine bei mir melden.

Inhalt

In der Vorlesung DAP1 stand der Entwurf von Software, also Programmierung und Eigenschaften von Programmen, im Vordergrund. Ein Softwareprodukt ist aber erst dann rundum gut, wenn es effizient arbeitet. Daher behandeln wir in der Vorlesung DAP2 Datenstrukturen und Entwurfsmethoden für effiziente Algorithmen.

Naive Lösungen algorithmischer Probleme können praktisch nutzlos sein, da die benötigten Ressourcen an Rechenzeit und/oder Speicherplatz nicht zur Verfügung stehen. Mit Hilfe des Einsatzes geeigneter Datenstrukturen und algorithmischer Methoden lassen sich viele algorithmische Probleme effizienter lösen. Diese Effizienz kann sich im praktischen Gebrauch erweisen und zuvor mit Experimenten belegt werden; besser ist jedoch ein Produkt mit Gütegarantie. Dies bedeutet den formalen Beweis, dass die Datenstruktur oder der Algorithmus das Gewünschte leistet, und die Abschätzung der benötigten Ressourcen. Daher gehören zu dieser Vorlesung stets auch Korrektheitsbeweise und Analysen.

Wie entwirft man nun für ein gegebenes Problem einen effizienten Algorithmus? Zunächst benötigen wir grundlegende Kenntnisse über das Gebiet, aus dem das Problem stammt. Dieses Wissen kann in späteren Spezialvorlesungen erlernt werden, oder es wird direkt bei der Bearbeitung des Problems erworben. In dieser grundlegenden Vorlesung werden wir nur solche Probleme behandeln, für die derartige Spezialkenntnisse nicht erforderlich sind. Darüber hinaus ist der Entwurf effizienter Algorithmen ein Handwerk, wobei Meisterleistungen nur mit viel Erfahrung, dem richtigen Gefühl für das Problem und einer Portion Intuition, manchmal auch Glück, erbracht werden. Ziel unserer Vorlesung muss es also sein, das notwendige Handwerkszeug bereitzustellen und dieses praktisch zu erproben.

Die von uns behandelten Probleme sind so ausgewählt, dass es sich einerseits um wichtige und interessante Probleme handelt und andererseits bei der Lösung dieser Probleme allgemeine Prinzipien und Methoden erlernt werden können.

Skript

Kapitel 1: Einführung (v.0.2.1)
Kapitel 2: Abstrakte Datentypen und Datenstrukturen (v.0.4)
Kapitel 3: Sortieren (v.0.5)
Kapitel 4: Suchen (v.0.2.1)
Kapitel 5: Hashing (v.0.4)
Kapitel 6: Graphen und Graphenalgorithmen (v.0.3)
Kapitel 7: Optimierung
Kapitel 8: Geometrische Algorithmen (v.0.6)

An den obigen Kapiteln werden von Zeit zur Zeit Veränderungen, insbesondere Ausbesserungen, vorgenommen. Daher sind sie auf der Titelseite mit einer Versionsnummer versehen. Details kann man dem CHANGELOG entnehmen.

Folien

Die Folien liegen als PDF vor, wahlweise mit einer Folie pro Seite (pdf-1) oder mit 6 Folien pro Seite (pdf-6).

1. Vorlesung(4. April) pdf-1 pdf-6
Asymptotik(6. April) pdf-1 pdf-6
ADT(11. April) pdf-1 pdf-6 Zusätzliche Folien
ADT / Sort (Ins., Sel., Merge)(13. April) pdf-1 pdf-6
Sort: Merge, Quick(18. April) pdf-1 pdf-6
Sort: Quick, Heap(20. April) pdf-1 pdf-6
Sort: Extern(25. April) pdf-1 pdf-6
Sort: untere Schr., linear(27. April) pdf-1 pdf-6
Binäre Suche(2. Mai) pdf-1 pdf-6
Binäre Suchbäume(9. Mai) pdf-1 pdf-6
AVL Bäume(11. Mai) pdf-1 pdf-6 AVL-Baum-Rotations-Animation
AVL / B-Bäume(16. Mai) pdf-1 pdf-6
B-Bäume (18. Mai) pdf-1 pdf-6
B-Bäume / Skiplisten (23. Mai) pdf-1 pdf-6
Skiplisten / Hashing(30. Mai) pdf-1 pdf-6
Hashing(1. Juni) pdf-1 pdf-6
Graphen: Intro(6. Juni) pdf-1 pdf-6
Graphen: DFS(8. Juni) pdf-1 pdf-6
Graphen: TopSort(13. Juni) pdf-1 pdf-6 TopSort-Animation
Graphen: Kruskal(20. Juni) pdf-1 pdf-6
Graphen: Prim, Dijkstra(22. Juni) pdf-1 pdf-6 Prim-Animation, Dijkstra-Animation
Graphen: APSP(27. Juni) pdf-1 pdf-6
Opt: Approx(29. Juni) pdf-1 pdf-6
Opt: Enum, B&B(4. Juli) pdf-1 pdf-6
Opt: Dyn. Programm.(6. Juli) pdf-1 pdf-6
Opt: Verbesserungsheur.(11. Juli) pdf-1 pdf-6
Geometrische Alg.(13. Juli) pdf-1 pdf-6

Literatur

Als weiterführende Literatur empfehlen wir eines der folgenden Bücher:

Robert Sedgewick: Algorithmen (2. Auflage, Pearson Studium 2002)
Sehr anschauliches und gut zu lesendes Buch. Sowohl auf Deutsch als auch auf Englisch erhältlich. Diese (aktuelle) Ausgabe beschreibt die Algorithmen - so wie wir es auch in der Vorlesung tun werden - mittels Pseudocode, und umfasst den gesamten Stoffumfang.
Es existieren vom selben Autor auch die sehr ähnlichen Werke "Algorithmen für C++", "Algorithmen für Java", etc. Doch Obacht! Die aktuellen Ausgaben dieser programmierspracheninkludierenden Bücher sind in 2 Bände (Band 1 = Teil 1-4, Band 2 = Teil 5) geteilt; in der Vorlesung behandeln wir den Stoff aus beiden Bänden!
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms (2nd Edition, MIT Press 2001)
Dieses Buch ist ausschliesslich auf Englisch verfügbar, stellt aber das wissenschaftliche Standardwerk auf diesem Gebiet dar. Es erklärt den Inhalt sehr schön und ausführlich.
T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen (4. Auflage, Spektrum Akademischer Verlag 2001)
Bietet ebenfalls einen sehr anschaulichen Einstieg in die Thematik.

Übung

Zur Vertiefung des Lerninhaltes bieten wir eine mit der Vorlesung synchronisierte Übung zu DAPII an.

<webmaster  ls11.cs.tu-dortmund.de>
Die Universität übernimmt keine Haftung für den Inhalt verlinkter externer Internetseiten