Metoda Greedy 4c1k6u

1

Pointeri  Variabile şi adrese În limbajul C, orice variabilă are o adresă: o valoare numerică, ce indică locul din memorie unde e memorată valoarea variabilei. Operatorul prefix & dă adresa operandului: &x reprezintă adresa variabilei x. O adresă poate fi tipărită (în hexazecimal) cu formatul %p în printf #include <stdio.h> double d; int a[10]; /* variabile globale */ int main(void) { int k; /* variabilˇa localˇa */ printf("Adresa lui d: %p\n", &d); /* de ex. 0x80496c0 */ printf("Adresa lui a[0]: %p\n", &a[0]); /* 0x80496e0 */ printf("Adresa lui a[5]: %p\n", &a[5]); /* 0x80496f4 */ printf("Adresa lui k: %p\n", &k); /* 0xbffff8e4 */ } /* Obs &a[5] - &a[0] == 5 * sizeof(int) (pozitii consecutive) */

 Tipuri pointer. Declarare. Indirectare Orice expresie în C are un tip, la fel şi expresiile adresă. Dacă variabila x are tipul tip, &x are tipul tip * int x; // &x are tipul int *, adica pointer la int (adresă de int) char c; // &c are tipul char *, (pointer la char, adresă de char) Există tipuri de adresă diferite pentru fiecare tip de date. Putem declara variabile de aceste tipuri (pointeri): tip * nume_var; // nume_var e pointer la (adresa pt.) o valoare de tipul tip pointer = o variabilă care conţine adresa altei variabile Operatorul prefix * dă obiectul *p de la adresa dată de operandul p. Operandul = pointer. Rezultatul = referinţă la obiectul indicat de pointer sau operator de indirectare (dereferenţiere, referire indirectă prin adresă) Dacă pointerul p are tipul tip *, atunci *p are tipul tip. Sintaxa declaraţiei (aceeaşi dar citită în două feluri) sugerează folosirea: – char* p; // p e o variabila de tipul char * (adresă de char) – char *p; // *p (obiectul de la adresa p) are tipul char  Operatorii de adresă şi dereferenţiere Pointerii au adrese, ca orice variabile: – int *p; // adresa &p are tipul int ** – int ** pp = &p; // pp are tipul int **, adică adresa unei adrese de int dar putem citi int* *pp sau int **pp, deci *pp are tipul int * (adresă de int) şi **pp are tipul int (val. de la adr. *pp)

2

Înainte de folosire, un pointer trebuie iniţializat, de ex. cu adresa unei variabile de tipul potrivit: int x, *p, **pp; p = &x; pp = &p; O referinţă *p poate fi folosită la stânga sau la dreapta unei atribuiri (în cazul de mai sus, *p se foloseşte absolut la fel (sinonim) cu x) int x, y, z, *p; p = &x; z = *p; /* z = x */ *p = y; /* x = y */ Operatorii adresă & şi de indirectare * sunt unul inversul celuilalt: – *&x este chiar x, pentru orice obiect (variabilă) x – &*p are valoarea p, pentru orice variabilă pointer p (dar p e o variabilă şi poate fi atribuită; &*p e o expresie şi nu poate) 

Pointeri ca argumente/rezultate de funcţii

În limbajele de programare există două mecanisme principale de transfer ale parametrilor: transferul prin valoare şi transferul prin referinţă. În C parametrii se transferă numai prin valoare - aceasta înseamnă că parametrii actuali sunt copiaţi în zona de memorie rezervată pentru parametrii formali. Modificarea parametrilor formali se va reflecta asupra copiilor parametrilor actuali şi nu afectează parametrii actuali, adică parametrii actuali nu pot fi modificaţi ! Astfel funcţia: void schimb(int a, int b) { int c=a; a=b; b=c; }

nu produce interschimbul parametrilor actuali x şi y din funcţia main(): void main(void) { int x=10,y=15; printf(“%d\t%d\n”, x, y); schimb(x, y); printf(“%d\t%d\n”, x, y); }

Se afişează: 10 15 10 15 Forma corectă a funcţiei schimb() obţinută prin simularea transferului prin referinţă cu pointeri este: În C void schimb(int *a, int *b) { int c; c = *a; *a = *b; *b = c; }

 Alocarea dinamică a memoriei

În C++ void schimb(int &a, int &b) { int c; c = a; a = b; b = c; }

3 Utilizatorul poate solicita în timpul execuţiei programului alocarea unei zone de memorie. Această zonă de memorie poate fi eliberată, în momentul în care nu mai este necesară. Alocarea şi eliberarea de memorie la execuţie permite gestionarea optimă a memoriei. Biblioteca standard oferă 4 funcţii, având prototipurile în şi <stdlib.h>. Acestea sunt: void *malloc(unsigned n); Funcţia alocă un bloc de memorie de n octeţi. Funcţia întoarce un pointer la începutul zonei alocate. În caz că cererea de alocare nu poate fi satisfăcută, funcţia returnează NULL. void *calloc(unsigned nelem, unsigned dim);

Alocă nelem*dim octeţi de memorie (nelem blocuri formate din dim octeţi fiecare). Întoarce un pointer la începutul zonei alocate sau NULL. Memoria alocată este iniţializată cu zerouri. void free(void *p); Funcţia eliberează o zonă de memorie indicată de p, alocată în prealabil prin malloc() sau calloc(). void

*realloc(void *p, unsigned dim);

Modifică dimensiunea spaţiului alocat prin pointerul p, la dim. Funcţia întoarce adresa zonei de memorie realocate, iar pointerul p va adresa zona realocată.  dacă dimensiunea blocului realocat este mai mică decât a blocului iniţial, p nu se modifică, iar funcţia va întoarce valoarea lui p.  dacă dim==0 zona adresată de p va fi eliberată şi funcţia întoarce NULL.  dacă p==NULL, funcţia alocă o zonă de dim octeţi (echivalent cu malloc()). Funcţiile de alocare întorc pointeri generici (void*) la zone de memorie, în timp ce utilizatorul alocă memorie ce păstrează informaţii de un anumit tip. Pentru a putea accesa memoria alocată, indirect, prin intermediul pointerului, acesta va trebui să fie un pointer cu tip, ceea ce impune conversia explicită (prin cast) a pointerului întors de funcţia de alocare într-un pointer cu tip. De exemplu, pentru a aloca un vector de întregi, având n elemente vom folosi: int *p: if (p=(int*)malloc(n*sizeof(int))==NULL) { printf(“Memorie insuficienta\n”); exit(1); }

Funcţiile care întorc pointeri sunt utile în alocarea de spaţiu pentru variabile dinamice. Variabilele dinamice sunt alocate în momentul execuţiei, nu au nume şi sunt accesate prin pointeri. Un constructor este o funcţie care alocă spaţiu în mod dinamic pentru o variabilă şi întoarce un pointer la spaţiul rezervat. Un destructor este o funcţie care primeşte un pointer la o zonă alocată dinamic şi eliberează această zonă. O funcţie utilă, strdup() – salvează un şir de caractere într-o zonă alocată dinamic şi întoarce un pointer la acea zonă sau NULL. char *strdup(char *s)

{ char *p; p=(char*) malloc(strlen(s)+1);

4 if (p!=NULL) stry(p,s); return p; } În C++, alocarea dinamică se face mai simplu şi mai sigur, folosind operatorii new şi delete. Operatorul new permite alocarea de memorie în heap. El se foloseşte într-una din formele: tip *p, *q, *r; p=new tip; //rezerva in heap o zona de sizeof(tip) octeti q=new tip(expresie);//acelasi efect cu initializare cu val.expresiei r=new tip[expint]; //rezerva o zona neinitializata de // expint*sizeof(tip) octeti Eliberarea memoriei alocate se face prin: delete p; delete [] r; //elibereaza memoria alocata pentru tablou

Metoda Greedy Metoda Greedy (greedy=lacom) este aplicabilă problemelor de optim. Considerăm mulţimea finită A={a1,...,an} şi o proprietate p definită pe mulţimea submulţimilor lui A (notată P(A)): p() 1 p:P(A){0,1} cu  p(X) p(Y),Y  X

O submulţime S  A se numeşte soluţie dacă p(S)=1. Dintre soluţii dorim să alegem una care optimizează o funcţie f:P(A)R dată. Metoda urmăreşte evitarea parcurgerii tuturor submulţimilor (ceea ce ar necesita un timp de calcul exponenţial), mergându-se "direct" spre soluţia optimă. Nu este însă garantată obţinerea unei soluţii optime; de aceea aplicarea metodei Greedy trebuie însoţită neapărat de o demonstraţie. Distingem două variante generale de aplicare a metodei Greedy: S for i=1,n xalege(A); AA\{x} if p(S{x})=1 SS{x}

Observaţii:

prel(A) S for i=1,n if p(S{ai})=1 SS{ai}

5 -

în algoritm nu apare funcţia f timpul de calcul este liniar (exceptând prelucrările efectuate de procedurile prel şi alege); dificultatea constă în a concepe procedurile alege, respectiv prel, în care este "ascunsă" funcţia f.

Exemplul 1 Se consideră mulţimea de valori reale A={a1,...,an}. Să se determine o submulţime a lui A a cărei sumă a elementelor este maximă. Soluție. Vom parcurge mulţimea şi vom selecta numai elementele pozitive. Dacă nu există elemente pozitive, soluția este dată de cel mai mare element din mulțime. Corectitudinea soluției este evidentă. Exemplul 2 (Contraexemplu) Se consideră mulţimea A={a1,...,an} cu elemente pozitive. Să se determine o submulţime a lui A de sumă maximă, dar cel mult egală cu o valoare M dată. Dacă alegem la fiecare pas cel mai mare element care poate fi adăugat la soluție fără a depăși M, pentru A={6,3,4,2} şi M=7 obţinem {6}. Dar soluţia optimă este {3,4} cu suma egală cu 7. Continuăm cu prezentarea unor exemple clasice.

 Memorarea textelor pe bandă n texte cu lungimile L(1),...,L(n) urmează a fi aşezate pe o bandă. Pentru a citi textul de pe poziţia k, trebuie citite textele de pe poziţiile 1,2,...,k (conform specificului accesului secvenţial pe bandă). Să se determine o modalitate de așezare a textelor pe bandă astfel încât timpul mediu de acces să fie minimizat. Soluție. O soluţie înseamnă o permutare pSn. Pentru o astfel de permutare (ordine de aşezare a textelor pe bandă), timpul pentru a citi textul de pe poziţie k este: Tp(k)=L(p1)+...+L(pk). Presupunând textele egal probabile, trebuie minimizată valoarea T(p)

1 n  Tp(k). n k1

Să observăm că funcţia T se mai poate scrie: T(p)

1 n (n  k  1)L(pk) n k1

Conform strategiei Greedy, începem prin a ordona crescător vectorul L. Rezultă că în continuare L(i)L(j), i<j.

6 Propoziţie. Dacă L(1)  L(2)  …  L(n) atunci poziţionarea corespunzătoare permutării identice este optimă. Demonstraţie. Fie p  ( p1 , , pn ) o poziţionare optimă (   Sn T ( p)  T ( ) ). Presupunem prin reducere la absurd că p nu este permutarea identică. Rezultă ca există i, j, 1  i  j  n astfel încât L( pi )  L( p j ) . Fie p  permutarea obţinută din p prin interschimbarea poziţiilor i şi j: p  ( p1 , , pi 1 , p j , pi 1 , , p j 1 , pi , p j 1 , T ( p) 

pn ) .

Avem:

n

1  (n  k  1)L( pk ) n k 1

T ( p)  T ( p)  (n  i  1) L( pi )  (n  i  1) L( p j )  (n  j  1) L( p j )  (n  j  1) L( pi ) 

 T ( p)  (i  j ) L( pi )  ( j  1) L( p j )  T ( p)  (i  j )(L( pi )  L( p j ))  T ( p)

Am obţinut T ( p)  T ( p) . Contradicţie! Generalizare. Memorarea a n texte pe m benzi. Strategia Greedy: La fiecare pas se alege textul cel mai scurt dintre cele rămase şi se plasează pe banda cea mai libera. Textele se memorează în ordinea crescătoare a lungimilor lor. Fiecare text se plasează pe banda următoare celei pe care a fost plasat textul anterior. Demonstraţia corectitudinii: temă.

 Problema continuă a rucsacului Se consideră un rucsac de capacitate (greutate) maximă G şi n obiecte caracterizate prin: - greutăţile lor g1,...,gn; - câştigurile c1,...,cn obţinute la încărcarea lor în totalitate în rucsac. Din fiecare obiect poate fi încărcată orice fracţiune a sa. Să se determine o modalitate de încărcare de (fracţiuni de) obiecte în rucsac, astfel încât câştigul total să fie maxim. xi [0,1],i n   gi xi  G i1

Soluție. Prin soluţie înţelegem un vector x=(x1,…,xn) cu 

n

O soluţie optimă este soluţie care maximizează funcţia f(x)  cixi . i1

Dacă suma greutăţilor obiectelor este mai mică decât G, atunci încărcăm toate obiectele: x=(1,...,1). De aceea presupunem în continuare că g1+...+gn>G. Conform strategiei Greedy, ordonăm obiectele descrescător după câştigul la unitatea de greutate, deci lucrăm în situaţia:

7 c1 c2 c  ... n g1 g2 gn

(*)

Algoritmul constă în încărcarea în această ordine a obiectelor, atâta timp cât nu se depăşeşte greutatea G (ultimul obiect poate fi eventual încărcat parţial): G1  G { G1 reprezintă greutatea disponibilă } for i=1,n if giG1 xi1; G1G1-gi else xiG1/gi; for j=i+1,n xj  0 stop write(x)

Am obţinut deci x=(1,...,1,xj,0,...,0) cu xj[0,1). Corectitudine. Arătăm că soluţia astfel obţinută este optimă. Fie y soluţia optimă care are cele mai multe elemente în comun cu x: n   giyi  G y=(...,yk,...) cu i1 n   c y maxim i1 i i

Dacă yx, fie k prima poziţie pe care ykxk. Atunci avem 

kj: pentru k>j se depăşeşte G.



yk<xk:

– pentru k<j: evident, deoarece xk=1; – pentru k=j: dacă yk>xk se depăşeşte G. Considerăm soluţia: y’=(y1,...,yk-1,xk,yk+1,..., yn) cu <1 (primele k-1 componente coincid cu cele din x). Păstrăm greutatea totală G, deci: gkxk+(gk+1yk+1+...+gnyn)=gkyk+gk+1yk+1+...+gnyn.

Rezultă: gk(xk-yk)=(1-)(gk+1yk+1+…+gnyn)

Comparăm performanţa lui y' cu cea a lui y:

(**)

8 f(y’)-f(y) = ckxk +ck+1yk+1 +...+ cnyn - (ckyk+ck+1yk+1 +...+cnyn) = = ck(xk-yk) + (-1)(ck+1yk+1+...+cnyn) = = ck/gk[gk(xk-yk)+(-1)(gk/ckck+1yk+1+...+gk/ckcnyn)]

Dar -1<0 şi gk/ck gs/cs, s>k. Atunci f(y’)-f(y)ck/gk [gk(xk-yk)+(-1)(gk+1yk+1+...+gnyn)]=0, deci f(y')  f(y). Deoarece y este optimă, rezultă că f(y') = f(y). Contradicţie (y' are mai multe elemente în comun cu x). Problema discretă a rucsacului diferă de cea continuă prin faptul că fiecare obiect poate fi încărcat numai în întregime în rucsac. Să observăm că aplicarea metodei Greedy eşuează în acest caz. Într-adevăr, aplicarea ei pentru: G=5, n=3 şi g=(4,3,2), c=(6,4,2.5) are ca rezultat încărcarea primul obiect; câştigul obţinut este 6. Dar încărcarea ultimelor două obiecte conduce la câştigul superior 6.5.

Exerciţii 1. Problema spectacolelor: Se dau n spectacole prin ora de început și ora de sfârșit. Să se selecteze dintre aceste spectacole un număr maxim de spectacole care nu se suprapun. 2. Se dau mulțimile de numere întregi nenule A  {a1 , a2 , , am } și B  {b1 , b2 , , bn } , unde m ≤ n. Să se determine o submulțime B  {x1 , x2 , , xm } a lui B astfel încât suma a1 x1  a2 x2 

 am xm să fie maximă şi să se precizeze cum s-a obţinut.

3. Se dau n compozitori şi pentru fiecare dintre ei anii de viaţă. Să se tipărească numărul maxim de compozitori contemporani. 4. Interclasarea optimă a n șiruri ordonate. Se dau lungimile a n șiruri ordonate, L1 , L2 , , Ln . Dorim să obținem un șir ordonat crescător care conține toate elementele celor n șiruri inițiale, interclasând succesiv perechi de șiruri. Știind că interclasarea a două șiruri de lungimi A, respectiv B, necesită A+B deplasări, să se determine o ordine în care trebuie să se realizeze interclasările astfel încât numărul total de deplasări să fie minim.