Subiecte de examen la Algoritmi i Calculabilitate

- 8 iulie 2011 -

1) Considerm c avem m tipuri de monezi de valori S[1], S[2] .. S[m]. Scriei algoritmul greedy care exprim o sum x folosind un numr minim de monezi, folosind tipurile date. Presupunem c avem disponibile un numr infinit de monezi din fiecare tip.

2) Timpul pentru algoritmul mergesort se exprim recursiv astfel:

t(n) = { 1, pentru n=12t(n /2)+n , pentru n>1Analizai ordinul de timp al algoritmului (demonstrai care care este ordinul de timp).

3) Pentru graful orientat din figur:function Dijkstra(L[1..n, 1..n])

C {2, 3, .., n}for i 2 to n do D[i] L[1, i]repeat n-2 times

v vrful din C care minimizeaz D[v]C C \ {v}for fiecare w din C do

D[w] min(D[w], D[v]+L[v,w])return D

Determinai cele mai scurte drumuri de la vrful 1 la toate celelalte vrfuri folosind algoritmul lui Dijkstra.

Realizai un tabel indicnd, la fiecare pas, numrul iteraiei (pasul), vrful v selectat, setul C precum i valorile tabloului D. Indicai drumurile (vrfurile care le compun) precum i costurile lor.

4) Fie o secven T[1..n] de ntregi nenegativi distinci, ordonai cresctor. Pentru un k ntreg care nu se cunoate, 1 < k < n, se realizeaz o tietur n ir. Un al doilea ir, S = {T[k+1], T[k+2] .., T[n], T[1], T[2], .., T[k]} se obine astfel din T, prin concatenarea irurilor T[k+1 .. n] i T[1 .. k]. Realizai un algoritm eficient (cu timp subliniar) care gsete poziia unui ntreg x n irul S. Dac elementul x nu exist, algoritmul va ntoarce un indice invalid (-1).

5) Analizai ordinul de timp al urmtorului algoritm:

Toate subiectele sunt notate cu 2p n afara subiectului 2 care este notat cu 1p. Se acord 1p din oficiu.

for i 1 to n doj iwhile j > 0 do

j j div 2

Ce instruciune barometru alegei ? De cte ori se execut aceasta? Justificai.