AuK/Teile und Herrsche 1 SS11

Wiki-Quelltext dieser Seite.

Autoren:
* Maik Linke ([mailto:s3malink@stud.hs-zigr.de s3malink@stud.hs-zigr.de])
* Romy Müller ([mailto:s3romuel@stud.hs-zigr.de s3romuel@stud.hs-zigr.de])



== Die Idee ==
=== Teile und Herrsche ===
Bei der systematischen Programmentwicklung und für die unmittelbare Ableitung von Aufwandsaussagen sind verschiedene Entwurfsmethoden für Algorithmen hilfreich. 
Zu den Entwurfsmethoden gehören zum Beispiel:
# Teile und Herrsche
# [[Greedy-Algorithmen]]
# [[dynamisches Programmieren]]

Teile und Herrsche (engl. "divide and conquer", lat. "divide et impera") ist die Entwurfsmethode für Algorithmen die wir nachfolgend genauer betrachten wollen.

Diese Methode hat seinen Ursprung als Redewendung und Strategie in der Kriegsführung. Bereits um 500 v. Chr. erwähnte  [http://de.wikipedia.org/wiki/Sunzi Sunzi], ein chinesischer General sinngemäß "Teile und Herrsche" als Stratgie der chinesischen Kriegskunst. Mit ''divise pour régner'' (frz. für "teilen, um zu herrschen") wurde sie als Ausspruch des frz. Königs [http://de.wikipedia.org/wiki/Ludwig_XI. Ludwig XI.] (*1423 †1483) bekannt. Des Weiteren ist die Strategie in der römischen Außenpolitik zu Zeiten [http://de.wikipedia.org/wiki/Gaius_Iulius_Caesar Julius Caesars] wieder zu erkennen. In Bezug auf Kriegsführung besteht die Taktik darin, die Gegner durch gezieltes gegeneinander Ausspielen in kleine Gruppen zu spalten und somit leichter besiegen zu können.

Das Prinzip ist in der Informatik das Gleiche/ Selbe (!?), wenn auch weniger grausam. Die Methode löst Probleme, indem es
# in Teilprobleme zerlegt wird ("divide")
# die Teilprobleme gelöst und 
# die Lösungen der Teilprobleme wieder zusammengesetzt werden ("conquer").

=== Effizienzbetrachtung von Teile und Herrsche ===
Wir wollen feststellen ob mit Algorithmen, die nach der Methode "divide and conquer" entworfen wurden, eine Effizienzverbesserung erzielt werden kann. Wir betrachten einen Algorithmus <math> A </math> der unser Problem in <math> \mathcal{O} \left( n \right) </math>, d.h mit <math> T_A \left(n\right) \leq c \cdot n^2 </math> löst.


<center><math>
\begin{array}{ccl}
T_B \left( n \right) & = & 3 \cdot T_A \cdot\left(\left\ \lceil\frac{n}{2}\right\ \rceil \right) + d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n+1}{2}\right) ^2 + d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n+1}{2}\right) \left( \frac{n+1}{2}\right) +d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n^2 + 2n + 1}{4}\right) + d \cdot n\\\\
                 & \leq     & 3 \cdot c \cdot \left( \frac{n^2}{4} + \frac{2n}{4} + \frac{1}{4}\right) + d \cdot n\\\\
                 & \leq     & \frac{3cn^2}{4} + \frac{6cn}{4} + \frac{3c}{4} + d \cdot n\\\\
                 & \leq     & \frac{3}{4}cn^2 + \frac{3}{2}cn + \frac{3}{4}c + d \cdot n\\\\
                 & \leq     & \frac{3}{4}cn^2 + \left(\frac{3}{2}c + d\right) \cdot n + \frac{3}{4} c\\\\
\end{array}
</math>
</center>


Das Ergebnis zeigt, dass eine Effizienzverbesserung von 25 % festgestellt werden kann. Der Aufwand ist jedoch nach wie vor quadratisch, wie der Exponent der Funktion zeigt. Das bedeutet, dass für größere <math> n </math> keine große Verbesserung in der Effizienz erzielt werden kann.  
Die Betrachtung eines Algorithmus <math> C </math> , der die drei Teilprobleme mit Rekursion löst, verdeutlicht, dass wir uns mit diesem Ergebnis nicht zufrieden geben müssen. Der Basisfall <math> n \leq n_0 </math> wird weiterhin vom Algorithmus <math> A </math> übernommen. Es entstehen folgende Aufwandsziehungen:

== Quicksort ==
=== Verfahren ===

=== Funktionsorientierte Beschreibung ===

=== Effizienzbetrachtung von Quicksort ===



== Mergesort ==
=== Verfahren ===

=== Funktionsorientierte Beschreibung ===

=== Effizienzbetrachtung von Mergesort ===

== Quellenverzeichnis ==
[http://de.wikipedia.org/wiki/Divide_et_impera Divide et Impera]