Teile und Herrsche

Aus ProgrammingWiki

Archivierte Version vom 2016-01-10T16:26:05+00:00. Aktuelle Version

Teile und herrsche (Divide and conquer)

Definition

Das Entwurfsverfahren Teile und Herrsche dient dem Entwurf rekursiver Algorithmen.
Die Idee ist es, ein Problem der Groeßen in mehrere gleichartige aber kleinere Teilprobleme zu zerlegen ( divide).
Aus rekursiv gewonnenen Lösungen der Teilprobleme ( conquer) gilt es dann, eine Gesamtlösung für das ursprüngliche Problem zusammenzusetzen .
Ziel dieser Methode ist es eine Effiziensverbesserung zu erreichen.

Entwurfsmethode für Algorithmen

1. Teile das Problem in kleinere Unterprobleme (Divide)
2. Löse rekursiv die entstehenden Unterprobleme (Conquer)
3. Setze die Lösungen zusammen.

Eigenschaften

kann bei konzeptionell schwierigen Problemen hilfreich sein
kann effiziente Lösungen realisieren
für Parallelverarbeitung geeignet

Beispiele

Beispiel 1 : Sortierverfahren (Merge-Sort)

Sortiere eine Array indem zwei Teilarrays sortiert und dann gemischt werden.

sort ( [ 19 17 23 31 3 5 7 29 2 11 17 ] ) Teile!
=> merge (
sort ( [ 19 17 23 31 3 ] ), Herrsche über Teilproblem 1
sort ( [ 5 7 29 2 11 17 ] ) ) Heersche über Teilproblem 2
= merge ( [ 3 17 19 23 31 ] , [ 2 5 7 11 17 29 ] ) Kombiniere zur Gesamtlösung
= [ 2 3 5 7 11 17 17 19 23 29 31 ]

Beispiel 2 : Die Türme von Hanoi

Wenn die Anzahl der Scheiben 1 beträgt, ist die Lösung des Problems trivial.
Bei mehr als einer Scheibe läßt sich das Gesamtproblem in drei Teilprobleme zerlegen:

Transportiere n-1 Scheiben vom Anfangsplatz auf den Hilfsplatz.
Transportiere die letzte Scheibe vom Anfangsplatz auf Zielplatz.
Transportiere n-1 Scheiben vom Hilfsplatz auf den Zielplatz.

Übung 1 : Die Türme von Hanoi

Transportiere n Scheiben vom Anfangsplatz auf den Zielplatz, verwende einen Hilfsplatz.

Übung 2 : Hanoi Java-Code

Pseudo - Code

procedure turm(ap,zp,hp,n:byte);  
begin 
if n=1 then  
writeln(' Scheibe von Platz ',ap,' auf Platz ',zp)
        else begin  
        turm(ap,hp,zp,n-1);  
        writeln(' Scheibe von Platz ',ap,' auf Platz ',zp);  
        turm(hp,zp,ap,n-1);
     end;  
end;

Java-Code

Auf der Grundlage diese Pseudocode schreiben Sie Java-Code für Hanoi.
Denken Sie auch an der Klasse Main, welche wird die Methode turm benutzen.

...

Spiele

http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm

Quicksort

Das Verfahren

Quicksort ist ein schneller Sortieralgorithmus auf der Basis rekursiver Vergleiche von Elementen, welcher von C.A.O Hoare im Jahre 1960 entwickelt wurde.

Das Prinzip ist eine gegebene Gesamtliste G so in zwei Teillisten L und R auf zuteilen (divide), dass alle Elemente von L kleiner (oder gleich) als ein Vergleichselement (Pivotelement) v \in G
und alle Elemente von R größer (oder gleich) als v sind.

Es existieren zwei Basisfälle:
1. : G ist leer
2. : G enthält nur ein einziges Element

Wird nun der Quicksortalgorithmus auf jede der enstandenen Teillisten angewandt, ergibt sich dadurch die rekursive Verarbeitung. Und es wird dann nach endlich vielen Zerlegungen einer der beiden Basisfälle erreicht.
Das bedeutet die Teillisten liegen dann sortiert vor (conquer). Letztlich setzt man die einzelnen Teillisten zu der sortierten Gesamtliste G_sortiert zusammmen (combine) und zwar genau in der Form: G_sortiert = L_sortiert v R_sortiert

funktionaler Aufbau

(define teillisten
       (lambda (ls v)
           (if (null? ls)
               (values '() '())
               (call-with-values
               (lambda () (teillisten (cdr ls) v))
               (lambda (l r)
                   (let ((x (car ls)))
                      (if (< x v)
                          (values (cons x l) r)
                          (values l (cons x r)))))))))

Durch diese Prozedur entstehen die zwei Teillisten L und R, die für die Unterscheidung der Relation in Bezug auf das Pivotelement benötigt werden.

Um nun den Algorithmus richtig anwenden zu können, bedarf es einer weiteren Prozedur, die die Vorhergehende immer wieder rekursiv aufruft und dabei jeweils auf L und R quicksort anwendet um diese zu sortieren.

(define quicksort
    (lambda (ls)
        (if (or (null? ls) (null? (cdr ls)))
            ls
            (let ((v (car ls)))
                (call-with-values
                    (lambda () (teillisten (cdr ls) v))
                    (lambda (l r)
                        (append
                           (quicksort l)
                           (list v)
                           (quicksort r))))))))

interne Suchverfahren

Quicksort kann in die Kategorie der internen Suchverfahren eingeordnet werden. Das sind Algorithmen die in-place arbeiten, was bedeutet sie benötigen keinen zusätzlichen Speicherplatz.
Bei der vorherigen Implementierung ergibt sich aber eben dieser Nachteil dadurch, dass die Elemente von G, die die jeweilige Relation (>= v oder <= v) erfüllen, in eine der beiden erzeugten Listen eingetragen werden.
Im Erzeugen von L und R liegt also hier das Problem.

Um die Bedingung des Quicksort Algorithmus (l <= v <= r) erfüllen zu können und den genannten Nachteil zu eliminieren, nutzt man die Idee, die die folgende Implementierung verfolgt. Zunächst um der Speicherplatzbildung entgegenzuwirken muss die Bildung der Teillisten in G erfolgen. Um auf jedes Element zugreifen zu können, wird in der folgenden Implementierung ein Vektor a verwendet.
Das Pivot erhält die erste Poition, also a[0]. Zusätzlich werden zwei Zeiger l und r initiiert, wobei l = a[1] und r = a[n-1].

(define split
  (lambda (a)
    (let
        ((v (vector-ref a 0))
         (swap
          (lambda (pos1 pos2)
            (let ((helper 'nothing))
                  (set! helper (vector-ref a pos1))
                  (vector-set! a pos1 (vector-ref a pos2))
                  (vector-set! a pos2 helper)))))
         (letrec
             ((loop
               (lambda (l r)
                 (cond
                   ((> l r) (swap 0 r) a)
                   ((< (vector-ref a l) v)(loop(+ l 1) r))
                   ((not (< (vector-ref a r) v))(loop l (- r 1)))
                   (else
                    (swap l r)
                    (loop (+ l 1)(- r 1)))))))
           (loop 1 (- (vector-length a) 1))))))

In Einerschritten wird:

1. l solange nach rechts verschoben bis a[l] > v und
   r solange nach links verschoben bis a[r] < v
2. wenn jeweils ein Element gefunden wurde, wird a[l] mit a[r] getauscht und die Zeigerbewegung fortgesetzt
3. ansonsten wird a[r] mit a[0] vertauscht und a ausgegeben 
4. Insofern die Elemente links bzw. rechts vom Pivotelement aus noch unsortiert sind wiederhole bei 1.

Viualisierung

Die folgende Animation zeigt den verbildlichten Ablauf des Algorithmus:

roter Balken = Pivotelement p der jeweiligen Teilliste
blaue Linie = Wert von p

Beispiel 1

Sortieren von (natürlichen) Zahlen:

In diesem Beispiel soll eine Liste L [6,13,3,7,9,7,2,1,15,10,5,6] mit Quicksort sortiert werden.
Es folgt eine ausführliche Lösung zum Erhalt der sortierten Liste:

Effizienz von Quicksort

Wegen Gründen der Vereinfachung zwecks Erklärung, wurde im Beispiel 1 das erste Element als Pivotelement gewählt, aber bei Anwendung des Algorithmus sollte man auf die Wahl achten.
Denn wie effizient der Quicksort-Algorithmus ist, hängt in erster Linie von der Wahl des Pivotelementes ab.

Best Case

Im besten Fall wird das Pivotelement so gewählt, dass dieses in der sortierten Liste genau in der Mitte liegt und somit die Gesamtliste G aus (etwa) zwei gleich großen Listen besteht.
Desweiteren arbeitet Quicksort besser je höher die Anzahl der Elemente n ist.

T(0) = 0

T(n) = 2 * T (\frac{n}{2}) + c * n

Nach Auflösung mit der Meistermethode ergibt das einen Aufwand T(n) = \mathcal{O}(n \ \log_{2} \ n) .

Average Case

Im Durchnitt nähert sich die Laufzeit gleichzeitig an den besten bzw. schlechtesten Fall an, was Insgesamt für eine ausgeglichene Laufzeit sorgt.

Worst Case

Im schlechtesten Fall wird das Pivotelement so gewählt, dass dieses in der sortierten Liste entweder am Anfang oder am Ende liegt und somit auf der einen Seite das Pivotelement v und auf der anderen Seite der Rest von G liegt.
Ist außerdem G vor Anwendung von Quicksort bereits sortiert, führt das zu einem sehr langsamen Quicksort, was zum einen aus Definitionssicht wiedersprüchlich erscheint und zum anderen aus Anwendersicht für Konfusion sorgt.

T(0) = 0

T(n) = \underbrace{T(0)}_\text{= 0} + T(n-1) + c * n

Anwendung der Iterationsmethode ergibt:

T(n-1) = T(n-2) + c(n-1)

T(n-2) = T(n-3) + c(n-2)

T\underbrace{( n-k )}_{\text{=1 \curvearrowright k = n - 1}} = T(0) + c(n-k)

Einsetzen aller Ausrücke in darüberstehender Zeile:
T(n) = c * \sum\limits_{k=0}^{n-1} (n-k)

\ \ \ \ \ \ \ \ = c * (\sum\limits_{k=0}^{n-1} (n) - \sum\limits_{k=0}^{n-1} (k))

\ = c (n^2 - \frac{n-1}{2}((n-1) + 1))

\ = c (\frac{n^2}{2} + \frac{n}{2})

T(n) = \mathcal(O)(n^2)

Mergesort

Definition

Das Sortierverfahren Mergesort erzeugt eine sortierte Folge durch Verschmelzen sortierter Teilstücke.
Das Verfahren beruht auf dem Divide-and-Conquer-Prinzip Erklärung.
Die zu sortierende Folge wird zunächst in zwei Hälften aufgeteilt (divide), die jeweils für sich sortiert werden (conquer).
Dann werden die sortierten Hälften zu einer insgesamt sortierten Folge verschmolzen (combine).
Dieses Verfahren bietet die Möglichkeit einer iterativen Implementierung.

Vorteile

Geschickter Einsatz der Teile-und-Herrsche Technik.
Gutes Laufzeitverhalten für große Eingabegrößen

                Sei \mathit{T}\left(n\right) die Laufzeit von Merge-Sort.
                Das Aufteilen braucht \mathcal{O}\left(1\right) Schritte.
                Die rekursiven Aufrufe brauchen 2\cdot \mathit{T}\left(\frac{n}{2}\right) Schritte.
                Das Mischen braucht \mathcal{O}\left(n\right) Schritte.
                Um Mergesort zu analysieren, ist die Rekursionsgleichung : \mathit{T}\left(n\right) = 2\cdot \mathit{T}\left(\frac{n}{2}\right) + \mathcal{O}\left(n\right), wenn n > 1
                Basisfall : \mathit{T}\left(1\right) = 0 , also :

Best-Case: \mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)
Average-Case: \mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)
Worst-Case: \mathit{T}\left(n\right) = \mathcal{O}\left(n \log n\right)

Die Stabilität

Die relative Ordnung zweier Elemente , welche gleich sind , wird beibehalten.

Abarbeiten Daten sequentiell.

Nachteile

der zusätzlich benötigte Speicher

Anwendung

Der Mergesort wird vor allem dann verwendet, wenn man eine große sortierte Datenmenge verwalten möchte.

Viualisierung , Simulation, Animation

http://palash90.in/tools.html#/algorithms/mergeSort http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html

Pseudocode

funtion mergesort( liste ):
  if liste.laenge <= 1 then 
      return liste;
  else
      linkeListe = liste[0] bis liste[laenge/2];
      rechteListe = liste[laenge-(laenge/2)] bis liste[laenge-1];
      linkeListe =mergesort(linkeListe);
      rechteListe=mergesort(rechteListe);
  return merge(linkeListe, rechteListe);
end

Beispiele

Beispiel 1

Beispiel 2

Analogie: Sortieren eines Kartenstapels
Karten sind mit Zahlen beschriftet

Schritt 1 : Teile den Stapel in zwei gleich grosse Stapel.

Schritt 2 : Sortiere beide Stapel getrennt.

Schritt 3 : Mische die beiden sortieren Stapel zu einem sortieren Stapel : lege dazu jeweils die kleinere der beiden oberen Karten umgedreht auf einen neuen Stapel.

Übungen

Übung 1

Sortieren Sie ein Array.

Zusammenfassung

Teile und Herrsche - Zerlegung größerer Aufgaben oder Probleme in kleinere Aufgaben oder Probleme, die einfacher zu bewältigen oder leichter gelöst werden können.
Mergesort - ein schnelleres (und rekursives) Sortierverfahren.
- Ein Feld wird in zwei Teilfelder aufgeteilt, die dann rekursiv sortiert werden. Anschließend werden diese sortierten Teilfelder wieder zu einem Feld zusammengefügt. Dabei macht man sich zu nutze, daß die beiden Teilfelder bereits sortiert sind.
- Mit einer Zeitkomplexität von Θ(n log(n)) ist das Verfahren immer optimal.
http://www.sorting-algorithms.com/

Übung 2

Sortieren Sie eine Array indem zwei Teilarrays sortiert und dann gemischt werden.

Übung 3

Sortieren Sie die Buchstaben in der Zeichenkette aus Ihrem zusammengeschriebenen Vor- und Nachnamen mit Merge Sort.

Übung 4

Binäres Suchen

Quellen

Wagenknecht, 2003, Algorithmen und Komplexität
Cormen, Leierson, Rivest und Stein, 2004, Algorithmen - Eine Einführung
http://www.inf-schule.de/
http://www.awb1.ch/
http://www.ki.informatik.uni-frankfurt.de/
http://ddi.cs.uni-potsdam.de/
http://thm.de/
http://de.wikiversity.org/
http://www.roland-illig.de/

Teile und Herrsche

Inhaltsverzeichnis