Teile und Herrsche
Inhaltsverzeichnis |
Teile und herrsche
Definition
Teile und herrsche ist eine Problemlösestrategie, bei der ein Problem immer weiter in Teilprobleme zerlegt wird, bis sich diese einfach lösen lassen. Aus den Lösungen der Teilprobleme wird dann die Lösung des Gesamtproblems zusammengesetzt.
Beispiel
Aufgabe
Transportiere n Scheiben vom Anfangsplatz auf den Zielplatz, verwende einen Hilfsplatz.
Die Spielregeln
Es sind n Scheiben unterschiedlichen Durchmessers gegeben, welche geordnet zu einem Turm geschichtet sind, die untere Scheibe ist die größte. Der Turm steht auf einem Anfangsplatz. Unter Verwendung eines Hilfsplatzes soll dieser Turm nun zu einem Zielplatz transportiert werden, wobei verschiedene Regeln einzuhalten sind.
http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm
Sortieren
Aufteilen der Eingabe
Rekursiv Sortieren
Zusammenfügen
Lebkuchenhaus
Entwurfsmethode für Algorithmen
1. Teile das Problem in kleinere Unterprobleme (Divide)
2. Löse rekursiv die entstehenden Unterprobleme (Conquer)
3. Setze die Lösungen zusammen.
Instanzen
• Mergesort
• Quicksort
• Intervallhalbierung (Binärbäumen)
Die Idee
Quicksort
Mergesort
Binäres Suchen
Zusammenfassung
- Teile und Herrsche - Zerlegung größerer Aufgaben oder Probleme in kleinere Aufgaben oder Probleme, die einfacher zu bewältigen oder leichter gelöst werden können.
Quellen
Wagenknecht, 2003, Algorithmen und Komplexität
http://www.inf-schule.de/
http://www.awb1.ch/
http://www.ki.informatik.uni-frankfurt.de/