Divide et Impera (desparte si stapaneste)

O scurta introducere in istorie: Expresia  Divide et impera este atribuita lui Filip al II-lea (rege al Macedoniei (382-336 IC) descriind politica sa asupra oraselor state-grecesti.

Dezbină si stăpâneşte reprezinta, din punct de vedere politic si sociologic, o combinaţie de tactici (politice, militare sau economice) prin care se urmareste castigarea si mentinerea puterii prin divizarea unei populatii in entitati mai mici care luate separat au putere mai mica decat cele care sunt unite, impunandu-si astfel puterea.

Aceasta tactica are rezultate atunci cand cei cu mai putina putere si influenta doresc sa-si impuna puterea asupra celor care, daca s-ar uni, ar avea o putere mare.

Elementele constitutive aceste strategii sunt:

-crearea sau neimpotrivirea la formarea unor grupuri mici in randul populatiei vizate

-ajutarea si promovarea celor care doresc sa colaboreze (in randul carora intra si tradatorii) cu cel ce doreste sa se impuna ca forta

-promovarea neincrederii si neintelegerilor intre membrii grupurilor mici

-impunerea propriei vointe asupra grupurilor/membrilor unui grup in vederea obtinerii rezultatelor dorite.

In informatica, aceasta strategie reprezinta o metoda de rezolvare a problemelor. Ideea de baza consta in impartirea unei probleme in 2 sau mai multe subprobleme care se rezolva separat, apoi se trece la combinarea rezultatelor problemelor rezolvate obtinandu-se, astfel, solutia finala.

La baza problemelor rezolvabile prin aceasta metoda sta urmatorul enunt:

Se da un sir de valori (secventa de valori) a1, a2, a3,…, an. Aceasta secventa trebuie prelucrata.

Prelucrarea se va realize in felul urmator: sirul se imparte in 2 sau mai multe subsiruri. Fiecare subsir se va impartii, dupa aceiasi metoda, in 2 sau mai multe subsiruri pana cand se ajunge la o problema rezolvabila sau un rezultat cunoscut.  Din aproape in aproape, prin combinarea rezultatelor obtinute, se obtine rezultatul final.

Exemple de probleme rezolvabile prin aceasta tehnica (metoda):

-calculul sumei/produsului elementelor unui sir

-determinarea minimului/maximului dintr-un sir

-sa se verifice anumiti termini din sir care au o anumita proprietate data (sunt pare/ sunt prime/ sunt positive etc).

Algoritmul general al functiei/procedurii metodei Divide et Impera este urmatorul:

Subprogram DivideEtImpara(inceput,sfarsit,rezultat)

{inceput-pozitia primului termen din sir/subsir; sfarsit-pozitia ultimului termen din sir/subsir}

1.       Daca <s-a terminat divizarea sirului in unu sau doi termini> atunci

1.1. Prelucrez_secventa_divizata(inceput,sfarsit,rezultat)

                                                                                                                    altfel

1.2. Divizez_secventa(inceput,sfarsit,m) {nu in toate problemele m reprezinta pozitia elementului de la mijloc)

1.3. DivideEtImpera(inceput,m,rezultat1)

1.4. DivideEtImpera(m,sfarsit,rezultat2)

1.5. Combin_rezultate(rezultat1,rezultat2,rezultat)

Sfarsit subprogram

De exemplu dorim sa realizam suma numerelor de la 5 la 10.

Sirul de valori este 5,6,7,8,9,10. Pe prima pozitie in sir este 5 iar pe ultima (pozitia 6) este 10.

Inceput=1; sfarsit=6.

Impartim sirul in 2 subsiruri. Pentru acest lucru trebuie sa gasim pozitia elementului din mijloc.

m=(inceput+sfarsit)/2=(1+6)/2=3

prin urmare, de exemplu, primul subsir s1=(5,6,7) iar al doilea este s2=(8,9,10)

Prelucram primul subsir dupa aceiasi metoda ca si sirul din care a provenit.

Inceput=1; sfarsit=3; mijloc=(1+3)/2=2;

Prin urmare obtinem:

S11=(5,6) si S12=(7).

Cele 2 subsiruri au 2 si respectiv 1 element.

Pentru S12=(7) suma este 7 prin urmare rezultat12=7.

Sirul S11 il putem imparti in 2 subsiruri sau sa tratam in algoritm situatia cand sirul are 2 termesni iar solutia este usor de aflat. Algem metoda cand impartim sirul in 2 subsiruri.

S121=(5) prin urmare rezultatul sumei elementelor este 5 si rezultatat121=5.

S122=(6)=>suma elementelor din subsir este 6 iar rezultat122=6.

Combinam cele 2 rezultate si obtinem ca s12=s121+s122=5+6=11=> rezultat12=11;

Din rezultat12 si rezultat 11 putem obtine rezultatul pentru s1.

Rezultat1=rezultat11+rezultat12=11+7=18.

Trecem acum la gasirea sumei in sirul s2.

Procedand analog obtinem:

rezultat211=8; rezultat212=9; prin urmare rezultat21=17.

Rezultat22=10;

Combinam rezultatele si obtinem: rezultat2=rezultat21+rezultat22=17+10=27.

Avand rezultatele rezultat1 si rezultat2 obtinem rezultatul problemei ca suma dintre cele 2 rezultate: rezultat=27+18=45.

Ca sa intelegeti mai bine aceas procedeu va recomand sa faceti schemele de rezolvare pentru fiecare problem pe care doriti sa o rezolvati folosind aceasta metoda.