Department of Computer Science
Chair of Algorithm Engineering (Ls11)
Home Contact Deutsch English
menu-en
Vorlesung SS08: Datenstrukturen, Algorithmen und Programmierung (DAP) 2

Datenstrukturen, Algorithmen und Programmierung (DAP) 2

Vorlesung im Modul INF-BA-104

Sommersemester 2008

Prof. Dr. Petra Mutzel


Termine

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

Beginn: 08.04.2008

Teilnahmevoraussetzungen

Voraussetzung für die Teilnahme an dieser Veranstaltung sind gute Programmierkenntnisse in Java (oder C++), wie sie im Programmierpraktikum zu DAP1 vermittelt wurden.

Die erfolgreiche Teilnahme an der Übung zu DAP2 ist Voraussetzung für die Teilnahme an der Modulprüfung (Klausur).

Klausur / Haupttermin

  • Termin: 25.07. 9:00 - 10:30 Uhr
  • Stoffumfang: Der gesamte Stoff der Vorlesung bis auf das Kapitel zur Optimierung
    (Skript: Kapitel 1 bis 6 einschließlich, ohne Abschnitt 3.3 Externes Sortieren)
  • Die Hörsaaleinteilung erfolgt nach Matrikelnummern:
    • 000000 bis 116199: Audimax
    • 116200 bis 122999: HS1 HG2
    • 123000 bis 999999: HS6 HG2
  • Klausurangaben: Gruppe Oahu, Gruppe Maui
  • Ergebnisse [.txt]
    Die Liste enthält jeweils Matrikelnummer, Punktzahl und Note. Von 300 Teilnehmern haben 260 (86,7%) bestanden. Zum Bestehen waren 25 von 50 Punkten notwendig. Die durchschnittliche Punktzahl liegt bei 32,9 Punkten und die durchschnittliche Note bei 2,8.
  • Die Klausureinsicht fand am 9. September in R202 OH14 statt.
    • Matr.-Nr. bis 116199: 8:00-9:45 Uhr
    • Matr.-Nr. ab 116200 + Schüler: 10:00-12:00 Uhr

Klausur / Nebentermin

  • Termin: 06.10. 14:00 - 15:30 Uhr
  • Stoffumfang: Der gesamte Stoff der Vorlesung
    (Skript: Kapitel 1 bis 7 einschließlich, ohne Abschnitt 3.3 Externes Sortieren)
  • Die Klausur findet für alle im Audimax statt.
  • Klausurangabe
  • Ergebnisse [.txt]
    Die Liste enthält jeweils Matrikelnummer, Punktzahl und Note. Von 55 Teilnehmern haben 26 (47,3%) bestanden. Zum Bestehen waren 25 von 50 Punkten notwendig. Die durchschnittliche Punktzahl liegt bei 22,6 Punkten und die durchschnittliche Note bei 4,2.
  • Die Klausureinsicht fand am 10. November in R202 OH14 von 10:00-12:00 Uhr statt.

Scheine

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

Das Skipt kann hier (Version 1.0) heruntergeladen werden. Änderungen in neuen Versionen des Skripts können im Changelog nachvollzogen werden.

Folien

Die Vorlesungsfolien gibt es als pdf, jeweils mit einer Folie / Blatt oder 6 Folien / Blatt.

Einführung (08.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Asymptotische Schranken (10.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Abstrakte Datentypen und Datenstrukturen (15.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Einführung Sortieren (17.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Merge-Sort (22.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Quick-Sort (24.04.): [1 Folie/Blatt] [6 Folien/Blatt]
Heap-Sort (29.04.): [1 Folie/Blatt] [6 Folien/Blatt] Animation [.pps]
Lineare Sortierverfahren (08.05.): [1 Folie/Blatt] [6 Folien/Blatt]
Heap-Sort und Priority Queues (13.05.): [1 Folie/Blatt] [6 Folien/Blatt]
Binäre Suche (15.05.): [1 Folie/Blatt] [6 Folien/Blatt]
Binäre Suchbäume (20.05.): [1 Folie/Blatt] [6 Folien/Blatt]
AVL-Bäume (27.05.): [1 Folie/Blatt] [6 Folien/Blatt] Animation [.pps]
B-Bäume (03.06.): [1 Folie/Blatt] [6 Folien/Blatt]
B-Bäume (Fortsetzung) (03./05.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Skiplisten (05./10.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Hashing (12./17.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Graphen (17.06.): [1 Folie/Blatt] [6 Folien/Blatt]
DFS (19.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Topologisches Sortieren, MST (24.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Kruskal's Algorithmus (26.06.): [1 Folie/Blatt] [6 Folien/Blatt]
Prim's Algorithmus (01.07.): [1 Folie/Blatt] [6 Folien/Blatt]
Kürzeste Wege (03.07.): [1 Folie/Blatt] [6 Folien/Blatt] Animation [.pps]
Optimierung (Einführung) (08.07.): [1 Folie/Blatt] [6 Folien/Blatt]
Heuristiken und approximative Algorithmen (10.07.): [1 Folie/Blatt] [6 Folien/Blatt]
Enumerationsverfahren, Branch-and-Bound (15.07.): [1 Folie/Blatt] [6 Folien/Blatt]
Verbesserungsheuristiken (17.07.): [1 Folie/Blatt] [6 Folien/Blatt]

Literatur

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

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Algorithmen - Eine Einführung (2. Auflage, Oldenbourg Verlag 2007)
Dieses Buch gilt als Standardwerk auf dem Gebiet Datenstrukturen und Algorithmen. Es erklärt die Themen sehr schön und ausführlich und kann auch über den Stoffumfang von DAP2 hinweg als Nachschlagewerk dienen.

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 sehr ähnliche Werke für bestimmte Programmiersprachen, z.B. "Algorithmen in C++". Doch Vorsicht! Diese 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. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen (4. Auflage, Spektrum Akademischer Verlag 2002)
Bietet ebenfalls einen sehr anschaulichen Einstieg in die Thematik.

A. Levition: Introduction to the Design and Analysis of Algorithms (2nd Edition, Addison Wesley 2006)
Dieses Buch legt den Schwerpunkt auf den Entwurf von Algorithmen und beschreibt verschiedene Entwurfstechniken ausführlich an Hand von Algorithmen, die die jeweilige Technik benutzen.

Begleitende Veranstaltungen

Zur Vertiefung des Stoffs von DAP2 findet die Übung zu DAP 2, sowie das Programmierpraktikum zu DAP2 statt.

Imprint
<webmaster  ls11.cs.tu-dortmund.de>
The university does not accept liability for the contents of linked external internet sites