Teile und Herrsche
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== <font color="green"> '''Teile und herrsche (divide et impera)''' </font> ==
=== Definition ===
<center>
<div style= "background-color:#D6D6C2; padding:10px">
Das Entwurfsverfahren <font color="green"> '''Teile und Herrsche'''</font> ( 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 (<font color="green"> '''divide'''</font>).
Aus rekursiv gewonnenen Lösungen der Teilprobleme gilt es dann, eine Gesamtlösung für das ursprüngliche Problem zusammenzusetzen (<font color="green"> '''conquer'''</font>).
</div>
<br>
[[Bild:S3anbrem_Def.PNG]]
</center>
=== 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>
<center>
[[Bild:S3anbrem_Anw.PNG]]
</center>
=== Eigenschaften ===
<ul>
<li>
kann bei konzeptionell schwierigen Problemen hilfreich sein
<li>
kann effiziente Lösungen realisieren
<li>
für Parallelverarbeitung geeignet
</ul>
=== Instanzen ===
* Mergesort <br>
* Quicksort <br>
* Intervallhalbierung (Binärbäumen)<br>
=== Beispiele ===
==== Beispiel 1 : Sortierverfahren (Merge-Sort) ====
* Sortiere eine Array indem zwei Teilarrays sortiert und dann gemischt werden. <br>
'''sort''' ( [ <font color="green"> '''19 17 23 31 3''' </font> <font color="yellow"> '''5 7 29 2 11 17''' </font> ] ) Teile! <br>
=> '''merge''' ( <br>
'''sort''' ( [ <font color="green"> '''19 17 23 31 3''' </font> ] ), Herrsche über Teilproblem 1 <br>
'''sort''' ( [ <font color="yellow"> '''5 7 29 2 11 17''' </font> ] ) ) Heersche über Teilproblem 2 <br>
= '''merge''' ( [ 3 17 19 23 31 ] , [ 2 5 7 11 17 29 ] ) Kombiniere zur Gesamtlösung <br>
= [ <font color="red"> ''' 2 3 5 7 11 17 17 19 23 29 31 ''' </font> ]
==== Beispiel 2: Lebkuchenhaus ====
[[Bild:S3anbrem_Lkh.PNG]]
==== Beispiel 3 : Die Türme von Hanoi ====
Wenn die Anzahl der Scheiben '''1''' beträgt, ist die Lösung des Problems '''trivial'''. <br>
Bei mehr als einer Scheibe läßt sich das Gesamtproblem in drei Teilprobleme zerlegen:
* Transportiere <font color="green"> '''n-1'''</font> Scheiben vom <font color="green"> '''Anfangsplatz'''</font> auf den <font color="green"> '''Hilfsplatz'''</font>.
* Transportiere die letzte Scheibe vom <font color="green"> '''Anfangsplatz'''</font> auf <font color="green"> '''Zielplatz'''</font>.
* Transportiere <font color="green"> '''n-1'''</font> Scheiben vom <font color="green"> '''Hilfsplatz'''</font> auf den <font color="green"> '''Zielplatz'''</font>.
[[Bild:S3anbrem_Azh.PNG]]
<language>Java</language>
=== Ü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>
==== Neuigkeit ====
* Der '''2.''' Schritt ist '''trivial''' und sofort '''ausführbar'''. <br>
* 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.
==== Spiele ====
http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm
=== Übung 2 : Hanoi Java-Code ===
==== Pseudo - Code ====
<code id="5686b20aa7bbc">
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:">
<center>
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>
</center>
</popup>
==== Java-Code ====
* Schreiben Sie Java-Code für Hanoi Java-Code fort. <br>
1. Implementieren Sie eine Klasse "'''Hanoi'''". <br><br>
'''Klasse bewege'''<br>
''Bewegt '''n''' Scheiben von Turm '''a''' nach Turm '''c''' und benutzt als Zwischenspeicher Turm '''b'''.'' <br>
1. Implementieren Sie in der Klasse eine Klasse "'''bewege'''" mit den Parameter:
'''a''','''b''','''c''' als char und '''n''' als int Variable . <br>
2. Implementieren Sie die Schleife: <br>
- '''if'''(n==1) '''than''' Drucken Sie die Text : ("Lege die oberte scheiben von " + ... + "Turm" + ... + "auf Turm" + ... + ".");<br>
<code>
...
else {
bewege(a, c, b, n-1);
bewege(a, b, c, 1);
bewege(b, a, c, n-1);
}
</code>
'''Klasse Main''' <br>
1. Implementieren Sie eine Klasse "Main". <br>
2. Benutzen Sie die Klasse(Methode) '''bewege'''. <br>
<code id="5688ea23bbf1b">... </code>
== Quicksort ==
===Das Verfahren===
<div style= "background-color:#D6D6C2; padding:10px">
Quicksort ist ein schneller Sortieralgorithmus auf der Basis rekursiver Vergleiche von Elementen, welcher von C.A.O Hoare im Jahre 1960 entwickelt wurde.<br><br>
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. </div>
Hier und im folgenden wird vereinbart, dass alle Elemente von $G$ natürliche Zahlen sind.
===funktionaler Aufbau===
<code id="5686beb31df88">(define teillisten
(lambda (ls v)
(if (null? ls)
(values '() '())
(call-with-values
(lambda () (teillisten (cdr ls) v))
(lambda (l r)
(let ((x (car ls))
(if (< x v)
(values (cons x l) r)
(values l (cons x r)))))))))</code><br>
<div style= "background-color:#D6D6C2; padding:10px">
Durch diese Prozedur entstehen die zwei Teillisten, die für die Unterscheidung der Relation in Bezug auf das Pivotelement benötigt werden.<br>
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.
</div>
<code id="5686beb31e01d">(define quicksort
(lambda (ls)
(if (or (null? ls) (null? (cdr ls)))
ls
(let ((v (car ls)))
(call-with-values
(lambda() (teile (cdr ls) v))
(lambda (l r)
(append
(quicksort l)
(list v)
(mv-quick r))))))))</code>
===Viualisierung===
Die folgende Animation zeigt den verbildlichten Ablauf des Algorithmus:
[[Bild:quicksort_animation.gif]]
===Beispiel===
===Effizienz von Quicksort===
<language>Java</language>
== <font color="green">'''Mergesort''' </font> ==
=== Definition ===
<div style= "background-color:#D6D6C2; padding:10px">
* '''Das Sortierverfahren Mergesort''' erzeugt eine sortierte Folge durch '''Verschmelzen''' sortierter Teilstücke.
* Das Verfahren beruht 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''').
* Dieses Verfahren bietet die Möglichkeit einer iterativen Implementierung.
</div>
=== Vorteile ===
* Geschickter Einsatz der '''Teile-und-Herrsche''' Technik.
* Gutes '''Laufzeitverhalten''' für große Eingabegrößen <br>
Sei <font color="green">'''$\mathit{T}\left(n\right)$''' </font> die Laufzeit von Merge-Sort.<br>
Das <font color="green">'''Aufteilen''' </font> braucht '''$\mathcal{O}\left(1\right)$''' Schritte.<br>
Die <font color="green">'''rekursiven Aufrufe''' </font> brauchen 2 T(n/2) Schritte.<br>
Das <font color="green">'''Mischen''' </font> braucht '''$\mathcal{O}\left(n\right)$''' Schritte. <br>
Also: <font color="green">'''$\mathit{T}\left(n\right) = 2 * \mathit{T}(n/2) + \mathcal{O}\left(n\right)$'''</font>, wenn n > 1 .<br><br>
(<font color="green">'''Best-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)$ <font color="green">'''Worst-Case'''</font>: $\mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)$
* Die '''Stabilität'''
Die relative Ordnung zweier Elemente , welche gleich sind , wird beibehalten.
*''' Abarbeiten Daten sequentiell'''
=== Nachteile ===
* der zusätzlich benötigte '''Speicher'''
=== Anwendung ===
* Der Mergesort wird vor allem dann verwendet, wenn man eine große sortierte Datenmenge verwalten möchte.
=== Pseudocode ===
<code>
funtion mergesort( liste ):
if liste.laenge <= 1 then
return liste;
else
linkeListe = liste[0] bis liste[laenge/2];
rechteListe = liste[laenge-(laenge/2)] bis liste[laenge-1];
linkeListe =mergesort(linkeListe);
rechteListe=mergesort(rechteListe);
return merge(linkeListe, rechteListe);
end
</code>
=== Animation===
http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html
=== Beispiele ===
==== Beispiel 1 ====
[[Bild:S3anbrem_Msb1.PNG]]
==== Beispiel 2 ====
<ul>
<li> Analogie: Sortieren eines Kartenstapels<br>
<li> Karten sind mit Zahlen beschriftet<br>
</ul>
[[Bild:S3anbrem_Merrge-sort-beispiel-1.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>
=== Viualisierung ===
[[Bild:S3anbrem_Mergesort-o.gif]]
=== Übungen ===
==== Übung 1 ====
* Sortieren Sie eine Array. <br>
[[Bild:S3anbrem_Merge-sort-bsp1.PNG]] <br>
<popup name="1. Aufteilen der Eingabe">
[[Bild:S3anbrem_Merge-sort-bsp1b.PNG]] <br> <br>
[[Bild:S3anbrem_Merge-sort-bsp1c.PNG]] <br> <br>
[[Bild:S3anbrem_Merge-sort-bsp1d.PNG]] <br> <br>
</popup>
<popup name="2. Teilen, Sortieren und Mischen der Eingabe">
[[Bild:S3anbrem_Merge-sort-bsp1e.PNG]] <br> <br>
</popup>
<popup name="3. Mischen der Eingabe">
[[Bild:S3anbrem_Merge-sort-bsp1f.PNG]] <br> <br>
</popup>
<popup name="4. Ergebnis">
[[Bild:S3anbrem_Merge-sort-bsp1g.PNG]] <br> <br>
</popup>
==== Übung 2 ====
* Sortieren Sie eine Array indem zwei Teilarrays sortiert und dann gemischt werden. <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>
==== Übung 3 ====
Sortieren Sie die Buchstaben in der Zeichenkette aus Ihrem zusammengeschriebenen Vor- und Nachnamen mit Merge Sort.
==== Übung 4 ====
* Schreiben Sie Java-Code für MergeSort fort. <br>
<code id="568810449ab04">
.......
if (N <= 1)
return;
int mid = low + N/2;
// recursively sort
sort(a, low, mid);
sort(a, mid, high);
// merge two sorted subarrays
int[] temp = new int[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)
temp[k] = a[j++];
else if (j == high)
temp[k] = a[i++];
else if (a[j]<a[i])
temp[k] = a[j++];
else
temp[k] = a[i++];
}
for (int k = 0; k < N; k++)
a[low + k] = temp[k];
}
</code>
<popup name="Klasse MergeSort">
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>
</popup>
<br>
<popup name="Klasse Main">
1. Implementieren Sie eine Klasse''' „main"'''. <br>
2. Importieren Sie '''Scanner'''. <br>
3. Fragen Sie den Nutzer nach '''Anzahl die Elemente'''. <br>
4. Initialisieren Sie diese Zahl als Variable number_of_integer_elements. <br>
5. Drucken Sie diese Zahl. <br>
5. Erstellen Sie eindimensionales Array , welche beträgt '''new int[number_of_integer_elements]'''. <br>
6. Fragen Sie den Nutzer nach den Wert diese Elemente.(Schleife) <br>
7. Implementieren Sie die Schleife , welche ruft diese Werte ab. <br>
8. Benutzen Sie Methode '''sort''' für arr, 0, number_of_integer_elements. <br>
9. '''Drucken''' Sie diese Elemente. <br>
</popup>
== 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.
<li> '''Mergesort''' - ein schnelleres (und rekursives) '''Sortierverfahren'''.
* Ein Feld wird in zwei Teilfelder aufgeteilt, die dann rekursiv sortiert werden. Anschließend werden diese sortierten Teilfelder wieder zu einem Feld zusammengefügt. Dabei macht man sich zu nutze, daß die beiden Teilfelder bereits sortiert sind.
* Mit einer Zeitkomplexität von Θ(n log(n)) ist das Verfahren immer '''optimal'''.
</ul>
== Quellen ==
Wagenknecht, 2003, Algorithmen und Komplexität <br>
Cormen, Leierson, Rivest und Stein, 2004, Algorithmen - Eine Einführung <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>
http://thm.de/ <br>
http://de.wikiversity.org/ <br>
http://www.roland-illig.de/ <br>