Kurs:Algorithmen und Datenstrukturen/Vorlesung/Entwurfsprinzipien

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Entwurfsprinzipien

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

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

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

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

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.