Analiza Algoritmilor · 2015 · Sesiune

1p oficiu

(1.5p) 1. Fie A ⊆ N o multime. Aratati ca exista o functie recursiva f : A → N <=> exista un generator al lui A.

(1.5p) 2. Demonstrati urmatoarea propozitie: Fie a ϵ N^*, b ϵ R, b > 1 constante, f : {1, b, b², ...}→ R^* o functie si g : {1, b, b², ...}→ R₊^* o functie de forma: g(n) = Σ(j=0 to log_b(n-1)) aʲ * f(n/bʲ). Atunci, daca ∃ c ϵ (0,1), ∃ n₀ ϵ N^* astfel incat a*f(n/b) ≤ c * f(n), ∀ n ≥ n₀, atunci g(n) = θ(f(n)).

(1p) 3. Teorma Cook: Serial, Stop (formule + explicatii)

(1p) 4. Fie relatia < peste intervalul [5, 17]. Stabiliti daca relatia < este bine formata.

(1p) 5. Descrieti pe scurt algoritmul de aproximare Khuller-Vishkin pentru problema λ-arc conectivitate.

(1.5p) 6. Rezolvati folosing metoda substitutiei:

    T(n) = 3 * T(ceiling(n/7)) + k2 * n³, n > 1 si T(1) = k1

(1.5p) 7. Fie G = (V, E) un graf neorientat. Notam cu k_card(G) cel mai mic numar natural k pentru care ∃ v₁, v₂, ..., v_k submultimi ale lui V astfel incat sa fie indeplinite simultan conditiile:

    a) Vi ∩ Vj = Ø, ∀ i ≠ j

       ⋃ Vi = V, i = 1..k

    b) ∀ i = 1..k, ∀ u,v ϵ Vi avem (u,v) ∉ E

Notam cu Q(k) problema de decizie: k_card(G) = k ?

Sa se stabileasca daca Q(k) ϵ NP.