Teile und Herrsche

Inhaltsverzeichnis 1 '''Teile und herrsche (divide et impera)''' 1.1 Definition 1.2 Entwurfsmethode für Algorithmen 1.3 Eigenschaften 1.4 Instanzen 1.5 Beispiele 1.5.1 Beispiel 1 : Sortierverfahren (Merge-Sort) 1.5.2 Beispiel 2: Lebkuchenhaus 1.5.3 Beispiel 3 : Die Türme von Hanoi 1.6 Übung 1 : Die Türme von Hanoi 1.6.1 Neuigkeit 1.6.2 Spiele 1.7 Übung 2 : Hanoi Java-Code 1.7.1 Pseudo - Code 1.7.2 Java-Code 2 Quicksort 2.1 Das Verfahren 2.2 funktionaler Aufbau 2.3 Viualisierung 2.4 Beispiel 2.5 Effizienz von Quicksort 3 '''Mergesort''' 3.1 Definition 3.2 Vorteile 3.3 Nachteile 3.4 Anwendung 3.5 Pseudocode 3.6 Animation 3.7 Beispiele 3.7.1 Beispiel 1 3.7.2 Beispiel 2 3.8 Viualisierung 3.9 Übungen 3.9.1 Übung 1 3.9.2 Übung 2 3.9.3 Übung 3 3.9.4 Übung 4 4 Binäres Suchen 5 Zusammenfassung 6 Quellen

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.

Übung 1 : Die Türme von Hanoi

Die Spielregeln

Es sind n Scheiben unterschiedlichen Durchmessers gegeben, welche geordnet zu einem Turm geschichtet sind, die untere Scheibe ist die größte. Der Turm steht auf einem Anfangsplatz. Unter Verwendung eines Hilfsplatzes soll dieser Turm nun zu einem Zielplatz transportiert werden, wobei verschiedene Regeln einzuhalten sind.

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

Lösung

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.

Spiele

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

Übung 2 : Hanoi Java-Code

Pseudo - Code

Bedeutung der Variablen:

ap - Anfangsplatz
zp - Zielplatz
hp - Hilfsplatz
n - Anzahl der Scheiben
Die Übergabe des Hilfsplatzes als Parameter kann auch entfallen, wenn man als Berechnung einsetzt:
hp := 6 - ap - zp.

Java-Code

• Schreiben Sie Java-Code für Hanoi Java-Code fort.
  

1. Implementieren Sie eine Klasse "Hanoi".

Klasse bewege
Bewegt n Scheiben von Turm a nach Turm c und benutzt als Zwischenspeicher Turm b.
1. Implementieren Sie in der Klasse eine Klasse "bewege" mit den Parameter: a,b,c als char und n als int Variable .
2. Implementieren Sie die Schleife:
- if(n==1) than Drucken Sie die Text : ("Lege die oberte scheiben von " + ... + "Turm" + ... + "auf Turm" + ... + ".");

Klasse Main
1. Implementieren Sie eine Klasse "Main".
2. Benutzen Sie die Klasse(Methode) bewege.

Quicksort

Das Verfahren

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

funktionaler Aufbau

Viualisierung

Die folgende Animation zeigt den verbildlichten Ablauf des Algorithmus:

Beispiel

Effizienz von Quicksort

Mergesort

Definition

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 * \mathit{T}(n/2) Schritte.
                Das Mischen braucht \mathcal{O}\left(n\right) Schritte.
                Also: \mathit{T}\left(n\right) = 2 * \mathit{T}(n/2) + \mathcal{O}\left(n\right), wenn n > 1 .

        (Best-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.

Pseudocode

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.
  

1. Aufteilen der Eingabe

2. Teilen, Sortieren und Mischen der Eingabe

3. Mischen der Eingabe

4. Ergebnis

Übung 2

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

1. Aufteilen der Eingabe

2. Rekursiv Sortieren

3. Zusammenfügen

Ü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];

    }

Klasse MergeSort

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 .

Klasse Main

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 Zeit­komplexitä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/
http://www.roland-illig.de/