Post on 07-Feb-2018
- 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ă