PRIMENE RAČUNARA - jun 2003.

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. Kodirati sledeću rečenicu optimalnim binarnim prefiksnim kodom: SVAKA PTICA SVOME JATU LETI

3. Dat je usmereni graf G = (V, E) i njegov čvor v ∈ V. Konstruisati algoritam složenosti O(|E| + |V |) koji ispituje da li G jeste korensko stablo sa korenom v. Smatrati da su u korenskom stablu grane usmerene od korena ka listovima.

4. Dokazati NP -kompletnost problema klika.

PRIMENE RAČUNARA - jun 2003.

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. Kodirati sledeću rečenicu optimalnim binarnim prefiksnim kodom: SVAKA PTICA SVOME JATU LETI

3. Dat je usmereni graf G = (V, E) i njegov čvor v ∈ V. Konstruisati algoritam složenosti O(|E| + |V |) koji ispituje da li G jeste korensko stablo sa korenom v. Smatrati da su u korenskom stablu grane usmerene od korena ka listovima.

4. Dokazati NP -kompletnost problema klika.

PRIMENE RAČUNARA - jun 2003.

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. Kodirati sledeću rečenicu optimalnim binarnim prefiksnim kodom: SVAKA PTICA SVOME JATU LETI

3. Dat je usmereni graf G = (V, E) i njegov čvor v ∈ V. Konstruisati algoritam složenosti O(|E| + |V |) koji ispituje da li G jeste korensko stablo sa korenom v. Smatrati da su u korenskom stablu grane usmerene od korena ka listovima.

4. Dokazati NP -kompletnost problema klika.