Datenstrukturen, Algorithmen, Programmierung 2 (DAP 2)

Grundvorlesung 4V + 2 Ü, Sommersemester 2007

Prof. Dr. Ingo Wegener / PD Dr. Martin Sauerhoff


[Inhalt] [Termine] [Skript und Folien] [Klausur] [Übungen]


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 unrealisierbar" 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 effizient lösen. Die Effizienz kann sich im praktischen Gebrauch erweisen und zuvor mit Experimenten belegt werden. Besser ist es jedoch, ein Produkt mit Gütegarantie herzustellen. Dies bedeutet den formalen Beweis, dass die Datenstruktur oder der Algorithmus das Gewünschte leistet (Korrektheitsbeweis), und Abschätzung der benötigten Ressourcen (Analyse). Daher gehören zu dieser Vorlesung stets auch Korrektheitsbeweise und Analysen der benötigten Ressourcen.

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 Umsetzung effizienter Algorithmen erfordert schließlich noch den Einsatz passender Datenstrukturen. Passende effiziente Datenstrukturen bilden also das Kernstück aller effizienten Algorithmen.

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. Da der zweite Aspekt auf lange Sicht der wichtigere ist, werden wir in Kapitel 1 mit zwei Problemen beginnen, deren Lösung sich nicht lohnen würde, wenn wir dabei nicht das allgemeine Vorgehen exemplarisch kennenlernen würden.

In diesem einführenden Kapitel werden, wie schon angesprochen, zwei exemplarische Probleme ausführlich gelöst. Um einen Bezugspunkt für die Messung von Rechenzeit und Speicherplatz zu haben, wird das Modell der Registermaschinen als Rechnermodell vorgestellt. Schließlich werden grundlegende Komplexitätsmaße diskutiert und der Gebrauch der O-Notation wiederholt und gerechtfertigt.

In Kapitel 2 werden Eigenschaften grundlegender Datenstrukturen wie Arrays, Stacks, Queues, Listen, Bäume und Graphen kurz wiederholt und wichtige komplexere Datenstrukturen mit ihren Eigenschaften vorgestellt.

In Kapitel 3 konzentrieren wir uns auf dynamische Datenstrukturen. Dies sind Datenstrukturen, bei denen die zu speichernde Datenmenge nicht statisch vorgegeben ist, sondern sich während der Anwendung dynamisch ändert. Operatinen wie das Einfügen und Entfernen von Daten müssen unterstützt werden. Die zwei wichtigsten Methodenklassen sind das Hashing und der Entwurf balancierter Suchbäume.

In Kapitel 4 wird das Problem, n Objekte zu sortieren, ausführlich behandelt. Sortieralgorithmen sind vermutlich die immer noch am häufigsten benutzten Unterprogramme. An diesem Problem werden wir exemplarisch zeigen, dass in der Umgebung paralleler Rechner andere Algorithmen effizient sind als in der Umgebung sequentieller Rechner.

Schließlich wenden wir uns in Kapitel 5 Entwurfsmethoden für effiziente Algorithmen zu. Dabei werden wir allgemeine Methoden kennenlernen und exemplarisch anwenden.

Bei vielen Optimierungsproblemen ist es naheliegend, die einzelnen Teile der Lösung lokal zu optimieren. Wir diskutieren, wann derartige greedy (gierige) Algorithmen zu optimalen oder zumindest guten Lösungen führen. Mit der dynamischen Programmierung wird der Gefahr begegnet, Teilprobleme wiederholt zu behandeln. Dagegen wird mit Branch-and-Bound Methoden versucht, den Suchraum gezielt so zu durchsuchen, dass auf die Untersuchung großer Bereiche verzichtet werden kann, weil bereits klar ist, dass dort keine optimalen Lösungen liegen. Divide-and-Conquer ist eine wohlbekannte Entwurfsmethode für Algorithmen. Nach einer allgemeinen Analyse dieses Ansatzes wollen wir etwas ausgefallenere Anwendungen kennenlernen: die Berechnung nächster Nachbarn in der Ebene, die Multiplikation quadratischer Matrizen und die FFT (Fast Fourier Transform), die in der Bild- und Signalverarbeitung grundlegend ist. Die Sweepline Technik, die viele Anwendungen in der algorithmischen Geometrie hat, wird mit einer Beispielanwendung vorgestellt. Die Methode des Backtracking ist sicherlich den meisten bekannt. Für eine effiziente Anwendung, z. B. in der Schachprogrammierung, ist es auch hier nötig, die Suche so zu gestalten, dass viele Bereiche des Suchraumes nicht näher betrachtet werden. Die Strategie des alpha-beta-Pruning wird diskutiert. Abschließend wird eine Einführung in randomisierte Suchheuristiken gegeben, dazu gehören die randomisierte lokale Suche, Simulated Annealing, Tabu Search und evolutionäre Algorithmen.


Termine

Wann? Wer? Wo?
Vorlesungen: Di 12.15 - 13.45 Ingo Wegener
Martin Sauerhoff
Audimax
Do 14.15 - 15.45 Ingo Wegener
Martin Sauerhoff
Audimax
Übungen:
Gruppe 1 Mo 14.15 - 15.45 Peter Bollweg GB 4, R 228
Gruppe 2 Mo 14.15 - 15.45 Stefan Droste OH 14, R 304
Gruppe 3 Mo 16.15 - 17.45 Peter Bollweg GB 4, R 228
Gruppe 4 Mo 16.15 - 17.45 Thomas Wilk OH 14, R 304
Gruppe 5 Di 14.15 - 15.45 Sylvie Temme GB 4, R 228
Gruppe 6 Di 16.15 - 17.45 Eike Riedemann GB 4, R 228
Gruppe 7 Mi 12.15 - 13.45 Eike Riedemann GB 4, R 228
Gruppe 8 Mi 12.15 - 13.45 Florian Schmoll GB 4, R 113
Gruppe 9 Mi 14.15 - 15.45 Mathias Schwarzhoff GB 4, R 113
Gruppe 10 Mi 14.15 - 15.45 Alexander Munteanu GB 4, R 228
Gruppe 11 Do 16.15 - 17.45 Björn Grothe GB 4, R 126
Gruppe 12 Do 16.15 - 17.45 Holger Willebrandt GB 4, R 228
Gruppe 13 Fr 10.15 - 11.45 Sariette Bille GB 4, R 228
Globalübung Fr 12.15 - 13.45 Stefan Droste OH 14, E23

Skript und Folien

Folien zu der Vorlesung findet man in folgendem Verzeichnis.

Das Skript zur Veranstaltung gibt es als PDF-Version.

Als eine kleine Hilfe zum Lernen gibt es hier eine Formelsammlung der wichtigsten in DAP2 verwendeten Formeln. Vielen Dank an Alexander Munteanu für die Erstellung dieser Sammlung!


Informationen zu der Klausur

Alte Klausuren aus den Jahren 2002 bis 2005 findet man unter folgenden Adressen:

http://ls2-www.cs.uni-dortmund.de/lehre/dap2klausuren/

http://ls2-www.cs.uni-dortmund.de/lehre/sommer2005/dap2/#Klausur

Die erste Klausur fand am 30. Juli ab 12:30 Uhr statt. Hier kann man sich die Kurzaufgaben und die Langaufgaben herunterladen. Die Ergebnisse der Klausur vom 30. Juli finden sich hier: http://ls2-www.cs.uni-dortmund.de/lehre/sommer2007/dap2/DAP2Klausur1 - Ergebnis.htm

Die zweite Klausur fand am 1. Oktober ab 9:45 Uhr statt. Hier kann man sich die Kurzaufgaben und die Langaufgaben herunterladen. Die Ergebnisse der Klausur vom 1. Oktober finden sich hier: http://ls2-www.cs.uni-dortmund.de/lehre/sommer2007/dap2/DAP2Klausur2 - Ergebnis.htm

Die Einsicht in die Klausur findet am 26. Oktober von 13 bis 15 Uhr im Raum 304 im Gebäude Otto-Hahn-Str. 14 statt.


Übungen

Die Übungsblätter werden jeweils am Dienstag bis zu der Vorlesung ausgegeben. Die Bearbeitungen der Übungsaufgaben sind bis zum folgenden Montag, 12 Uhr, abzugeben.

Die Einteilung in die Übungsgruppen gibt es hier.

  • Blatt 0:   PDF-Format
    (Ausgabe: 3.04., Abgabe: keine Abgabe)
  • Blatt 1:   PDF-Format
    (Ausgabe: 10.04., Abgabe: 16.04.)
  • Blatt 2:   PDF-Format
    (Ausgabe: 17.04., Abgabe: 23.04.)
  • Blatt 3:   PDF-Format
    (Ausgabe: 24.04., Abgabe: 30.04.)
  • Blatt 4:   PDF-Format
    (Ausgabe: 30.04., Abgabe: 07.05.)
  • Blatt 5:   PDF-Format
    (Ausgabe: 08.05., Abgabe: 14.05.)
  • Blatt 6:   PDF-Format
    (Ausgabe: 15.05., Abgabe: 21.05.)
  • Blatt 7:   PDF-Format
    (Ausgabe: 22.05., Abgabe: 29.05.)
  • Blatt 8:   PDF-Format
    (Ausgabe: 29.05., Abgabe: 04.06.)
  • Blatt 9:   PDF-Format
    (Ausgabe: 05.06., Abgabe: 11.06.)
  • Blatt 10:   PDF-Format
    (Ausgabe: 12.06., Abgabe: 18.06.)
  • Blatt 11:   PDF-Format
    (Ausgabe: 19.06., Abgabe: 25.06.)
  • Blatt 12:   PDF-Format
    (Ausgabe: 26.06., Abgabe: 02.07.)
  • Blatt 13:   PDF-Format
    (Ausgabe: 03.07., Abgabe: 10.07. Dieses Blatt ist für die Scheinvergabe nicht relevant.)
Java-Programme zu einigen der Übungsaufgaben finden sich in folgendem Verzeichnis.

Ansprechpartner bezüglich der Übungen ist Stefan Droste.