tutego

Eine effektive Problemlösungsstrategie ist es, zunächst das Problem in Teilprobleme zu legen, dann die Teilprobleme zu lösen und anschließend zur Gesamtlösung zu kommen. Wer morgens im Bett liegt und Hunger verspürt, wird erst dann satt sein, wenn gewisse Teilprobleme gelöst sind. Diese Problemlösungsstrategie wird teile und herrsche (engl. divide and conquer, D&C[1]) genannt. Zunächst wird die Aufgabe ist kleine Häppchen zerlegt und anschließend abgearbeitet.

Teile und herrsche ist nicht nur eine Lösung, wie wir eine große Pizza „verarbeiten“, sondern auch in der Informatik eine beliebte algorithmische Methode: Das Hauptproblem wird in Teilprobleme zerlegt, die Teilprobleme dann gelöst und zur großen Lösung zusammengefügt. Zwei populäre Beispiele sind Sortierungen und die Multiplikation von großen Zahlen.

Sortieren über das Merge-Sort Verfahren

Der von John von Neumann vorgestellte Algorithmus basiert auf der Idee, die zu sortierende Liste ein zwei Teillisten zu zerlegen, diese dann wiederum in zwei Teile zu zerlegen, diese wiederum, usw., bis die Listen so klein sind, dass sie vielleicht nur noch aus zwei Zahlen bestehen, die trivial in eine Reihenfolge zu bringen sind. Ist eine Teilfolge dann sortiert, muss sie mit sortieren Nachbarfolge zusammenfügt (engl. merge) werden. Während also das Zerlegen und Sortieren von oben nach unten erfolgt, läuft das Zusammenlegen der sortierten Teillisten zur neuen größeren sortieren Teillisten von unten nach oben, bis schließlich die Gesamtliste sortierten ist. Der Algorithmus lässt sich sehr gut rekursiv implementieren. Auch das bekannte Quicksort arbeitet ähnlich. (Hier geht es allerdings darum, ein sogenanntes Pivot-Element zu wählen, dann die Liste in zwei Teillisten aufzuspalten, wobei in die erste Liste (erst einmal unsortiert) die Elemente kleiner dem Pivot-Element verschoben werden und in die andere Liste die Elemente größer dem Pivot-Element. Die Auswahl eines neuen Pivot-Elemens und das Kopieren in den richtigen Bereich wird rekursiv für die Unterbereiche wiederholt, was natürlich zu einer Sortierung führt. In der Regel kommt Quicksort mit weniger Speicher aus und ist in der Praxis schneller, da Merge-Sort in der einfachen Implementierung immer neue Teillisten aufbauen muss und Quicksort die Vertauschoperationen auf der originalen Datenstruktur (in-place genannt) ausführen kann.

Multiplikation von großen Ganzzahlen

In Java ist das Multiplizieren von Ganzahlen einfach. Sind die Zahlen klein genug, erledigt der *-Operator die Aufgabe, sind sie größer hilft die Klasse BigInteger und die Methode multiply(). Das sind natürlich hübsche Abstraktionen, aber im Java Bytecode gibt für die Multiplikation von int und long lediglich imul und lmul[2], und alles andere, etwa die Multiplikation von großen Zahlen für RSA-Schlüssel.

Das Produkt von großen Zahlen lässt sich einfach auf das Produkt von kleinern Zahlen mit ein paar Additionen abbilden. Statt Zahlen mit hunderten von Stellen zu nehmen, ein einfacheres Beispiel, was das Prinzip zeigt. Nehmen wir dazu die Zahl A = 1234, die mit B = 5678 multipliziert werden soll. Dann ist AB = (12 · 10^2 + 34) · (56 · 10^2 + 78) = 12 · 56 · 10^4 + (12 · 78 + 34 · 56) · 10^2 + 34 · 78. Waren bei 1234 und 5678 die Zahlen noch vierstellig, sind sie bei der Umschreibung nur noch zweistellig. Zählen wir die Anzahl Multiplikationen – und lassen wir die einfachen Multiplikation mit 10^4 bzw. 10^2 beiseite – so kommen wir auf vier, denn wir müssen 12 · 56, 12 · 78, 34 · 56 und 34 · 78 ausführen. Bei einem rekursiven D&C-Algorithmus ist also das Problem zur Multiplikation von 1234 · 5678 auf die vier Multiplikationen und Additionen abgeschwächt worden. Das können wir dann auch weiter aufspalten bis wir bei einstelligen Zahlen sind. Stehen wir also vor der Aufgabe beliebig große Zahlen mit n Stellen zur multiplizieren, können wir das Abbilden auf eine Multiplikation von Zahlen der Größe n/2 und ein paar Additionen. Kommen wir noch zu einer kleinen Optimierung. Wenn Zahlen sehr groß werden und dann multipliziert werden müssen (etwa zu Schlüsselgenerierung) ist es wichtig, jede überflüssige Operation wegzulassen, da arithmetische Operationen dann bei großen Zahlen und dem häufiger Durchführung doch ihre Zeit kosten. Interessanterweise kann durch geschickte Umstellung kann die Anzahl Multiplikationen von 4 auf 3 gesenkt werden. Zwei der Multiplikationen stammen aus 12 · 56 · 10^4 + (12 · 78 + 34 · 56) · 10^2 + 34 · 78 stammen aus dem Teil 12 · 78 + 34 · 56. Hier können wir etwas umschreiben, denn 12 · 78 + 34 · 56 = (12 + 34) · (56 + 78) – 12 · 56 – 34 · 78. Obwohl das auf den ersten Blick schlimmer aussieht (drei Multiplikationen statt zwei), fällt bei zweiten Blick auf, dass wie die beiden Produkte 12 · 56 und 34 · 78 schon im ersten Schritt berechnet haben. Also ergibt sich letztendlich 12 · 56 · 10^4 + ((12 + 34) · (56 + 78) – 12 · 56 – 34 · 78) · 10^2 + 34 · 78 und das macht insgesamt drei Multiplikationen für den Preis von ein paar zusätzlichen Subtraktionen, die im allgemeinen billiger ist als die Multiplikation, die bei dem D&C-Ansatz ja recht aufwändig ist.

Die Arbeitsweise von D&C-Algorithmen im Pseudocode sieht wie folgt aus:

löse Problem:

ist Problem klein:

löse Problem direkt

andernfalls:

zerlege das Problem in Teilprobleme

löse die Teilprobleme

setzte Problemlösung aus den Teillösungen zusammen

Attraktiv sind D&C-Algorithmen dann, wenn die Teilprobleme unabhängig voneinander und parallel gelöst werden können.

Bei unserem Eingangsbeispiel mit dem Aufstehen und Essen gibt es eine Abhängigkeit, so dass zwei beide Teilprozesse zwar eine Teilaufgabe des Gesamtproblems lösen, aber ohne Aufstehen man nicht zum Kühlschrank kommt. Das Sortieren über Merge-Sort ist erfüllt dabei das Kriterium, dass wenn die Liste in zwei Unterlisten zerlegt wird, die beiden Unterlisten problemlos parallel sortiert werden können.

[1] Nicht D&G, „ein anspruchsvolles und zeitgemäßes Markenzeichen und Ausdruck einer sich wandelnden Welt“ …

[2] http://java.sun.com/docs/books/jvms/second_edition/html/Mnemonics.doc.html

Labels: Insel