Teile und Herrsche

Wiki-Quelltext dieser Seite.

==Teile und herrsche == 
=== Definition ===

<div style= "background-color:#D6D6C2; padding:10px">
<b> Teile und herrsche </b> 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.
</div>

=== Entwurfsmethode für Algorithmen ===
1. Teile das Problem in kleinere Unterprobleme (Divide) <br>
2. Löse rekursiv die entstehenden Unterprobleme (Conquer) <br>
3. Setze die Lösungen zusammen.<br>

=== Instanzen ===
• Mergesort <br>
• Quicksort <br>
• Intervallhalbierung (Binärbäumen) <br>
 
=== Beispiel ===


==== Sortieren ====
[[Bild:S3anbrem_B1a1.PNG]]
<popup name="Aufteilen der Eingabe">
[[Bild:S3anbrem_B1a.png]]
</popup>
<popup name="Rekursiv Sortieren">
[[Bild:S3anbrem_B1b.png]]
</popup>
<popup name="Zusammenfügen">
[[Bild:S3anbrem_B1c.png]]
</popup>

==== Lebkuchenhaus ====
[[Bild:S3anbrem_B1.PNG]]

=== U1 ===

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

[[Bild:S3anbrem_U1.png]]

<popup name="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. 
</popup>

<popup name="Lösung">
[[Bild:S3anbrem_B4.PNG]]
</popup>

<popup>

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.
<br>
Bei näherer Betrachtung der Teilprobleme fällt folgendes auf:  
a) Der 2. Schritt ist trivial und sofort ausführbar.  <br>
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. <br>
Damit hat man für das Gesamtproblem eine rekursive Lösungsvorschrift formuliert.  

</popup>


<popup>
<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;</code>
</popup>

<popup>
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.
</popup>
Spiele:
http://www.gf-webdesign.de/tuerme-von-hanoi/tuerme-von-hanoi.htm

== Die Idee ==

== Quicksort ==

== Mergesort ==

== Binäres Suchen == 

== Zusammenfassung ==
<ul>
<li>'''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. 
</ul>

== Quellen ==
Wagenknecht, 2003, Algorithmen und Komplexität <br>
http://www.inf-schule.de/ <br>
http://www.awb1.ch/ <br>
http://www.ki.informatik.uni-frankfurt.de/ <br>