DIVIDEANDCONQUERVERFAHREN

Divide-and-Conquer-Verfahren

 

[dt. »teile und herrsche«], Verfahren der Software-Entwicklung mit zwei wesentlichen Phasen: In der ersten Phase wird ein komplexes Problem in mehrere unabhängige Teilprobleme zerlegt; ist auch ein solches Teilproblem nicht ohne weiteres zu lösen, muss man es so lange weiter zerlegen, bis das Ausgangsproblem in lauter lösbare Einzelprobleme geteilt ist, deren Lösungen sich direkt in der jeweiligen Programmiersprache umsetzen lassen. Diese erste Phase entspricht der Top-Down-Methode.

 

In der zweiten Phase werden die einzelnen Teilprogramme zu einem komplexen Gesamtprogramm zusammengefügt; diese zweite Phase entspricht der Bottom-Up-Methode.

 

Analog wird der Begriff »Divide and Conquer« auch zur Typisierung von Algorithmen verwendet: Ein Problem auf einer großen Datenmenge wird auf zwei oder mehr Probleme derselben Art auf kleineren Datenmengen reduziert. Diese Datenpartition wird rekursiv fortgesetzt, bis so kleine Datenmengen entstehen, dass sich das Problem leicht lösen lässt. Ein typischer Divide-and-Conquer-Algorithmus ist das Sortierverfahren Quicksort.