AuK/Teile und Herrsche 1 WS13-14

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Autoren:
* [mailto:s3darich@stud.hs-zigr.de Daniel Richter]
* [mailto:s3addank@stud.hs-zigr.de Adrian Danker]

== Vorbetrachtungen ==
=== Grundsätzliches ===

* Ein großes Problem wird in in kleinere Teilprobleme zerlegt (teile - divide).
* Teilprobleme werden einzeln gelöst (herrsche - conquer).
* Zusammensetzen der einzelnen Lösungen zu einer Gesamtlösung.

=== Beispiele allgemein und aus der Informatik ===

* Das Programmingwiki: Das große Problem der Veranstaltung Algorithmen wird aufgeteilt (Themen) und diese zerlegten Teilprobleme von einzelnen (Studenten) bearbeitet und gelöst(Referat). Am Ende werden die einzelnen Lösungen zusammengefügt und bilden die Lehrveranstaltung Algorithmen und Komplexität.
* Beim Sortieren: Es ist eine Gesamtliste L gegeben mit n Elementen, also $L = (e_{1}, e_{2},..., e_{n})$, welche nach der göße der Elemente Sortiert werden soll. Man teilt die Liste auf und sortiert die Teillisten nach der Größe  und fügt die geortneten Listen in der richtigen Reihenfolge wieder zusammen.

=== Effizienzbetrachtung von Teile und Herrsche ===

Es wird erhofft das diese Technik effizienter ist als das Lösen des Gesamtproblems ohne es zu zerlegen.

Angenommen, ein Algorithmus $\mathcal{A}$ löst das Problem in $\mathcal{O}\left(n^{2}\right)$,d.h. mit $\mathit{T}_{\mathcal{A}}\left(n\right)\leq c\cdot n$. Für den Gesamtaufwand $\mathit{T}_{\mathcal{B}}$ eines Algorithmus $\mathcal{B}$, der beispielsweise drei dieser Probleme der Größe $\frac{n}{2}$ mittels Prozedur $\mathcal{A}$  bearbeitet, um die Teillösungen anschließend mit dem Aufwand in $\mathcal{O}\left(n\right)$ zusammenzufügen, gilt damit: <br /> <br />

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

== Binäres Suchen ==

Wann immer ein Gegenstand oder eine Information gesucht werden muss, gibt es verschiedene Herangehensweisen. Um einen Eintrag im Duden oder eine Abfahrtszeit im Bahnfahrplan zu finden, kann durch einen Vergleich der vorangehenden oder nachfolgenden Einträge bereits nach einem Ausschlussverfahren vorgegangen werden. Hierbei handelt es sich allerdings schon um "sortierte Listen".
Sucht man dagegen etwas in einer "unsortierten Liste", wie etwa eine Schraube in einer "Restekiste" mit diversen Schrauben, prüft man elementeweise, ob das gesuchte Element (die Schraube) in der Liste (die Schraubenrestekiste) vorhanden ist. Ist im ungünstigsten Fall die gesuchte Schraube das letzte Element, ist der Aufwand $\mathcal{O}(n)$. Entsprechend hat die Suche einen linearen Aufwand und ist für besonders große Listen (Nadel im Heuhaufen) nicht zu empfehlen. Implementiert in Scheme würde eine solche Suche folgendermaßen aussehen:

<code id="526257538a59f">(define lineareUnsortierteSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Element ist nicht in der Liste enthalten")
      ((= element (car liste)) "Das Element ist in der Liste enthalten")
      (else
       (lineareUnsortierteSuche element (cdr liste))))))</code>
<run id="526257538a6ef">(lineareUnsortierteSuche 21 '(89 5 2 55 13 1 144 3 21 34 8 233))</run>

Die Nachteile dieses Suchalgorithmus liegen auf der Hand:
* Mit wachsender zahl der Elemente steigt der Aufwand linear
* Ist das Element nicht enthalten, wird in jedem Fall die Liste komplett durchsucht

In einer aufsteigend sortierten Liste erlaubt eine kleine Modifikation des Algorithmus den Abbruch der Suche, falls das Element nicht in der Liste vorhanden ist:

<code id="526257538a630">(define lineareSortierteSuche
  (lambda (element liste)
    (cond
      ((null? liste) "Element ist nicht in der Liste enthalten")
      ((< element (car liste)) "Element ist nicht in der Liste enthalten")
      ((= element (car liste)) "Das Element ist in der Liste enthalten")
      (else
       (lineareSortierteSuche element (cdr liste))))))</code>
<run id="526257538a784">(lineareSortierteSuche 13 '(1 2 3 5 8 13 21 34 55 89 144 233))</run>

Nach wie vor zeigt der Worst case (Das gesuchte Element ist immer das Letzte oder nicht vorhanden), dass hier ein linearer Aufwand vorliegt.

Um also einen geringeren Aufwand zu erreichen, soll bei der Suche nun systematisch vorgegangen werden. In dem Beispiel mit der Suche eines Wortes im Duden wird der Duden mittig aufgeschlagen und anschließend je nach Anfangsbuchstaben des gesuchten Wortes der Vordere oder hintere Teil des Dudens erneut halbiert bis die Zielseite gefunden ist. Der Suchraum wird auf diese Weise immer halbiert und die Zielseite wird deutlich schneller gefunden.

Für die binäre Suche reduzieren wir das Suchproblem auf eine Liste mit <math>n</math> Elementen aus dem Zahlenbereich der ganzen Zahlen $\mathcal{\mathbb{Z}}$:

$\mathcal{L=\{e_{1}, e_{2}, \dots ,e_{n}\}}$ <br />mit $\mathcal{e\in\mathbb{Z}}$ <br />und $\mathcal{n\in\mathbb{N}}$