Divide et impera (informatică)
De la Wikipedia, enciclopedia liberă
 |
Deşi acest articol conţine o listă de referinţe bibliografice, sursele sale rămân neclare deoarece îi lipsesc notele de subsol. Puteţi ajuta introducând citări mai precise ale surselor. |
Divide et impera este o clasă de algoritmi care funcţionează pe baza tacticii divide et impera.
Cuprins |
[modifică] Prezentare generală
Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai uşoare), care se rezolvă, iar soluţia pentru problema iniţială se obţine combinând soluţiile subproblemelor. De multe ori, subproblemele sunt de acelaşi tip şi pentru fiecare din ele se poate aplica aceeaşi tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.
Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin "divide et impera" este relativ mic, tocmai datorită cerinţei ca problema să admită o descompunere repetată.
Divide et impera este o tehnică ce admite o implementare recursivă. Principiul general prin care se elaborează algoritmi recursivi este: "ce se întâmplă la un nivel, se întâmplă la orice nivel" (având grijă să asigurăm condiţiile de terminare). Aşadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilităţi:
- s-a ajuns la o problemă care admite o rezolvare imediată (condiţia de terminare), caz în care se rezolvă şi se revine din apel;
- nu s-a ajuns în situaţia de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcţiei, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revnirii din apel.
[modifică] Aplicaţii
[modifică] Maximul dintr-un vector
Se citeşte un vector cu n componente, numere naturale. Se cere să se tipărească valoarea maximă.
Funcţia căutată va genera valoarea maximă dintre numerele reţinute în vector pe o poziţie dintre i şi j (iniţial, i=1, j=n). Pentru aceasta, se procedează astfel:
- dacă i=j, valoarea maxima va fi v[i];
- în caz contrar, se imparte vectorul în doi subvectori - presupunem varianta pentru paralelizare pe 2 procesoare. Se calculează mijlocul m al intervalului [i, j]: m = (i+j) div 2. Primul subvector va conţine componentele de la i la m, al doilea va conţine componentele de la (m+1) la j; se rezolvă subproblemele (aflându-se astfel maximul pentru fiecare din subvectori), iar soluţia curentă va fi dată de valoarea maximă dintre rezultatele celor două subprobleme.
#include<iostream.h>
int v[10],n;
int max(int i, int j)
{
int a, b, m;
if (i==j) return v[i];
else
{
m = (i+j)/2;
a = max(i, m);
b = max(m+1, j);
if (a>b) return a;
else return b;
}
}
main( )
{
cout<<”n=”;cin>>n;
for (int i=1; i<=n; i++)
{
cout<<”v[“<<i<<”]=”; cin>>v[i];
}
cout<<”max=”<<max(1,n);
}
[modifică] Căutare binară
Se citeşte un vector cu n componente numere întregi (numerele se presupun ordonate crescător) şi o valoare întreagă ("nr"). Să se decidă dacă nr se găseşte sau nu printre numerele citite, iar în caz afirmativ să se tipărească indicele componentei care conţine această valoare.
O rezolvare în care nr se compară pe rând cu toate cele n componente reperzintă o pierdere de performanţă (nu exploatează faptul că cele n valori sunt în secvenţă crescătoare). Algoritmul care va fi propus este optim şi se poate spune că face parte dintre algoritmii "clasici".
Funcţia care va fi implementată va decide dacă valoarea căutată se găseşte printre numerele aflate pe poziţii de indice cuprins între i şi j (iniţial, i=1, j=n). Pentru aceasta, se va proceda astfel:
- dacă nr coincide cu valoarea de la mijloc, aflată pe poziţia de indice (i+j)/2, se tipăreşte indicele şi se revine din apel (problema a fost rezolvată).
- în caz contrar, dacă mai sunt şi alte elemente de analizat (adică i<j, deci nu au fost verificate toate poziţiile necesare), problema se descompune astfel:
-
- dacă nr este mai mic decât valoarea testată (din mijloc), înseamnă că nu se poate afla pe poziţiile din partea dreaptă, întrucât acestea sunt cel puţin mai mari decât valoarea testată. Nr se poate găsi doar printre componentele cu indice între i şi (i+j)/2 - 1, caz în care se reapelează funcţia cu aceşti parametri;
- dacă nr este mai mare decât valoarea testată (din mijloc), înseamnă că nu se poate afla în stânga; se poate găsi doar printre componentele cu indicele între (i+j)/2 + 1 şi j, caz în care se reapelează funcţia cu aceşti parametri.
- dacă nu mai sunt alte elemente de analizat (pentru că i=j şi valoarea din mijloc, v[i], nu coincide cu nr), se concluzionează că nr nu apare în cadrul vectorului.
Această problemă nu mai necesită analiza tuturor subproblemelor în care se descompune, ea se reduce la o singură subproblemă, iar partea de combinare a soluţiilor dispare. În linii mari, această rezolvare este tot de tip "divide et impera".
#include<iostream.h>
int v[100], n, nr;
void caut(int i, int j)
{
int m = (i+j)/2;
if (nr==v[m])
cout<<”gasit, indice=”<<m;
else
if (i<j)
if (nr<v[m])
caut(i, m-1);
else caut(m+1, j);
else cout<<”nu a fost gasit.”;
}
main( )
{
cout<<”n=”; cin>>n;
for (int i=1; i<=n; i++)
{
cout<<”v[“<<i<<”]=”; cin>>v[i];
}
cout<<”nr=”; cin>>nr;
caut (1,n);
}
[modifică] Bibliografie
- Doina Logofătu: Algoritmi fundamentali in C++. Aplicaţii, Ed. 1, Editura Polirom, Iaşi, 2007, ISBN 9734600939.
- Doina Logofătu: Algoritmi fundamentali in Java. Aplicaţii, Ed. 1, Editura Polirom, Iaşi, 2007, ISBN 9734608157.
