Teile und Herrsche (Informatik)
- Teile und Herrsche (Informatik)
-
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.
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.
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.
Siehe auch
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
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 1… … Deutsch Wikipedia
Teile und herrsche — steht für: Divide et impera, eine Redewendung Teile und herrsche (Informatik), einen Lösungsansatz in der Informatik Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort bezeichnete … Deutsch Wikipedia
Klassifikator (Informatik) — Ein Klassifikator (Informatik) ist ein Algorithmus, der Objekte (z.B. Dokumente) anhand ihrer Merkmale in vorgegebene Kategorien einordnet. Der Begriff Klassifikator wird meist spezifisch für solche Algorithmen verwendet, in denen der… … Deutsch Wikipedia
Merge-Sort — Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der… … Deutsch Wikipedia
MergeSort — ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der zusätzliche… … Deutsch Wikipedia
Merge Sort — Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der… … Deutsch Wikipedia
Natural Mergesort — Mergesort ist ein rekursiver, stabiler Sortieralgorithmus, der ähnlich wie Quicksort nach dem Prinzip Teile und herrsche (lat. Divide et impera, engl. Divide and Conquer) arbeitet. Er wurde erstmals 1945 durch John von Neumann vorgestellt. Der… … Deutsch Wikipedia
Fast-Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… … Deutsch Wikipedia
Fast Fourier-Transformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… … Deutsch Wikipedia
Schnelle Fouriertransformation — Die schnelle Fourier Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der Werte einer diskreten Fourier Transformation (DFT). Bei dem Algorithmus handelt es sich um ein… … Deutsch Wikipedia
