AuK/Teile und Herrsche 1 SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== Die Idee ==
"Teile und Herrsche" (engl. "divide and conquer" bzw. lat. "divide et impera") beschreibt ein Verfahren zur Lösung von Problemen, wobei das Problem<br />
# in Teilprobleme zerlegt wird
# die Teilprobleme gelöst werden
# die Teilprobleme zu einer Lösung vereint werden.<br />
<br />
Die folgende Rechnung dient als Beweis, dass eine Effizienzverbesserung auftritt:<br />
Wir nehmen an, dass ein bestimmter Algorithmus <math>A</math> ein Problem mit <math>O\left(n^2\right)</math>, also <math>T_A\leq c \cdot n^2</math>, löst. Für ein Algorithmus <math>B</math>, der drei dieser Probleme der Größe <math>\frac{n}{2}</math> mit <math>A</math> bearbeitet und mit <math>O\left( n \right) </math> zusammenfügt gilt:<br /><br />
<math>
\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 c\\\\
& \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}nc+\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}
</math><br /><br />
Es tritt also eine Effizienzverbesserung um 25% auf. Da der Aufwand allerdings quadratisch ist, kann man bei großen n den Faktor vernachlässigen. Es ist also offensichtlich das eine Effizienzverbesserung nur auftritt, wenn der Exponent kleiner wird.<br /><br />
Um dies zu erreichen nehmen wir an, das wir einen Algorithmus <math>C</math> haben, der die Teilprobleme rekursiv löst. Das bedeutet, dass der Algorithmus auch die Teilprobleme löst, einzig die Basisfälle <math>n \leq n_0</math> werden von dem Algorithmus <math>A</math> übernommen. Das bedeutet:<br /><br />
<math>T_C(n)=\begin{cases}T_A(n), & wenn n\leq n_0 \\ 3T_C(\frac{n}{2}), & sonst\end{cases}</math><br /><br />
Die Anwendung der Meistermethode ergibt:<br />
<math>T_C(n)=O(n^{1,59})</math>.<br /><br />
Anhand der Ergebnisses kann man sehen, das "Teile und Herrsche" aus Effizienzgründen immer mit Rekursion arbeitet.
== Quicksort ==
=== Das Verfahren ===
Quicksort wurde 1962 von C.A.O. Hoare entwickelt und ist ein Algotithmus, der nach dem "Teile und Herrsche" - Verfahren arbeitet.<br />
Die Idee von Quicksort besteht darin, jedes Listenelement mit einem Vergleichselement (Pivotelement) zu vergleichen und, je nachdem ob es kleiner oder größer ist, in eine linke oder eine rechte Liste einzufügen. Auf die beiden Teillisten wird jetzt wieder Quiksort angewandt (rekursive Verarbeitung aus Effizienzgründen) und anschließend werden die beiden Listen und das Pivotelement nach folgender Vorschrift zusammengefügt:<br />
# linke Liste
# Pivotelement
# rechte Liste.
Damit die rekursive Abarbeitung terminiert, müssen noch zwei Basisfälle vorgesehen werden:<br />
# die Gesamtliste ist leer
# die Gesamtliste besteht aus nur einem Element.
In beiden Fällen ist die Liste schon sortiert.
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
<language>Scheme</language>
=== Funktionsorientierte Beschreibung ===
Die linke bzw. rechte Teilliste wird in dem folgendem Beispiel von den Hilfsfunktionen ''linke_liste'' und ''rechte_liste'' erzeugt. Das Pivotelement wird durch die Funktion ''trennelement'' ermittelt. Die Teillisten werden in der Hauptfunktion durch rekusrive Aufrufe von Quicksort ebenfalls sortiert und danach zu einer Erbnisliste zusammengefügt.<br />
<code>
;Hilfsprozedur um ein Pivotelement zu erzeugen
(define trenneelement
(lambda (ls)
(if (null? ls)
('())
(car ls))))
;Hilfsfunktion zur Erzeugung der linken Liste
(define linke_liste
(lambda (ls v)
(cond
((null? ls) '())
((= (car ls) v) (cons (car ls) (linke_liste (cdr ls) v)))
((< (car ls) v) (cons (car ls) (linke_liste (cdr ls) v)))
(else
(linke_liste (cdr ls) v)))))
;Hilfsfunktion zur Erzeugung der rechten Liste
(define rechte_liste
(lambda (ls v)
(cond
((null? ls) '())
((> (car ls) v) (cons (car ls) (rechte_liste (cdr ls) v)))
(else
(rechte_liste (cdr ls) v)))))
;Hauptfunktion
(define quicksort_trad
(lambda (ls)
(cond
((null? ls) ())
(else
(append (quicksort_trad (linke_liste (cdr ls) (trenneelement ls))) (list (trenneelement ls))
(quicksort_trad (rechte_liste (cdr ls) (trenneelement ls))))))))
</code>
<eval>
(quicksort_trad '(9 129 4 2548 4 2395 9 82 4 21 5 2 1 4 6 3 5 67))
</eval>
Da die beiden Funktion ''linke_liste'' und ''rechte_liste'' sich nur durch das Relationszeichen unterscheiden könnte man die Teillistenbildung auch in einer Prozedur abhandeln. Nun besteht hier das Problem, dass in der funktionsorientierten Programmierung Prozeduren nur ein Funktionswert (Rückgabewert) besitzen. Es ist allerdings möglich, die beiden Teillisten wieder in einer Liste zu verpacken. Da die Teillisten aber bei den rekursiven Aufruf wieder benötigt werden, müsste die entsprechende Teilliste vor Aufruf von Quicksort wieder ausgepackt werden. Man sieht, dass dies ein ständiges verpacken und entpacken bedeutet.<br />
<br />
Die Lösung liegt im '''Multiple-value-context'''. Dabei können Funktionen mehrere Funktionswerte besitzen, die an andere Funktionen weitergegeben und weiterverarbeitet werden können.<br />
Dafür sind zwei Sprachelemente von nöten:
* (values a1 a2 ... an) liefert n Rückgabewerte
* (call-with-values p c) nimmt zwei Argumente, einen ''Producer'' (p) und einen ''Consumer'' (c)
Der ''Producer'' ist eine nullstellige Prozedur, der n Rückgabewerte dem n-wertigen ''Consumer'' liefert.<br />
<br />
Nachfolgend ist eine Prozedur zu sehen, die die Teillisten erzeugt und die jeweiligen Listen getrennt zurück gibt.
<code>
(define teillisten
(lambda (ls v)
(if(null? ls)
(values '() '())
(call-with-values
(lambda () (teillisten (cdr ls) v))
(lambda (links rechts)
(let ((x (car ls)))
(if (< x v)
(values (cons x links) rechts)
(values links (cons x rechts)))))))))
</code>
<eval>
(teillisten '(9 2 7 12 4 1 24 77 3 1) 8)
</eval>
Um jetzt Quicksort rekursiv auszuführen, wird in der folgenden Prozedur ''teillisten'' mittels ''call-with-values'' auf den Consumer angewandt. Der Consumer ruft dann Quicksort einmal für die linke und einmal für die rechte Liste auf.
<code>
(define mv-quicksort
(lambda (ls)
(if (or (null? ls)(null? (cdr ls)))
ls
(let ((v (car ls)))
(call-with-values
(lambda ()(teillisten (cdr ls) v))
(lambda (links rechts)
(append
(mv-quicksort links)
(list v)
(mv-quicksort rechts))))))))
</code>
<eval>
(mv-quicksort '(9 129 4 2548 4 2395 9 82 4 21 5 2 1 4 6 3 5 67))
</eval>
=== Effizienz von Quicksort ===
=== Interne Suchberfahren ===
== Mergesort ==
=== Das Verfahren ===
=== Funktionsorientierte Beschreibung mit Multiple-value-context ===
=== Effizienzanalysen ===