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.