Quelltext der Seite Teile-und-herrsche-Verfahren

{{Dieser Artikel|1=beschreibt ein Verfahren der Informationstechnik. Für die politische Strategie siehe [[Divide et impera]].}}
Das '''Teile-und-herrsche-Verfahren''' ({{enS|''divide and conquer''}} bzw. {{laS|''[[divide et impera]]''}}) bezeichnet in der [[Informatik]] ein [[Paradigma]] für den Entwurf von effizienten [[Algorithmus|Algorithmen]].

Der Grundsatz findet unter anderem Anwendung in [[Suchverfahren|Such-]] und [[Sortierverfahren]].

== Grundprinzip ==

Bei einem Teile-und-herrsche-Ansatz wird das eigentliche – in seiner [[Gesamtheit]] – als zu schwierig erscheinende Problem so lange [[Rekursion|rekursiv]] in ''kleinere'' und einfachere Teilprobleme zerlegt, bis diese gelöst („beherrschbar“) sind. Anschließend wird aus diesen Teillösungen eine Lösung für das Gesamtproblem (re-)konstruiert.

== Historische Vorläufer ==

Die [[binäre Suche]] nach einem [[Nummerung|Schlüssel]] ist eine der ersten algorithmischen Anwendungen  des Prinzips von „teile und herrsche“. Sie lässt sich zu den [[Babylonien|Babylonier]]n zurückverfolgen. Bei der binären Suche wird ein Schlüssel in einer [[Sortierung|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.  <!-- Quellenangabe ergänzen: Knuth TACP Vol. 3? -->

Der [[Euklidischer Algorithmus|euklidische Algorithmus]] zur Bestimmung des [[Größter gemeinsamer Teiler|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 ==

„Teile und herrsche“ ist eines der wichtigsten Prinzipien für effiziente [[Algorithmus|Algorithmen]]. Dabei wird ausgenutzt, dass bei vielen Problemen der Lösungsaufwand sinkt, wenn das Problem in kleinere Teilprobleme zerlegt wird. 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 [[Optimierungsproblem]]en der [[Lösungsraum]] aufgeteilt und aus den [[Unterraum|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 [[Programmiersprache]]n wird die Gliederung von [[Computerprogramm]]en in [[Prozedur (Programmierung)|Prozeduren]], [[Funktion (Programmierung)|Funktionen]], [[Modul (Software)|Module]], [[Objekt (Programmierung)|Objekte]], [[Komponente (Software)|Komponenten]], [[Prozess (Informatik)|Prozesse]] und [[Thread (Informatik)|Threads]] nach dem Prinzip „Teile und herrsche“ umgesetzt.

== Anwendung jenseits der Informatik ==

Die Methode „Teile und herrsche“  lässt sich auch für Probleme nicht-mathematischer Fachbereiche und im Alltag anwenden. Man zerlegt ein schwieriges Problem in kleine Teilprobleme, die man dann einzeln lösen und zu einem Gesamtergebnis zusammenfügen kann. Wer beispielsweise ein Buch schreiben will, kann eine Skizze als Gerüst verfassen, dann jede Komponente einzeln angehen und abschließend alles zu einem zusammenhängenden Werk zusammenfügen.<ref>[[Charles Fadel]], Bernie Trilling, Maya Bialik: ''Four-Dimensional Education: The Competencies Learners Need to Succeed.'' 2015, ISBN 978-1-5186-4256-2, S. 79.</ref>

== Siehe auch ==

* [[Dynamische Programmierung]]

== Einzelnachweise ==

<references/>

{{Normdaten|TYP=s|GND=4291466-8|REMARK=Divide-and-conquer- bzw. Teile-und-herrsche-Verfahren.}}

[[Kategorie:Algorithmus]]
[[Kategorie:Programmierung]]