Teile und Herrsche 1 SS10

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2010-04-09T00:36:38+00:00. Aktuelle Version

Inhaltsverzeichnis

Autoren:


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.

D a C (eng. "Divide and Conquer") auf deutsch "Teile und Herrsche" genannt und in lat. "divide et impera". Es beschreibt folgendes Vorgehen bei Problemen:

  1. Teile das Problem in eine Anzahl von Teilproblemen auf. (divide)
  2. Beherrsche die Teilprobleme durch rekursives Lösen. Wenn die Teilprobleme ausreichend klein sind, dann löse die Teilprobleme sofort. (conquer)
  3. Verbinde die Lösungen der Teilprobleme zur Lösung des Ausgangsproblems. (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 D a C

Ein großer Vorteil von der Technik Divide and 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 PC's verwendet werden. Die heutigen MultiCore Prozessoren arbeiten nach dem Schema DaC. Die einzelnen Kernen müssen sich den Speicher und die Aufgaben teilen, dies geschieht mit dieser D a C Technik.

MultiCore.jpg


Aufwandsbetrachtung von D a C

In der untenstehenden Formel wird erklärt, wie sich der Gesamtaufwand T\left( n \right) eines Algorithmus B aus den Teilproblemen multipliziert mit der Größe von Teilproblemen \frac{n}{2} plus den Teiler von n im rekursiven Aufruf ergibt. Dies alles wird dann anschließend mit einem Aufwand in O\left( n \right) verbunden.


\begin{array}{ccl} T_B \left( n \right) & = & 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. Leider ist zu sehen, dass wir immer noch einen quadratischen Aufwand verzeichnen. Erst wenn der Exponent fällt, kann der Faktor von große n wieder in Betracht gezogen werden.

Das schnelle Sortieren

Das Musterbeispiel für Divide and Conquer, nennt sich Quicksort. Dies 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.

Quicksort wendet folgende D a C Technik an:

  1. Zerlege das Problem ganau in zwei Teilprobleme (möglicherweise leer), L linkes Problem und R rechtes Problem. Alle Elemente in L < und R > , als das Pivotelement (Vergleichselement).
  2. Sortiere die beiden Teilprobleme L und R durch rekursiven Aufruf von Quicksort.
  3. Das sortierte Grundproblem G_s_o_r_t_i_e_r_t setzt sich wie folgt zusammen: L_s_o_r_t_i_e_r_t v R_s_o_r_t_i_e_r_t

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.

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei daten das zu sortierende Feld ist. Dabei hat beim ersten Aufruf von quicksort (oberste Rekursionsebene) der Parameter links den Wert 0 (Index des ersten Feld-Elements) und rechts den Wert n-1 (Index des letzten Feld-Elements). Die Bezeichnungen links und rechts beziehen sich auf die Anordnung des Felds: daten[0], daten[1], ... , daten[n-1].

funktion quicksort(links, rechts)
    falls links < rechts dann
        teiler := teile(links, rechts)
        quicksort(links, teiler-1)
        quicksort(teiler+1, rechts)
    ende
ende
funktion teile(links, rechts)
    i := links 
    // Starte mit j links vom Pivotelement
    j := rechts - 1
    pivot := daten[rechts]
    wiederhole
        // Suche von links ein Element, welches größer als das Pivotelement ist
        wiederhole solange daten[i] ≤ pivot und i < rechts
            i := i + 1  
        ende 
        // Suche von rechts ein Element, welches kleiner als das Pivotelement ist
        wiederhole solange daten[j] ≥ pivot und j > links
             j := j - 1 
        ende  
        falls i < j dann 
            tausche daten[i] mit daten[j]
        ende
    solange i < j // solange i an j nicht vorbeigelaufen ist 
    // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
  
    falls daten[i] > pivot dann
            tausche daten[i] mit daten[rechts] 
    ende
    
    // gib die Position des Pivotelements zurück
   
    antworte i
ende
Quelle Wikipedia

Quicksort Bildlich

QuickSort.png
QuickSort.png

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 Quicksort

Hier geht es zur 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

  1. 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).
  2. Conquer:
    Dieses Verfahren, sortiert zwei Teillisten rekursiv mit Hilfe von Sortieren durch Mischen. Ausnahme sind kleine Unterprobleme, diese werden direkt gelöst.


Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei liste die zu sortierenden Elemente enthält.

funktion mergesort(liste);
  falls (Größe von liste <= 1) dann antworte liste
  sonst
      halbiere die liste in linkeListe, rechteListe
      antworte merge(mergesort(linkeListe), mergesort(rechteListe));
funktion merge(linkeListe, rechteListe);
   neueListe
   solange (linkeListe und rechteListe nicht leer)
   |    falls (erstes Element der linkeListe <= erstes Element der rechteListe)
   |    dann füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
   |    sonst füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
   solange_ende
   solange (linkeListe nicht leer) 
   |    füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe
   solange_ende
   solange (rechteListe nicht leer) 
   |    füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe
   solange_ende
   antworte neueListe
Quelle Wikipedia

Mergesort Bildlich

Merge_sort_animation2.gif
Mergesort.gif

Schemeumsetzung

<eval id="4bbdf2704047a">(merge-sort &lt; '(3 5 4 1 7 9 6 8 2))</eval>

Javaumsetzung Mergesort

Hier geht es zur Javaumsetzung:

Vergleich Quicksort und Mergesort

Aufwandsbetrachtungen

Also Borstel - hier soll T(n) rein mit n=10 usw. ebenso auch noch n^2 (worst Case) für die n Fälle und für (n log2 (n)) (best und average)

\begin{array}{|c|c|c|c|c|c|c|} \hline & \text Rechenzeit in s fuer n\\ \hline T(n) & n = 10 & n = 100 & n = 1000 & n = 10000 & n = 100000 & n = 1000000\\ \hline n & 10^{-5} & 10^{-4} & 10^{-3} & 0,01 & 0,1 & 1\\ \hline n^2 & 10^{-4} & 0,1 & 1 & 100 & 10000 \approx 2,8 d & 1000000 \approx 277 h 45 min \\ \hline n * \log_2(n) & \approx 3,2 * 10^{-5} & \approx 6,6 * 10^{-4} &\approx 1,0 * 10^{-2} & \approx 0,13 & \approx 1,7 & \approx 20 \\ \hline \end{array}


Aus urheberrechtlichen Gründen, konnten wir die Tabelle mit der Aufstellung der Rechenzeit für (n) in Sekunden nicht verwenden und verweisen deshalb auf folgende Seite:

Hinweis - Ihr solltet bei der angegebenen Seite etwas runterscrollen!

Übungen