Analiza Algoritmilor · 2015 · Sesiune
- Profesor
- Andrei Mogos
- Anul examenului
- 2015
- Sesiune
- Sesiune
- Serie
- CC
- Grupă
- 321
- Adăugat
- 22 ianuarie 2015 de anonim
22.01.2015
321CC + 322CC - NR 2
1p oficiu
(1.5p) 1. Aratati ca Hom(N,N) este ∞ - nenumarabila.
(1.5p) 2. Prezentati inductia bine formata (definitii, exemple, schema, fara demonstratii).
(1p) 3. Prezentati metoda potentialului.
(1p) 4. Definiti conceptul de graf compus si dati un exemplu.
(1p) 5. Calculati complexitatea spatiala a algoritmului:
(1.5p) 6. Rezolvati folosind metoda substitutiei (se va folosi clasa θ):
(1.5p) 7. Definim problema Q6: "Fie G = (V,E) un graf neorientat. Numim multime de tip 0 a lui G o multime D ⊆ V astfel incat ∀ x ϵ V - D , {y | y ϵ D, (x,y) ϵ E} = Ø. Notam cu D0(G) cardinalul celei mai mari multimi de tip 0 a lui G. Fie k ϵ N*. Stabiliti daca D0(G) = k". Aratati ca problema Q6 este in NP.
321CC + 322CC - NR 2
1p oficiu
(1.5p) 1. Aratati ca Hom(N,N) este ∞ - nenumarabila.
(1.5p) 2. Prezentati inductia bine formata (definitii, exemple, schema, fara demonstratii).
(1p) 3. Prezentati metoda potentialului.
(1p) 4. Definiti conceptul de graf compus si dati un exemplu.
(1p) 5. Calculati complexitatea spatiala a algoritmului:
Alg(n) {
r = 0
for (i = 1; i <= n; i++)
r = r + i*i
return r
}(1.5p) 6. Rezolvati folosind metoda substitutiei (se va folosi clasa θ):
T(n) = 3 * T(floor(n/5)) + k2 * n², n > 1 si T(1) = k1
(1.5p) 7. Definim problema Q6: "Fie G = (V,E) un graf neorientat. Numim multime de tip 0 a lui G o multime D ⊆ V astfel incat ∀ x ϵ V - D , {y | y ϵ D, (x,y) ϵ E} = Ø. Notam cu D0(G) cardinalul celei mai mari multimi de tip 0 a lui G. Fie k ϵ N*. Stabiliti daca D0(G) = k". Aratati ca problema Q6 este in NP.