Teile und Herrsche

Aus ProgrammingWiki
Archivierte Version vom 2016-01-01T13:48:46+00:00. Aktuelle Version

Inhaltsverzeichnis

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).


S3anbrem_Def.PNG

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.

S3anbrem_Anw.PNG

Beispiel: 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 ]

Eigenschaften

  • kann bei konzeptionell schwierigen Problemen hilfreich sein

  • kann effiziente Lösungen realisieren

  • für Parallelverarbeitung geeignet

Instanzen

  • Mergesort
  • Quicksort
  • Intervallhalbierung (Binärbäumen)

Anwendung

Beispiele

  • Lebkuchenhaus

S3anbrem_B1.PNG

Ü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.

S3anbrem_U1.png


Lösung

S3anbrem_B4.PNG

Teilprobleme

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.


Bei näherer Betrachtung der Teilprobleme fällt folgendes auf: a) Der 2. Schritt ist trivial und sofort ausführbar.
b) 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.



Bedeutung der Variablen:

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.

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

Quicksort

Mergesort

ein schnelleres (und rekursives) Sortierverfahren.

  • Analogie: Sortieren eines Kartenstapels
  • Karten sind mit Zahlen beschriftet

S3anbrem_Ms.PNG

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

Schritt 2 : Sortiere beide Stapel getrennt.
S3anbrem_Ms3.PNG

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.
S3anbrem_Ms4.png


Sortieren durch Mischen ( merge sort )

Teile n-elementige Folge in zwei Teilfolgen der Groeße n / 2 ( + 1 ). Sortiere die beiden Teilfolgen rekursiv. Füge die nunmehr sortierten Teilfolgen zusammen durch Reißverschlussverfahren.

Analyse von Merge-Sort

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.

Ubung 1

  • Sortierverfahren

S3anbrem_B1a1.PNG

1. Aufteilen der Eingabe

S3anbrem_B1a.png

2. Rekursiv Sortieren

S3anbrem_B1b.png

3. Zusammenfügen

S3anbrem_B1c.png

Ubung 2

n - Anzahl Elemente

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 .
4. Implementieren Sie die Schleifen :

  • für N kleiner gleich 1


1. Implementieren Sie eine Klasse „main".
2. Importieren Sie Scanner. 3. Deklarieren Sie zwei Variablen n und i.
4. Fragen Sie den Nutzer nach Anzahl die Elemente.
5. Initialisieren Sie diese Zahl als Variable n.
6. Erstellen Sie eindimensionales Array , welche beträgt new int[n].
7. Fragen Sie den Nutzer nach den Wert diese Elemente.
8. Implementieren Sie die Schleife , welche ruft diese Werte ab.
9. Benutzen Sie Mathode sort für arr,0,n.
10. 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.

Quellen

Wagenknecht, 2003, Algorithmen und Komplexität
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/