Algorithmen und Datenstrukturen - Eine Einführung mit Java

8 Entwurf von Algorithmen (S. 205-206)

Der Entwurf von Algorithmen und damit von Programmen ist eine konstruktive und kreative Tätigkeit, die den Entwerfer immer wieder vor neue Herausforderungen stellt – neben der reinen Funktionalität sind ja auch Fragen der Laufzeitkomplexität und andere, nichtfunktionale Anforderungen zu berücksichtigen. Wir hatten ja bereits gesehen, dass die automatische Ableitung eines optimalen Algorithmus aus einer Beschreibung der Anforderungen prinzipiell nicht automatisierbar ist. Inhalt dieses Abschnitts kann es daher nur sein, anhand von Beispielen Prinzipien des Entwurfs und einige typische Muster für Algorithmen vorzustellen. Derartige »best practice«-Beispiele helfen dem Entwerfer, brauchbare Erfahrungen für das Angehen neuer Probleme zu sammeln. Nach einer allgemeinen Diskussion von Entwurfsprinzipien werden wir vier typische Algorithmenmuster vorstellen: Greedy- Algorithmen, Divide-and-Conquer, Backtracking und dynamische Programmierung.

8.1 Entwurfsprinzipien
In den vorherigen Kapiteln haben wir quasi nebenbei schon einige Techniken angewendet, die beim praktischen Entwurf von Programmen hilfreich sind. Drei der wichtigsten dieser Techniken werden wir noch einmal kurz rekapitulieren: die schrittweise Verfeinerung, den Einsatz von Algorithmenmustern und Problemreduzierung durch Rekursion.

8.1.1 Schrittweise Verfeinerung

Die Vorgehensweise der schrittweisen Verfeinerung hatten wir bereits bei der ersten Diskussion des intuitiven Algorithmenbegriffs anhand von Pseudocode-Algorithmen kennen gelernt. Diese Verfeinerung basiert auf dem Ersetzen von Pseudocodeteilen durch verfeinerten Pseudocode und letztendlich durch konkrete Algorithmenschritte bzw. Programmiersprachencode.

In der Terminologie der Programmierung entspricht der Verfeinerungsschritt der Formulierung von Algorithmen auf einer abstrakten Stufe, bei der statt ausführbarer Einzelschritte Prozeduraufrufe eingesetzt werden, deren Bedeutung dann durch die Ausprogrammierung der Prozedur konkretisiert wird. So könnte man eine Primzahlsuche unter Verwendung eines Prozeduraufrufs TestAufPrimzahl(n) formulieren und diesen Test in einem weiteren Verfeinerungsschritt konkretisieren.

8.1.2 Einsatz von Algorithmenmustern
Die Idee des Einsatzes von Algorithmenmustern besteht darin, generische algorithmische Muster für bestimmte Problemklassen zu entwi- ckeln und diese dann jeweils an eine konkrete Aufgabe anzupassen. Man versucht also für eine allgemeine Problemklasse, zum Beispiel das Finden einer kostenoptimalen Lösung in einem großen Lösungsraum (etwa das Finden kürzesterWege), eine Muster-Implementierung zu .nden und diese dann an das konkrete Problem anzupassen. Diese Grundidee kann man auf verschiedene Weise konkretisieren:

- Das Lösungsverfahren wird an einem möglichst einfachen Vertreter der Problemklasse vorgeführt und dokumentiert. Der Entwerfer versteht die Problemlösungsstrategie und überträgt diese auf sein Programm.

- Eine Bibliothek von Mustern (»Design Pattern«, »best practice«- Strategien) wird genutzt, um einen abstrakten Programmrahmen zu generieren. Die freien Stellen dieses Programmrahmens werden dann problemspezi.sch ausgefüllt.

- Moderne Programmiersprachen benutzen parametrisierte Algorithmen und Vererbung mit Überschreiben, um Algorithmenmuster als lauffähige Programme zur Verfügung zu stellen und diese dann an ein konkretes Problem anzupassen.

Im Verlauf dieses Kapitels werden wir einige derartige Muster kennen lernen und ebenfalls deren Übertragbarkeit auf verwandte Probleme behandeln.