Kurs:Algorithmen und Datenstrukturen/Vorlesung/Algorithmenentwurf

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

Algorithmenentwurf

Dieses Kapitel behandelt die Vorgehensweise zum Algorithmenentwurf.

Vom Algorithmus zur Programmausführung

1. Der Algorithmus wird unabhängig von Programmiersprache und Rechnerhardware entworfen
2. Der Algorithmus wird in einer höheren Programmiersprache, z.B. Java, programmiert
3. Das Programm wird in Maschinensprache übersetzt
4. Die CPU interpretiert den Maschinencode und das Programm wird ausgeführt

Vom Algorithmus zum Programm

Vorgehensweise Algorithmus-Entwurf

• Hintergrundwissen erwerben: Derjenige der ein Problem beschreibt ist oft nicht derjenige, der den Algorithmus entwirft, dadurch kommt es zu unklaren Aufgabenstellungen, unterschiedlichem Vorwissen und verschiedenen Annahmen.
• Problem definieren: Erfordert Hintergrundwissen und Übung in der Definition von Problemen
• Algorithmus entwerfen: Erfordert Wissen zu Algorithmen und Datenstrukturen
• Programm erstellen: Erfordert Wissen über Programmiersprache (Java) und Programmierung
• Lösung überprüfen: Erfordert methodisches Wissen zu Termination, Korrektheit und Effizienz

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 2 und 8.1 zu finden.