Teile und herrsche (Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.
Bisher sind keinerlei Quellen angegeben. --DF5GO • 16:25, 14. Jan. 2013 (CET)

In der Informatik bezeichnet teile und herrsche (englisch divide and conquer bzw. lateinisch divide et impera) ein Paradigma für den Entwurf von effizienten Algorithmen.

Grundprinzip[Bearbeiten]

Bei einem „teile und herrsche“-Ansatz wird das eigentliche Problem so lange rekursiv 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[Bearbeiten]

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 Babyloniern zurückverfolgen. Bei der binären Suche wird ein Schlüssel in einer sortierten Schlüsselmenge gesucht. Dazu vergleicht man den gesuchten Schlüssel mit dem Median der Schlüsselmenge und sucht dann entsprechend in der Teilmenge der Elemente kleiner als der Median oder in der Teilmenge der Elemente größer als der Median rekursiv weiter.

Der Euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen folgt ebenfalls dem „Teile-und-herrsche“-Prinzip. Hierbei wird das Problem iterativ vereinfacht, indem man „gemeinsame“ Teile entfernt.

Anwendung in Algorithmen[Bearbeiten]

„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[Bearbeiten]

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[Bearbeiten]