Teile und Herrsche 1 SS11
Inhaltsverzeichnis |
Autoren:
- Maik Linke (s3malink@stud.hs-zigr.de)
- Romy Müller (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 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 Ludwig XI. (*1423 †1483) bekannt. Des Weiteren ist die Strategie in der römischen Außenpolitik zu Zeiten 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 A der unser Problem in \mathcal{O} \left( n \right) , d.h mit T_A \left(n\right) \leq c \cdot n^2 löst. Der Algorithmus T_B bearbeitet drei Probleme der Größe \frac{n}{2} mittels der Prozedur A . Der Gesamtaufwand von unserem Algorithmus T_B fasst die Teillösungen mit einem Aufwand \mathcal{O} \left( n \right) zusammen.
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 n keine große Verbesserung in der Effizienz erzielt werden kann. Die Betrachtung eines Algorithmus C , der die drei Teilprobleme mit Rekursion löst, verdeutlicht, dass wir uns mit diesem Ergebnis nicht zufrieden geben müssen. Der Basisfall n \leq n_0 wird weiterhin vom Algorithmus A übernommen. Es entstehen folgende Aufwandsziehungen:
Diese Rekursionsgleichung lösen wir mit dem 1. Fall der Meistermethode.
Die Lösung zeigt, dass durch eine rekursive Lösung die Effizienz dem quadratischen Aufwand gegenüber deutlich verbessert werden kann. Dies veranschaulicht, dass Teile-und-Herrsche-Verfahren immer rekursive Lösung der gebildeten Teilprobleme enthalten müssen. Die Teilprobleme haben eine geringere Problemgröße bei gleicher Problematik, als das zu lösende Ausgangsproblem. Zur rekursiven Lösung gehört ein allgemeiner Fall, wie auch ein Basisfall. Je nach Problem kann aber auch mehrere Basisfälle geben.
Quicksort
Verfahren
Quicksort (schnelles Sortieren) wurde 1962 von dem britischen Informatiker Charles Anthony Richard Hoare (* 11. Januar 1934) entwickelt. Die Idee des Algorithmus besteht darin, die Gesamtliste G = (a_1, a_2, ...,a_n) in eine linke und eine rechte Teilliste zu zerlegen, so dass alle Elemente von L kleiner und von R größer sind als das Vergleichsobjekt v \in G .
Wir vereinbaren, dass die Elemente von G paarweise verschieden sind, also für alle i \not = j gilt a_i \not = a_j. Diese Einschränkung ist nicht notwendig, aber sinnvoll, da es sich um Schlüssel zur Identifikation von Datensätzen handelt. Wir verabreden des Weiteren, dass es sich um natürliche Zahlen handelt. Zusätzlich legen wir fest, dass wir das am weitesten links stehende Element aus G als Vergleichselement v verwenden, also v = a_1 . Die Listen L_{sortiert} , v und R_{sortiert} bilden die sortierte Gesamtliste G_{sortiert} genau in dieser genannten Reihenfolge. Aus Effizienzgründen werden die Teillisten mit Quicksort sortiert.
Es gibt zwei Basisfälle: G ist leer oder besteht aus nur einem Element, dann ist G = G_{sortiert} . Wenn man G in die Teillisten L und R zerlegt, entstehen durch die Entnahme von v Listen, die mindestens ein Element weniger enthalten als G . Somit wird nach endlich vielen Zerlegungen einer der Elementarfälle erreicht.
Funktionsorientierte Beschreibung
traditionelles Quicksort
Multiple-Value-Quicksort
Effizienzbetrachtung von Quicksort
Best Case
Am Besten arbeitet Quicksort wenn die Teillisten ungefähr gleich groß sind. Es ergibt sich die Lösung von
einen Aufwand T\left( n\right) = \mathcal{O} \left( n \log_2 n \right) . Zur Lösung der Rekursionsgleichung haben wir die Meistermethode verwendet. Die in der allgemeinen Form
vorkommenden Variablen enthalten für Teile- und Herrsche-Verfahren besondere Bedeutung. Die Variable a steht für die Anzahl der Teilprobleme und \frac{n}{c} für die Größe eines Teilproblems, wobei die Zerlegung immer aufgehen sollte.
Worst Case
Den Worst Case Fall des Verfahrens kennzeichnet eine vollständig sortierte Liste.
Eigentlich wäre der Sortieraufwand somit gleich null da das Ergebnis bereits vorliegt. Die Rekursionsgleichung für T(n)
Mit der Iterationsmethode kann die Gleichung leicht gelöst werden.
Das in die Summenschreibweise übertragen
Average Case
Gehen wir davon aus das jede der n Teillistenlängen mit der gleichen Wahrscheinlichkeit von \frac {1} {n} auftritt, dann sprechen wir von dem Average Case.
Dann gilt
Setzt man dies ein, so ergibt das
Jetzt wollen wir das Summenzeichen beseitigen indem wir die Differenz bilden
Mit den Harmonischen Zahlen H(n) = \sum\limit_{k=1}^{n} \frac{1}{k} und deren bekannten Schranken \frac {\lfloor log_{2} n \rfloor +1}{2} < H_{n} < \lfloor log_{2} n \rfloor +1 ergibt sich dann
Interne Suchverfahren
darauf wird an dieser Stelle nicht eingegangen.
Mergesort
Verfahren
Quicksort und Mergesort sind eng verwandt. Merge bedeutet soviel wie "zusammenführen" oder "einfädeln", ähnlich wie es im Straßenverkehr geschieht wenn zwei Fahrspuren zusammengeführt werden. Die Übersetzung "Sortieren durch Mischen" trifft nicht zu. Die zu sortierende Gesamtliste
wird zunächst mit n = \left| G \right | \div 2 = m\div2 in zwei etwa gleich große Teillisten geteilt.
Es erfolgen im Gegensatz zu Quicksort also keine Vorsortierungen oder Vergleiche. \div steht für die ganzzahlige Division, sodass entweder m = 2n oder m = 2n + 1 gilt. Im Conquer-Schritt sollen L und R rekursiv durch Mergesort sortiert werden. Es gelten die gleichen Elementarfälle wie bei Quicksort. Die dadurch entstandenen sortierten Teillisten werden nach dem Reißverschlussprinzip zusammengeführt. Die jeweils ersten Elemente der Teillisten werden miteinander verglichen. Ist l_i < r_j so wird l_i an die nächste Stelle der neuen Gesamtliste gestellt. Ansonsten rutscht r_j nacht, während l_i noch einmal mit dem nächsten Element von r also r_{j+1} verglichen wird. Das jeweils kleinere Element wird an das vorhergehende "aussortierte" hinten angestellt.
Funktionsorientierte Beschreibung
Effizienzbetrachtung von Mergesort
Da Mergesort jede Liste, ob sortiert oder unsortiert halbiert und abarbeitet, ist die Effizienz von Mergesort im best, worst und average case immer gleich. Es ergeben sich folgende Aufwandsbeziehungen
Wir nehmen vereinfachend an, dass die Anzahl der Elemente n eine Zweipotenz ist. Durch Anwendung des zweiten Falles der Meistermethode ergibt sich folgende Lösung.
Binäres Suchen
Das Verfahren
Neben dem Sortieren von Schlüsseln ist das effiziente Suchen von großer Bedeutung, insbesondere für das Gebiet infomation retrieval ("Wiederauffinden/ Wiedergewinnung von Informationen"). Praktische Anwendungsgebiete für die binäre Suche sind Auskunftssysteme aller Art, wie zum Beispiel das Telefonbuch. Eine ineffiziente Suche kann viel Ressourcen in Anspruch nehmen. Um das aufwändige Umspeichern von Daten zu vermeiden verwendet man eine Indexliste und Schlüssel, zur Identifizierung von Datensätzen. Die Suche von x in einer aufsteigend sortierten Gesamtliste
erfolgt durch die Suche in den beiden Teillisten L = \left( a_1,a_2,..., a_k \right) und R = (a_{k+1}, a_{k+2},..., a_n \right). Der Divide-Prozess der Zerlegung erfolgt mit k = n\div2 . Wir gehen vereinfachend davon aus, dass n eine Zweierpotenz ist. In der Implementation wird k = \lfloor \frac{n}{2} \rfloor verwendet.
Bei der Suche wird x immer mit dem ersten Element a_{k+1 aus der rechten Teilliste R verglichen. Ist x = a_{k+1} ist die Suche bereits beendet. Ist x<a_{k+1} wird die Suche in der linken Teilliste L , ist x> a_{k+1} in der rechten Teilliste R fortgesetzt. Die Fortsetzung der Suche erfolgt jedoch nur, wenn die zu durchsuchende Liste nicht leer ist.
Funktionsorientierte Beschreibung mit Multiple-value-context
Effizienzanalyse
Die Länge der Teillisten wird in jedem Schritt halbiert, insbesondere wenn die Anzahl n der Elemente von G eine Zweierpotenz ist. Die Anzahl der rekursiven Aufrufe entspricht der Anzahl der Halbierungsschritte, also log_2 n Stück. Setzt man für den in jedem Schritt stattfindenden Vergleich einen konstanten Aufwand \mathcal{O}\left( c \right) ein, erhält man den Gesamtaufwand
Die trifft für alle drei Fälle zu. Der best case benötigt nur einen einzigen Vergleich und arbeitet mit konstantem Aufwand T\left(n\right) = \mathcal{O}\left(c\right) , unabhängig von der Anzahl n.
Hier gehört noch der Vergleich von sequentieller und binärer Suche rein