Wikipedia · einfach zusammengefasst · Stand
Teile-und-herrsche-Verfahren
Die binäre Suche nach einem Schlüssel ist eine der ersten algorithmischen Anwendungen des Prinzips von „teile und herrsche“. Sie lässt sich zu den …
Inhalt6 Abschnitte
Kernidee
Das Teile-und-herrsche-Verfahren ist in der Informatik ein Paradigma, also ein grundlegendes Entwurfsprinzip, für effiziente Algorithmen. Es wird besonders bei Such- und Sortierverfahren eingesetzt. Die zentrale Idee lautet: Ein Problem, das als Ganzes zu schwierig erscheint, wird rekursiv in kleinere und einfachere Teilprobleme zerlegt. Rekursiv bedeutet, dass dieselbe Vorgehensweise auf die kleineren Teilprobleme erneut angewendet wird.
Die Zerlegung wird so lange fortgesetzt, bis die Teilprobleme einfach genug sind, um direkt gelöst zu werden. Danach werden die Teillösungen wieder zu einer Lösung für das Gesamtproblem rekonstruiert. Das Verfahren besteht also aus drei gedanklichen Schritten: Teilen des Problems, Lösen der Teilprobleme und Zusammenführen oder Auswählen der passenden Teillösungen.
Algorithmische Bedeutung
„Teile und herrsche“ gehört zu den wichtigsten Prinzipien für effiziente Algorithmen. Es nutzt aus, dass bei vielen Aufgaben der Lösungsaufwand sinkt, wenn man sie in kleinere Teilprobleme aufspaltet. Diese Teilprobleme können parallel oder sequenziell bearbeitet werden. Parallel bedeutet gleichzeitig, sequenziell bedeutet nacheinander.
Oft wird das Prinzip durch rekursive Programmierung umgesetzt. Dabei werden Teilprobleme wie eigenständige Probleme behandelt, bis sie auf triviale Lösungen zurückgeführt sind oder ein Restfehler hinreichend klein ist. Triviale Lösungen sind so einfache Fälle, dass sie ohne weitere Zerlegung gelöst werden können.
Je nach Algorithmus liegt die eigentliche Schwierigkeit an unterschiedlicher Stelle. Bei Quicksort steckt die Kernidee vor allem im Teilen; die Rekombination ist einfach. Bei Mergesort ist das Teilen einfach, während der „Merge“-Schritt, also das Zusammenführen zweier sortierter Teile, die wichtige Arbeit leistet. Bei manchen Algorithmen sind sowohl das Teilen als auch das Wiederzusammensetzen komplex.
Arten der Gesamtlösung
Die Lösung des Gesamtproblems entsteht je nach Verfahren auf verschiedene Weise.
Eine Möglichkeit ist das Zusammenfügen von Teillösungen. Beim Quicksort-Algorithmus wird eine sortierte Ergebnisliste aus kleineren, jeweils für sich sortierten Teillisten durch Aneinanderreihen zusammengesetzt.
Eine zweite Möglichkeit ist das Kombinieren von Teillösungen. Beim Mergesort-Algorithmus wird das Ergebnis aus je zwei sortierten Teilen durch den „Merge“-Schritt konstruiert.
Eine dritte Möglichkeit ist die Auswahl der besten Teillösung nach bestimmten Kriterien. Bei manchen Optimierungsproblemen wird der Lösungsraum in Unterräume aufgeteilt. In diesen Unterräumen sucht man jeweils nach optimalen Lösungen; aus diesen „Unterraumoptima“ wird dann die beste Lösung als Gesamtlösung gewählt. Als konkretes Beispiel nennt der Artikel Krylow-Unterraum-Verfahren.
Eine vierte Möglichkeit besteht darin, dass die Lösung des letzten Teilproblems bereits die Lösung des Gesamtproblems ist. Beim Suchen in einem Binärbaum ist nach dem letzten Suchschritt die passende Stelle im Baum bestimmt.
Ein weiterer wichtiger Anwendungsbereich des Teile-und-herrsche-Prinzips ist die schnelle Fourier-Transformation, abgekürzt FFT.
Frühe Beispiele
Ein frühes Beispiel für das Prinzip ist die binäre Suche nach einem Schlüssel. Sie lässt sich bis zu den Babyloniern zurückverfolgen. Bei der binären Suche sucht man einen Schlüssel in einer sortierten Schlüsselmenge. Dazu vergleicht man den gesuchten Schlüssel mit dem Median der Schlüsselmenge. Der Median ist hier das mittlere Element beziehungsweise der Wert, der die Menge in zwei Bereiche teilt. Danach sucht man rekursiv entweder in der Teilmenge der kleineren Elemente oder in der Teilmenge der größeren Elemente weiter.
Auch der euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen folgt dem Teile-und-herrsche-Prinzip. Dabei wird das Problem iterativ vereinfacht, indem man „gemeinsame“ Teile entfernt. Iterativ bedeutet, dass ein Schritt wiederholt angewendet wird.
Programmierpraxis
Das Teile-und-herrsche-Prinzip zeigt sich nicht nur in einzelnen Algorithmen, sondern auch in der Struktur von Computerprogrammen. Viele Programmiersprachen gliedern Programme in kleinere Einheiten wie Prozeduren, Funktionen, Module, Objekte, Komponenten, Prozesse und Threads.
Diese Gliederung folgt demselben Grundgedanken: Ein großes Programm oder eine große Aufgabe wird in überschaubare Teile zerlegt. Jeder Teil übernimmt eine bestimmte Aufgabe und kann getrennt betrachtet, entwickelt oder ausgeführt werden.
Alltägliche Anwendung
Die Methode lässt sich auch außerhalb der Informatik nutzen, etwa in nicht-mathematischen Fachbereichen oder im Alltag. Ein schwieriges Problem wird in kleinere Teilprobleme zerlegt. Diese werden einzeln gelöst und anschließend zu einem Gesamtergebnis zusammengefügt.
Als Beispiel nennt der Artikel das Schreiben eines Buches. Man kann zuerst eine Skizze als Gerüst verfassen, danach jede Komponente einzeln bearbeiten und abschließend alles zu einem zusammenhängenden Werk zusammenfügen.
