- 1 -

Universitatea Al.I.Cuza Iasi Facultatea de Informatică

Nume: Grupa:

Tehnici de proiectarea şi analiza algoritmilor – Test scris 30.01.12 (B) Observaţii: 1. Nu este permisă consultarea bibliografiei. 2. Toate întrebările sunt obligatorii. 3. Fiecare întrebare este notată cu un număr de puncte indicat în paranteză. Alegerea corectă a variantei la întrebările grila se punctează numai dacă justificarea este total sau parţial corectă. 4. Nu este permisă utilizarea de foi suplimentare. 1. (2.5p)    Se  consideră  următoarea  problemă  LDE:  

Instanță:  trei  numere  întregi  pozitive  a,  b  și  c;  Întrebare:  există  numerele  întregi    pozitive  x  și  y  astfel  încât    a*x  +  b*y  =  c?  

a. Să  se  scrie  un  algoritm  care  rezolvă  LDE.  b. Să  se  determine  numărul  de  operații  elementare  executate  de  algoritm  în  cazul  cel  mai  nefavorabil.  c. Să  se  determine  complexitatea  în  cazul  cel  mai  nefavorabil  luând  ca  dimensiunea  a  instanței  lungimea  reprezentării  

lui  c:  n  =  log  c.    Comparați  cu  rezultatul  obținut  la  b.  și  explicați  diferența.  Răspuns.  

 

                       2. (2p)    a.  Să  se  construiască  un  arbore  bicolor    de  inălțime  minimă  de  noduri  care  reprezintă  mulțimea  {3,  5,  8,  12,  15,  21,  34,  

35}.    b.  Să  se  explice  cum  se  aplică  algoritmul  de  inserare  pentru  a  adăuga  17  la  arborele  de  la  a.  

Răspuns  +  justificare.  

           

- 2 -

                                   3. (2p)      Se  consideră  următoarea  instanță  a  problemei  rucsacului  varianta  0/1  (discretă):    n  =  3  (numărul  de  obiecte),  M  =  7  

(capacitate  rucsac),  w=(2,  3,  5)  (greutăți),    p  =  (6,  8,  7)  (profituri).      a.  Să  se  aplice  algoritmul  greedy  pentru  rezolvarea  instanței.  Explicați.  b.  Să  se  aplice  algoritmul  de  programare  dinamică  pentru  rezolvarea  instanței.  Explicați.  Răspuns.  

 

                                               

- 3 -

 4. (1.5p)    Se  consideră  următoarea  extensie  a  problemei  LDE  de  la  Exercițiul  1,  notată  cu  QDE:    

Instanță:  trei  numere  întregi  pozitive  a,  b  și  c;  Întrebare:  există  numerele  întregi  x  și  y  astfel  încât    a*x*x  +  b*y  =  c?  

a. Să  se  arate  că  QDE  este  în  NP.  b. Să  se  precizeze  dacă  QDE  este  pseudo-­‐polinomiala.  Justificați  răspunsul.  Răspuns.  

 

 

         5.  (1p)      Să  se  descrie  un  algoritm  probabilist  Monte  Carlo  care  rezolvă  problema  QDEde  la    Exercițiul  4.    Să  se  calculeze  media  variabilei  aleatoare  care  descrie  ieșirea.  Răspuns.  

 

 

 

- 4 -

Ciornă