Teile und Herrsche 1 WS13-14

Autoren:

• Daniel Richter
• 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:

\begin{align} \begin{array}{ccl} T_{B} \left( n \right) & = & 3 \cdot T_{A} \cdot\left(\lceil\frac{n}{2} \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} \end{align}

Man erkennt an den führenden Summanden, das es tatsächlich eine Effizienzsteigerung von ca. 25% ergibt. Aber es ergibt sich immer noch ein quadratischer Aufwand mit \mathcal{O}\left(n^{2}\right). Daher betrachten wir nun einen Algorithmus \mathcal{C}, welcher das Problem auf rekursive Art löst.

\begin{align} \mathit{T}_{\mathcal{C}}\left(n\right) = \begin{cases} \mathit{T}_{\mathcal{A}}\left(n\right), \mbox{wenn}\ n\leq n_{0} \\ \mathit{3\ T}_{\mathcal{C}}\left(\dfrac{n}{2}\right), \mbox{sonst}\end{cases} \end{align}

Nach dem Lösen dieser Formel kommen wir zu dem Ergebnis \mathit{T}_{\mathcal{C}}\left(n\right)=\mathcal{O}\left(n^{1.59}\right).

Quicksort

Der Quicksort Algorithmus wurde 1962 von C.A.O. Hoare angegeben. Der Grundgedanke ist eine Liste L = (e_{1}, e_{2},\dots, e_{n}) in zwei Teillisten zu zerlegen. Eine linke Teilliste TL und eine rechte Teilliste TR. Diese Listen werden durch einen Vergleich mit einem Pivotelment (Vergleichselement) v gebildet. dabei muss \mathit{v} \in G gelten. Es wird verabredet das alle Elemente von L paarweise verschieden sind, also m \neq n also gilt e_{m} \neq e_{n}. Dies ist zwar nicht erforderlich aber im Allgemeinen sinnvoll, da es normalerweise um Schlüssel zur Identifikation von Datenätzen handelt. Weiterhin wird verabredet das es sich um eine Liste mit natürlichen Zahlen handelt. Eine weitere Festlegung, das am weitesten links stehende Element aus L als v zu nehmen, das bedeutet \mathit{v} = e_{1}. Die sortierte Gesamtliste L_{sortiert} entsteht durch die Teilliste TL_{sortiert}, \mathit{v} und TR_{sortiert}. in dieser Reihenfolge. Die Abarbeitung der Teillisten findet dabei Rekursiv statt. Die zwei Elementarfälle: Ist L leer oder hat nur ein einzelnes Element, dann ist L = L_{sortiert}. Bei der Teilung der Liste L in TL und TR entstehen wieder Listen die mindestens L-1 Elemente enthalten, da v entfernt wurde. Es wird nah endlich vielen Zerlegungen einer der Elementarfälle erreicht.

Funktionaler Aufbau

Hierbei entstehen 2 Teillisten um eine sortierte Liste zu bekommen benötigen wir noch eine weitere Prozedur.

Effizienz von Quicksort

best case

Quicksort arbeitet am effektivsten wenn die zu sortierenden Teillisten etwa gleich lang sind.

\begin{align} \mathit{T}\left(0\right) &= 0\notag\\ \mathit{T}\left(n\right) &= 2 \cdot \mathit{T}\left(\frac{n}{2}\right) + c \cdot n\notag \end{align}

Dabei kommen wir auf einen Aufwand von \mathit{T}\left(n\right)= \mathcal{O}\left(n \log_{2} n\right).

worst case

Dieser Fall ist etwas sonderbar, da hier eine vollständig sortierte Liste schon vorliegt und das Ergebnis eigentlich schon entsprechend vorhanden ist. Hier ist die Rekursionsgleichung:

\begin{align} \mathit{T}\left(0\right) &= 0\notag\\ \mathit{T}\left(0\right) &= \underbrace{\mathit{T}\left(0\right)}_\text{= 0} + \mathit{T}\left(n - 1\right) + c \cdot n\notag \end{align}

Diese Gleichung kann iterativ gelöst werden.

\begin{align} \mathit{T}\left(n - 1\right) &= \mathit{T}\left(n - 2\right) + c \left(n - 1\right)\notag\\ \mathit{T}\left(n - 2\right) &= \mathit{T}\left(n - 3\right) + c \left(n - 2\right)\notag\\\\ \vdots \\\\ \mathit{T}\underbrace{\left(\quad n - k \quad\right)}_\text{ = 1 \curvearrowright k = n - 1} &= \mathit{T}\left(0\right) + c \left(n - k\right)\notag\\ \end{align}

Setzt man jeden Ausdruck in die Klammer ein, so kommt man auf

\begin{align} \begin{array}{ccl} T(n) &=& c \cdot \sum\limits_{k=0}^{n-1} \left(n-k\right)\\\\ &=& c\cdot\sum\limits_{k=0}^{n-1} n - \sum\limits_{k=0}^{n-1} k\\\\ &=& c\cdot\left(n^2 - \frac {n-1}{2}\left(\left(n-1\right)+1\right)\right)\\\\ &=& c\cdot\left(n^2 - \frac {n^2 -n}{2}\right)\\\\ &=& c\cdot\left(\frac {n^2} {2} + \frac {n} {2}\right) \\\\\\ T(n) &=& \mathcal{O}\left(n^2\right)\\\\ \end{array}\notag \end{align}

average case

Hier wird davon ausgegangen das jede der \mathit{n} Teillistenlängen mit der gleichen Wahrscheinlichkeit auftritt, nämlich \dfrac{1}{n}. Dann gilt:

\begin{align} \begin{array}{ccl} T(i) = T\left(n-i-1\right) = \frac {1}{n} \cdot \sum\limits_{j=0}^{n-1} T\left( j\right)\\\\ \underbrace{T\left(i\right)}_{linke\ Teilliste} + \underbrace{T\left(n-i-1\right)}_{rechte\ Teilliste} + \underbrace{c \cdot n}_{Teillistenbildung}\\\\ \end{array} \end{align}

Setzt man dies dann ein, so ergibt sich folgendes:

\begin{align} \begin{array}{ccl} T\left(n\right) &=& \frac {2}{n} \sum\limits_{j=0}^{n-1} T\left(j\right) + c \cdot n\\\\ \end{array} \end{align}

Nun wird die Summe beseitigt, dazu bilden wir Differenzen.

\begin{align} \begin{array}{ccl} nT\left(n\right) &=& 2 \sum\limits_{j=0}^{n-1} T\left(j\right) + c \cdot n \\\\ \left(n-1\right)T\left(n-1\right) &=& 2 \sum\limits_{j=0}^{n-2} T\left(j\right) + c \cdot \left(n-1\right)^2 \\\\ \\\\ nT\left(n\right) - \left(n-1\right)T\left(n-1\right) &=& 2T\left(n-1\right) + 2cn - c \mid -c\ \text{entfällt für}\ n \rightarrow \infty\\\\ \frac{T\left(n\right)}{n+1} &=& \frac{T\left(n-1\right)}{n} + \frac{2c}{n+1}\\\\ \frac {T\left(n-1\right)}{n} &=& \frac{T\left(n-2\right)}{n-1} + \frac{2c}{n}\\\\ \vdots & & \vdots\\\\ \frac{T\left(2\right)}{3} &=& \frac{T\left(1\right)}{2} + \frac{2c}{3}\\\\ \\\\ \frac{T\left(n\right)}{n+1} &=& \underbrace{\frac{T\left(1\right)}{2}}_{=0, da\ T\left(1\right) =0} + 2 \sum\limits_{i=3}^{n+1} \frac{1}{i}\\\\ \end{array} \end{align}

Bei der Benutzung der bekannten Schranken \frac {\lfloor log_{2} \ n \rfloor +1}{2} < \mathit{H}_{n} < \lfloor log_{2} \ n \rfloor +1 für die Harmonischen Zahlen \mathit{H}_{n} = \sum\limits_{k=1}^{n} \frac{1}{k}.

\begin{align} \frac {T\left(n\right)}{n+1} = \mathcal{O} \left(log_{2} \ n\right)\curvearrowright T\left(n\right)t = \mathcal {O} \left(n \cdot log_{2} \ n\right) \end{align}

Die Effizienz von Quicksort in allen drei Fällen:

\begin{align} \begin{array}{|c|c|} \hline best \ case & \mathcal{O}\left(n \ \log_{2} n\right) \\ \hline average \ case & \mathcal{O}\left(n \ \log_{2} n\right) \\ \hline worst \ case & \mathcal{O}\left(n^{2}\right) \\ \hline \end{array} \end{align}

Mergesort

Mergesort und Quicksort sind eng miteinander Verwandt, Merge kann mit Zusammenführen übersetzt werden. Eine zu sortierende Gesamtliste L= \left(Le_{1}, Le_{2}, Le_{3}, \cdots , Le_{n}, Re_{1}, Re_{2}, Re_{3}, \cdots , Re_{m}\right) wird in zwei etwa gleich große Teillisten, TL= \left(Le_{1}, Le_{2}, Le_{3}, \cdots , Le_{n}\right) und TR= \left(Re_{1}, Re_{2}, Re_{3}, \cdots , Re_{m}\right) geteilt. n = |L|\div 2 = m\div 2. Es wird kein Vergleich oder Vorsortierung vorgenommen.Das \div Zeichen steht für eine ganzzahlige Division. Es gilt entweder m = 2n oder m = 2n +1. Dann werden die beiden Teillisten rekursiv, das bedeutet mit Mergesort, sortiert. Die Elementarfälle sind die selben wie bei Quicksort.

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:

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:

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 n Elementen aus dem Zahlenbereich der ganzen Zahlen \mathcal{\mathbb{Z}}:

\mathcal{L=\{e_{1}, e_{2}, \dots ,e_{n}\}}

mit \mathcal{e\in\mathbb{Z}}

und \mathcal{n\in\mathbb{N}}

Zuerst muss die Liste in zwei Teillisten geteilt werden. Bei einer ungeraden Anzahl von Listenelementen wird abgerundet (floor).

\mathcal{k=\lfloor\frac{n}{2}\rfloor}

mit \mathcal{k} als mittlestem Listenelement der Liste \mathcal{L}

Anschließend gibt es eine linke und eine rechte Teilliste:

\mathcal{L_{l}=\{e_{1}, e_{2}, \dots , e_{k}\}}

\mathcal{L_{r}=\{e_{k+1}, e_{k+2}, \dots , e_{n}\}}

Ist \mathcal{x} das gesuchte Element, wird \mathcal{x} mit dem ersten Element der rechten Teilliste verglichen \mathcal{x < e_{k+1}}. Das Ergebnis entscheidet darüber, ob mit der rechten oder linken Teilliste fortgefahren wird. Die neue Teilliste wird so lange rekursiv verarbeitet, bis \mathcal{x} gefunden wurde oder alle Teillisten untersucht wurden. Bestenfalls ist das erste Element \mathcal{e_{k+1}} der Teilliste \mathcal{L_{r}} bereits das gesuchte Element \mathcal{x}.

Die rekursive Bildungsvorschrift zur binären Suche kann folgendermaßen angegeben werden:

Mit der binären Suche ist es möglich, in einem Duden mit 140.000 Stichwörtern und 1216 Seiten mit höchstens \mathcal{17} (\mathcal{\approx \log_2 140000}) Wortvergleichenvergleichen jedes Wort zu finden.

Das Verfahren

Nicht nur bei der Suche von Schrauben in einer Kiste, sondernauch für die Suche von Informationen (z.B. Duden, Telefonbuch, Bahnfahrplan) ist eine effiziente Suche sehr vorteilhaft, da durch ineffiziente Verfahren sehr viele Ressourcen unnötig gebunden werden können.

In einer aufsteigend sortierten Gesamtliste

\mathcal{G = \left( a_1,a_2,\dots, a_k, a_{k+1},\dots,a_n \right)}

erfolgt die Suche von \mathcal{x} durch die Suche in den beiden Teillisten \mathcal{L = \left( a_1,a_2,\dots, a_k \right)} und \mathcal{R = \left(a_{k+1}, a_{k+2},\dots, a_n \right)}. Ausgehend von \mathcal{n} als Zweierpotenz erfolgt die Zerlegung mit \mathcal{k = n\div2}. In der Implementierung wird \mathcal{k = \lfloor \frac{n}{2} \rfloor} verwendet.

Im Suchvorgang wird \mathcal{x} stets mit dem ersten Element \mathcal{a_{k+1}} aus der rechten Teilliste \mathcal{R} verglichen. Stimmt \mathcal{x} mit \mathcal{a_{k+1}} überein, ist das Ergebnis der Suche \mathcal{a_{k+1}}. Andernfalls wird bei \mathcal{x<a_{k+1}} die Suche in der linken Teilliste \mathcal{L }, bzw. bei \mathcal{x> a_{k+1} } in der rechten Teilliste \mathcal{R} unter der Voraussetzung, dass die zu durchsuchende Teilliste nicht leer ist, fortgesetzt.

Scheme-Implementierung

Um eine Implementierung in Scheme zu realisieren, benötigen wir die bereits im Kapitel über mergesort thematisierte Funktion "teillisten2".

Scheme-Implementierung der binären Suche:

Zur Demonstration der Korrekten Arbeitsweise des Algorithmus ist hier eine Liste explizit angegeben. Bei der späteren selbständigen Arbeit mit der binären Suchen können auch die Prozeduren zzls (Erstellt eine Liste mit Zufallszahlen) und mergesort (sortiert eine Liste) verwendet werden. Beide Prozeduren werden für die Übungen bekannt gegeben.

Um nicht nur zu erfahren, dass das gesuchte Element gefunden wurde, sondern zusätzlich dessen Position ausgegeben zu bekommen, muss der Algorithmus erneut angepasst werden. Auch die Anzahl der Rekursionsschritte ist für eine Aufwandsanalyse sehr aussagekräftig, weshalb auch diese berücksichtigt wird. Zuerst müssen daher Zähler für die Aufrufe und Rekursionsschritte definiert und in den vorhandenen Code integriert werden.

Eine weitere Prozedur wird zum Aufruf der binären Suche verwendet:

Ein Aufruf unserer neuen binären Suche ergibt dann das gewünschte Ergebnis.