Devide and Conquer

[Tockra]

Hallo Leute,

ich und ein Freund müssen bis morgen ein Referat zu dem Devide and Conquer Prinzip in Java halten.
Leider finden wir über Google nur Erklärungen, die leider nicht selbsterklärend sind.
Z.B. diese hier: http://www.bullhost.de/d/divide-and-conquer-verfahren.html
Leider ist die Erklärung des Verfahrend immer die selbe. Es wird immer von einer Zerteilung eines Problems in mehrere Teilprobleme geredet und dann von der anschließenden Zusammensetzung, sobald die Teilprobleme lösbar sind.
Nun wird nie so wirklich ein Anwendungsbeispiel erwähnt. Mit Strings, die mathematische Gleichungen darstellen kann man es sich evtl. noch vorstellen, so dass ein Term solange verkleinert wird bis man anstatt "5+7*8+9" = "5+7" "*" "8+9" hat.
Allerdings ist unser Verständnis dieser Methode auch nach langem googlen nur etwas schemenhaft vorhanden.
Vielleicht kann einer von euch uns weiterhelfen!

Gruß
Tim

 

[Marius]

Nimm als Referatuntertitel:

"Löse die kleinen Probleme und die Großen folgen ganz von selbst"

 

[yetisports]

Schaue dir mal den Quicksort-Algorithmus an. Das ist "Devide And Conquer" in einer Rekursion.

 

[Deneb91]

Im Prinzip ist Divide and Conquer (bzw. divide et impera) ganz simpel. Dein Problem wird solange in kleinere Teilprobleme aufgeteilt, bis du sie lösen kannst. Beim Quicksort wäre das der Fall, wenn dein Problem aus genau einem Element besteht, dieses ist trivialerweise sortiert.

Im Prinzip ist qSort ein richtig schönes Beispiel dafür. Oder auch MergeSort.

EDIT:
Och mist, nächstes mal F5 drücken. :/

 

[Quickbeam2k1]

Ein anderes (fortgeschritteneres) Beispiel ist die Berechnung der konvexen Hülle mittels eines divide and conquer verfahrens. Auch wenns ein direktlink ist: http://ddi.cs.uni-potsdam.de/Lehre/UebersichtInfoSST/KonvexeHuelle.pdf

Vorteil ist halt, dass man direkt eine geometrische Vorstellung hat (geht natürlich mit sortieralgorithmen auch)

 

[maxwell-cs]

das verfahren wird da angewandt, wo die laufzeit überproportional in der länge des inputs ansteigt, d.h. z.b.: doppelt so langer input resultiert in mehr als doppelt so langer laufzeit.

in diesen fällen können also zwei kleine instanzen schneller gelöst werden als eine große.

zusätzlich muss man aus lösungen von teilproblemen eine lösung des gesamtproblems zusammensetzen könnnen.

beispiel sortieren: man kann schneller zweimal n zahlen getrennt sortieren als ein mal 2n zahlen.

hat man aber zwei mal n zahlen bereits sortiert, kann man diese zu einer sortierten liste von 2n zahlen zusammenfügen. das ist genau das prinzip von mergesort.

wenn ihr verstanden habt, wie mergesort funktioniert, habt ihr divide & conquer verstanden.

quicksort geht zwar auch, aber ich finde, bei mergesort sieht man besser, was passiert.