“Divide et impera: divide si vei domni;divide si vei deveni bogat;divide si vei insela oamenii...divide si vei insela justitia.”

Prodhon





Metoda de programare DIVIDE ET IMPERA consta in impartirea problemei initiale de dimensiuni [n] in doua sau mai multe probleme de dimensiuni reduse .In general se executa impartirea in doua subprobleme de dimensiuni aproximativ egale si anume [n/2] . Impartirea in subprobleme are loc pana cand dimensiunea acestora devine suficient de mica pentru a fi rezolvate in mod direct(cazul de baza).Dupa rezolvarea celor doua subprobleme se executa faza de combinare a rezultatelor in vederea rezolvarii intregii probleme
Metoda
DIVIDE ET IMPERA se poate aplica in rezolvarea unei probleme care indeplineste urmatoarele conditii :
-se poate descompune in ( doua sau mai multe) suprobleme ;
-aceste suprobleme sunt independente una fata de alta (o subproblema nu se rezolva pe baza alteia si nu se foloseste rezultate celeilalte);
-aceste subprobleme sunt similare cu problema initiala;
-la randul lor subproblemele se pot descompune (daca este necesar) in alte subprobleme mai simple;
-aceste subprobleme simple se pot solutiona imediat prin algoritmul simplificat.



dd.jpg





back to Metoda Divide et Impera