Teile und herrsche (Informatik)

aus Wikipedia, der freien Enzyklopädie

Der Grundsatz Teile und herrsche (engl. divide and conquer bzw. lat. divide et impera) findet in vielen Teilgebieten der Informatik Anwendung und beschreibt einen reduktionistischen Lösungsansatz.

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

[Bearbeiten] Algorithmen

Das Prinzip wird aufgrund seiner Universalität auch in zahlreichen Algorithmen angewendet. Dabei wird ausgenutzt, dass bei vielen Problemen der Lösungsaufwand sinkt, wenn man das Problem in kleinere Teilprobleme zerlegt. Die Teilprobleme werden dann gleichzeitig parallel oder sequenziell (einzeln nacheinander) gelöst. Die Lösung für das Gesamtproblem ergibt sich je nach Algorithmus auf verschiedene Weise. Möglichkeiten sind unter Anderem:

• 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.
• 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 zusammengesetzt.
• 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.

[Bearbeiten] Siehe auch

• Teile und herrsche
• Dynamische Programmierung