- Teile und herrsche (Informatik)
-
Der Grundsatz teile und herrsche (englisch divide and conquer bzw. lateinisch divide et impera) findet in vielen Teilgebieten der Informatik Anwendung und beschreibt einen reduktionistischen Lösungsansatz.
Inhaltsverzeichnis
Grundprinzip
Bei einem „teile und herrsche“-Ansatz wird das eigentliche Problem so lange in kleinere und einfachere Teilprobleme zerlegt, bis man diese lösen („beherrschen“) kann. Anschließend wird aus diesen Teillösungen eine Lösung für das Gesamtproblem (re-)konstruiert.
Historische Vorläufer
Die Suche in sortierten Listen kann nach diesem Prinzip erfolgen. Hierzu wird das Element in der Mitte der Liste mit dem gesuchten Eintrag verglichen. Anschließend muss nur noch in dem vorhergehenden oder nachfolgenden Teil weiter gesucht werden. Dazu kann dieser erneut auf diese Art und Weise halbiert werden. Diese Suchmethode, heutzutage bekannt als Binäre Suche, geht bereits auf die Babylonier zurück.
Der Euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen kann als eine einfache Art des „teile und herrsche“ Prinzips betrachtet werden. Hierbei wird das Problem iterativ vereinfacht, indem man „gemeinsame“ Teile entfernt.
Anwendung in Algorithmen
„Teile und herrsche“ ist eines der wichtigsten Prinzipien für effiziente Algorithmen. Dabei wird ausgenutzt, dass bei vielen Problemen der Lösungsaufwand sinkt, wenn man das Problem in kleinere Teilprobleme zerlegt. Dies lässt sich meist durch Rekursive Programmierung umsetzen, bei der die Teilprobleme wie eigenständige Probleme gleichzeitig parallel oder sequenziell (einzeln nacheinander) behandelt werden, bis sie auf triviale Lösungen zurückgeführt sind oder der Restfehler hinreichend klein ist. Bei manchen Algorithmen steckt dabei die Kernidee im Schritt des „Teilens“, während die „Rekombination“ einfach ist (beispielsweise Quicksort). In anderen Verfahren (beispielsweise Mergesort) ist das Teilen einfach, während die Rekombination die Kernidee des Algorithmus enthält. In manchen Algorithmen sind beide Schritte komplex.
Die Lösung für das Gesamtproblem ergibt sich je nach Algorithmus auf verschiedene Weise. Möglichkeiten sind unter Anderem:
- Die Teillösungen werden zu einer Gesamtlösung zusammengefügt. Beispielsweise wird beim Sortieren mit dem Quicksort-Algorithmus die sortierte Ergebnisliste aus kleinen, jeweils für sich sortierten Teillisten durch Aneinanderreihen zusammengesetzt.
- Die Teillösungen werden zu einer Gesamtlösung kombiniert. Beispielsweise wird beim Sortieren mit dem Mergesort-Algorithmus das Ergebnis aus je zwei sortierten Teilen durch den „Merge“-Schritt konstruiert.
- Aus den Teillösungen wird nach bestimmten Kriterien die beste Lösung als Lösung für das Gesamtproblem ausgewählt. Beispielsweise wird bei manchen Optimierungsproblemen der Lösungsraum aufgeteilt und aus den Unterräumen die optimale Lösung gesucht. Aus den „Unterraumoptima“ wird dann die beste Lösung als Gesamtlösung gewählt. Konkret etwa Krylow-Unterraum-Verfahren.
- Die Lösung für das letzte Teilproblem ist gleichzeitig Lösung des gesamten Problems. Beispielsweise ist beim Suchen im Binärbaum nach dem letzten Suchschritt die passende Stelle im Baum bestimmt.
- Ein weiterer wichtiger Anwendungsbereich ist die Schnelle Fourier-Transformation (FFT).
Anwendung in Programmiersprachen
In vielen Programmiersprachen wird die Gliederung von Computerprogrammen in Prozeduren, Funktionen, Module, Objekte, Komponenten, Prozesse und Threads nach dem Prinzip teile und herrsche umgesetzt.
Siehe auch
Wikimedia Foundation.
