PRIMENE RAČUNARA - februar 2004.

1. Opisati realizaciju apstraktnog tipa podataka koji podržava sledeće operacije: Umetni(x): umetanje ključa x u strukturu podataka, ako već nije prisutan u njoj Obriši(x): brisanje ključa x iz strukture podataka (ako postoji) Naredni(x): pronalaženje najmanjeg ključa u strukturi podataka koji je veći od x Izvršavanje svake od navedenih operacija treba da ima vremensku složenost O(log n) u najgorem slučaju, gde je n broj elemenata u strukturi podataka.

2. Dat je usmereni graf G = (V, E) sa skupom čvorova V = {1,2,3,4} i skupom grana E sa dužinama redom

\begin{aligned}E = \{ & (1,2), & (2,3), & (3,4), & (4,1), & (2,4), & (1,3) \} \\ & 3 & 4 & 8 & 6 & 3 & 9 \end{aligned}

Odrediti sve najkraće puteve izmedju čvorova ovog grafa.

3. Konstruisati algoritam koji prirodan broj n ≥ 3 predstavlja u obliku sume najviše log_{2} n različitih Fibonačijevih brojeva. Dokazati korektnost algoritma. Fibonačijevi brojevi su definisani rekurentnom formulom: F (n) = F (n − 1) + F (n − 2), n > 2, F (1) = F (2) = 1.

4. Dokazati NP -kompletnost slededećeg problema: Zadat je Bulov izraz u KNF u kome svaka klauza sadrži tačno tri literala. Ustanoviti da li izraz jeste zadovoljiv.