IMPERA - METODA DIVIDE ET IMPERA REFERAT SCOALA

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. Deoarece putine probleme indeplinesc conditiile de mai sus ,aplicarea metodei este destul de rara. Dupa cum sugereaza si numele "desparte si stapaneste "etapele rezolvarii unei probleme (numita problema initiala) in DIVIDE ET IMPERA sunt : - descompunerea problemei initiale in subprobleme independente ,smilare problemei de baza ,de dimensiuni mai mici ; descompunerea treptata a subproblemelor in alte subprobleme din ce in ce mai simple ,pana cand se pot rezolva imediata ,prin algoritmul simplificat ; rezolvarea subproblemelor simple ; combinarea solutiilor gasite pentru construirea solutiilor subproblemelor de dimensiuni din ce in ce mai mari ; combinarea ultimelor solutii determina obtinerea solutiei problemei initiale .