Teile und Herrsche
Inhaltsverzeichnis |
Teile und herrsche (divide et impera)
Definition
Das Entwurfsverfahren Teile und Herrsche (divide-and-conquer) dient dem Entwurf rekursiver Algorithmen. Die Idee ist es, ein Problem der Groeßen in mehrere gleichartige aber kleinere Teilprobleme zu zerlegen (divide). Aus rekursiv gewonnenen Lösungen der Teilprobleme gilt es dann, eine Gesamtlösung für das ursprüngliche Problem zusammenzusetzen (conquer).
Eigenschaften
-
kann bei konzeptionell schwierigen Problemen hilfreich sein
-
kann effiziente Lösungen realisieren
-
für Parallelverarbeitung geeignet
Instanzen
- Mergesort
- Quicksort
- Intervallhalbierung (Binärbäumen)
Laufzeiten der Form
T(1) = const
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.
Beispiele
Beispiel 1 : Sortierverfahren (Merge-Sort)
- Sortiere eine Array indem zwei Teilarrays sortiert und dann gemischt werden.
sort ( [ 19 17 23 31 3 5 7 29 2 11 17 ] ) Teile!
=> merge (
sort ( [ 19 17 23 31 3 ] ), Herrsche über Teilproblem 1
sort ( [ 5 7 29 2 11 17 ] ) ) Heersche über Teilproblem 2
= merge ( [ 3 17 19 23 31 ] , [ 2 5 7 11 17 29 ] ) Kombiniere zur Gesamtlösung
= [ 2 3 5 7 11 17 17 19 23 29 31 ]
Beispiel 2: Lebkuchenhaus
Beispiel 3 : Die Türme von Hanoi
Wenn die Anzahl der Scheiben 1 beträgt, ist die Lösung des Problems trivial.
Bei mehr als einer Scheibe läßt sich das Gesamtproblem in drei Teilprobleme zerlegen:
- Transportiere n-1 Scheiben vom Anfangsplatz auf den Hilfsplatz.
- Transportiere die letzte Scheibe vom Anfangsplatz auf Zielplatz.
- Transportiere n-1 Scheiben vom Hilfsplatz auf den Zielplatz.
Spiele:
http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm
Übung 1 : Die Türme von Hanoi
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.
- Transportiere n Scheiben vom Anfangsplatz auf den Zielplatz, verwende einen Hilfsplatz.
Lösung
Neuigkeit
- Der 2. Schritt ist trivial und sofort ausführbar.
- Der 1. und der 3. Schritt sind von der gleichen Art wie das Ausgangsproblem, nur die Anzahl der Scheiben ist um 1 kleiner und die Bedeutung der Plätze hat sich verändert.
Damit hat man für das Gesamtproblem eine rekursive Lösungsvorschrift formuliert.
Pseudo - Code
Bedeutung der Variablen:
ap - Anfangsplatz
zp - Zielplatz
hp - Hilfsplatz
n - Anzahl der Scheiben
Die Übergabe des Hilfsplatzes als Parameter kann auch entfallen, wenn man als Berechnung einsetzt:
hp := 6 - ap - zp.
Spiele
http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm
Quicksort
Das Verfahren
Quicksort ist ein schneller Sortieralgorithmus auf der Basis rekursiver Vergleiche von Elementen, welcher von C.A.O Hoare im Jahre 1960 entwickelt wurde.
Das Prinzip ist eine gegebene Gesamtliste G so in zwei Teillisten L und R auf zuteilen, dass alle Elemente von L kleiner als ein Vergleichselement v \in G
und alle Elemente von R größer als v sind.
funktionaler Aufbau
Durch diese Prozedur entstehen die zwei Teillisten, die für die Unterscheidung der Relation in Bezug auf das Pivotelement benötigt werden.
Durch Enstehung dieser ist aber die eigentliche Sortieung noch nicht beendet. Dafür bedarf es einer weiteren Prozedur die die vorhergehende solange rekursiv aufruft, bis
alle Elemente sortiert sind. Die Sorierung erfolgt in der Implementierung einfach durch das Vertauschen der Vergeichselemente.
Viualisierung
Die folgende Animation zeigt den verbildlichten Ablauf des Algorithmus:
Beispiel
Effizienz von Quicksort
Mergesort
Definition
- Das Sortierverfahren Mergesort erzeugt eine sortierte Folge durch Verschmelzen (engl.: to merge) sortierter Teilstücke.
- Mit einer Zeitkomplexität von Θ(n log(n)) ist das Verfahren optimal.
Idee
- Ähnlich wie Quicksort beruht das Verfahren auf dem Divide-and-Conquer-Prinzip Erklärung.
- Die zu sortierende Folge wird zunächst in zwei Hälften aufgeteilt (divide), die jeweils für sich sortiert werden (conquer).
- Dann werden die sortierten Hälften zu einer insgesamt sortierten Folge verschmolzen (combine).
Beispiele
Beispiel 1
Beispiel 2
- Analogie: Sortieren eines Kartenstapels
- Karten sind mit Zahlen beschriftet
Schritt 1 : Teile den Stapel in zwei gleich grosse Stapel.
Schritt 2 : Sortiere beide Stapel getrennt.
Schritt 3 : Mische die beiden sortieren Stapel zu einem sortieren Stapel : lege dazu jeweils die kleinere der beiden oberen Karten umgedreht auf einen neuen Stapel.
Analyse von Merge-Sort
Sei T(n) die Laufzeit von Merge-Sort.
Das Aufteilen braucht O(1) Schritte.
Die rekursiven Aufrufe brauchen 2 T(n/2) Schritte.
Das Mischen braucht O(n) Schritte.
Also: T(n) = 2 T(n/2) + O(n), wenn n > 1 NB T(1) ist irgendein fester Wert.
Viualisierung
Übungen
Übung 1
- Sortieren Sie eine Array indem zwei Teilarrays sortiert und dann gemischt werden.
1. Aufteilen der Eingabe
2. Rekursiv Sortieren
3. Zusammenfügen
Übung 2
Sortieren Sie die Buchstaben in der Zeichenkette aus Ihrem zusammengeschriebenen Vor- und Nachnamen mit Merge Sort.
Übung 3
n - Anzahl Elemente
1. Implementieren Sie eine Klasse „MergeSort".
2. Implementieren Sie in der Klasse eine Methode „sort“ mit den Parameter:
- eindimensionales Array -> a
- low
- high
3. Deklarieren Sie Variable N und initialisieren als die Unterschied zwischen high und low .
4. Implementieren Sie die Schleifen :
- für N kleiner gleich 1
1. Implementieren Sie eine Klasse „main".
2. Importieren Sie Scanner.
3. Deklarieren Sie zwei Variablen n und i.
4. Fragen Sie den Nutzer nach Anzahl die Elemente.
5. Initialisieren Sie diese Zahl als Variable n.
6. Erstellen Sie eindimensionales Array , welche beträgt new int[n].
7. Fragen Sie den Nutzer nach den Wert diese Elemente.
8. Implementieren Sie die Schleife , welche ruft diese Werte ab.
9. Benutzen Sie Mathode sort für arr,0,n.
10. Drucken Sie diese Elemente.
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.
- Mergesort - ein schnelleres (und rekursives) Sortierverfahren.
Quellen
Wagenknecht, 2003, Algorithmen und Komplexität
http://www.inf-schule.de/
http://www.awb1.ch/
http://www.ki.informatik.uni-frankfurt.de/
http://ddi.cs.uni-potsdam.de/
http://thm.de/
http://de.wikiversity.org/