AuK/Teile und Herrsche 1 WS13-14
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
Autoren:
* [mailto:s3darich@stud.hs-zigr.de Daniel Richter]
* [mailto:s3addank@stud.hs-zigr.de Adrian Danker]
== Vorbetrachtungen ==
=== Grundsätzliches ===
* Ein großes Problem wird in in kleinere Teilprobleme zerlegt (teile - divide).
* Teilprobleme werden einzeln rekursiv gelöst (herrsche - conquer).
* Zusammensetzen der einzelnen Lösungen zu einer Gesamtlösung.
=== Beispiele allgemein und aus der Informatik ===
* Das Programmingwiki: Das große Problem der Veranstaltung Algorithmen wird aufgeteilt (Themen) und diese zerlegten Teilprobleme von einzelnen (Studenten) bearbeitet und gelöst(Referat). Am Ende werden die einzelnen Lösungen zusammengefügt und bilden die Lehrveranstaltung Algorithmen und Komplexität.
* Beim Sortieren: Es ist eine Gesamtliste L gegeben mit n Elementen, also $L = (e_{1}, e_{2},..., e_{n})$, welche nach der göße der Elemente Sortiert werden soll. Man teilt die Liste auf und sortiert die Teillisten nach der Größe und fügt die geortneten Listen in der richtigen Reihenfolge wieder zusammen.
=== Effizienzbetrachtung von Teile und Herrsche ===
Es wird erhofft das diese Technik effizienter ist als das Lösen des Gesamtproblems ohne es zu zerlegen.
Angenommen, ein Algorithmus $\mathcal{A}$ löst das Problem in $\mathcal{O}\left(n^{2}\right)$,d.h. mit $\mathit{T}_{\mathcal{A}}\left(n\right)\leq c\cdot n$. Für den Gesamtaufwand $\mathit{T}_{\mathcal{B}}$ eines Algorithmus $\mathcal{B}$, der beispielsweise drei dieser Probleme der Größe $\frac{n}{2}$ mittels Prozedur $\mathcal{A}$ bearbeitet, um die Teillösungen anschließend mit dem Aufwand in $\mathcal{O}\left(n\right)$ zusammenzufügen, gilt damit: <br /> <br />
\begin{align}
\begin{array}{rcl}
T_{B} \left( n \right) & = & 3 \cdot T_{A} \cdot\left(\lceil\frac{n}{2} \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+1}{2}\right) \left( \frac{n+1}{2}\right) + d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n^{2} + 2n + 1}{4}\right) + d \cdot n\\\\
& \leq & 3 \cdot c \cdot \left( \frac{n^{2}}{4} + \frac{2n}{4} + \frac{1}{4}\right) + d \cdot n\\\\
& \leq & \frac{3cn^{2}}{4} + \frac{6cn}{4} + \frac{3c}{4} + 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) \cdot n + \frac{3}{4} c\\\\
\end{array}
\end{align}
Man erkennt an den führenden Summanden, das es tatsächlich eine Effizienzsteigerung von ca. 25% ergibt. Aber es ergibt sich immer noch ein quadratischer Aufwand mit $\mathcal{O}\left(n^{2}\right)$. Daher betrachten wir nun einen Algorithmus $\mathcal{C}$, welcher das Problem auf rekursive Art löst.
\begin{align}
\mathit{T}_{\mathcal{C}}\left(n\right) = \begin{cases} \mathit{T}_{\mathcal{A}}\left(n\right), \mbox{$wenn$}\ n\leq n_{0} \\
\mathit{3\ T}_{\mathcal{C}}\left(\dfrac{n}{2}\right), \mbox{$sonst$}\end{cases}
\end{align}
Nach dem Lösen dieser Formel kommen wir zu dem Ergebnis $\mathit{T}_{\mathcal{C}}\left(n\right)=\mathcal{O}\left(n^{1.59}\right)$.
== Quicksort ==
Der Quicksort Algorithmus wurde 1962 von C.A.O. Hoare angegeben. Der Grundgedanke ist eine Liste $L = (e_{1}, e_{2},\dots, e_{n})$ in zwei Teillisten zu zerlegen. Eine linke Teilliste TL und eine rechte Teilliste TR. Diese Listen werden durch einen Vergleich mit einem Pivotelment (Vergleichselement) ''v'' gebildet. dabei muss $\mathit{v} \in G$ gelten. Es wird verabredet das alle Elemente von L paarweise verschieden sind, also $m \neq n$ also gilt $e_{m} \neq e_{n}$. Dies ist zwar nicht erforderlich aber im Allgemeinen sinnvoll, da es normalerweise um Schlüssel zur Identifikation von Datenätzen handelt. Weiterhin wird verabredet das es sich um eine Liste mit natürlichen Zahlen handelt. Eine weitere Festlegung, das am weitesten links stehende Element aus L als ''v'' zu nehmen, das bedeutet $\mathit{v} = e_{1}$.
Die sortierte Gesamtliste $L_{sortiert}$ entsteht durch die Teilliste $TL_{sortiert}, \mathit{v}$ und $TR_{sortiert}$. in dieser Reihenfolge. Die Abarbeitung der Teillisten findet dabei Rekursiv statt.
Die zwei Elementarfälle: Ist L leer oder hat nur ein einzelnes Element, dann ist L = $L_{sortiert}$.
Bei der Teilung der Liste L in TL und TR entstehen wieder Listen die mindestens L-1 Elemente enthalten, da ''v'' entfernt wurde. Es wird nah endlich vielen Zerlegungen einer der Elementarfälle erreicht.
=== Funktionaler Aufbau ===
<code id="5262a386ef6db">(define teile
(lambda (ls v)
(if (null? ls)
(values '() '())
(call-with-values
(lambda () (teile (cdr ls) v))
(lambda (tl tr)
(let ((x (car ls)))
(if (< x v)
(values (cons x tl) tr)
(values tl (cons x tr)))))))))</code>
<run id="5262a386ef8a3">(teile '(1 2 3 5 8 13 21 34 55 89 143 232) 8)</run>
Hierbei entstehen 2 Teillisten um eine sortierte Liste zu bekommen benötigen wir noch eine weitere Prozedur.
<code id="5262a386ef7b6">(define mv-quick
(lambda (ls)
(if (or (null? ls) (null? (cdr ls)))
ls
(let ((v (car ls)))
(call-with-values
(lambda() (teile (cdr ls) v))
(lambda (tl tr)
(append
(mv-quick tl)
(list v)
(mv-quick tr))))))))</code>
<run id="5262a386ef955">(mv-quick '(3 8 5 14 19 17 10 13 18 20 16 22 7 6 9 4 15 21 23 11))</run>
=== Effizienz von Quicksort ===
==== best case ====
Quicksort arbeitet am effektivsten wenn die zu sortierenden Teillisten etwa gleich lang sind.
\begin{align}
\mathit{T}\left(0\right) &= 0\notag\\
\mathit{T}\left(n\right) &= 2 \cdot \mathit{T}\left(\frac{n}{2}\right) + c \cdot n\notag
\end{align}
Dabei kommen wir auf einen Aufwand von $\mathit{T}\left(n\right)= \mathcal{O}\left(n \log_{2} n\right)$. Zur Lösung der Rekursionsgleichung haben wir die Meistermethode verwendet. Dies ist naheliegend, da diese in der allgemeinen Form
\begin{align}
\mathit{T}\left(n\right) &= a \cdot \mathit{T}\left(\frac{n}{c}\right) + f \left(n\right)
\end{align}
vorkommenden Variablen eine ganz bestimmte Bedeutung haben:
:Anzahl der Teilprobleme: $a \dots$
:Größe des Teilproblems, wobei die Zerlegung immer "aufgehen" möge: $\frac{n}{c} \dots$
==== worst case ====
Dieser Fall ist etwas sonderbar, da hier eine vollständig sortierte Liste schon vorliegt und das Ergebnis eigentlich schon entsprechend vorhanden ist.
Hier ist die Rekursionsgleichung:
\begin{align}
\mathit{T}\left(0\right) &= 0\notag\\
\mathit{T}\left(0\right) &= \underbrace{\mathit{T}\left(0\right)}_\text{= 0} + \mathit{T}\left(n - 1\right) + c \cdot n\notag
\end{align}
Diese Gleichung kann iterativ gelöst werden.
\begin{align}
\mathit{T}\left(n - 1\right) &= \mathit{T}\left(n - 2\right) + c \left(n - 1\right)\notag\\
\mathit{T}\left(n - 2\right) &= \mathit{T}\left(n - 3\right) + c \left(n - 2\right)\notag\\\\
\vdots \\\\
\mathit{T}\underbrace{\left(\ n - k \ \right)}_{\text{ = 1 $\curvearrowright$ k = n - 1}} &= \mathit{T}\left(0\right) + c \left(n - k\right)\notag\\
\end{align}
Setzt man jeden Ausdruck in die Klammer ein, so kommt man auf
\begin{align}
\begin{array}{rcl}
T(n) &=& c \cdot \sum\limits_{k=0}^{n-1} \left(n-k\right)\\\\
&=& c\cdot(\sum\limits_{k=0}^{n-1} n - \sum\limits_{k=0}^{n-1} k)\\\\
&=& c\cdot\left(n^2 - \frac {n-1}{2}\left(\left(n-1\right)+1\right)\right)\\\\
&=& c\cdot\left(n^2 - \frac {n^2 -n}{2}\right)\\\\
&=& c\cdot\left(\frac {n^2} {2} + \frac {n} {2}\right)
\\\\\\
T(n) &=& \mathcal{O}\left(n^2\right)\\\\
\end{array}\notag
\end{align}
==== average case ====
Hier wird davon ausgegangen das jede der $\mathit{n}$ Teillistenlängen mit der gleichen Wahrscheinlichkeit auftritt, nämlich $\dfrac{1}{n}$.
Dann gilt:
\begin{align}
\begin{array}{rcl}
T(i) = T\left(n-i-1\right) = \frac {1}{n} \cdot \sum\limits_{j=0}^{n-1} T\left( j\right)\\\\
T(n) = \underbrace{T\left(i\right)}_{linke\ Teilliste} + \underbrace{T\left(n-i-1\right)}_{rechte\ Teilliste} + \underbrace{c \cdot n}_{Teillistenbildung}\\\\
\end{array}
\end{align}
Setzt man dies dann ein, so ergibt sich folgendes:
\begin{align}
\begin{array}{rcl}
T\left(n\right) &=& \frac {2}{n} \sum\limits_{j=0}^{n-1} T\left(j\right) + c \cdot n\\\\
\end{array}
\end{align}
Nun wird die Summe beseitigt, dazu bilden wir Differenzen.
\begin{align}
\begin{array}{rcl}
nT\left(n\right) &=& 2 \sum\limits_{j=0}^{n-1} T\left(j\right) + c \cdot n^{2} \\\\
\left(n-1\right)T\left(n-1\right) &=& 2 \sum\limits_{j=0}^{n-2} T\left(j\right) + c \cdot \left(n-1\right)^2 \mid \text{für} \ n:=n - 1; -\\\\
\\\\
nT\left(n\right) - \left(n-1\right)T\left(n-1\right) &=& 2T\left(n-1\right) + 2cn - c \mid -c\ \text{entfällt für}\ n \rightarrow \infty\\\\
\frac{T\left(n\right)}{n+1} &=& \frac{T\left(n-1\right)}{n} + \frac{2c}{n+1}\\\\
\frac {T\left(n-1\right)}{n} &=& \frac{T\left(n-2\right)}{n-1} + \frac{2c}{n}\\\\
\vdots & & \vdots\\\\
\frac{T\left(2\right)}{3} &=& \frac{T\left(1\right)}{2} + \frac{2c}{3}\\\\
\\\\
\frac{T\left(n\right)}{n+1} &=& \underbrace{\frac{T\left(1\right)}{2}}_{=0, da\ T\left(1\right) =0} + 2 \sum\limits_{i=3}^{n+1} \frac{1}{i}\\\\
\end{array}
\end{align}
Bei der Benutzung der bekannten Schranken $\frac {\lfloor log_{2} \ n \rfloor +1}{2} < \mathit{H}_{n} \leq \lfloor log_{2} \ n \rfloor +1$ für die Harmonischen Zahlen $\mathit{H}_{n} = \sum\limits_{k=1}^{n} \frac{1}{k}$.
\begin{align}
\frac {T\left(n\right)}{n+1} = \mathcal{O} \left(log_{2} \ n\right)\curvearrowright T\left(n\right) = \mathcal {O} \left(n \cdot log_{2} \ n\right)
\end{align}
Die Effizienz von Quicksort in allen drei Fällen:
\begin{align}
\begin{array}{|c|c|}
\hline
best \ case & \Theta\left(n \ \log_{2} n\right) \\
\hline
average \ case & \mathcal{O}\left(n \ \log_{2} n\right) \\
\hline
worst \ case & \Omega\left(n^{2}\right) \\
\hline
\end{array}
\end{align}
== Mergesort ==
Mergesort und Quicksort sind eng miteinander Verwandt, Merge kann mit Zusammenführen übersetzt werden. Eine zu sortierende Gesamtliste
:''L'' $= \left(Le_{1}, Le_{2}, Le_{3}, \dots , Le_{n}, Re_{1}, Re_{2}, Re_{3}, \dots , Re_{m}\right)$
wird in zwei etwa gleich große Teillisten,
:''TL''$= \left(Le_{1}, Le_{2}, Le_{3}, \dots , Le_{n}\right)$ und ''TR''$= \left(Re_{1}, Re_{2}, Re_{3}, \dots , Re_{m}\right)$
geteilt.
:$n = |L|\div 2 = m\div 2$.
Es wird kein Vergleich oder Vorsortierung vorgenommen.Das $\div$ Zeichen steht für eine ganzzahlige Division. Es gilt entweder $m = 2n$ oder $m = 2n +1$. Dann werden die beiden Teillisten rekursiv, das bedeutet mit Mergesort, sortiert. Die Elementarfälle sind die selben wie bei Quicksort.
Der dritte Schritt besteht darin, die sortierten Teillisten mit einem Reißverschlusssystem wieder zusammenzufügen. Die jeweiligen führenden Teilelemente $Le_{i}$ und $Re_{j}$ gelangen an ein "Tor", wenn $Le_{i} < Re_{j}$ gilt wird $Le_{i}$ durchgelassen und nimmt die nächste freie Position in der Gesamtliste ein. $Re_{j}$ wird dann mit $Le_{i+1}$ verglichen. Ansonsten natürlich umgekehrt.
<code id="5263f65037ec9">
(define mergesort
(lambda (ls)
(if(or (null? ls)(null? (cdr ls)))
ls
(call-with-values
(lambda() (teillisten2 ls))
(lambda (ls1 ls2)
(verbinden
(mergesort ls1)
(mergesort ls2)))))))
</code>
<code id="5263f6503801c">
(define teillisten2
(lambda (ls)
(let ((k (floor (/ (length ls) 2))))
(letrec
((helfer
(lambda (ls i)
(if (= i 0)
(values '() ls)
(call-with-values
(lambda () (helfer (cdr ls)(- i 1)))
(lambda (links rechts)
(values (cons (car ls) links) rechts)))))))
(helfer ls k)))))
</code>
<code id="5263f6503819f">
(define verbinden
(lambda (lls rls)
(cond
((null? lls) rls)
((null? rls) lls)
(else
(let (( x (car lls)) ( y (car rls)))
(if (< x y)
(cons x (verbinden (cdr lls) rls))
(cons y (verbinden lls (cdr rls)))))))))
</code>
<run id="5263f65038616">(mergesort '(9 2 7 12 8 24 78 3 77 1))</run>
=== Effizienz von Mergesort ===
Um Mergesort zu analysieren ist die Rekursionsgleichung
:$\mathcal{\mathit{T}\left(n\right) = 2\cdot \mathit{T}\left(\frac{n}{2}\right)+\Theta\left(n\right)}$
mit
:$\mathcal{T(0)=0}$
und
:$\mathcal{T(1)=0}$
zu lösen. Wir nehmen vereinfacht an das die Anzahl der Elemente $n$ eine Zweierpotenz ist.
Das Ergebnis lautet für alle auftretenden Fälle, also best case, worst case und average case
:$\mathit{T}\left(n\right) = \mathcal{O}\left(n \log_{2} n\right)$
Das ist kein Zufall, da Quicksort und Mergesort eng miteinander verwand sind, ist dies auch das Ergebnis für den best case bei Quicksort.
==Internes Sortierverfahren==
Die bisherigen Implementierungen von Quick- bzw. Mergesort verstoßen gegen eine wichtige Forderung, welche auch für für die zwei genannten Verfahren gilt. Es handelt sich um interne Sortierverfahren, das bedeutet es darf dem Vorgabefeld gegenüber kein zusätzlicher Speicher benutzt werden. Die Prozedur Teile gibt aber zwei Listen zurück, die einen neuen Speicherplatz benutzen. Es muss also der Erzeugung der Teillisten besondere Aufmerksamkeit gegeben werden. Mit der Idee des Splitting-Algorithmus "Burn the candle on both ends" wird die Bildung der Teillisten ohne Zusatzspeicher umgesetzt.
Das Vergleichselement $\mathcal{v}$ ist in diesem Fall die 0-te Listenkomponete, also $a_{0}$. Ein linker Zeiger $l$ steht auf $a_{1}$. Ein weiterer Zeiger $r$ steht auf dem Element $a_{n-1}$. $l$ wird solange um eins nach rechts geschoben bis gilt $a_{l} > \mathcal{v}$. Bei $r$ wird dies analog durchgeführt allerdings bis $a_{l} < \mathcal{v}$ gilt. Dies erfolgt jeweils in Einzelschritten. Wenn nach den Zeigerwanderungen immernoch gilt $\mathit{l}\leq \mathit{r}$ werden die beiden Zeiger vertauscht, danach werden die Zeigerwanderungen fortgesetzt. Anderenfalls werden die Zeigerbewegungen eingestellt und $a_{r}$ mit $a_{0}$ vertauscht. $\mathcal{v}$ steht nun an der richtigen Position da alle Elemente kleiner oder größer sind als $\mathcal{v}$. Die Liste wird dann als Ergebnis zurückgegeben.