Algoritmi de Programare Dinamica. Trei Principii Fundamentale ale Programarii Dinamice

Introducere

Programarea dinamică este o metodă de elaborare a algoritmilor care se aplică în general problemelor pentru care se cere determinarea unui optim în urma adoptării unor decizii.

Nu există un criteriu pe baza căruia să identificăm cu siguranță o problema pentru rezolvarea căreia trebuie să utilizăm metoda programării dinamice, dar putem formula doua proprietăți care sugerează o soluție prin programare dinamica.

În această lucrare încerc să prezint câteva din metodele generale de elaborare a algoritmilor.

Primul capitol al acestei lucrări este redată o prezentare generală despre structura optimală și subproblemee superpozabile cât și despre alte operații optimale.

În al doilea capitol sunt prezentați algoritmi de programare dinamică și trei principii fundamentale ale programării dinamice.

Capitolul trei prezintă câteva metode de sortare, algoritmii divide et impera și tehnica divide et impera.

Programarea dinamică și căteva probleme de alocare unidimensională, sunt prezentate în ultimul capitol al acestei lucrări.

Capitolul I

PREZENTARE GENERALĂ

1.1. Substructura optimală

Problema data poate fi descompusa în subprobleme si soluția optima a problemei depinde de soluțiile optime ale subproblemelor sale.

Acest criteriu nu indica neapărat o soluție prin programare dinamica, ar putea fi si un indiciu ca se poate aplica metoda Greedy sau metoda "Divide et Impera".

1.2. Subprobleme superpozabile

Subproblemele problemei date nu sunt independente, ci se suprapun.

Datorită faptului că subproblemele problemei date se suprapun, deducem că o abordare prin metoda "Divide et Impera" ar fi dezastruoasă din punctul de vedere al timpului de execuție (datorită faptului ca problemele se suprapun se ajunge la rezolvarea repetată a aceleiași subprobleme). Prin urmare, vom rezolva subproblemele o singura, dată, reținând rezultatele într-o structură de date suplimentară (de obicei un tablou).

Rezolvarea unei probleme prin programare dinamica presupune următorii pași:

– Se identifica subproblemele problemei date.

– Se alege o structura de date suplimentară, capabilă să rețină soluțiile subproblemelor.

– Se caracterizează substructură optimală a problemei printr-o relație de recurentă.

Pentru a determina soluția optimă, se rezolva relația de recurență în mod bottom-up (se rezolva subproblemele în ordinea crescătoare a dimensiunii lor).

În cele ce urmează vom exemplifica pas cu pas modul de rezolvare a problemelor prin metoda programarii dinamice.

1.3. Înmulțirea optimală a matricelor

Fie n matrice A1, A2, …, An, de dimensiuni d0xd1, d1xd2, …, dn-1xdn. Produsul A1xA2x…xAn se poate calcula în diverse moduri, aplicând asociativitatea operației de înmulțire a matricelor. Numim înmulțire elementară înmulțirea a doua elemente. În funcție de modul de parantezare diferă numărul de înmulțiri elementare necesare pentru calculul produsului A1xA2x…xAn. Determinați o parantezare optimală a produsului A1xA2x…xAn (costul parantezării, adică numărul total de înmulțiri elementare sa fie minim).

Exemplu:

Pentru n=3 matrice cu dimensiunile (10,1000), (1000,10) si (10,100), produsul A1xA2xA3 se poate calcula în doua moduri:

(A1xA2)xA3 necesitând 1000000+10000=1010000 înmulțiri elementare

A1x(A2xA3), necesitând 1000000+1000000=2000000 înmulțiri.

Reamintim ca numărul de înmulțiri elementare necesare pentru a înmulți o matrice A cu n linii si m coloane si B o matrice cu m linii si p coloane este n*m*p

Soluție:

Pentru a calcula A1xA2x…xAn, în final trebuie sa înmulțim două matrice, deci vom paranteza produsul astfel: (A1xA2x…xAk)x(Ak+1x…xAn ). Această observație se aplică si produselor dintre paranteze. Prin urmare, subproblemele problemei inițiale constau în determinarea parantezării optimale a produselor de matrice de forma AixAi+1x…xAj, 1<=i<=j. Observăm că subproblemele nu sunt independente. De exemplu, calcularea produsului AixAi+1x…xAj și calcularea produsului Ai+1xAi+2x…xAj+1, au ca subproblema comuna calcularea produsului Ai+1x…xAj.

Pentru a retine soluțiile subproblemelor, vom utiliza o matrice M, cu n linii și n coloane, cu semnificația:

M[i][j] = numărul minim de înmulțiri elementare necesare pentru a calcula produsul AixAi+1x…xAj, 1<=i<=j<=n.

Evident, numărul minim de înmulțiri necesare pentru a calcula A1xA2x…xAn este M[1][n].

Pentru ca parantezarea să fie optimală, parantezarea produselor A1xA2x…xAk și Ak+1x…xAn trebuie să fie de asemenea optimală. Prin urmare elementele matricei M trebuie sa satisfacă următoarea relație de recurenta:

M[i][i]=0, i={1,2,…,n}.

M[i][j]=min{M[i][k] + M[k+1][j] + d[i-1]*d[k]*d[j]}

i<=k<j

Cum interpretam aceasta relație de recurenta? Pentru a determina numărul minim de înmulțiri elementare pentru calculul produsului AixAi+1x…xAj, fixăm poziția de parantezare k în toate modurile posibile (între i si j-1), și alegem variantă care ne conduce la minim. Pentru o poziție k fixată, costul parantezării este egal cu numărul de înmulțiri elementare necesare pentru calculul produsului AixAi+1x…xAk, la care se adaugă numărul de înmulțiri elementare necesare pentru calculul produsului Ak+1x…xAj si costul înmulțirii celor doua matrice rezultate (di-1*dk*dj).

Observăm că numai jumătatea de deasupra diagonalei principale din M este utilizată. Pentru a construi soluția optimă este utilă și reținerea indicelui k, pentru care se obține minimul. Nu vom considera un alt tablou, ci-l vom reține, pe poziția simetrică față de diagonala principala (M[j][i]).

Rezolvarea recursivă a relației de recurenta de mai sus este ineficientă, datorită faptului că subproblemele de suprapun, deci o abordare recursia ar conduce la rezolvarea aceleiași subprobleme de mai multe ori. Prin urmare vom rezolva relația de recurenta în mod bottom-up: (determinam parantezarea optimală a produselor de două matrice, apoi de 3 matrice, 4 matrice, etc).

long

M[NMax][NMax];

void

dinamic()

{ int nr,

i, j, k, kmin;

long

min, Infinit=1000000000;

for

(nr=2; nr<=n; nr++) //nr =câte matrice se înmulțesc

for

(i=1; i<=n-nr+1; i++)

{j=i+nr-1;

//se înmulțesc nr matrice, de la Ai la Aj

for (k=i,

min=Infinit; k<j; k++)

//determin minimul si poziția sa

if

(min>M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j])

{min=M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j];

kmin=k;}

M[i][j]=min; M[j][i]=kmin; }

}

Reconstituirea soluției optime se face foarte ușor în mod recursiv, utilizând informațiile reținute sub diagonala principala în matricea M:

void

afisare(int i, int j)

{//afișează parantezarea optimală a produsului Aix…xAj

if

(i==M[j][i]) cout<<"A"<<i;

else

{cout<<"("; afișare(i,M[j][i]);

cout<<")";}

cout<<"x";

if

(j==M[j][i]+1) cout<<"A"<<j;

else

{cout<<"("; afișare(M[j][i]+1,j);

cout<<")";}}

1.4. Subșir crescător maximal

Fie un șir A=(a1, a2, …, an). Numim subșir al șirului A o succesiune de elemente din A, în ordinea în care acestea apar în A: ai1, ai2, …, aik, unde 1<= i1<i2<…<ik. Determinați un subșir crescător al șirului A, de lungime maximă.

Exemplu:

Pentru A=(8,3,6,50,10,8,100,30,60,40,80) o soluție poate fi:

( 3,6, 10, 30,60, 80).

Soluție

Fie Ai1=(ai1<=ai2<= …<= aik) cel mai lung subșir crescător al lui șirului A. Observăm ca el coincide cu cel mai lung subșir crescător al șirului (ai1, ai1+1, …, an). Evident Ai2=(ai2<=ai3<= …<= aik) este cel mai lung subșir crescător al lui (ai2, ai2+1, …, an), etc. Prin urmare, o subproblemă a problemei inițiale constă în determinarea celui mai lung subșir crescător care începe cu ai, i={1,.., n}. Subproblemele nu sunt independente: pentru a determina cel mai lung subșir crescător care începe cu ai, este necesar sa determinam cele mai lungi subșiruri crescătoare care încep cu aj, ai<=aj, j={i+1,.., n}.

Pentru a retine soluțiile subproblemelor vom considera doi vectori suplimentari l și poz, fiecare cu cate n componente, având semnificația:

l[i]=lungimea celui mai lung subșir crescător care începe cu a[i];

poz[i]=pozitia elementului care urmează după a[i] în cel mai lung subșir crescător care începe cu a[i], dacă un astfel de element există, sau -1 dacă un astfel de element nu exista.

Relația de recurenta care caracterizează substructura optimală a problemei este:

l[n]=1; poz[n]=-1;

l[i]=max{1+l[j]|a[i]<=a[j]}

j=i+1,n

poz[i]= indicele j pentru care se obține maximul l[i].

Rezolvam relația de recurență în mod bottom-up:

int i, j;

l[n]=1; poz[n]=-1;

for (i=n-1; i>0; i–)

for (l[i]=1,

poz[i]=-1, j=i+1; j<=n; j++)

if (a[i] <=

a[j] && l[i]<1+l[j])

{l[i]=1+l[j];

poz[i]=j;}

Pentru a determina soluția optima a problemei, determinam maximul din vectorul l, apoi afișăm soluția, începând cu poziția maximului si utilizând informațiile memorate în vectorul poz:

//determin maximul din vectorul l

int max=l[1], pozmax=1;

for (int i=2; i<=n; i++)

if (max<l[i]) {max=l[i]; pozmax=i;}

cout<< "Lungimea celui mai lung subșir crescător: " <<max;

cout<<"\nCel mai lung subșir:\n";

for (i=pozmax; i!=-1; i=poz[i])

cout<<a[i]<<' ';

1.5. Suma în triunghi

Să considerăm un triunghi format din n linii (1<n<=100), fiecare linie conținând numere întregi din domeniul [1,99], ca in exemplul următor:

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

Problema constă în scrierea unui program care sa determine cea mai mare sumă de numere aflate pe un drum între numărul de pe prima linie și un număr de pe ultima linie. Fiecare număr din acest drum este situat sub precedentul, la stânga sau la dreapta acestuia. (IOI, Suedia 1994)

Soluție

Vom reține triunghiul într-o matrice pătratica T, de ordin n, sub diagonala principala. Subproblemele problemei date constau în determinarea sumei maxime care se poate obține din numere aflate pe un drum între numărul T[i][j], până la un număr de pe ultima linie, fiecare număr din acest drum fiind situat sub precedentul, la stânga sau la dreapta sa. Evident, subproblemele nu sunt independente: pentru a calcula suma maxima a numerelor de pe un drum de la T[i][j] la ultima linie, trebuie sa calculăm suma maximă a numerelor de pe un drum de la T[i+1][j] la ultima linie si suma maximă a numerelor de pe un drum de la T[i+1][j+1] la ultima linie.

Pentru a retine soluțiile subproblemelor, vom utiliza o matrice suplimentara S, pătratica de ordin n, cu semnificația S[i][j]= suma maxima ce se poate obține pe un drum de la T[i][j] la un element de pe ultima linie, respectând condițiile problemei.

Evident, soluția problemei va fi S[1][1].

Relația de recurenta care caracterizează substructura optimală a problemei este:

S[n][i]=T[n][i], i={1,2,…,n}

S[i][j]=T[i][j]+max{S[i+1][j], S[i+1][j+1]}

Rezolvăm relația de recurenta în mod bottom-up:

int i,j;

for (i=1; i<=n; i++) S[n][i]=T[n][i];

for (i=n-1; i>0; i–)

for (j=1; j<=i; j++)

{S[i][j]=T[i][j]+S[i+1][j];

if (S[i+1][j]<S[i+1][j+1])

S[i][j]=T[i][j]+S[i+1][j+1]);}

Exercitiu

Afișați si drumul în triunghi pentru care se obține soluția optimă.

1.6. Subșir comun maximal

Fie X=(x1, x2, …, xn) si Y=(y1, y2, …, ym) două șiruri de n, respectiv m numere întregi. Determinați un subșir comun de lungime maximă.

Exemplu

Pentru X=(2,5,5,6,2,8,4,0,1,3,5,8) si Y=(6,2,5,6,5,5,4,3,5,8) o soluție posibilă este: Z=(2,5,5,4,3,5,8)

Soluție

Notăm cu Xk=(x1, x2, …, xk) (prefixul lui X de lungime k) si cu Yh=(y1, y2, …, yh) prefixul lui Y de lungime h. O subproblemă a problemei date constă în determinarea celui mai lung subșir comun al lui Xk, Yh. Notăm cu LCS(Xk,Yh) lungimea celui mai lung subșir comun al lui Xk, Yh. Utilizând aceste notații, problema cere determinarea LCS(Xn,Ym), precum și un astfel de subșir.

Observație 1. Daca Xk=Yh atunci LCS(Xk,Yh)=1+LCS(Xk-1,Yh-1).

2.Daca Xk Yh atunci LCS(Xk,Yh)=max(LCS(Xk-1,Yh), LCS(Xk,Yh-1)).

Din observația precedentă deducem ca subproblemele problemei date nu sunt independente și că problema are substructură optimalădente: pentru a calcula suma maxima a numerelor de pe un drum de la T[i][j] la ultima linie, trebuie sa calculăm suma maximă a numerelor de pe un drum de la T[i+1][j] la ultima linie si suma maximă a numerelor de pe un drum de la T[i+1][j+1] la ultima linie.

Pentru a retine soluțiile subproblemelor, vom utiliza o matrice suplimentara S, pătratica de ordin n, cu semnificația S[i][j]= suma maxima ce se poate obține pe un drum de la T[i][j] la un element de pe ultima linie, respectând condițiile problemei.

Evident, soluția problemei va fi S[1][1].

Relația de recurenta care caracterizează substructura optimală a problemei este:

S[n][i]=T[n][i], i={1,2,…,n}

S[i][j]=T[i][j]+max{S[i+1][j], S[i+1][j+1]}

Rezolvăm relația de recurenta în mod bottom-up:

int i,j;

for (i=1; i<=n; i++) S[n][i]=T[n][i];

for (i=n-1; i>0; i–)

for (j=1; j<=i; j++)

{S[i][j]=T[i][j]+S[i+1][j];

if (S[i+1][j]<S[i+1][j+1])

S[i][j]=T[i][j]+S[i+1][j+1]);}

Exercitiu

Afișați si drumul în triunghi pentru care se obține soluția optimă.

1.6. Subșir comun maximal

Fie X=(x1, x2, …, xn) si Y=(y1, y2, …, ym) două șiruri de n, respectiv m numere întregi. Determinați un subșir comun de lungime maximă.

Exemplu

Pentru X=(2,5,5,6,2,8,4,0,1,3,5,8) si Y=(6,2,5,6,5,5,4,3,5,8) o soluție posibilă este: Z=(2,5,5,4,3,5,8)

Soluție

Notăm cu Xk=(x1, x2, …, xk) (prefixul lui X de lungime k) si cu Yh=(y1, y2, …, yh) prefixul lui Y de lungime h. O subproblemă a problemei date constă în determinarea celui mai lung subșir comun al lui Xk, Yh. Notăm cu LCS(Xk,Yh) lungimea celui mai lung subșir comun al lui Xk, Yh. Utilizând aceste notații, problema cere determinarea LCS(Xn,Ym), precum și un astfel de subșir.

Observație 1. Daca Xk=Yh atunci LCS(Xk,Yh)=1+LCS(Xk-1,Yh-1).

2.Daca Xk Yh atunci LCS(Xk,Yh)=max(LCS(Xk-1,Yh), LCS(Xk,Yh-1)).

Din observația precedentă deducem ca subproblemele problemei date nu sunt independente și că problema are substructură optimală.

Pentru a reține soluțiile subproblemelor vom utiliza o matrice cu n+1 linii si m+1 coloane, denumita lcs. Linia și coloana 0 sunt utilizate pentru inițializare cu 0, iar elementul lcs[k][h] va fi lungimea celui mai lung subșir comun al șirurilor Xk si Yh.

Vom caracteriza substructura optimală a problemei prin următoarea relație de recurentă:

lcs[k][0]=lcs[0][h]=0, k={1,2,..,n}, h={1,2,..,m}

lcs[k][h]=1+lcs[k-1][h-1], daca x[k]=y[h]

max{lcs[k][h-1], lcs[k-1][h]}, daca x[k]<>y[h]

Rezolvăm relația de recurență în mod bottom-up:

for (int k=1; k<=n; k++)

for (int h=1; h<=m; h++)

if (x[k]==y[h])

lcs[k][h]=1+lcs[k-1][h-1];

else

if (lcs[k-1][h]>lcs[k][h-1])

lcs[k][h]=lcs[k-1][h];

else

lcs[k][h]=lcs[k][h-1];

Deoarece nu am utilizat o structură de date suplimentară cu ajutorul căreia sa memoram soluția optima, vom reconstitui soluția optimă pe baza rezultatelor memorate în matricea lcs. Prin reconstituire vom obține soluția în ordine inversă, din acest motiv vom memora soluția într-un vector, pe care îl vom afișa de la sfârșit câtre început:

cout<<"Lungimea subșirului comun maximal: "

<<lcs[n][m];

int d[100];

cout<<"\nCel mai lung subsir comun este: \n";

for (int i=0, k=n, h=m; lcs[k][h]; )

if (x[k]==y[h])

{d[i++]=x[k];k–; h–;}

else

if (lcs[k][h]==lcs[k-1][h])

k–;

else

h–;

for

(k=i-1;k>=0; k–)cout<<d[k]<<' ';

Capitolul II

ALGORITMI DE PROGRAMARE DINAMICĂ

TREI PRINCIPII FUNDAMENTALE ALE PROGRAMĂRII DINAMICE

Programarea dinamică, ca și metoda divide et impera, rezolvă problemele combinând soluțiile problemelor. După cum am văzut, algoritmii divide et impera partiționează problemele în subprobleme independente, rezolvă problemele în mod recursiv, iar apoi combină soluțiile lor pentru a rezolva problema inițială. Dacă subproblemele conțin subprobleme comune, în locul metodei divide et impera este mai avantajoas de aplicat tehnica programării dinamice.

2.1. Determinarea celor mai scurte drumuri într-un graf

Fie G=<V,M> un graf orientat, unde V este mulțimea vârfurilor și M este mulțimea muchiilor. Fiecărei muchii i se asociază o lungime negativă. Dorim să calculăm lungimea celui mai scurt drum între fiecare pereche de vârfuri.

Vom presupune că vârfurile sunt numerotate de la 1 la n, și că matricea L dă lungimea fiecărei muchii: L[i,i]=0, L[i,j]0 pentru ij, L[i,j]=+ dacă muchia (i,j) nu există.

Principiul optimalității este valabil: dacă cel mai scurt drum de la i la j trece prin vârful k, atunci porțiunea de drum de la i la k cât și cea de la k la j, trebuie să fie, de asemenea optime.

Construim o matrice D care să conțină lungimea celui mai scurt drum între fiecare pereche de vârfuri. Algoritmul de programare dinamică inițializează pe D cu L, apoi efectuează n iterații. După iterația k, D va conține lungimile celor mai scurte drumuri care folosesc ca vârfuri intermediare doar vârfurile din {1,2,…,k}. După n iterații, obține rezultatul final. La iterația k, algoritmul trebuie să verifice pentru fiecare pereche de vârfuri (i,j) dacă există sau nu un drum, trecând prin vârful k, care este mai bun decât actualul drum optim ce trece doar prin vârfurile din {1,2,…,k-1}. Fie Dk matricea D după iterația k.

Verificarea necesară este atunci:

Dk[i,j]=min(dk-1[i,j], Dk-1[i,k]+Dk-1[k,j])

unde am făcut uz de principiul optimalității pentru a calcula lungimea celui mai scurt drum via k. implicit, am considerat că un drum optim care trece prin k nu poate trece de două ori prin k.

Acest algoritm simplu este datorat lui Floyd (1962):

function Floyd(L[1..n, 1..n])

array D[1..n, 1..n]

DL

for k1 to n do

for i1 to n do

for j1 to n do

D[i,j] min (D[i,j], D[i,k]+D[k,j])

return D

De exemplu, dacă avem

obținem succesiv

De obicei dorim să aflăm nu numai lungimea celui mai scurt drum, dar și traseul său. În această situație, vom construi o a doua matrice P, inițializată cu zero. Bucla cea mai interioară a algoritmului devine

if D[i,k]+D[k,j]<D[i,j] then D[i,j]D[i,k]+D[k,j]

P[i,j]k

Când algoritmul se oprește, P[i,j] va conține vârful din ultima iterație care a cauzat o modificare în D[i,j]. Pentru a afla prin ce vârfuri trece cel mai scurt drum de la i la j, consultăm elementul P[i,j]. Dacă P[i,j]=0, atunci cel mai scurt drum este chiar muchia (i,j). Dacă P[i,j]=k, atunci cel mai scurt drum de la i la j trece prin k și urmează să consultăm recursiv elementele P[i,k] și P[k,j] pentru a găsi și celelalte vârfuri intermediare.

Algoritmi de programare dinamică

2.2. Arbori binari optimi de căutare

Un arbore binr în care fiecare fârf conține o valoare numită cheie este un arbore de căutare, dacă cheia fiecărui vârf neterminal este mai mare sau egală cu cheia descendenților săi stângi și mai mică sau egală cu cheia descendenților săi drepți. Dacă cheile arborelui sunt distincte, aceste inegalități sunt, în mod evident, stricte.

Figura de mai sus este un exemplu de arbore de căutare *, conținând cheile A, B, C,…,H. vârfurile pot conține și alte informații în afară de chei, la care să avem acces prin intermediul cheilor. Această structură de date este utilă, deoarece permitee o căutare eficientă a valorilor în arbore:

Cu o mulțime dată de chei, se pot construi mai mulți arbori de căutare(fig. de sus). Pentru a căuta o cheie X în arborele de căutare, X va fi comparată la început cu cheia rădăcinei arborelui. Dacă X este mai mică decât cheia rădăcinii, atunci se continuă căutarea în subarborele stâng. Dacă X este egală cu cheia rădăcinii, atunci căutarea se incheie cu succes. Dacă X este mai mare decât cheia rădăcinii, atunci se cotinuă căutarea în subarborele drept. Se continuă astfel recursiv accest proces.

Generăm un arbore binar, conform următoarei metode recursive:

-rădăcina este etichetată cu (1,n)

-dacă un vârf este etichetat cu (i,j), i este mai mic decât j, atunci fiul său stâng va fi etichetat cu (i,r[i,j]-1) ;i fiul său drept cu(r[i,j]+1,j)

-vârfurile terminale sunt etichetate cu (i,i)

plecând de la acest arbore, arborele de căutare optim se obține schimbând etichetele (i,j), i<j, în cr[i,j], iar etichetele (i,i) în ci.

2.3. Arborii binari de căutare tip dată

Într-o primă aproximare, arborele binar este un tip de dată similar tipului listă. Vârfurile sunt compuse din informație cheie și legături, iar arborele propriu-zis este complet precizat prin adresa vârfului rădăcină.

În cazul arborelui de căutare, nu mai este necesară o astfel de generalitate, deoarece vom implementa direct operațiile specifice. În mare, aceste operații sunt îpărțite în:

-Căutări. Localizarea vârfului cu o anumită cheie, a succesorului sau predecesorului său, precum și a vârfurilor cu cheile de valoare maximă, respectiv minimă.

-Modificări. Arborele se modifică prin ștergerea sau inserarea unor vârfuri.

-Organizări. Arborele nu este construit prin inserarea elementelor, ci global prin stabilirea unei legături unice între vârfuri. Un caz particular al acestei operații este reorganizarea arborelui dupăo perioadă suficient de mare de utilizare.

2.4. Arborele optim

Vom rezolva problema obținerii arborelui optim în cel mai simplu caz posibil. Având în vedere specificul diferit al operațiilor de organizare față de celelalte operații efectuate asupra grafurilor, am considerat util să încapsulăm optimizarea într-o clasă pe care o vom numi structura pentru optimizarea arborilor.

Funcționalitatea ei constă în:

-inițializarea unui tablou cu adresele vârfurilor în ordinea crescătoare a probabilităților cheilor.

-stabilirea de noi legăturiîntre vârfuri, astfel încât arborele să fie optim.

Principala cauză pentru care a fost aleasăaceastă implementare este că sunt necesare doar operații de modificare a legăturilor. Deplasarea unui vârf înseamnă nu numai deplasarea cheii, ci și a informațieiasociate.

2.5. Căutarea în arbore

Principala operație efectuată prin intermediul arborilor binari de căutare este regăsirea informației asociate unei anumite chei. Actualizarea probabilităților cheilor din arbore, după fiecare căutare, este cea mai delicată, deoarece impune stabilirea importanței evaluărilor existente în raport cu rezultatul căutărilor. De fapt este vorba de un proces de invățare care pornește de la cunoștințe deja existente în memorie. Problema este de a stabili gradul de importanță al cunoștințelor existente în raport cu cele nou dobândite.

2.6. Modificarea arborelui

Modificarea structurii arborelui de căutare, prin inserare sau ștergerea unor vârfuri trebuie realizată astfel încât proprietatea de arbore de căutare să nu se altereze. Cele două operații sunt diferite în privința complexității. Ștergerea este mai dificilă și mult mai diferită de operațiile obișnuite.

Complexitatea funcției de ștergere este tipică pentru structurile de căutare. Aceste structuri tind să devină atât de compacte încât ștergerea fiecărei chei necesită reparații destul de complicate. De aceea se preferă de cele mai multe ori o ștergere leneșă, prin care vârful este doar marcat ca fiind șters, ștergerea fizică realizându-se cu ocazia unor reorganizări periodice.

2.7. Programarea dinamică comparată cu tehnica GREEDY

Atât programarea dinamică, cât și tehnica greedy, pot fi folosite atunci când soluția unei probleme este privită ca rezultatul unei secvențe de decizii. Deoarece principiul optimalității poate fi exploatat de ambele metode, s-ar putea să fim tentați să elaborăm o soluție prin programare dinamică, acolo unde este suficientă o metodă greedy, atunci când este necesară de fapt aplicarea programării dinamice.

Vom considera o problemă clasică de optimizare:

Un hoț pătrunde într-un magazin și fură n obiecte,un obiect i având valoarea vi și greutatea gi cum să-și optimizeze hoțul profitul, dacă poate transporta cu un rucsac cel mult o greutate G? deosebim două cazuri. În primul dintre ele, pentru orice obiect i, se poate lua orice fracțiune din el, iar în al doilea caz un obiect poate fi încărcat numai integral în rucsac. Corespunzător acestor două cazuri, obținem problema continuă a rucsacului. Evident, hoțul va selecta obiectele a.î să maximizeze funcția obiectiv, unde x=(x1,x2,…,xn) verifică condiția.

Soluția problemei rucsacului poate fi privită ca rezultatul unei secvențe de decizii. De exemplu, hoțulve decide pentru început asupra valorii lui x1, apoi asupra lui x2 etc. printr-o secvență optimă de decizii el va încerca să maximizeze funcția obiectiv. Se observă că este valabil principiul optimalității. Ordinea deciziilor poate fi oricare alta.

Problema continuă a rucsacului se poate rezolva prin metode greedy, selectând la fiecare pas, pe cât posibil în întregime, obiectul pentru care vi/gi este maxim. Fără a restrânge generalitatea, vom presupune că:

v1/g1v2/g2…vn/gn

Putem demonstra că prin acest algoritm obținem soluția optimă și că aceasta este de forma x*=(1,…,1,xk*,0,…,0), k fiind un indice, 1kn, astfel încât 0xk1. Algoritmul greedy găsește secvența optimă de decizii, luând la fiecare pas câte o decizie care este optimă local. Algoritmul este corect, deoarece nici o decizie din secvență nu este eronată. Dacă nu considerăm timpul necesar sortării inițiale a obiectelor, timpul este în ordinul lui n.

Se observă imediat că tehnica greedy nu conduce în general la rezultatul dorit. De exemplu, pentru g=(1,2,3), v=(6,10,12), G=5, algoritmul greedy furnizează soluția(1,1,0), în timp ce soluția optimă este (0,1,1). De aici vedem că tehnica greedy nu poate fi aplicată, deoarece generează o decizie (x1=1) care este optimă local, nu și global. Cu alte cuvinte, la primul pas, nu avem suficientă informație locală pentru a decide asupra valorii lui x1.

Problema se poate rezolva printr-un algoritm de programare dinamică, în această situație exploatându-se complet principiul optimalității.

Diferența esențială dintre tehnica greedy și programarea dinamică constă în faptul că metoda greedy generează o singură secvență de decizii, exploatând incomplet principiul optimalității. În programarea dinamică se generează mai multe subsecvențe de decizii. O altă caracteristică importantă a programării dinamice este că se memorează subsecvențele optime, evitându-se astfel recalcularea lor.

Capitolul III

ALGORITMI DIVIDE ET IMPERA

TEHNICA DIVIDE ET IMPERA

Divide et impera este o tehnică de elaborare a algoritmilor care constă în:

• Descompunerea cazului ce trebuie rezolvat intr-un număr de subcazuri mai mici ale aceleiași probleme.

• Rezolvarea succesivă și independenta a fiecăruia din aceste subcazuri.

• Recompunerea subsoluțiilor astfel obținute pentru a găsi soluția cazului inițial.

Să presupunem că avem un algoritm A cu timp pătratic. Fie c o constantă, astfel încât timpul pentru a rezolva un caz de mărime n este tA(n) = cn2. Să presupunem că este posibil să rezolvam un astfel de caz prin descompunerea în trei subcazuri, fiecare de mărime .n/2.. Fie d o constantă, astfel încât timpul necesar pentru descompunere și recompunere este t(n) = dn. Folosind vechiul algoritm și ideea de descompunere-recompunere a subcazurilor, obtinem un nou algoritm B, pentru care:

Termenul 3/4cn2 domină pe ceilalți când n este suficient de mare, ceea ce înseamnă ca algoritmul B este în esență cu 25% mai rapid decât algoritmul A. Nu am reușit însă să schimbăm ordinul timpului, care rămâne pătratic. Putem să continuăm în mod recursiv acest procedeu, împărțind subcazurile în subsubcazuri etc. Pentru subcazurile care nu sunt mai mari decât un anumit prag n0, vom folosi tot algoritmul A. Obținem astfel algoritmul C, cu timpul.

Iată o descriere generală a metodei divide et impera:

function divimp(x)

{returnează o soluție pentru cazul x}

if x este suficient de mic then return adhoc(x)

{descompune x în subcazurile x1, x2, …, xk}

for i . 1 to k do yi . divimp(xi)

{recompune y1, y2, …, yk în scopul obținerii soluției y pentru x}

return y

unde adhoc este subalgoritmul de bază folosit pentru rezolvarea micilor subcazuri ale problemei în cauza (in exemplul nostru, acest subalgoritm este A).

Un algoritm divide et impera trebuie să evite descompunerea recursivă a subcazurilor “suficient de mici”, deoarece, pentru acestea, este mai eficienta aplicarea directa a subalgoritmului de baza. Ce înseamnă însă “suficient de mic”?

In exemplul precedent, cu toate ca valoarea lui n0 nu influentează ordinul timpului, este influențată însă constanta multiplicativa a lui , ceea ce poate avea un rol considerabil în eficienta algoritmului. Pentru un algoritm divide et impera oarecare, chiar dacă ordinul timpului nu poate fi îmbunătățit, se dorește optimizarea acestui prag în sensul obținerii unui algoritm cât mai eficient. Nu există o metodă teoretică generală pentru aceasta, pragul optim depinzând nu numai de algoritmul în cauză, dar și de particularitatea implementării. Considerând o implementare dată, pragul optim poate fi determinat empiric, prin măsurarea timpului de execuție pentru diferite valori ale lui n0 și cazuri de mărimi diferite.

În general, se recomandă o metodă hibridă care constă în:

determinarea teoretică a formei ecuațiilor recurente;

ii) găsirea empirică a valorilor constantelor folosite de aceste ecuații, în funcție de implementare.

Revenind la exemplul nostru, pragul optim poate fi găsit rezolvând ecuația:

Empiric, găsim n0 67, adică valoarea pentru care nu mai are important dacă aplicăm algoritmul A în mod direct, sau dacă continuam descompunerea. Cu alte cuvinte, atâta timp cât subcazurile sunt mai mari decât n0, este bine să continuăm descompunerea. Dacă continuăm însă descompunerea pentru subcazurile mai mici decât n0, eficienta algoritmului scade.

Observăm ca metoda divide et impera este prin definiție recursivă. Uneori este posibil să eliminam recursivitatea printr-un ciclu iterativ. Implementata pe o mașina convenționala, versiunea iterativa poate fi ceva mai rapida (în limitele unei constante multiplicative). Un alt avantaj al versiunii iterative ar fi faptul că economisește spațiul de memorie. Versiunea recursivă folosește o stiva necesară memorării apelurilor recursive. Pentru un caz de mărime n, numărul apelurilor recursive este de multe ori în .(log n), uneori chiar în .(n).

3.1. Căutarea binară

Căutarea binară este cea mai simplă aplicație a metodei divide et impera, fiind cunoscută încă înainte de apariția calculatoarelor. În esența, este algoritmul după care se caută un cuvânt intr-un dicționar, sau un nume în cartea de telefon.

Fie T[1 .. n] un tablou ordonat crescător și x un element oarecare. Problema constă în a-l găsi pe x în T, iar dacă nu se află acolo în a găsi poziția unde poate fi inserat. Căutăm deci indicele i astfel încât 1 = i = n și T[i] = x < T[i+1], cu convenția T[0] = -8, T[n+1] = +8. Cea mai evidentă metodă este căutarea secvențială:

function sequential(T[1 .. n], x)

{caută secvențial pe x în tabloul T }

for i . 1 to n do

if T[i] > x then return i-1

return n

Algoritmul necesită un timp în Θ(1+r), unde r este indicele returnat; aceasta inseamnă Θ (1) pentru cazul cel mai favorabil și Θ (n) pentru cazul cel mai nefavorabil. Dacă presupunem că elementele lui T sunt distincte, ca x este un element al lui T și că se afla cu probabilitate egală în oricare poziție din T, atunci bucla for se execută în medie de (n2+3n-2)/2n ori. Timpul este deci în Θ (n) și pentru cazul mediu.

Pentru a mări viteza de căutare, metoda divide et impera sugerează sa-l căutam pe x fie în prima jumătate a lui T, fie în cea de-a doua. Comparându-l pe x cu elementul din mijlocul tabloului, putem decide în care dintre jumătăți să căutam.

Repetând recursiv procedeul, obținem următorul algoritm de căutare binară:

function binsearch(T[1 .. n], x)

{căuta binar pe x în tabloul T}

if n = 0 or x < T[1] then return 0

return binrec(T[1 .. n], x)

function binrec(T[i .. j], x)

{căuta binar pe x în subtabloul T[i .. j]; aceasta procedura

este apelata doar când T[i] = x < T[ j+1] și i = j}

if i = j then return i

k ← (i+j+1) div 2

if x < T[k] then return binrec(T[i .. k-1], x)

else return binrec(T[k .. j], x)

Algoritmul binsearch necesită un timp în Θ(log n), indiferent de poziția lui x în T (demonstrați acest lucru, revăzând. Procedura binrec execută doar un singur apel recursiv, în funcție de rezultatul testului “x < T[k]”. Din această cauză, căutarea binară este, mai curând, un exemplu de simplificare, decât de aplicare a tehnicii divide et impera.

Iată și versiunea iterativă a acestui algoritm:

function iterbin1(T[1 .. n], x)

{căutare binara iterativa}

if n = 0 or x < T[1] then return 0

i ←1; j ← n

while i < j do

{T[i] = x < T[ j+1]}

k ← (i+j+1) div 2

if x < T[k] then j ← k-1

else i ← k

return i

Acest algoritm de căutare binară pare ineficient în următoarea situație: dacă la un anumit pas avem x = T[k], se continuă totuși căutarea. Următorul algoritm evita acest inconvenient, oprindu-se imediat ce găsește elementul căutat.

function iterbin2(T[1 .. n], x)

{varianta a căutării binare iterative}

if n = 0 or x < T[1] then return 0

i ← 1; j ← n

while i < j do

{T[i] = x < T[ j+1]}

k . (i+j) div 2

case x < T[k]: j ← k-1

x = T[k+1]: i ← k+1

otherwise: i, j← k

return i

Timpul pentru iterbin1 este în È(log n). Algoritmul iterbin2 necesită un timp care depinde de poziția lui x în T, fiind în È(1), È(log n), È(log n) pentru cazurile cel mai favorabil, mediu și respectiv, cel mai nefavorabil.

Care din acești doi algoritmi este oare mai eficient? Pentru cazul cel mai favorabil, iterbin2 este, evident, mai bun. Pentru cazul cel mai nefavorabil, ordinul timpului este același, numărul de executări ale buclei while este același, dar durata unei bucle while pentru iterbin2 este ceva mai mare; deci iterbin1 este preferabil, având constanta multiplicativă mai mică. Pentru cazul mediu, compararea celor doi algoritmi este mai dificilă: ordinul timpului este același, o bucla while în iterbin1 durează în medie mai puțin decât în iterbin2, în schimb iterbin1 execută în medie mai multe bucle while decât iterbin2.

3.2. Mergesort (sortarea prin interclasare)

Fie T[1 .. n] un tablou pe care dorim să-l sortăm crescător. Prin tehnica divide et impera putem proceda astfel: separăm tabloul T în două părți de mărimi cât mai apropiate, sortăm aceste părți prin apeluri recursive, apoi interclasăm soluțiile pentru fiecare parte, fiind atenți să păstrăm ordonarea crescătoare a elementelor.

Obținem următorul algoritm:

procedure mergesort(T[1 .. n])

{sortează în ordine crescătoare tabloul T}

if n este mic

then insert(T)

else arrays U[1 .. n div 2], V[1 .. (n+1) div 2]

U . T[1 .. n div 2]

V . T[1 + (n div 2) .. n]

mergesort(U); mergesort(V)

merge(T, U, V)

unde insert(T) este algoritmul de sortare prin inserție cunoscut, iar merge(T, U, V) interclasează intr-un singur tablou sortat T cele doua tablouri deja sortate U și V.

Algoritmul mergesort ilustrează perfect principiul divide et impera: pentru n având o valoare mică, nu este rentabil să apelăm recursiv procedura mergesort, ci este mai bine să efectuam sortarea prin inserție. Algoritmul insert lucrează foarte bine pentru n = 16, cu toate ca, pentru o valoare mai mare a lui n, devine neconvenabil. Evident, se poate concepe un algoritm mai puțin eficient, care să meargă pâna la descompunerea totala; în acest caz, mărimea stivei este în Θ(log n).

Spațiul de memorie necesar pentru tablourile auxiliare U și V este în Θ (n). Mai precis, pentru a sorta un tablou de n = elemente, presupunând ca descompunerea este totală, acest spațiu este de elemente.

Putem considera ca algoritmul merge(T, U, V) are timpul de execuție în Θ(#U + #V), indiferent de ordonarea elementelor din U și V.

Separarea lui T în U și V necesită tot un timp în Θ(#U + #V). Timpul necesar algoritmului mergesort pentru a sorta orice tablou de n elemente este atunci

Această ecuație ne permite să conchidem ca timpul pentru mergesort este în Θ(n log n).

Pentru cazul mediu și pentru cazul cel mai nefavorabil insert și select necesită un timp în Θ(n2), iar heapsort un timp în Θ (n log n).

În algoritmul mergesort, suma mărimilor subcazurilor este egală cu mărimea cazului inițial. Această proprietate nu este în mod necesar valabilă pentru algoritmii divide et impera. Oare de ce este însă important ca subcazurile să fie de mărimi cât mai egale? Dacă în mergesort îl separam pe T în tabloul U având n-1 elemente și tabloul V având un singur element, se obține un nou timp de execuție, care este în Θ(n2). Deducem de aici că este esențial ca subcazurile să fie de mărimi cât mai apropiate (sau, altfel spus, subcazurile să fie cât mai echilibrate).

3.3. Mergesort în clasele tablou<T> și lista<E>

O soluție neinspirată:

Deși eficient în privința timpului, algoritmul de sortare prin interclasare are un handicap important în ceea ce privește memoria necesară. Într-adevăr, orice tablou de n elemente este sortat intr-un timp în È(n log n), dar utilizând un spațiu suplimentar de memorie* de 2n elemente. Pentru a reduce consumul de memorie, în implementarea acestui algoritm nu vom utiliza variabilele intermediare U și V de tip tablou<T>, ci o unică zonă de auxiliara de n elemente.

Convenim să implementam procedura mergesort ca membru private al clasei parametrice tablou<T>. Invocarea acestei proceduri se va realiză prin funcția membră:

template <class T>

tablou<T>& tablou<T>::sort( ) {

T *aux = new T[ d ]; // alocarea zonei de interclasare

mergesort( 0, d, aux ); // și sortarea propriu-zisa

delete [ ] aux; // eliberarea zonei alocate

return *this;

}

Spațiul suplimentar utilizat de algoritmul mergesort poate fi independent de numărul elementelor tabloului de sortat. Detaliile de implementare a unei astfel de strategii se găsesc în D. E. Knuth, “Tratat de programarea calculatoarelor. Sortare și cautare”,

Mergesort în clasele tablou<T> și lista<E>. Am preferat această manieră de “încapsulare” din următoarele doua motive:

• Alocarea și eliberarea spațiului suplimentar necesar interclasării se face o

singură dată, înainte și după terminarea sortării. Funcția mergesort(), ca funcție recursivă, nu poate avea controlul asupra alocării și eliberării acestei zone.

• Algoritmul mergesort are trei parametrii care pot fi ignorați la apelarea funcției de sortare. Aceștia sunt: adresa zonei suplimentare de memorie și cei doi indici prin care se încadrează elementele de sortat din tablou.

Implementarea interclasării se simplifică mult prin utilizarea unor valori “santinela” în tablourile de interclasat.

Functia mergesort():

template <class T>

void tablou<T>::mergesort( int st, int dr, T *x ) {

if ( dr – st > 1 ) {

// mijlocul intervalului

int m = ( st + dr ) / 2;

// sortarea celor doua parti

mergesort( st, m );

mergesort( m, dr );

// pregatirea zonei x pentru interclasare

int k = st;

for ( int i = st; i < m; ) x[ i++ ] = a[ k++ ];

for ( int j = dr; j > m; ) x[ –j ] = a[ k++ ];

// interclasarea celor doua parti din x în zona a

i = st; j = dr – 1;

for ( k = st; k < dr; k++ )

a[ k ] = x[ j ] > x[ i ]? x[ i++ ]: x[ j– ];

}

}

Se adaptează surprinzător de simplu la utilizarea “santinelelor”. Nu avem decât să transferam în zona auxiliara cele doua jumatați deja sortate, astfel încât valorile maxime să fie la mijlocul acestei zone. Altfel spus, prima jumătate va fi transferată crescător, iar cea de-a doua descrescător, în continuarea primei jumătăți. Începând interclasarea cu valorile minime, valoarea maxima din fiecare jumătate este santinela pentru cealaltă jumătate.

Sortarea prin interclasare prezintă un avantaj foarte important față de alte metode de sortare deoarece elementele de sortat sunt parcurse secvențial, element după element. Din acest motiv, metoda este potrivită pentru sortarea fișierelor sau listelor. De exemplu, procedura de sortare prin interclasare a obiectelor de tip:

lista<E>

template <class E>

lista<E>& lista<E>::sort() {

if ( head )

head = mergesort( head );

return *this;

}

Rearanjează nodurile în ordinea crescătoare a cheilor, fără a folosi noduri sau liste temporare. Prețul în spațiu suplimentar de memorie este totuși plătit, deoarece orice lista înlănțuită necesită memorie în ordinul numărului de elemente pentru realizarea înlănțuirii.

Conform algoritmului mergesort, lista se împarte în doua părți egale, iar după sortarea fiecăreia se realizează interclasarea. Împărțirea listei în cele doua părți egale nu se poate realiza direct, ca în cazul tablourilor, ci în mai mulți pași.

Astfel, vom parcurge lista pana la sfârșit, pentru a putea determina elementul din mijloc. Apoi stabilim care este elementul din mijloc și, în final, izolăm cele două părți, fiecare în cate o listă în funcția mergesort():

template <class E>

nod<E>* mergesort ( nod<E> *c ) {

if ( c && c->next ) {

// sunt cel puțin două noduri în lista

nod<E> *a = c, *b;

for ( b = c->next; b; a = a->next )

if ( b->next ) b = b->next->next;

else break;

b = a->next; a->next = 0;

return merge( mergesort( c ), mergesort( b ) );

}

else

// lista contine cel mult un nod

return c;

}

Împărțirea listei se realizează printr-o singură parcurgere, dar cu două adrese de noduri, a și b. Principiul folosit este următorul: dacă b înaintează în parcurgerea listei de doua ori mai repede decât a, atunci când b a ajuns la ultimul nod, a este la nodul de mijloc al listei.

Spre deosebire de algoritmul mergesort, sortarea listelor prin interclasare nu deplasează valorile de sortat. Funcția merge() interclasează listele de la adresele a și b prin simpla modificare a legaturilor nodurilor.

template <class E>

nod<E>* merge( nod<E> *a, nod<E> *b ) {

nod<E> *head; // primul nod al listei interclasate

if ( a && b )

// ambele liste sunt nevide;

// stabilim primul nod din lista interclasată

if ( a->val > b->val ) { head = b; b = b->next; }

else { head = a; a = a->next; }

else

// cel puțin una din liste este vida;

// nu avem ce interclasa

return a? a: b;

// interclasarea propriu-zisa

nod<E> *c = head; // ultimul nod din lista interclasata

while ( a && b )

if ( a->val > b->val ) { c->next = b; c = b; b = b->next; }

else { c->next = a; c = a; a = a->next; }

// cel putin una din liste s-a epuizat

c->next = a? a: b;

// se returneaza primul nod al listei interclasate

return head;

}

Funcția de sortare mergesort(), împreună cu cea de interclasare merge(), lucrează exclusiv asupra nodurilor. Deoarece aceste funcții sunt invocate doar la nivel de listă, ele nu sunt membre în clasa nod<E>, ci doar friend față de aceasta clasă. Incapsularea lor este realizată prin mecanismul standard al limbajului C++.

Deși aceste funcții aparțin domeniului global, ele nu pot fi invocate de aici datorită obiectelor de tip nod<E>, obiecte accesibile doar din domeniul clasei lista<E>. Această manieră de încapsulare nu este complet sigură, deoarece, chiar dacă nu putem manipula obiecte de tip nod<E>, totuși putem lucra cu adrese de nod<E>. De exemplu, funcția

void f( ) {

mergesort( (nod<int> *)0 );

}

“trece” de compilare, dar efectele ei la rularea programului sunt imprevizibile.

Prezentarea funcțiilor de sortare în tablou<T> și lista<E> (de fapt și în nod<E>) impune completarea claselor T și E cu operatorul de comparare >. Orice tentativă de a defini (atenție, de a defini și nu de a sorta) obiecte de tip tablou<T> sau lista<E> este semnalata ca eroare de compilare, dacă tipurile T sau E nu au definit acest operator. Situația apare, deoarece generarea unei clase parametrice implica generarea tuturor funcțiilor membre. Deci, chiar dacă nu invocam funcția de sortare pentru tipul tablou<T>, ea este totuși generată, iar generarea ei necesită operatorul de comparare al tipului T.

De exemplu, pentru a putea lucra cu liste de muchii, lista<muchie>, sau tablouri de tablouri, tablou< tablou<T> >, vom implementa operatorii de comparare pentru clasa muchie și clasa tablou<T>. Muchiile sunt comparate în funcție de costul lor, dar cum vom proceda cu tablourile? O soluție este de a lucra conform ordinii lexicografice, adică de a aplica aceeași metodă care se aplică la ordonarea numelor în cartea de telefoane, sau în catalogul școlar:

template <class T>

operator > ( const tablou<T>& a, const tablou<T>& b ) {

// minimul elementelor

int as = a.size( ), bs = b.size( );

int n = as < bs? as: bs;

// comparam pana la prima diferența

for ( int i = 0; i < n; i++ )

if ( a[ i ] != b[ i ] ) return a[ i ] > b[ i ];

// primele n elemente sunt identice

return as > bs;

}

Atunci când operatorii de comparare nu prezintă interes, sau nu pot fi definiți, îi putem implementa ca funcții inefective. Astfel, dacă avem nevoie de un tablou de liste sau de o listă de liste asupra cărora nu vom aplica operații de sortare, va trebui să definim operatorii inefectivi:

template <class E>

operator >( const lista<E>&, const lista<E>& ) {

return 1;

}

În concluzie, extinderea claselor tablou<T> și lista<E> cu funcțiile de sortare nu menține compatibilitatea acestor clase fata de aplicațiile dezvoltate pana acum.

Oricând este posibil ca recompilarea unei aplicații în care se utilizează, de exemplu, tablouri sau liste cu elemente de tip XA, XB etc, să devină un coșmar, deoarece, chiar dacă nu are nici un sens, trebuie să completam fiecare clasa XA, XB etc, cu operatorul de comparare >.

Programarea orientată pe obiect se folosește tocmai pentru a evita astfel de situații, nu pentru a le genera.

3.4. Tablouri sortabile și liste sortabile

Sortarea este o operație care completează facilitățile clasei tablou<T>, fără a exclude utilizarea acestei clase pentru tablouri nesortabile. Din acest motiv, funcțiile de sortare nu pot fi funcții membre în clasa tablou<T>.

O soluție posibila de încapsulare a sortării este de a construi, prin derivare publică din tablou<T>, subtipul tablouSortabil<T>, care să conțină tot ceea ce este necesar pentru sortare. Mecanismului standard de conversie, de la tipul derivat public la tipul de baza, permite ca un tablou Sortabil<T> să poata fi folosit oricând în locul unui tablou<T>.

În continuare, vom prezenta o altă varianta de încapsulare, mai puțin clasică, prin care atributul “sortabil” este considerat doar în momentul invocării funcției de sortare, nu apriori, prin definirea obiectului ca “sortabil”.

Sortarea se invoca prin funcția:

template <class T>

tablou<T>& mergesort( tablou<T>& t ) {

( tmsort<T> )t;

return t;

}

care constă în conversia tabloului t la tipul tmsort<T>. Clasa tmsort<T> încapsulează absolut toate detaliile sortării. Fiind vorba de sortarea prin interclasare.

template <class T>

class tmsort {

public:

tmsort( tablou<T>& );

private:

T *a; // adresa zonei de sortat

T *x; // zona auxiliara de interclasare

void mergesort( int, int );

};

Sortarea, de fapt transformarea tabloului t intr-un tablou sortat, este realizată prin constructorul

template <class T>

tmsort<T>::tmsort( tablou<T>& t ): a( t.a ) {

x = new T[ t.size( ) ]; // alocarea zonei de interclasare

mergesort( 0, t.size( ) ); // sortarea

delete [ ] x; // eliberarea zonei alocate

}

După cum se observă, în acest constructor se folosește membrul privat T *a (adresa zonei alocate elementelor tabloului) din clasa tablou<T>. Iată de ce, în clasa tablou<T> trebuie făcută o modificare (singura dealtfel): clasa tmsort<T> trebuie declarata friend. Functia mergesort() este practic neschimbată:

template <class T>

void tmsort<T>::mergesort( int st, int dr ) {

// …

// corpul funcției void mergesort( int, int, T* )

}

Pentru sortarea listelor se procedează analog, transformând implementarea în cea de mai jos.

template <class E>

lista<E>& mergesort( lista<E>& l ) {

( lmsort<E> )l;

return l;

}

template <class E>

class lmsort {

public:

lmsort( lista<E>& );

private:

nod<E>* mergesort( nod<E>* );

nod<E>* merge( nod<E>*, nod<E>* );

};

template <class E>

lmsort<E>::lmsort( lista<E>& l ) {

if ( l.head )

l.head = mergesort( l.head );

}

template <class E>

nod<E>* lmsort<E>::mergesort ( nod<E> *c ) {

// …

// corpul funcției nod<E>* mergesort( nod<E>* )

// …

}

template <class E>

nod<E>* lmsort<E>::merge( nod<E> *a, nod<E> *b ) {

// …

// corpul funcției nod<E>* merge( nod<E>*, nod<E>* )

// …

}

Clasa lmsort<E> folosește membrii privați atât din clasa lista<E>, cât și din clasa nod<E>, deci trebuie declarată friend în ambele.

3.5. Quicksort (sortarea rapidă)

Algoritmul de sortare quicksort, inventat de Hoare în 1962, se bazează de asemenea pe principiul divide et impera. Spre deosebire de mergesort, partea nerecursivă a algoritmului este dedicată construirii subcazurilor și nu combinării soluțiilor lor.

Ca prim pas, algoritmul alege un element pivot din tabloul care trebuie sortat.

Tabloul este apoi partiționat în doua subtablouri, alcătuite de-o parte și de alta a acestui pivot în următorul mod: elementele mai mari decât pivotul sunt mutate în dreapta pivotului, iar celelalte elemente sunt mutate în stânga pivotului. Acest mod de partiționare este numit pivotare. în continuare, cele doua subtablouri sunt sortate în mod independent prin apeluri recursive ale algoritmului. Rezultatul este tabloul complet sortat; nu mai este necesară nici o interclasare. Pentru a echilibra mărimea celor doua subtablouri care se obțin la fiecare partiționare, ar fi ideal să alegem ca pivot elementul median. Intuitiv, mediana unui tablou T este elementul m din T, astfel încât numărul elementelor din T mai mici decât m este egal cu numărul celor mai mari decât m.

Din păcate, găsirea medianei necesită mai mult timp decât merita. De aceea, putem pur și simplu să folosim ca pivot primul element al tabloului. Iată cum arata acest algoritm:

procedure quicksort(T[i .. j])

{sortează în ordine crescătoare tabloul T[i .. j]}

if j-i este mic

then insert(T[i .. j])

else pivot(T[i .. j], l)

{după pivotare, avem:

i = k < l . T[k] = T[l]

l < k = j . T[k] > T[l]}

quicksort(T[i .. l-1])

quicksort(T[l+1 .. j])

Mai rămâne să concepem un algoritm de pivotare cu timp liniar, care să parcurgă tabloul T o singura data. Putem folosi urmatoarea tehnică de pivotare: parcurgem tabloul T o singură dată, pornind insă din ambele capete. Încercați să întelegeți cum funcționează acest algoritm de pivotare, în care p = T[i] este elementul pivot:

procedure pivot(T[i .. j], l)

{permuta elementele din T[i .. j] astfel încât, în final, elementele lui T[i .. l-1] sunt = p, T[l] = p, iar elementele lui T[l+1 .. j] sunt > p}

p ← T[i]

k ← i; l ← j+1

repeat k ← k+1 until T[k] > p or k = j

repeat l ← l-1 until T[l] = p

while k < l do

interschimba T[k] și T[l]

repeat k← k+1 until T[k] > p

repeat l ← l-1 until T[l] = p

{pivotul este mutat în poziția lui finală}

interschimba T[i] și T[l]

Intuitiv, ne dăm seama că algoritmul quicksort este ineficient, dacă se întâmplă în mod sistematic ca subcazurile T[i .. l-1] și T[l+1 .. j] să fie puternic neechilibrate.

Ne propunem în continuare să analizam această situație în mod riguros. Operația de pivotare necesita un timp în Θ(n). Fie constanta n0, astfel încât, in cazul cel mai nefavorabil, timpul pentru a sorta n > n0 elemente prin quicksort să fie:

t(n) є Θ(n) + max{t(i)+t(n-i-1) | 0 ≤ i ≤ n-1}

Folosim metoda inducției constructive pentru a demonstra independent ca și .

Putem considera că există o constantă reală pozitivă c, astfel încât pentru 0 ≤ i ≤ n0. Prin ipoteza inducției specificate parțial, presupunem că pentru orice 0 ≤ i < n. Demonstrăm că proprietatea este adevarată și pentru n. Avem:

t(n) = dn + c + c max{i2+(n-i-1)2 | 0 = i = n-1}

d fiind o altă constantă. Expresia i2+(n-i-1)2 își atinge maximul atunci când i este 0 sau n-1. Deci,

Dacă luăm c = 2d, obținem . Am arătat că, dacă c este suficient de mare, atunci pentru orice n ≥ 0, adică, t є O(). Analog se arată ca t єΩ().

Am arătat, totodată, care este cel mai nefavorabil caz: atunci când, la fiecare nivel de recursivitate, procedura pivot este apelată o singură dată. Dacă elementele lui T sunt distincte, cazul cel mai nefavorabil este atunci când inițial tabloul este ordonat crescător sau descrescător, fiecare partiționare fiind total neechilibrată. Pentru acest cel mai nefavorabil caz, am arătat că algoritmul quicksort necesită un timp în ().

Ce se întâmplă însă în cazul mediu? Intuim faptul că, în acest caz, subcazurile sunt suficient de echilibrate. Pentru a demonstra aceasta proprietate, vom arăta că timpul necesar este în ordinul lui n log n, ca și în cazul cel mai favorabil.

Presupunem că avem de sortat n elemente distincte și că inițial ele pot să apară cu probabilitate egala în oricare din cele n! permutări posibile. Operația de pivotare necesită un timp liniar. Apelarea procedurii pivot poate poziționa primul element cu probabilitatea 1/n în oricare din cele n poziții. Timpul mediu pentru quicksort verifica relația

Mai precis, fie n0 și d două constante astfel încât pentru orice n > n0, avem

Prin analogie cu mergesort, este rezonabil să presupunem ca t . O(n log n) și să aplicăm tehnica inducției constructive, căutând o constantă c, astfel încât

t(n) ≤ cn lg n.

Deoarece i lg i este o funcție nedescrescatoare, avem

pentru n0 = 1.

Ținând cont de aceasta margine superioara pentru

puteți demonstra prin inducție matematică ca t(n) ≤ cn lg n pentru orice

n >no ≥ 1, unde

Rezultă că timpul mediu pentru quicksort este în O(n log n). Pe lângă ordinul timpului, un rol foarte important îl are constanta multiplicativă. Practic, constanta multiplicativa pentru quicksort este mai mică decât pentru heapsort sau mergesort. Dacă pentru cazul cel mai nefavorabil se acceptă o execuție ceva mai lenta, atunci, dintre tehnicile de sortare prezentate, quicksort este algoritmul preferabil.

Pentru a minimiza șansa unui timp de execuție în .(n2), putem alege ca pivot mediana șirului T[i], T[(i+j) div 2], T[ j]. Prețul plătit pentru această modificare este o ușoara creștere a constantei multiplicative.

3.6. Selecția unui element dintr-un tablou

Putem găsi cu ușurință elementul maxim sau minim al unui tablou T. Cum putem determina insa eficient mediana lui T ? Pentru început, să definim formal mediană unui tablou.

Un element m al tabloului T[1 .. n] este mediana lui T, dacă și numai dacă sunt verificate următoarele doua relatii:

#{i . {1, …, n} | T[i] < m} < .n/2.

#{i . {1, …, n} | T[i] ≤ m} ≥ n/2.

Această definiție ține cont de faptul ca n poate fi par sau impar și ca elementele din T pot să nu fie distincte. Prima relație este mai ușor de înțeles dacă observam că

#{i є {1, …, n} | T[i] < m} = n – #{i . {1, …, n} | T[i] ≥ m}

Condiția

#{i є{1, …, n} | T[i] < m} < .n/2.

este deci echivalentă cu condiția

#{i є {1, …, n} | T[i] = m} > n – .n/2. = .n/2.

Algoritmul “naiv” pentru determinarea medianei lui T constă în a sorta crescător tabloul și a extrage apoi elementul din poziția. Folosind mergesort, de exemplu, acest algoritm necesită un timp în Θ(n log n). Putem găsi o metodă mai eficienta? Pentru a răspunde la aceasta întrebare, vom considera o problema mai generală.

Fie T un tablou de n elemente și fie k un întreg, 1 = k = n. Problema selectiei constă în găsirea celui de-al k-lea cel mai mic element al lui T, adică a elementul m pentru care avem:

#{i . {1, …, n} | T[i] < m} < k

#{i . {1, …, n} | T[i] ≤ m} ≥ k

Cu alte cuvinte, este al k-lea element în T, dacă tabloul este sortat în ordine crescătoare. De exemplu, mediana lui T este al -lea cel mai mic element al lui T. Deoarece . = = (n+1) div 2, mediana lui T este totodată al ((n+1) div 2)-lea cel mai mic element al lui T.

Următorul algoritm, încă nu pe deplin specificat, rezolva problema selecției într-un mod similar cu quicksort dar și cu binsearch.

function selection(T[1 .. n], k)

{găsește al k-lea cel mai mic element al lui T;

se presupune ca 1 ≤ k ≤ n}

if n este mic then sortează T

return T[k]

p . un element pivot din T[1 .. n]

u . #{i . {1, …, n} | T[i] < p}

v . #{i . {1, …, n} | T[i] ≤ p}

if u = k then

array U[1 .. u]

U elementele din T mai mici decât p

{cel de-al k-lea cel mai mic element al lui T este

și cel de-al k-lea cel mai mic element al lui U}

return selection (U, k)

if v = k then {am găsit!} return p

{situația când u < k și v < k}

array V[1 .. n-v]

V . elementele din T mai mari decât p

{cel de-al k-lea cel mai mic element al lui T este și cel de-al (k-v)-lea cel mai mic element al lui V}

return selection(V, k-v)

Care element din T să fie ales ca pivot? O alegere naturală este mediana lui T, astfel încât U și V să fie de mărimi cât mai apropiate (chiar dacă cel mult unul din aceste subtablouri va fi folosit intr-un apel recursiv). Dacă în algoritmul selection alegerea pivotului se face prin atribuirea p. selection(T, (n+1) div 2) ajungem insă la un cerc vicios.

Să analizam algoritmul de mai sus, presupunând, pentru început, că găsirea medianei este o operație elementara. Din definiția medianei, rezultă că u < și v = . Obținem atunci relația n -v = . Dacă există un apel recursiv, atunci tablourile U și V conțin fiecare cel mult elemente. Restul operațiilor necesită un timp în ordinul lui n. Fie tm(n) timpul necesar acestei metode, în cazul cel mai nefavorabil, pentru a găsi al k-lea cel mai mic element al unui tablou de n elemente. Avem tm(n) є O(n) + max{tm(i) | i = }

Ce facem insă dacă trebuie să ținem cont și de timpul pentru găsirea pivotului?

Putem proceda ca în cazul quicksort-ului și să renunțăm la mediana, alegând ca pivot primul element al tabloului. Algoritmul selection astfel precizat are timpul pentru cazul mediu în ordinul exact al lui n. Pentru cazul cel mai nefavorabil, se obține insă un timp în ordinul lui n2. Putem evita acest caz cel mai nefavorabil cu timp pătratic, fără să sacrificăm comportarea liniară pentru cazul mediu. Ideea este să găsim rapid o aproximare buna pentru mediană. Presupunând n = 5, vom determina pivotul prin atribuirea

p ← pseudomed(T)

unde algoritmul pseudomed este:

function pseudomed(T[1 .. n])

{găsește o aproximare a medianei lui T}

s ← n div 5

array S[1 .. s]

for i ← 1 to s do S[i] ← adhocmed5(T[5i-4 .. 5i])

return selection(S, (s+1) div 2)

Algoritmul adhocmed5 este elaborat special pentru a găsi mediana a exact cinci elemente. să notăm ca adhocmed5 necesită un timp în O(1).

Fie m aproximarea medianei tabloului T, găsită prin algoritmul pseudomed.

Deoarece m este mediana tabloului S, avem

#{i ← {1, …, s} | S[i] ≤m}

Fiecare element din S este mediana a cinci elemente din T. în consecință, pentru fiecare i, astfel încât S[i] = m, exista i1, i2, i3 intre 5i-4 și 5i, astfel ca

În concluzie, m aproximează mediana lui T, fiind al k-lea cel mai mic element al lui T, unde k este aproximativ intre 3n/10 și 7n/10. O interpretare grafică ne va ajuta să înțelegem mai bine aceste relații să ne imaginam elementele lui T dispuse pe cinci linii, cu posibila excepție a cel mult patru elemente.

Presupunem că fiecare din cele .n/5. coloane este ordonată nedescrescător, de sus in jos. De asemenea, presupunem ca linia din mijloc (corespunzătoare tabloului S din algoritm) este ordonata nedescrescător, de la stânga la dreapta. Elementul subliniat corespunde atunci medianei lui S, deci lui m. Elementele din interiorul dreptunghiului sunt mai mici sau egale cu m. Dreptunghiul conține aproximativ 3/5 din jumătatea elementelor lui T, deci în jur de 3n/10 elemente.

Presupunând ca folosim “p . pseudomed(T)”, adică pivotul este pseudomediana, fie t(n) timpul necesar algoritmului selection, în cazul cel mai nefavorabil, pentru a găsi al k-lea cel mai mic element al unui tablou de n elemente. Din inegalitatile

#{i . {1, …, n} | T[i] ≤ m} ≥ (3n-12)/10

#{i . {1, …, n} | T[i] < m} < (7n+27)/10

rezultă că, pentru n suficient de mare, tablourile U și V au cel mult 3n/4 elemente fiecare.

Deducem relația

Vom arăta că t єΘ(n). să considerăm funcția f : N . R*, definită prin recurență

pentru n є . Prin inducție constructivă, putem demonstra că exista constantă reală pozitivă a astfel încât f(n) = an pentru orice n . N. Deci, fєO(n). Pe de alta parte, există constanta reală pozitivă c, astfel încât t(n) ≤ cf(n) pentru orice n є N. Este adevărată atunci și relația t є O(n). Deoarece orice algoritm care rezolva problema selecției are timpul de execuție în Ω(n), rezulta t єΩ.(n), deci, tєΘ(n).

Generalizând, vom încerca să aproximăm mediana nu numai prin împărțire la cinci, ci prin împărțire la un întreg q oarecare, 1 < q ≤ n. Din nou, pentru n suficient de mare, tablourile U și V au cel mult 3n/4 elemente fiecare. Relatia (*) devine

Dacă 1/q + 3/4 < 1, adică dacă numărul de elemente asupra cărora operează cele doua apeluri recursive din (**) este în scădere, deducem, intr-un mod similar cu situația când q = 5, ca timpul este tot liniar. Deoarece pentru orice q = 5 inegalitatea precedentă este verificată, rămâne deschisă problema alegerii unui q pentru care să obținem o constanta multiplicativa cât mai mica. În particular, putem determina mediana unui tablou în timp liniar, atât pentru cazul mediu cât și pentru cazul cel mai nefavorabil. Față de algoritmul “naiv”, al cărui timp este în ordinul lui n log n, îmbunătățirea este substanțială.

3.7. O problema de criptologie

Alice și Bob doresc să comunice anumite secrete prin telefon. Convorbirea telefonica poate fi insă ascultată și de Eva. în prealabil, Alice și Bob nu au stabilit nici un protocol de codificare și pot face acum acest lucru doar prin telefon. Eva va asculta insă și ea modul de codificare. Problema este cum sa comunice Alice și Bob, astfel încât Eva să nu poata descifra codul, cu toate că va cunoaște și ea protocolul de codificare*.

Pentru început, Alice și Bob convin în mod deschis asupra unui întreg p cu câteva sute de cifre și asupra unui alt întreg g intre 2 și p-1. Securitatea secretului nu este compromisă prin faptul ca Eva afla aceste numere. La pasul doi, Alice și Bob aleg la întâmplare cate un întreg A, respectiv B, mai mici decât p, fără să-și comunice aceste numere. Apoi, Alice calculează a = gA mod p și transmite rezultatul lui Bob; similar, Bob transmite lui Alice valoarea b = gB mod p. în final, Alice calculează x = bA mod p, iar Bob calculează y = aB mod p. Vor ajunge la același rezultat, deoarece x = y = gAB mod p. Aceasta valoare este deci cunoscuta de Alice și Bob, dar rămâne necunoscuta lui Eva. Evident, nici Alice și nici Bob nu pot controla direct care va fi aceasta valoare. Deci ei nu pot folosi acest protocol pentru a schimba in mod direct un anumit mesaj. Valoarea rezultata poate fi însă cheia unui sistem criptografic convențional.

Interceptând convorbirea telefonica, Eva va putea cunoaște în final următoarele numere: p, q, a și b. Pentru a-l deduce pe x, ea trebuie să găsească un întreg A', astfel încât a = gA' mod p și să procedeze apoi ca Alice pentru a-l calcula pe x' = bA' mod p. Se poate arata ca x' = x, deci ca Eva poate calcula astfel corect secretul lui Alice și Bob.

Calcularea lui A' din p, g și a este cunoscută ca problema algoritmului discret și poate fi realizată de următorul algoritm:

function dlog(g, a, p)

A . 0; k . 1

repeat

A . A+1

k . kg

until (a = k mod p) or (A = p)

return A

* O primă soluție a acestei probleme a fost data în 1976 de W. Diffie și M. E. Hellman. Intre timp sau mai propus și alte protocoale. Dacă logaritmul nu exista, functia dlog va returna valoarea p. De exemplu, nu există un întreg A, astfel încât 3 = 2A mod 7. Algoritmul de mai sus este insă extrem de ineficient. Dacă p este un număr prim impar, atunci este nevoie in medie de p/2 repetari ale buclei repeat pentru a ajunge la soluție (presupunând ca aceasta exista). Dacă pentru efectuarea unei bucle este necesară o microsecunda, atunci timpul de execuție al algoritmului poate fi mai mare decât vârsta Pământului! Iar aceasta se întâmplă chiar și pentru un număr zecimal p cu doar 24 de cifre. Cu toate ca există și algoritmi mai rapizi pentru calcularea logaritmilor discreți, nici unul nu este suficient de eficient dacă p este un număr prim cu câteva sute de cifre. Pe de alta parte, nu se cunoaște pana în prezent un alt mod de a-l obține pe x din p, g, a și b, decât prin calcularea logaritmului discret. Desigur, Alice și Bob trebuie să poată calcula rapid exponențierile de forma a = gA mod p, căci altfel ar fi și ei puși în situația Evei. Următorul algoritm pentru calcularea exponențierii nu este cu nimic mai subtil sau eficient decât cel pentru logaritmul discret.

function dexpo1(g, A, p)

a . 1

for i . 1 to A do a . ag

return a mod p

Faptul că x y z mod p = ((x y mod p) z) mod p pentru orice x, y, z și p, ne permite sa evitam memorarea unor numere extrem de mari. Obținem astfel o prima îmbunătățire:

function dexpo2(g, A, p)

a . 1

for i . 1 to A do a . ag mod p

return a

Din fericire pentru Alice și Bob, există un algoritm eficient pentru calcularea exponențierii și care folosește reprezentarea binara a lui A. Să considerăm pentru început următorul exemplu . L-am obținut deci pe prin doar două înmulțiri și patru ridicări la pătrat. Dacă în expresia înlocuim fiecare x cu un 1 și fiecare 1 cu un 0, obținem secvența 11001, adică reprezentarea binara a lui 25. Formula precedentă pentru are această formă, deoarece , etc. Rezultă un algoritm divide et impera în care se testează în mod recursiv dacă exponentul curent este par sau impar.

function dexpo(g, A, p)

if A = 0 then return 1

if A este impar then a . dexpo(g, A-1, p)

return (ag mod p)

else a . dexpo(g, A/2, p)

return (aa mod p)

Fie h(A) numărul de înmulțirii modulo p efectuate atunci când se calculează

dexpo(g, A, p), inclusiv ridicarea la pătrat. Atunci,

Dacă M(p) este limita superioară a timpului necesar înmulțirii modulo p a două numere naturale mai mici decât p, atunci calcularea lui dexpo(g, A, p) necesita un timp în O(M(p) h(A)). Mai mult, se poate demonstra că timpul este în O(M(p) log A), ceea ce este rezonabil. Ca și în cazul căutării binare, algoritmul dexpo este mai curând un exemplu de simplificare decât de tehnica divide et impera.

Vom înțelege mai bine acest algoritm, dacă consideram și o versiune iterativa a lui.

function dexpoiter1(g, A, p)

c . 0; a . 1

{fie A A reprezentarea binara a lui A}

for i . k downto 0 do

c . 2c

a . aa mod p

if Ai = 1 then c . c + 1

a . ag mod p

return a

A k k-1… 0

Fiecare iterație folosește una din identitățile:

în funcție de valoarea lui Ai (dacă este 0, respectiv 1). La sfârșitul pasului i,

valoarea lui c, în reprezentare binara, este A A A k k i -1…. Reprezentrea binară a lui A este parcursă de la stânga spre dreapta, invers ca la algoritmul dexpo. Variabila c a fost introdusă doar pentru a înțelege mai bine cum funcționează algoritmul și putem, desigur, să o eliminam.

Dacă parcurgem reprezentarea binara a lui A de la dreapta spre stânga, obținem un alt algoritm iterativ la fel de interesant.

function dexpoiter2(g, A, p)

n . A; y . g; a . 1

while n > 0 do

if n este impar then a . ay mod p

y . yy mod p

n . n div 2

return a

Pentru a compara acești trei algoritmi, vom considera următorul exemplu.

Algoritmul dexpo îl calculează pe x15 sub forma, cu șapte înmulțiri; algoritmul dexpoiter1 sub forma, cu opt înmulțiri; iar dexpoiter2 sub forma, tot cu opt înmulțiri (ultima din acestea fiind pentru calcularea inutila a lui).

Se poate observa că nici unul din acești algoritmi nu minimizează numărul de înmulțiri efectuate. De exemplu, poate fi obținut prin șase înmulțiri, sub forma ((x2x)2x)2x. Mai mult, poate fi obținut prin doar cinci înmulțiri.

3.8. Înmulțirea matricelor

Pentru matricile A și B de n × n elemente, dorim să obținem matricea produs C = AB. Algoritmul clasic provine direct din definiția înmulțirii a două matrici și necesita n3 înmulțiri și adunări scalare. Timpul necesar pentru calcularea matricii C este deci în Θ(). Problema pe care ne-o punem este să găsim un algoritm de înmulțire matricială al cărui timp să fie într-un ordin mai mic decât . Pe de alta parte, este clar că este o limită inferioară pentru orice algoritm de înmulțire matricială, deoarece trebuie în mod necesar să parcurgem cele elemente ale lui C.

Strategia divide et impera sugerează un alt mod de calcul a matricii C. Vom presupune în continuare ca n este o putere a lui doi. Partiționăm pe A și B în câte patru submatrici de n/2 × n/2 elemente fiecare. Matricea produs C se poate calcula conform formulei pentru produsul matricilor de 2 × 2 elemente:

unde

Pentru n = 2, înmulțirile și adunările din relațiile de mai sus sunt scalare; pentru n > 2, aceste operații sunt între matrici de n/2 × n/2 elemente. Operația de adunare matricială este cea clasica. în schimb, pentru fiecare înmulțire matricială, aplicăm recursiv aceste partiționări, până când ajungem la submatrici de 2 × 2 elemente.

Pentru a obține matricea C, este nevoie de opt înmulțiri și patru adunări de matrici de n/2 × n/2 elemente. Două matrici de n/2 × n/2 elemente se pot aduna într-un timp în Θ. Timpul total pentru algoritmul divide et impera rezultat este

Definim funcția

În timp ce înmulțirea matricilor necesită un timp cubic, adunarea matricilor necesită doar un timp pătratic. Este, deci, de dorit ca în formulele pentru calcularea submatricilor C să folosim mai puține înmulțiri, chiar dacă prin aceasta mărim numărul de adunări. Este însă acest lucru și posibil? Răspunsul este afirmativ. În 1969, Strassen a descoperit o metoda de calculare a submatricilor Cij, care utilizează 7 înmulțiri și 18 adunări și scăderi. Pentru început, se calculează șapte matrici de n/2 × n/2 elemente:

Este ușor de verificat ca matricea produs C se obține astfel:

Timpul total pentru noul algoritm divide et impera este

și în mod similar deducem că . Deoarece lg 7 < 2,81, rezultă că . Algoritmul lui Strassen este deci mai eficient decât algoritmul clasic de înmulțire matriciala. Metoda lui Strassen nu este unica: s-a demonstrat că exista exact 36 de moduri diferite de calcul a submatricilor Cij, fiecare din aceste metode utilizând 7 înmulțiri. Limita O() poate fi și mai mult redusă dacă găsim un algoritm de înmulțire a matricilor de 2 × 2 elemente cu mai puțin de șapte înmulțiri. S-a demonstrat însă că acest lucru nu este posibil. O altă metodă este de a găsi algoritmi mai eficienți pentru înmulțirea matricilor de dimensiuni mai mari decât 2 × 2 și de a descompune recursiv pana la nivelul acestor submatrici. Datorită constantelor multiplicative implicate, exceptând algoritmul lui Strassen, nici unul din acești algoritmi nu are o valoare practica semnificativă.

Pe calculator, s-a putut observa că, pentru n ≥ 40, algoritmul lui Strassen este mai eficient decât metoda clasica. în schimb, algoritmul lui Strassen folosește memorie suplimentară.

Poate că este momentul să ne întrebăm de unde provine acest interes pentru înmulțirea matricilor. Importanta acestor algoritmi* deriva din faptul că operații frecvente cu matrici (cum ar fi inversarea sau calculul determinantului) se bazează pe înmulțiri de matrici. Astfel, dacă notăm cu f(n) timpul necesar pentru a înmulți două matrici de n × n elemente și cu g(n) timpul necesar pentru a inversa o matrice nesingulară de n × n elemente, se poate arată ca f єΘ(g).

3.9. Înmulțirea numerelor întregi mari

Pentru anumite aplicații, trebuie să consideram numere întregi foarte mari. Dacă ați implementat algoritmii pentru generarea numerelor lui Fibonacci, probabil că v-ați confruntat deja cu aceasta problemă. Același lucru s-a atunci când s-au calculat primele 134 de milioane de cifre ale lui π. În criptologie, numerele întregi mari sunt de asemenea extrem de importante. Operațiile aritmetice cu operanzi întregi foarte mari nu mai pot fi efectuate direct prin hardware, deci nu mai putem presupune, că până acum, ca operațiile necesită un timp constant. Reprezentarea operanzilor în virgulă flotantă ar duce la aproximări nedorite. Suntem nevoiți deci să implementăm prin software operațiile aritmetice respective.

În cele ce urmează, vom da un algoritm divide et impera pentru înmulțirea întregilor foarte mari. Fie u și v doi întregi foarte mari, fiecare de n cifre zecimale (convenim să spunem ca un întreg k are j cifre dacă k < , chiar dacă k < ). Dacă s =, reprezentăm pe u și v astfel:

Întregii w și y au cate cifre, iar întregii x și z au câte . cifre. Din relația

obținem următorul algoritm divide et impera pentru înmulțirea a două numere

întregi mari.

function inmultire(u, v)

n ← cel mai mic întreg astfel încât u și v să aibă fiecare n cifre

if n este mic then calculează în mod clasic produsul uv

return produsul uv astfel calculat

s ← n div 2

w ← u div ; x ← u mod

y ← v div ; z ← v mod

return inmultire(w, y) ×

+ (inmultire(w, z)+inmultire(x, y)) ×

+ inmultire(x, z)

Înmulțirile sau împărțirile cu și , ca și adunările, sunt executate într-un timp liniar. Același lucru este atunci adevărat și pentru restul împărțirii întregi, deoarece

u mod = u – w, v mod= v – y

Notam cu td (n) timpul necesar acestui algoritm, în cazul cel mai nefavorabil,

pentru a înmulți doi întregi de n cifre. Avem

Dacă n este o putere a lui 2, aceasta relație devine

Deoarece înmulțirea întregilor mari este mult mai lentă decât adunarea, încercăm să reducem numărul înmulțirilor, chiar dacă prin aceasta mărim numărul adunărilor. Adică, încercăm să calculăm wy, wz+xy și xz prin mai puțin de patru înmulțiri. Considerând produsul r = (w+x)(y+z) = wy + (wz+xy) + xz observăm ca putem înlocui ultima linie din algoritm cu:

r ← inmult(w+x, y+z)

p ← inmult(w, y); q←inmult(x, z)

return 102sp + 10s(r-p-q) + q

Fie t(n) timpul necesar algoritmului modificat pentru a înmulți doi întregi, fiecare cu cel mult n cifre. Ținând cont ca w+x și y+z pot avea cel mult 1+ cifre, obținem

Prin definiție, funcția t este nedescrescătoare. Deci,

Notând T(n) = t(n+2) și presupunând că n este o putere a lui 2, obținem

T(n) є 3T(n/2) + O(n)

Prin metoda iterației, puteți arăta că este o putere a lui 2.

Sau, mai elegant, puteți ajunge la același rezultat aplicând o schimbare de variabilă.

Deci, este o putere a lui 2) obținem t O).

În concluzie, este posibil să înmulțim doi întregi de n cifre într-un timp în O(), deci și în O(). Ca și la metoda lui Strassen, datorită constantelor multiplicative implicate, acest algoritm este interesant în practică doar pentru valori mari ale lui n. O implementare bună nu va folosi probabil baza 10, ci baza cea mai mare pentru care hardware-ul permite ca două “cifre” să fie înmulțite direct.

Demonstrați că procedura binsearch se termină într-un număr finit de pași (nu ciclează).

Indicatie: Aratati ca binrec(T[i .. j], x) este apelata intotdeauna cu ij și că binrec(T[i .. j], x) apelează binrec(T[u .. v], x) întotdeauna astfel încât:

v-u < j-i

Se poate înlocui în algoritmul iterbin1:

i) “k (i+j+1) div 2” cu “k (i+j) div 2”?

ii) “i k” cu “i k+1”?

iii) “j k-1” cu “j k”?

Observați că bucla while din algoritmul insert .Se folosește o căutare secvențiala (de la coada la cap). să înlocuim această căutare secvențială cu o căutare binară. Pentru cazul cel mai nefavorabil, ajungem oare acum ca timpul pentru sortarea prin inserție să fie în ordinul lui n log n?

Arătați ca timpul pentru iterbin2 este în (1), (log n), (log n) pentru cazurile cel mai favorabil, mediu și respectiv, cel mai nefavorabil.

Fie T[1 .. n] un tablou ordonat crescător de întregi diferiți, unii putând fi negativi. Dați un algoritm cu timpul în O(log n) pentru cazul cel mai nefavorabil, care găsește un index i, 1 = i = n, cu T[i] = i, presupunând că acest index exista.

Rădăcina pătrata întreaga a lui n . N este prin definiție acel pN

pentru care p = n < p+1. Presupunând ca nu avem o funcție radical, elaborăm un algoritm care îl găsește pe p intr-un timp în O(log n).

Soluție: Se apelează pătrat(0, n+1, n), pătrat fiind funcția:

function patrat(a, b, n)

if a = b-1 then return a

m(a+b) div 2

if = n then patrat(m, b, n)

else patrat(a, m, n)

Fie tablourile U[1 .. N] și V[1 .. M], ordonate crescător. Elaborăm un algoritm cu timpul de execuție în (N+M), care să interclaseze cele două tablouri.

Rezultatul va fi trecut în tabloul T[1 .. N+M].

Soluție: Iată o primă variantă a acestui algoritm:

i, j, k1

while i N and j M do

if U[i] = V[j] then T[k] . U[i]

i i+1

else T[k] . V[j]

j j+1

k k+1

if i > N then for h j to M do

T[k] V[h]

k k+1

else for h i to N do

T[k] U[h]

k k+1

Se poate obține un algoritm și mai simplu, dacă se presupune că avem acces la locațiile U[N+1] și V[M+1], pe care le vom inițializa cu o valoare maximală și le vom folosi ca “santinele”:

i, j 1

U[N+1], V[M+1] . +8

for k 1 to N+M do

if U[i] < V[j] then T[k] U[i]

i i+1

else T[k] V[j]

j . j+1

Mai rămâne să analizăm eficiența celor doi algoritmi.

Modificăm algoritmul mergesort astfel încât T să fie separat nu în două, ci în trei părți de mărimi cât mai apropiate. Analizăm algoritmul obținut.

Arătați că, dacă în algoritmul mergesort separam pe T în tabloul U, având n-1 elemente, și tabloul V, având un singur element, obținem un algoritm de sortare cu timpul de execuție în . Acest nou algoritm seamănă cu unul dintre algoritmii deja cunoscuți. Cu care anume?

Iată și o altă procedură de pivotare:

procedure pivot1(T[i .. j], l)

pT[i]

l i

for k i+1 to j do

if T[k] = p then l l+1

interschimba T[k] și T[l]

interschimba T[i] și T[l]

Argumentați de ce procedura este corecta și analizați eficiența ei. Comparați numărul maxim de interschimbări din procedurile pivot și pivot1. Este oare rentabil ca în algoritmul quicksort să inlocuim procedura pivot cu procedura pivot1?

Argumentați de ce un apel funny-sort(T[1 ..n ]) al următorului algoritm sortează corect elementele tabloului T[1 .. n].

procedure funny-sort(T[i .. j])

if T[i] > T[ j] then interschimba T[i] și T[ j]

if i < j-1 then k ( j-i+1) div 3

funny-sort(T[i .. j-k])

funny-sort(T[i+k .. j])

funny-sort(T[i .. j-k])

Este oare acest simpatic algoritm și eficient?

Este un lucru elementar să găsim un algoritm care determina minimul

dintre elementele unui tablou T[1 .. n] și utilizează pentru aceasta n-1 comparații între elemente ale tabloului. Mai mult, orice algoritm care determină prin comparații minimul elementelor din T efectuează în mod necesar cel puțin n-1 comparații. În anumite aplicații, este nevoie să găsim atât minimul cât și maximul dintr-o mulțime de n elemente. Iată un algoritm care determina minimul și maximul dintre elementele tabloului T[1 .. n]:

procedure fmaxmin1(T[1 .. n], max, min)

max, min . T[1]

for i 2 to n do

if max < T[i] then max T[i]

if min > T[i] then min T[i]

Acest algoritm efectueaza 2(n-1) comparații intre elemente ale lui T. Folosind tehnica divide et impera, elaborați un algoritm care să determine minimul și maximul dintre elementele lui T prin mai puțin de 2(n-1) comparații. Puteți presupune ca n este o putere a lui 2.

Solutie: Un apel fmaxmin2(T[1 .. n], max, min) al următorului algoritm găsește minimul și maximul cerute

procedure fmaxmin2(T[i .. j], max, min)

case i = j : max, min T[i]

i = j-1 : if T[i] < T[ j] then max T[ j]

min T[i]

else max T[i]

min T[ j]

otherwise : m (i+j) div 2

fmaxmin2(T[i .. m], smax, smin)

fmaxmin2(T[m+1 .. j], dmax, dmin)

max maxim(smax, dmax)

min minim(smin, dmin)

Funcțiile maxim și minim determina, prin cate o singura comparație, maximul, respectiv minimul, a două elemente.

Putem deduce că atât fmaxmin1, cât și fmaxmin2 necesită un timp în È(n)

pentru a găsi minimul și maximul intr-un tablou de n elemente. Constanta multiplicativa asociata timpului în cele doua cazuri diferă însă. Notând cu C(n) numărul de comparații între elemente ale tabloului T efectuate de procedura fmaxmin2, obținem recurentă

Consideram n = și folosim metoda iterației:

Algoritmul fmaxmin2 necesita cu 25% mai puține comparații decât fmaxmin1. Se poate arata că nici un algoritm bazat pe comparații nu poate folosi mai puțin de 3n/2-2 comparații. în acest sens, fmaxmin2 este, deci, optim. Este procedura fmaxmin2 mai eficientă și în practică? Nu în mod necesar. Analiza ar trebui să considere și numărul de comparații asupra indicilor de tablou, precum și timpul necesar pentru rezolvarea apelurilor recursive în fmaxmin2. De asemenea, ar trebui să cunoaștem și cu cât este mai costisitoare o comparație de elemente ale lui T, decât o comparație de indici (adică, de întregi).

În ce constă similaritatea algoritmului selection cu algoritmul i) quicksort și ii) binsearch?

Generalizați procedura pivot, partiționând tabloul T în trei secțiuni T[1 .. i-1], T[i .. j], T[ j+1 .. n], conținând elementele lui T mai mici decât p, egale cu p și respectiv, mai mari decât p. Valorile i și j vor fi calculate în procedura de pivotare și vor fi returnate prin această procedură.

Folosind ca model versiunea iterativa a căutării binare și rezultatul

Elaborați un algoritm nerecursiv pentru problema selecției.

Analizați următoarea varianta a algoritmului quicksort.

procedure quicksort-modificat(T[1 .. n])

if n = 2 and T[2] < T[1]

then interschimba T[1] și T[2]

else if n > 2 then

p selection(T, (n+1) div 2)

arrays U[1 .. (n+1) div 2 ], V[1 .. n div 2]

U elementele din T mai mici decât p

și, în completare, elemente egale cu p

V elementele din T mai mari decât p

și, în completare, elemente egale cu p

quicksort-modificat(U)

quicksort-modificat(V)

Dacă presupunem că găsirea medianei este o operație elementară, am

văzut ca timpul pentru selection, în cazul cel mai nefavorabil, este

tm(n)O(n) + max{tm (i) | i n/2}

Demonstrati ca tmO(n)

Solutie: Fie n0 și d două constante astfel încât pentru n > n0 avem

Tm (n) dn + max{tm (i) | i n/2}

Putem conșidera ca exista constanta reala pozitiva c astfel încât tm(i) ci+c, pentru 0in0. Prin ipoteză inducției specificate parțial presupunem că t(i) ci+c, pentru orice 0 i < n. Atunci

Tm(n) = dn+c+c n/2 = cn+c+dn-cn/2 cn+c

deoarece putem să alegem constanta c suficient de mare, astfel încât cn/2 dn.

Am arătat deci prin inducție că, dacă c este suficient de mare, atunci

tm(n) cn+c, pentru orice n 0. Adică, tm O(n).

Arătați că luând “p T[1]” în algoritmul selection și considerând cazul cel mai nefavorabil, determinarea celui de-al k-lea cel mai mic element al lui T[1 .. n] necesita un timp de execuție în O().

Fie U[1 .. n] și V[1 .. n] doua tablouri de elemente ordonate nedescrescator. Elaborați un algoritm care să găsească mediana celor 2n elemente într-un timp de execuție în O(log n).

Un element x este majoritar în tabloul T[1 .. n], dacă #{i | T[i] = x} > n/2 . Elaborați un algoritm liniar care să determine elementul majoritar în T (dacă un astfel de element exista).

Să presupunem că Eva a găsit un A' pentru care

a = mod p = mod p

și că există un B, astfel încât b = mod p. Arătați că

x' = mod p = mod p = x

chiar dacă A' A.

Arătați cum poate fi calculat prin doar cinci înmulțiri (inclusiv ridicări la pătrat).

Solutie:

Găsiți un algoritm divide et impera pentru a calcula un termen oarecare din șirul lui Fibonacci.

Demonstrați ca algoritmul lui Strassen necesita un timp în O(nlg 7), folosind de această dată metoda iterației.

Solutie: Fie doua constante pozitive a și c, astfel încât timpul pentru algoritmul lui Strassen este:

Cum ați modifica algoritmul lui Strassen pentru a înmulți matrici de n × n elemente, unde n nu este o putere a lui doi? Arătați că timpul algoritmului rezultat este tot în

Indicație: Îl majorăm pe n până la cea mai mică putere a lui 2, completând corespunzător matricile A și B cu elemente nule.

Să presupunem ca avem o primitiva grafica box(x, y, r), care desenează un pătrat 2r × 2r centrat în (x, y), ștergând zona din interior. Care este desenul realizat prin apelul star(a, b, c), unde star este algoritmul:

procedure star(x, y, r)

if r > 0 then star(x-r, y+r, r div 2)

star(x+r, y+r, r div 2)

star(x-r, y-r, r div 2)

star(x+r, y-r, r div 2)

box(x, y, r)

Care este rezultatul, dacă box(x, y, r) apare înaintea celor patru apeluri recursive?

Arătați ca timpul de execuție pentru un apel star(a, b, c) este în .

Demonstrați ca pentru orice întregi m și n sunt adevărate următoarele

proprietăți:

i) dacă m și n sunt pare, atunci cmmdc(m, n) = 2cmmdc(m/2, n/2)

ii) dacă m este impar și n este par, atunci cmmdc(m, n) = cmmdc(m, n/2)

iii) dacă m și n sunt impare, atunci cmmdc(m, n) = cmmdc((m-n)/2, n)

Pe majoritatea calculatoarelor, operațiile de scădere, testare a parității unui întreg și împărțire la doi sunt mai rapide decât calcularea restului împărțirii întregi.

Elaborați un algoritm divide et impera pentru a calcula cel mai mare divizor comun a doi întregi, evitând calcularea restului împărțirii întregi. Folosiți proprietățile de mai sus.

Găsiți o structură de date adecvată, pentru a reprezenta numere întregi mari pe calculator. Pentru un întreg cu n cifre zecimale, numărul de biți folosiți trebuie să fie în ordinul lui n. Înmulțirea și împărțirea cu o putere pozitiva a lui 10 (sau alta baza, dacă preferați) trebuie să poată fi efectuate într-un timp liniar.

Adunarea si scăderea a două numere de n, respectiv m cifre trebuie să poată fi efectuate intr-un timp în (n+m). Permiteți numerelor să fie și negative.

Capitolul IV

PROGRAMARE DINAMICĂ

Dacă analizăm natura problemelor care au fost rezolvate prin programare liniară sau prin teoria grafurilor, constatăm că procesul economic pe care doream să îl optimizăm se desfășura într-o singură fază (etapă sau perioadă). Ținând cont de faptul că există numeroase probleme de optimizare care modelează procese economice care se desfășoară în mai multe perioade și la fiecare perioadă trebuie să stabilim soluția optimă, viziunea statică poate constitui un neajuns. Este evident faptul că succesiunea de soluții nu se poate determina ținând seama numai de parametrii fiecărei perioade analizate în parte, și că este necesar să identificăm o succesiune de soluții care optimizează întregul proces analizat. Problemele economice care reclamă o suită de decizii secvențiale se caracterizează prin faptul că o decizie care adoptată într-o anumită perioadă are atât un efect economic imediat, cât și unul de lungă durată, care influențează și asupra celorlalte etape.

Optimizarea proceselor secvențiale se obține prin metodele unei teorii matematice relativ recent constituite și care se numește programare dinamicã. Creatorul acestei teorii este Richard Bellman, iar lucrarea sa fundamentală este Dynamic Programming apărută în anul 1957. Programarea dinamică are un câmp larg de aplicație în cercetarea operațională (organizarea producției, gestiunea stocurilor, reînnoirea echipamentelor), precum și în alte domenii (navigație cosmică, procese cu conexiune inversă etc.). Să presupunem un proces secvențial a cărui desfășurare în timp depinde de o variabilă care poate lua o mulțime de valori în fiecare etapă. Ne putem decide pentru o valoare determinată a variabilei în fiecare etapă și din această cauză ea se numește variabilă de decizie sau de control. O succesiune oarecare de decizii constituie o politică și cea care ne interesează este politica optimă, de pildă aceea care conduce la un cost total minim al procesului.

Deosebim două tipuri principale de procese secvențiale:

a) deterministe, când la fiecare fază procesul este controlat în întregime de decizia pe care o luăm;

b) stohastice, atunci când evoluția procesului se desfășoară sub dubla influență a deciziilor și a hazardului.

Se numește politică optimă acea succesiune de decizii care optimizează procesul în ansamblu lui, fiind vorba de un proces determinist. În cazul unui proces stohastic, se folosește în mod corespunzător noțiunea de strategie optimă.

Procesele dinamice pot fi continue sau discrete. Un exemplu de proces discret este următorul: o întreprindere trebuie să-și întocmească planul de aprovizionare anual pentru un anumit material; se consideră 12 perioade (luni) și pentru fiecare perioadă se stabilește cantitatea de aprovizionat, astfel ca pe întregul an să rezulte un cost total minim. Procesele dinamice discrete pot avea orizontul limitat (în exemplu de mai sus 12 perioade) sau nelimitat.

4.1. Introducere

Programarea Dinamică (PD) este o metodă de rezolvare a unor probleme de optimizare în care se operează pe FAZE (SECVENTE) numite în continuare PERIOADE. Prin aplicarea acestei metode, soluția optimă se obține în urma rezolvării unui șir de probleme de optimizare LEGATE INTRE ELE, fiecare de dimensiune si complexitate mult mai mică decât problema originală. Deși teoretic PD este aplicabilă oricărei probleme de optimizare multidimensională, totuși metoda a dat rezultate foarte bune – în sensul ușurării rezolvării – numai pe anumite clase de probleme cum sunt cele care modelează evoluția în timp a unui proces economic sau probleme de alocare (repartiție).

4.2. Probleme de alocare unidimensională

Presupunem ca avem la dispoziție o anumită resursã economicã. Termenul poate reprezenta, după caz, un anume tip de materii prime, forță de muncă, energie, bani sau un anumit serviciu etc. Se produce un CONFLICT de INTERESE din faptul ca această resursă poate fi utilizată în MAI MULTE MODURI.

Un mod particular de utilizare a resursei în cauză se va numi în continuare ACTIVITATE. Ca urmare a utilizării resursei într-o activitate sau alta rezultă un anumit VENIT. Și acest termen are o sferă foarte largă putând desemna un produs finit, o sumă de bani sau pur și simplu satisfacția. Mărimea venitului depinde de cantitatea de resurse alocată activității respective, dar și de specificul acesteia.

În continuare vom adopta următoarele ipoteze simplificatoare:

1) Venitul rezultat din diferitele activități poate fi măsurat cu o unitate de măsura comuna.

2) Venitul rezultat dintr-o activitate nu depinde de alocările făcute în alte activități.

3) Venitul total este egal cu suma veniturilor individuale.

Problema fundamentală constă în a repartiza resursa între activitățile concurente de așa manieră încât venitul total sa fie MAXIM.

4.3. Un model matematic

Ordonăm într-un mod oarecare activitățile și le numerotăm: 1, 2,…, N. În continuare, fiecare activitate va fi identificată prin numărul său de ordine. Asociem fiecărei activități i o FUNCȚIE DE UTILITATE gi reprezentând DEPENDENȚA VENITULUI său de cantitatea de RESURSĂ ALOCATĂ. Conform ipotezei 2), gi depinde numai de cantitățile xi de resursă alocată activității i, așa că gi(xi) va reprezenta venitul obținut din activitatea i ca urmare a alocării cantității xi. Indicele i din simbolul gi al funcției de utilitate este menit să arate că venitul rezultat din activitatea i depinde nu numai de volumul de resurse alocat, dar și de specificul acestei activități (altfel spus, funcțiile de utilitate pot diferi de la o activitate la alta).

În diferitele situații practice funcția gi poate fi dată:

• printr-o expresie ANALITICĂ, de exemplu:

gi(xi)=aixi+bi, cu ai, bi constante (CAZ LINIAR); sau gi(xi)=aixi 2+bixi (CAZ NELINIAR-PATRATIC).

• printr-o lista de VALORI NUMERICE corespunzătoare unor NIVELE ale resursei alocate, ca de exemplu:

xi

0 1 2 3 4 5

yi

(xi) 0 0,18 0,38 0,46 0,51 0,55

Venitul total rezultat în urma alocării resursei în cele N activități va fi dat de expresia:

2

V(x1,x2,…,xN) = g1(x1) + g2(x2) +…+ gN(xN) (1)

ca urmare a ipotezelor 1) si 3).

Maximizarea funcției V se impune, datorită faptului că resursa se află disponibilă într-o cantitate limitată S. Astfel, alocările făcute diferitelor activități trebuie sa satisfacă cerințele:

x1 + x2 + …+xN=S (2)

xi = 0, i = 1,…,N (3)

Obiectivul nostru este acela de a maximiza funcția V(x1,x2,…,xN) din (1) pe mulțimea tuturor ALOCĂRILOR (x1,x2,…,xN) care satisfac restricția (2) și condițiile de nenegativitate (3).

4.4. Posibilități de rezolvare. Dificultăți

Să notăm cu (P) problema de optimizare rezultată:

(max)V(x1,…,xN) = g1(x1) +… + gN(xN)

(P) x1 +…+ xN = S

xi = 0, 1 = i = N

(P) = problemă de PROGRAMARE MATEMATICĂ cu o singură RESTRICȚIE LINIARĂ și o funcție obiectiv SEPARABILĂ și NELINIARĂ ÎN GENERAL. Dacă funcțiile g1,…,gN sunt derivabile, iar variabilele x1,…,xN pot lua orice valoare reală nenegativă, (P) se poate rezolva utilizând aparatul matematic al analizei clasice – Teoria EXTREMELOR CU LEGĂTURI. Nu insistăm asupra acestei metode, deoarece ea va fi studiata ulterior. Semnalăm totuși faptul că în multe situații concrete metoda MULTIPLICATORILOR LAGRANGE nu se dovedește a fi eficientă din cauza formei complicate pe care o pot avea funcțiile de utilitate gi.

Metoda amintită este inaplicabila în cazul în care funcțiile gi nu sunt derivabile sau în cazul în care variabilele xi nu pot lua decât valori nenegative ÎNTREGI. În asemenea situații – care nu sunt puține – se impun metodele de optimizare noi.

4.5. Rezolvarea problemelor de alocare unidimensionale (P) prin (PD)

Ideea metodei constă în a îngloba problema (P) într-o FAMILIE de probleme de alocare diferențiate prin numărul de activități și cantitatea de resursă disponibilă. În loc de a privi STATIC procesul alocării disponibilului S între cele N activități, aceasta însemnând considerarea diferitelor variante de repartiție (x1,…,xN) și clasificarea lor după venitul posibil de realizat, vom adopta un punct de vedere DINAMIC în care alocările se fac UNA CATE UNA. Mai precis, vom determina venitul maxim care se obține efectuând o alocare numai în PRIMA activitate, după care vom afla care este venitul maxim rezultat din efectuarea unei alocări în PRIMELE DOUĂ activități, apoi în PRIMELE TREI, s.a.m.d. În toate aceste procese PARȚIALE cantitatea de resursă alocată va fi VARIABILĂ –dar nedepășind plafonul maxim S – așa că rezultatele nu vor fi simple mărimi numerice, ci niște FUNCȚII reprezentând DEPENDENȚA VENITULUI MAXIM față de volumul de resursă alocată.

În termeni mai preciși, pentru fiecare întreg 1 = n = N și fiecare 0 = s = S vom considera problema de alocare unidimensionalã similară cu (P):

(max)V(x1,…,xn) = g1(x1) +…+ gn(xn)

Pn(s) = x1 +…+ xn = s

xi = 0, i=1,…, n

Cu noua notație (P) devine PN(S).

Vom nota cu fn(s) maximul obiectivului problemei Pn(s), adică venitul maxim rezultat din alocarea cantității s în regiunile (activitățile) 1, 2,…, n:

fn(s) = MAX [g1(x1) +…+ gn(xn)], x1 +…+ xn= s și xi = 0 (4)

Rezultă că maximul obiectivului problemei originale (P) este fN(S). Notăm că pentru n fixat și s variabil fn este o FUNCȚIE de o singură variabilă s al cărei domeniu de valori admisibile este intervalul [0, S]. Este evident ca pentru n=1, f1=g1, adică:

F1(s) = g1(s) pentru oricare ar fi 0 = s = S

Pentru n>1 valorile funcției fn se deduc pe baza următoarei relații de RECURENȚĂ:

Pentru 0 = s = S fn(s) = MAX[f n-1(s-xn)+gn(xn)], 0 = xn = s (5)

ECUAȚIA FUNDAMENTALĂ A PD

Demonstrația relației de recurenta (5) relevă următorul principiu general cunoscut sub numele de PRINCIPIUL DE OPTIMALITATE al lui BELLMAN. O strategie OPTIMĂ are proprietatea că oricare ar fi STAREA INIȚIALĂ și DECIZIA INIȚIALĂ, deciziile rămase constituie o strategie OPTIMĂ în raport cu STAREA care rezultă din prima decizie.

ALGORITM DE REZOLVARE A PROBLEMEI (P) PRIN PD

Etapa I (INIȚIALIZARE):

Pentru fiecare 0 = s = S definim f1(s) = g1(s)

Etapa n (1<n<N): Definim funcția fn în fiecare 0 = s = S după formula (5) și notăm cu xn*(s) acea valoare a variabilei xn în care se realizează EFECTIV maximul din (5)

:

Etapa N: Calculăm f (S)= max [f -1(S-xn)+gN(xN)] N N 0 = xN = S

Etapa finală (de determinare a alocării OPTIMALE (x1*,…,xN*)). Componentele acesteia se determina DIN APROAPE ÎN APROAPE “de la sfârșit la început” astfel:

xN*=xN*(S)

Pentru (.) 1 = n = N

xn*=xn*(s – sn), unde sn=xn+1*+…+xN*

EXEMPLU NUMERIC

Conducerea unei firme a decis să facă un efort investițional pentru impulsionarea vânzărilor sale în 4 piețe diferite. Suma totală de investit este S=10 milioane $. Experții firmei au evaluat profiturile posibil de realizat în funcție de investiția făcută în una sau alta dintre piețe. Problema constă în a vedea cum trebuie repartizate cele 10 milioane pentru ca profitul firmei să fie maxim.

REZOLVARE:

1. Reprezentați în graficul suma investită – profitul realizat pentru cele 4 piețe.

2. Dependența între profit și suma investită nu este dată printr-o expresie analitică ci prin câteva valori corespunzătoare unor nivele ale investiției exprimate prin valori întregi. Din acest motiv, suma totală va fi împărțită de așa manieră încât investiția în fiecare zonă să fie exprimată tot printr-un număr întreg, evident nenegativ.

Reprezentând grafic dependența investiție – profit probabil constatăm ca ea nu este liniară și că pe măsură ce suma investită crește, curba corespondentă are tendința de aplatizare ca urmare a efectului de saturare.

Modelul matematic nu diferă de cel prezentat în general decât prin cerința ca variabilele sa ia numai valori întregi, dată fiind maniera particulară în care s-au dat funcțiile de utilitate. El este:

Să se determine x*1, x*2, x*3, x*4 care maximizează profitul Π(x1,x2,x3,x4)=g1(x1)+g2(x2)+g3(x3)+g4(x4)

cu restricția x1+x2+x3+x4=10

și condiția xi ≥ 0, întregi, i=1, 2, 3, 4

unde xi = suma prevăzută a se investi în piața i, iar gi(xi) este profitul probabil rezultat din aceasta investiție.

Pentru fiecare număr întreg 0 ≤ s ≤10 și 1 ≤ n ≤ 4 definim fn(s) = profitul maxim rezultat din investirea a s $ în primele 1, 2,…, n piețe.

Conform teoriei generale:

Deducerea alocării optimale:

f4(10) = f3(8) + g4(2) . x*4 = 2

f3(8) = f2(7) + g3(1) . x*3 = 1

f2(7) = f1(4) + g2(3) . x*2 = 3

f4(10) =g4(10) . x*1=4

4.6. O problemă de încărcare a unui vapor

Să presupunem că avem de încărcat un vapor cu o încărcătură formată din mărfuri de diferite tipuri. Mărfurile sosesc la încărcare în containere de diferite mărimi, fiecare marfă fiind așezată totuși în containere de aceeași mărime. Un container în care se află marfa i, i = 1,…, N are o anumită greutate Wi și o anumită valoare Vi. Există un plafon W al greutății încărcăturii. Câte containere din fiecare tip de marfă trebuie încărcate – în limita greutății maxime W, astfel încât valoarea încărcăturii sa fie maximă?

Modelul matematic

în care xi = numărul de containere în care se află marfa i.

Se presupune că și W este întreg.

Pentru oricare ar fi 1 = n = N și 0 = w = W întregi, notăm cu fn(w) valoarea maximă a unei încărcături cu greutatea cel mult egală cu w formată din mărfurile 1, 2,…, n.

Evident fn(w) = maxV(x1,…, xn), unde V(x1,…,xn) este funcția obiectiv din problema:

Noi suntem interesați în a afla fN(W) = maxV(x1,…, xN) și combinația (x*1,…, x*N) care realizează această valoare maximă.

Pentru n = 1 avem: f1(w) = v1·[w/w1], [·] = partea întreagă

n > 1 ecuația de dinamică este:

cu observația că pentru:

n = N se calculează numai

Exemplu numeric:

Considerăm dată problema de încărcare a unui vapor descrisă de informațiile:

Exemplu de calcul:

Soluția optimă de încărcare:

x*1 = x*2 = x*3 = 1

maxV = 33

APLICAȚIE

Programul următor este realizat în Turbo Pascal și prezintă toate posibilitățile de ieșire a unei bile din centrul unei table de șah cu înălțimi diferite.

uses crt,graph,menu,windows;

const NMAX=50;

Length=420;

Recursiv=false;

NDir=8;

dir_lin:array[1..NDir] of integer=(-1,-1, 0, 1, 1, 1, 0,-1);

dir_col:array[1..NDir] of integer=( 0, 1, 1, 1, 0,-1,-1,-1);

type hights=array[1..NMAX,1..NMAX] of word;

var open:boolean;

n:byte;

tablou:hights;

poz_lin,poz_col:byte;

cel:word;

solution,more_solution:boolean;

trace:array[1..5000,1..2] of word;

a:array[1..5000] of byte;

{Initializeaza modul grafic, deseneaza spatiul de lucru (chenar, butoane)}

procedure initgraf;

var gm,mode:integer;

i,j:byte;

begin

gm:=detect;

initgraph(gm,mode,'');

if graphresult<>grok then

begin

writeln('Eroare la initializarea modului grafic!');

halt;

end;

port[$60]:=243;

delay(1000);

port[$60]:=0;

fastwindow(0,0,getmaxx,getmaxy,10);

panel(12,12,getmaxx-23,getmaxy-23);

{frame(20,20,440,440,5);}

frame(470,20,150,60,5);

shadowwrite(480,30,'Program realizat');

shadowwrite(520,45,'de');

shadowwrite(485,60,' VATIA ALIN');

frame(520,100,70,130,5);

butf:=nil;

creazabuton(530,110,30,green,'Open',cmopen);

creazabuton(530,150,30,green,'Run',cmrun);

creazabuton(530,190,30,green,'Exit',cmies);

scriebutoane;

open:=false;

end;

{Afiseaza un mesaj pe ecran si asteapta apasarea unei taste}

procedure mesaj(text:string;x,y:word);

var p:pointer;

dx,dy,size:word;

ch:char;

begin

dx:=textwidth(text)+20;

dy:=textheight(text)+10;

size:=imagesize(x,y,x+dx,x+dy);

getmem(p,size);

getimage(x,y,x+dx,x+dy,p^);

panel(x,y,dx,dy);

shadowwrite(x+10,y+5,text);

ch:=readkey;

if ch=#0 then ch:=readkey;

putimage(x,y,p^,normalput);

end;

{Afiseaza numele fisierului curent}

procedure nume_fisier(name:string);

begin

setfillstyle(solidfill,_darkgray);

bar(480,400,600,450);

hole(480,400,120,50);

shadowwrite(490,410,name);

end;

{Afiseaza bila}

procedure bila(l,c:word);

var x,y:word;

begin

x:=27+cel*(c-1);

y:=27+cel*(l-1);

pieslice(x+cel div 2,y+cel div 2,0,360,cel div 2);

end;

{Afiseaza reteaua}

procedure grid(x,y:word);

var i,j:word;

begin

setfillstyle(solidfill,_darkgray);

bar(20,20,470,460);

cel:=Length div n;

frame(20,20,cel*n+14,cel*n+14,5);

setcolor(0);

for i:=1 to n do

for j:=1 to n do

rectangle(27+cel*(i-1),27+cel*(j-1),27+cel*i,27+cel*j);

bila(poz_lin,poz_col);

end;

{Citeste datele din fisier}

procedure citire_date(name:string);

var f:text;

i,j:byte;

begin

assign(f,name);

{$I-}

reset(f);

{$I+}

if ioresult<>0 then

begin

{file not found}

mesaj('Fisierul nu poate fi deschis!',100,100);

exit;

end;

readln(f,n,poz_lin,poz_col);

for i:=1 to n do

for j:=1 to n do

read(f,tablou[i,j]);

close(f);

open:=true;

nume_fisier(name);

grid(20,20);

end;

{Se afiseaza o solutie}

procedure afisare(m:word);

var i,x,y:word;

ch:char;

len:byte;

sir:string[10];

begin

solution:=true;

for i:=2 to m do

begin

x:=27+cel*(trace[i,2]-1);

y:=27+cel*(trace[i,1]-1);

setfillstyle(solidfill,red);

bar(x+1,y+1,x+cel-2,y+cel-2);

str(i-1,sir);

len:=textwidth(sir);

x:=27+cel*(trace[i,2]-1)+(cel-len) div 2;

len:=textheight(sir);

y:=27+cel*(trace[i,1]-1)+(cel-len) div 2;

outtextxy(x,y,sir);

end;

ch:=readkey;

if ch=#0 then ch:=readkey;

if ch=#27 then more_solution:=false;

for i:=2 to m do

begin

x:=27+cel*(trace[i,2]-1);

y:=27+cel*(trace[i,1]-1);

setfillstyle(solidfill,_darkgray);

bar(x+1,y+1,x+cel-2,y+cel-2);

end;

end;

{Backtracking nerecursiv}

procedure back_normal;

var i:word;

gata:boolean;

begin

trace[1,1]:=poz_lin;trace[1,2]:=poz_col;

i:=2;a[i]:=0;

while (i>1) do

begin

gata:=false;

while (a[i]+1<=NDir) and not(gata) do

begin

a[i]:=a[i]+1;

trace[i,1]:=trace[i-1,1]+dir_lin[a[i]];

trace[i,2]:=trace[i-1,2]+dir_col[a[i]];

if (tablou[trace[i,1],trace[i,2]]<tablou[trace[i-1,1],trace[i-1,2]]) then gata:=true;

end;

if gata then

if (trace[i,1]=1) or (trace[i,1]=n) or (trace[i,2]=1) or (trace[i,2]=n) then afisare(i)

else

begin

inc(i);

a[i]:=0;

end

else i:=i-1;

if not(more_solution) then break;

end;

end;

{Backtracking recursiv}

procedure back(l,c,step:word);

var ln,cn:word;

i:byte;

begin

trace[step,1]:=l;

trace[step,2]:=c;

if (l=1) or (c=1) or (l=n) or (c=n) then afisare(step)

else

begin

for i:=1 to NDir do

begin

ln:=l+dir_lin[i];

cn:=c+dir_col[i];

if more_solution and (tablou[ln,cn]<tablou[l,c]) then back(ln,cn,step+1);

if not(more_solution) then break;

end;

end;

end;

{Apeleaza rezolvarea problemei fie prin metoda recursiva fie cea normala}

procedure run;

begin

solution:=false;

more_solution:=true;

if Recursiv then back(poz_lin,poz_col,1)

else back_normal;

if not(solution) then mesaj('Nu avem solutie!',100,100)

else mesaj('S-au terminat solutiile',100,100);

end;

{Prelucreaza evenimentele aparute de la tastatura}

procedure work(var cmd:word);

var name:string;

begin

case cmd of

cmopen:begin

name:=inputf('Nume fisier:',100,100,12);

if name<>'.' then

citire_date(name);

end;

cmrun:if not(open) then mesaj('Nu avem date de intrare!',100,100)

else run;

cmies:;

end;

end;

begin

initgraf;

repeat

getevent(comand);

prelbut(comand);

if comand<>nocomand then work(comand);

until comand=cmies;

iesire;

end.

BIBLIOGRAFIE

Emil Cerchez, “Programare dinamică”, București 1998

Tudor Sorin, “Metoda Backtracking”, Craiova 1996

Tudor Sorin, “Algoritmi de programare”, Craiova 1994

D. E. Knuth, “Tratat de programarea calculatoarelor. Sortare si căutare”, Secțiunea 5.2.4.

http://vega.unitbv.ro,”Algoritmi divide et impera”