Teile und Herrsche
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
==Teile und herrsche (divide et impera) ==
=== Definition ===
<center>
<div style= "background-color:#D6D6C2; padding:10px">
<b> Teile und herrsche </b> 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.
</div>
</center>
<br>
=== Anwendung ===
Bei der Anwendung der Technik Teile-und-Herrsche wird
<br>
* das gegebene Problem auf die Lösung
* mehrerer (oft zwei) kleinere Probleme der gleichen Art
* der (etwa) gleichen Größe reduziert. Aus deren Lösung wird dann die Gesamtlösung konstruiert.
<br>
[[Bild:S3anbrem_Anw.PNG]]
=== Beispiele ===
Beispiel: Merge-Sort
Sortiere eine Array indem zwei Teilarrays sortiert und dann gemischt werden. <br><br>
'''sort''' ([1 9 7 2 7 4 7 2 8]) Teile! <br>
-> '''merge'''( <br>
'''sort'''([1 9 7 2 7]), Herrsche über Teilproblem 1 <br>
'''sort'''([4 7 2 8])) Heersche über Teilproblem 2 <br>
= '''merge'''([1 2 7 7 9],[2 4 7 8]) Kombiniere zur Gesamtlösung <br>
=[1 2 2 4 7 7 7 8 9] <br>
<br>
'''if''' p< r '''then''' <br>
q <- [(p +r)/2] <br>
Merge-Sort(A,p,q)<br>
Merge-Sort(A,q+1,r)<br>
Merge(A,p,q,r)<br>
O(n*log n) <br>
=== Entwurfsmethode für Algorithmen ===
1. <font color="green"> Teile </font> das Problem in kleinere Unterprobleme (Divide) <br>
2. <font color="green"> Löse </font> rekursiv die entstehenden Unterprobleme (Conquer) <br>
3. <font color="green"> Setze </font> die Lösungen zusammen.<br>
=== Instanzen ===
* Mergesort <br>
* Quicksort <br>
* Intervallhalbierung (Binärbäumen)<br><br>
=== Eigenschaften ===
<ul>
<li>
kann bei konzeptionell schwierigen Problemen hilfreich sein
<li>
kann effiziente Lösungen realisieren
<li>
für Parallelverarbeitung geeignet
</ul>
=== Beispiele ===
* Sortierverfahren <br>
[[Bild:S3anbrem_B1a1.PNG]]
<popup name="1. Aufteilen der Eingabe">
[[Bild:S3anbrem_B1a.png]]
</popup>
<popup name="2. Rekursiv Sortieren">
[[Bild:S3anbrem_B1b.png]]
</popup>
<popup name="3. Zusammenfügen">
[[Bild:S3anbrem_B1c.png]]
</popup>
<br>
* Lebkuchenhaus <br>
[[Bild:S3anbrem_B1.PNG]]
=== '''Übung 1 :''' Die Türme von Hanoi ===
<popup name="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.
</popup>
Transportiere n Scheiben vom Anfangsplatz auf den Zielplatz, verwende einen Hilfsplatz.
<br>
[[Bild:S3anbrem_U1.png]]
<popup name="Lösung">
[[Bild:S3anbrem_B4.PNG]]
</popup>
<popup name="Teilprobleme">
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.
<br>
Bei näherer Betrachtung der Teilprobleme fällt folgendes auf:
a) Der 2. Schritt ist trivial und sofort ausführbar. <br>
b) 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. <br>
Damit hat man für das Gesamtproblem eine rekursive Lösungsvorschrift formuliert.
</popup>
<code>procedure turm(ap,zp,hp,n:byte);
begin
if n=1 then
writeln(' Scheibe von Platz ',ap,' auf Platz ',zp)
else begin
turm(ap,hp,zp,n-1);
writeln(' Scheibe von Platz ',ap,' auf Platz ',zp);
turm(hp,zp,ap,n-1);
end;
end;</code>
<popup name = "Bedeutung der Variablen:">
Bedeutung der Variablen: <br>
ap - Anfangsplatz <br>
zp - Zielplatz <br>
hp - Hilfsplatz <br>
n - Anzahl der Scheiben <br>
Die Übergabe des Hilfsplatzes als Parameter kann auch entfallen, wenn man als Berechnung einsetzt: <br>
hp := 6 - ap - zp. <br>
</popup>
Spiele:
http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm
== Quicksort ==
== Mergesort ==
ein schnelleres (und rekursives) '''Sortierverfahren'''.
<br>
<ul>
<li> Analogie: Sortieren eines Kartenstapels<br>
<li> Karten sind mit Zahlen beschriftet<br>
</ul>
[[Bild:S3anbrem_Ms.PNG]]
<br>
'''Schritt 1 :''' Teile den Stapel in zwei gleich grosse Stapel.
<br>
[[Bild:S3anbrem_Ms2.png]]
<br>
'''Schritt 2 :''' Sortiere beide Stapel getrennt.
<br>
[[Bild:S3anbrem_Ms3.PNG]]
<br>
'''Schritt 3 :''' Mische die beiden sortieren Stapel zu einem sortieren Stapel : lege dazu jeweils die kleinere der beiden oberen Karten <i> umgedreht </i> auf einen neuen Stapel. <br>
[[Bild:S3anbrem_Ms4.png]]
<br>
==== Ubung1 ====
n - Anzahl Elemente <br>
1. Implementieren Sie eine Klasse „MergeSort". <br>
2. Implementieren Sie in der Klasse eine Methode „sort“ mit den Parameter:
<br>
- eindimensionales Array -> a
<br>
- low <br>
- high <br>
3. Deklarieren Sie Variable N und initialisieren als die Unterschied zwischen high und low . <br>
4. Implementieren Sie die Schleifen : <br>
* für N kleiner gleich 1 <br>
*
<br>
1. Implementieren Sie eine Klasse „main". <br>
2. Importieren Sie Scanner.
3. Deklarieren Sie zwei Variablen n und i. <br>
4. Fragen Sie den Nutzer nach Anzahl die Elemente. <br>
5. Initialisieren Sie diese Zahl als Variable n. <br>
6. Erstellen Sie eindimensionales Array , welche beträgt new int[n]. <br>
7. Fragen Sie den Nutzer nach den Wert diese Elemente. <br>
8. Implementieren Sie die Schleife , welche ruft diese Werte ab. <br>
9. Benutzen Sie Mathode sort für arr,0,n. <br>
10. Drucken Sie diese Elemente. <br>
== Binäres Suchen ==
== Zusammenfassung ==
<ul>
<li>'''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.
</ul>
== Quellen ==
Wagenknecht, 2003, Algorithmen und Komplexität <br>
http://www.inf-schule.de/ <br>
http://www.awb1.ch/ <br>
http://www.ki.informatik.uni-frankfurt.de/ <br>
http://ddi.cs.uni-potsdam.de/ <br>