Teile und Herrsche

Aus ProgrammingWiki

Archivierte Version vom 2016-01-02T18:16:41+00:00. Aktuelle Version

Teile und herrsche (divide et impera)

Definition

Das Entwurfsverfahren Teile und Herrsche ( divide-and-conquer ) 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 gilt es dann, eine Gesamtlösung für das ursprüngliche Problem zusammenzusetzen ( conquer).

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

Instanzen

Mergesort
Quicksort
Intervallhalbierung (Binärbäumen)

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: Lebkuchenhaus

Beispiel 3 : 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.

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

Übung 1 : Die Türme von Hanoi

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

Neuigkeit

Der 2. Schritt ist trivial und sofort ausführbar.
Der 1. und der 3. Schritt sind von der gleichen Art wie das Ausgangsproblem, nur die Anzahl der Scheiben ist um 1 kleiner und die Bedeutung der Plätze hat sich verändert.

Damit hat man für das Gesamtproblem eine rekursive Lösungsvorschrift formuliert.

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;

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, dass alle Elemente von L kleiner als ein Vergleichselement v \in G und alle Elemente von R größer als v sind.

Hier und im folgenden wird vereinbart, dass alle Elemente von G natürliche Zahlen sind.

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, die für die Unterscheidung der Relation in Bezug auf das Pivotelement benötigt werden.
Durch Enstehung dieser ist aber die eigentliche Sortieung noch nicht beendet. Dafür bedarf es einer weiteren Prozedur die die vorhergehende solange rekursiv aufruft, bis alle Elemente sortiert sind. Die Sorierung erfolgt in der Implementierung einfach durch das Vertauschen der Vergeichselemente.

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

Viualisierung

Die folgende Animation zeigt den verbildlichten Ablauf des Algorithmus:

Beispiel

Effizienz von Quicksort

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 T(n) die Laufzeit von Merge-Sort.
                Das Aufteilen braucht O(1) Schritte.
                Die rekursiven Aufrufe brauchen 2 T(n/2) Schritte.
                Das Mischen braucht O(n) Schritte.
                Also: T(n) = 2 T(n/2) + O(n), wenn n > 1 NB T(1) ist irgendein fester Wert.

        (Best-Case: O(n log(n)), Worst-Case: O(n log(n)))

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.

Pseudocode

func mergesort( var a as array )
     if ( n == 1 ) return a

     var l1 as array = a[0] ... a[n/2]
     var l2 as array = a[n/2+1] ... a[n]

     l1 = mergesort( l1 )
     l2 = mergesort( l2 )

     return merge( l1, l2 )
end func

func merge( var a as array, var b as array )
     var c as array

     while ( a and b have elements )
          if ( a[0] > b[0] )
               add b[0] to the end of c
               remove b[0] from b
          else
               add a[0] to the end of c
               remove a[0] from a
     while ( a has elements )
          add a[0] to the end of c
          remove a[0] from a
     while ( b has elements )
          add b[0] to the end of c
          remove b[0] from b
     return c
end func

Animation

http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html

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.

Viualisierung

Übungen

Übung 1

Sortieren Sie eine Array.

Ü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

Schreiben Sie Java-Code für MergeSort fort.

 .......


        if (N <= 1)

            return;

        int mid = low + N/2;

        // recursively sort 

        sort(a, low, mid);

        sort(a, mid, high);

        // merge two sorted subarrays

        int[] temp = new int[N];

        int i = low, j = mid;

        for (int k = 0; k < N; k++)

        {

            if (i == mid)

                temp[k] = a[j++];

            else if (j == high)

                temp[k] = a[i++];

            else if (a[j]<a[i])

                temp[k] = a[j++];

            else

                temp[k] = a[i++];

        }

        for (int k = 0; k < N; k++)

            a[low + k] = temp[k];

    }

1. Implementieren Sie eine Klasse „MergeSort".
2. Implementieren Sie in der Klasse eine Methode „sort“ mit den Parameter:
- eindimensionales Array -> a
- low
- high
3. Deklarieren Sie Variable N und initialisieren als die Unterschied zwischen high und low .

1. Implementieren Sie eine Klasse „main".
2. Importieren Sie Scanner.
3. Fragen Sie den Nutzer nach Anzahl die Elemente.
4. Initialisieren Sie diese Zahl als Variable number_of_integer_elements.
5. Drucken Sie diese Zahl.
5. Erstellen Sie eindimensionales Array , welche beträgt new int[number_of_integer_elements].
6. Fragen Sie den Nutzer nach den Wert diese Elemente.(Schleife)
7. Implementieren Sie die Schleife , welche ruft diese Werte ab.
8. Benutzen Sie Methode sort für arr, 0, number_of_integer_elements.
9. Drucken Sie diese Elemente.

Binäres Suchen

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.

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/

Teile und Herrsche

Inhaltsverzeichnis