Teile und Herrsche

Aus ProgrammingWiki

Archivierte Version vom 2016-01-01T11:32:21+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Teile und herrsche (divide et impera)
2 Quicksort
3 Mergesort
- 3.1 Ubung1
4 Binäres Suchen
5 Zusammenfassung
6 Quellen

Teile und herrsche (divide et impera)

Definition

Teile und herrsche ist eine Problemlösestrategie, bei der ein Problem immer weiter in Teilprobleme zerlegt wird, bis sich diese einfach lösen lassen. Aus den Lösungen der Teilprobleme wird dann die Lösung des Gesamtproblems zusammengesetzt.

Anwendung

Bei der Anwendung der Technik Teile-und-Herrsche wird

das gegebene Problem auf die Lösung
mehrerer (oft zwei) kleinere Probleme der gleichen Art
der (etwa) gleichen Größe reduziert. Aus deren Lösung wird dann die Gesamtlösung konstruiert.

Beispiele

Beispiel: Merge-Sort Sortiere eine Array indem zwei Teilarrays sortiert und dann gemischt werden.
sort ([1 9 7 2 7 4 7 2 8]) Teile!
=> merge(

     sort([1 9 7 2 7]),              Herrsche über Teilproblem 1 

     sort([4 7 2 8]))                Heersche über Teilproblem 2

= merge([1 2 7 7 9],[2 4 7 8]) Kombiniere zur Gesamtlösung

  if p< r <b> then </b> <br>
q <- [(p +r)/2] <br>
Merge-Sort(A,p,q)<br>
Merge-Sort(A,q+1,r)<br>
Merge(A,p,q,r)<br>

O(n*log n) <br>

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.

Instanzen

Mergesort
Quicksort
Intervallhalbierung (Binärbäumen)

Eigenschaften

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

Beispiele

Sortierverfahren

Lebkuchenhaus

Übung 1 : Die Türme von Hanoi

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

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

Mergesort

ein schnelleres (und rekursives) Sortierverfahren.

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.

Ubung1

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/