Kurs:Algorithmen und Datenstrukturen/Vorlesung/Entwurfsprinzipien




Entwurfsprinzipien

Bearbeiten

Auf dieser Seite werden wir und mit Entwurfsprinzipien und einer Einführung in die Entwurfsmuster beschäftigen. Die Ableitung eines optimalen Algorithmus aus Anforderungsbeschreibungen ist nicht automatisierbar. Der Algorithmenentwurf ist eine kreative Tätigkeit, die durch Muster ( best practices) unterstützt wird. Vergleichbar ist das mit Mustern von Gebäuden in der Architektur oder mit Mustern aus der Softwarearchitektur.

Schrittweise Verfeinerung

Bearbeiten

Der Entwurf von Algorithmen erfolgt nach dem Prinzip der schrittweisen Verfeinerung von Pseudo Code Algorithmen. Pseudo Code Teile werden im ersten Schritt durch verfeinerten Pseudo Code ersetzt und im nächsten Schritt durch Programmiersprachen Code.

Beispiel 1

Bearbeiten

1. Pellkartoffeln kochen

verfeinert zu :

1.1 Fülle Topf mit Kartoffeln

1.2 Füge Wasser dazu

1.3 Stelle topf auf Herdplatte

1.4 Stelle Drehknopf auf 7

1.5 Koche das Wasser

Beispiel 2

Bearbeiten

Wir benutzen die Fakultät als Prozeduraufruf

Factorial(n)

Nun schreiben wir die Fakultät als Algorithmus

Fac: var X;Y:int;
input X; 
Y:=1;
while X>1 do Y:=Y*X; X:=  X-1 od
output Y

Nun schreiben wir die Fakultät als Implementierungscode

public static int factorial (int x) {
...
}

Einsatz von Algorithmenmustern

Bearbeiten

Die Idee ist, dass generische Algorithmenmuster für bestimmte Problemklassen an eine konkrete Aufgabe angepasst werden. Das Lösungsverfahrens wird am Beispiel eines einfachen Vertreters der Problemklasse dokumentiert. Es wird eine Bibliothek von Mustern (Design Pattern) zur Ableitung eines abstrakten Programmrahmens benutzt. Durch parametrisierte Algorithmen und Vererbung wird die Programmiersprache unterstützt.