Metoda Divide et Impera

Metoda Divide et Impera ('desparte si stapaneste') consta in impartirea repetata a unei probleme de dimensiuni mari in mai multe subprobleme de acelasi tip, urmata de rezolvarea acestora si combinarea rezultatelor obtinute pentre a determina rezultatul corespunzator problemei initiale. Pentru fiecare subproblema procedam in acelasi mod, cu exceptia cazului in care dimensiunea ei este suficient de mica pentru a fi rezolvata direct.

            Este evident caracterul recursiv al acestei metode.

·        Schema generala

Descriem schema generala pentru cazul in care aplicam metoda pentru o prelucrare oarecare asupra elementelor unui vector. Functia DivImp, care intoarce rezultatul prelucrarii asupra unei subsecvente a_p,a_u, va fi apelata prin DivImp(1,n).

function DivImp(p,u)   

   if u–p<ε                

   then r ← Prel(p,u)

   else m ← Interm (p,u);

        r1 ← DivImp(p,m);

        r2 ← DivImp(m+1,u);

        r ← Combin(r1,r2)

   return r

end;

unde:

-         functia Interm intoarce un indice in intervalul p..u (de obicei m=ë(p+u)/2û ).

-         functia Prel este capabila sa intoarca rezultatul subsecventei p..u, daca aceasta este suficient de mica;

-         functia Combin intoarce rezultatul asamblarii rezultatelor partiale r1 si r2.

Exemple:

§         Calculul maximului elementelor unui vector;

§         Parcurgerile in preordine, inordine si postordine ale unui arbore binar;

§         Sortarea folosind arbori de sortare.

·        Cautarea binara

Se considera vectorul a=(a₁, ,a_n) ordonat crescator si o valoare x. Se cere sa se determine daca x apare printre componentele vectorului.

Problema enuntata constituie un exemplu pentru cazul in care problema se reduce la o singura subproblema.

            Tinand cont de faptul ca a este ordonat crescator, vom compara pe x cu elementul din 'mijlocul' vectorului. Daca avem egalitate, algoritmul se incheie; in caz contrar vom lucra fie pe 'jumatatea' din stanga, fie pe cea din dreapta.

            Vom adauga a=-∞, a_n+1=+ ∞. Cautam perechea (b,i) data de:

§         (true,i)                        daca a_i=x;

§         (false,i)          daca a_i-1<x<a_i.

Deoarece problema se reduce la o singura subproblema, nu mai este necesar sa folosim recursivitatea.

Algoritmul este urmatorul:

procedure CautBin                 

   p ← u; u ← n

   while p≤u

      i ← ë(p+u)/2û

      case a_i>x : u ← i-1                

           a_i=x : write(true,i); stop

           a_i<x : p ← i+1

   write(false,p)

end

            Algoritmul necesita o mica analiza, legata de corectitudinea sa partiala. Mai precis, ne intrebam: cand se ajunge la p>u?

§         pentru cel putin 3 elemente : nu se poate ajunge la p>u;

§         pentru 2 elemente, adica pentru u=p+1: se alege i=p. Daca x<a_i, atunci u¬p-1. Se observa ca se iese din ciclul while si a_i-1<x<a_i=a_p;

§         pentru un element, adica p=u: se alege i=p=u. Daca x<a_i atunci u¬p-1, iar daca x>a_i atunci p¬u+1; in ambele cazuri se paraseste ciclulwhile si tipareste un rezultat corect.