Metoda de programare divide & impera

Expresia provine din latina unde exista si ca proverb: ,,Divide et impera" . In romana este mai cunoscut ca: ,,dezbina si stapaneste". Alte posibile traduceri ar fi: dezbina si impune-ti vointa sau dezbina si domina.

In politica si sociologie, dezbina si stapaneste este o combinatie de tactici (politice, militare sau economice) de castigare si mentinere a puterii prin divizarea unei populatii in entitati mai mici care luate separat au putere mai mica decit cel care isi impune vointa. Este deseori intalnita ca o strategie in care grupuri de putere mica sunt impiedicate sa se uneasca si sa devina mai puternice.

Folosita efectiv, acesta strategie permite celor cu putere reala putina sa-si impuna vointa asupra celor care colectiv au putere mare (sau ar avea daca ar reusi sa se unesca).

Expresia este atribuita lui Filip al II-lea, rege al Macedoniei (382-336 I.C.), descriind politica sa impotriva oraselor-state grecesti.

In informatica, Divide et impera este o clasa de algoritmi care functioneaza pe baza tacticii divide et impera.

Divide et impera se bazeaza pe principiul descompunerii problemei in doua sau mai multe subprobleme (mai usoare), care se rezolva, iar solutia pentru problema initiala se obtine combinand solutiile subproblemelor. De multe ori, subproblemele sunt de acelasi tip si pentru fiecare din ele se poate aplica aceeasi tactica a descompunerii in (alte) subprobleme, pana cand (in urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediata.

Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma ca numarul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorita cerintei ca problema sa admita o descompunere repetata.

Divide et impera este o tehnica ce admite o implementare recursiva. Principiul general prin care se elaboreaza algoritmi recursivi este: "ce se intampla la un nivel, se intampla la orice nivel" (avand grija sa asiguram conditiile de terminare). Asadar, un algoritm prin divide et impera se elaboreaza astfel: la un anumit nivel avem doua posibilitati:

1. s-a ajuns la o problema care admite o rezolvare imediata (conditia de terminare), caz in care se rezolva si se revine din apel;

2. nu s-a ajuns in situatia de la punctul 1, caz in care problema curenta este descompusa in (doua sau mai multe) subprobleme, pentru fiecare din ele urmeaza un apel recursiv al functiei, dupa care combinarea rezultatelor are loc fie pentru fiecare subproblema, fie la final, inaintea revenirii din apel.

2. Aplicatii ale metodei ,,Divide & impera"

Metoda ,Divide & impera' se preteaza doar anumitor probleme. Printre acestea pot fi mentionate urmatoarele:

1. Problema ,,Turnurilor din Hanoi"

2. Sortarea rapida (quicksort)

3. Sortarea prin interclasare (mergesort)

Problema Turnurilor din Hanoi va fi prezentata mai pe larg in paginile urmatoare.

Sortarea rapida (quicksort)

Sortarea rapida (quicksort) sorteaza datele dupa principiul "imparte si stapaneste" (divide et impera) pentru a segmenta o lista in doua sub-liste.

Pasii care realizeaza aceasta divizare sunt:

1. Se alege un element, care se va numit pivot din elementele listei.

2. Se reordoneaza lista astfel incat toate elementele care detin o valoare mai mica decat valoarea elementului pivot (care este valoare de mijloc a listei) se vor pozitiona inaintea elementului pivot, si de asemeni elementele care au o valoare mai mare decat valoarea elementului pivot se vor pozitiona dupa elementul pivot (chiar si cu elementele cu valori egale se va proceda asa). Dupa aceasta aranjare a alementelor (partitionare) in functie de pivot, pivotul va fi pozitionat la locul potrivit. Aceasta operatie poarta denumirea de partitionare.

3. Se sorteaza recursiv sub-lista care detine elementele cu valorile mai mici decat valoarea elementului de mijloc (pivotul), apoi se sorteaza sub-lista care contine elementele cu valori mai mari decat valoarea elementului de mijloc.

Cazul de baza a unei recursivitati sunt listele de dimensiune zero sau unu, care sunt si ele sortate. Acest principiu este o varianta

[1] ***, http://ro.wikipedia.org/wiki/Divide_et_impera;

[2] ***, www.eed.usv.ro/~tudor_c/ASA_lab_8.pdf;

[3] ***, www.jocuri-online.page.tl/Turnurile-din-Hanoi.htm