AuK/Teile und Herrsche 1 SS09

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>
=== 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)))
      (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 ls (trenneelement ls))) (list (trenneelement ls)) (quicksort_trad (rechte_liste ls (trenneelement ls))))))))

(quicksort_trad '(9 129 4 2548 4 2395 9 82 4 21 5 2 1 4 6 3 5 67))
</code>

=== Effizienz von Quicksort ===
=== Interne Suchberfahren ===


== Mergesort ==
=== Das Verfahren ===
=== Funktionsorientierte Beschreibung mit Multiple-value-context ===
=== Effizienzanalysen ===