Teile und Herrsche 1 SS10
Inhaltsverzeichnis |
Autoren:
- Raffael Thomas Lang (siralang@stud.hs-zigr.de)
- Sebastian Kramer (sisekram@stud.hs-zigr.de)
Hinweis:
- Wenn ihr verschiedene Programmiersprachen verwendet, lagert eure Beispiele auf Unterseiten aus etwa Java Beispiel 1. Auf jeder neuen Wikiseite könnt ihr eine andere Programmiersprache auswählen.
- Im Wiki wird ein Java-Interpreter verwendet (BeanShell) ihr benötigt deshalb keine "main" Methoden oder ähnliches und könnt den Quellcode viel kompakter gestalten. Schaut euch andere Codebeispiele hier im Wiki zu Java an.
Was ist überhaupt Divide and Conquer?
In vielen Programmiersprachen wird die Gliederung von Computerprogrammen in Prozeduren, Funktionen, Module, Objekte, Komponenten, Prozesse und Threads nach dem Prinzip teile und herrsche umgesetzt.
DaC (eng. "Divide and Conquer") auf deutsch "Teile und Herrsche" genannt und in lat. "divide et impera". Es beschreibt folgendes Vorgehen bei Problemen:
- zerteilen des Problems in Teilprobleme (divide)
- lösen der einzelnen Teilprobleme, mittels rekursiver Programmierung (conquer)
- Teillösungen zusammenführen zu der Gesamtlösung (konkatenieren)
Ziel
Ziel dieser Methode ist es eine Effiziensverbesserung zu erreichen. Der Lösungsaufwand soll minimiert werden durch die Zerlegung des Hauptproblems in Teilprobleme, welche dem Hauptproblem ähneln. Sind die Teilprobleme noch zu aufwändig in der Lösung, werden diese weiter in noch kleinere Teilprobleme zerlegt, bis alle mit einem geringem Aufwand lösbar sind.
Vorteile von DaC
Ein großer Vorteil von Divide und Conquer ist die Zerlegung der Probleme. Dadurch wird es möglich die Probleme in mehreren Instanzen, also sie parallel zu lösen. Beispielweise können, je nach Aufwand des Problems, dafür Multicore Prozessoren oder gar mehrere rechner verwendet werden.
Effizienz von DaC
In der untenstehenden Formel wird erklärt, wie sich der Gesamtaufwand eines Algorithmus aus den Teilproblemen multipliziert mit der Größe der Teilprobleme plus den Aufwand ergibt.
-
\begin{array}{ccl}
T_B & = & 3T_A\left(\left\lceil \frac{n}{2}\right\rceil\right)+d\cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n+1}{2}\right)^2+d\cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n}{2} + \frac{1}{2} \right)^2+d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n^2}{4}+2\frac{n}{4}+\frac{1}{4} \right)+d \cdot n\\\\
& \leq & \frac{3}{4}cn^2+\frac{3}{2}cn+\frac{3}{4}c+d \cdot n\\\\
& \leq & \frac{3}{4}cn^2+\left(\frac{3}{2}c+d\right)n+\frac{3}{4}c
\end{array}
-
\begin{array}{ccl}
T_B & = & 3T_A\left(\left\lceil \frac{n}{2}\right\rceil\right)+d\cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n+1}{2}\right)^2+d\cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n}{2} + \frac{1}{2} \right)^2+d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n^2}{4}+2\frac{n}{4}+\frac{1}{4} \right)+d \cdot n\\\\
& \leq & \frac{3}{4}cn^2+\frac{3}{2}cn+\frac{3}{4}c+d \cdot n\\\\
& \leq & \frac{3}{4}cn^2+\left(\frac{3}{2}c+d\right)n+\frac{3}{4}c
\end{array}
Es tritt eine Effiziensverbesserung von 25% auf, jedoch ist zubeachten das immer ein rekursiver Aufruf enthalten sein muss.
Das schnelle Sortieren
Quicksort, das schnelle Sortieren, dient der Sortierung von Listen. Die zu sortierende Liste wird geteilt, so dass zwei Teillisten entstehen. Das wird solange ausgeführt bis die Teillisten nur noch aus einem oder keinem Element besteht. Sobald der Elementarfall erreicht ist, werden die Einzellisten wieder zusammengeführt.
Grundprinzip
Quicksort nimmt eine Liste Zahlen und Teilt sie mit Hilfe eines Hilfselements (Pivotelement) auf. Dabei werden 2 Teillisten erzeugt. Diese beiden Teillisten werden wie folgt gefüllt. In die Sogenannte linke Liste kommen alle Zahlen die kleiner als das Pivotelement sind hinein. Jede Zahl die größer oder Gleich dem Vergleichselement sind kommen in die rechte Teilliste. Das Pivotelement, kann auf verschiedene Art und Weise gewonnen werden. Beispielsweise nimmt man sich willkürliche eine Zahl aus der Gesamtliste herraus oder man berechnet das Element in dem alle Elemente der Liste mit einander addiert und durch die gesamte Anzahl der Listenelemente Teilt, also man das Durchschnittselement berechnet. Dies hat je nach wahl des Pivotelements Auswirkungen auf die Effizienz von Quicksort, was aber nur im Worstcase eine Rolle spielt. Die Teilung der Listen wird solange rekursiv durchgeführt, bis nur noch einzel Elemente in den Teillisten übrig sind. Diese einzelnen listen werden dann von links nach rechts wieder zusammengefügt und erählt somit eine sortierte Liste.
Effzienz
Schemeumsetzung
<eval id="4bbc796487c77">(quicksort '( 2 8 9 13 30 21 7 1 3 6 18 14 20 16 10 12 15 19 25 11 4 5 17 ))</eval>
Javaumsetzung
Mergesort
Ein treffender Begriff hierfür ist "einfädeln, was man aus dem Straßenverkehr kennt. Zusammenführen ist auch recht treffend. "Sortieren durch Mischen" ist jedoch irreführend, weil hierbei das Prinzip von Mergesort nicht erfasst wird.
Grundprinzip
- Divide:
Das Verfahren teilt die Große Liste in zwei etwa gleichgroße Teillisten, was ohne Vergleichselement geschieht. Die Spaltung der Listen wird mit Hilfe von n = |G| \div 2 = m \div 2 realisiert (\div steht für die ganzzahlige Division). - Conquer:
Bla Blub Bla
Effzienz
Schemeumsetzung
Javaumsetzung
Vergleich Quicksort und Mergesort
Übungen
- Aufgabe
- Aufgabe
- Aufgabe
- Aufgabe
- Aufgabe