PRIMENE RAČUNARA - oktobar 2003.

1.Zadat je graf G = (V, E). Konstruisati algoritam složenosti O(|E|+|V |) koji u slučaju acikličkog grafa G daje topološko uredjenje čvorova grafa, a u suprotnom pronalazi neki ciklus u grafu G.

2. Odrediti edit rastojanje stringova abbcba i babbcb i naći bar jedan niz edit operacija najmanje cene koji prvi string transformiše u drugi string. Dozvoljene su tri vrste edit operacija koje imaju cenu 1: umetanje karaktera, brisanje karaktera i zamena jednog karaktera drugim.

3. Dat je skup od n duži koje pripadaju jednoj pravoj. (Duži su predstavljene svojim krajnjim tačkama). Konstruisati algoritam složenosti O(n log n) za odredjivanje svih duži koje nisu sadržane u nekoj drugoj duži iz skupa.

4. Neka je dat neusmereni graf G = (V, E) prirodan broj k. Dokazati NP -kompletnost problema koji ustanovljuje da li u G postoji dominirajući skup sa najviše k čvorova. Smatrati da skup D ⊂ V je dominirajući ako svaki čvor grafa G se nalazi u skupu D ili je susedan bar jednom čvoru iz skupa D.

PRIMENE RAČUNARA - oktobar 2003.

1.Zadat je graf G = (V, E). Konstruisati algoritam složenosti O(|E|+|V |) koji u slučaju acikličkog grafa G daje topološko uredjenje čvorova grafa, a u suprotnom pronalazi neki ciklus u grafu G.

2. Odrediti edit rastojanje stringova abbcba i babbcb i naći bar jedan niz edit operacija najmanje cene koji prvi string transformiše u drugi string. Dozvoljene su tri vrste edit operacija koje imaju cenu 1: umetanje karaktera, brisanje karaktera i zamena jednog karaktera drugim.

3. Dat je skup od n duži koje pripadaju jednoj pravoj. (Duži su predstavljene svojim krajnjim tačkama). Konstruisati algoritam složenosti O(n log n) za odredjivanje svih duži koje nisu sadržane u nekoj drugoj duži iz skupa.

4. Neka je dat neusmereni graf G = (V, E) prirodan broj k. Dokazati NP -kompletnost problema koji ustanovljuje da li u G postoji dominirajući skup sa najviše k čvorova. Smatrati da skup D ⊂ V je dominirajući ako svaki čvor grafa G se nalazi u skupu D ili je susedan bar jednom čvoru iz skupa D.

PRIMENE RAČUNARA - oktobar 2003.

1.Zadat je graf G = (V, E). Konstruisati algoritam složenosti O(|E|+|V |) koji u slučaju acikličkog grafa G daje topološko uredjenje čvorova grafa, a u suprotnom pronalazi neki ciklus u grafu G.

2. Odrediti edit rastojanje stringova abbcba i babbcb i naći bar jedan niz edit operacija najmanje cene koji prvi string transformiše u drugi string. Dozvoljene su tri vrste edit operacija koje imaju cenu 1: umetanje karaktera, brisanje karaktera i zamena jednog karaktera drugim.

3. Dat je skup od n duži koje pripadaju jednoj pravoj. (Duži su predstavljene svojim krajnjim tačkama). Konstruisati algoritam složenosti O(n log n) za odredjivanje svih duži koje nisu sadržane u nekoj drugoj duži iz skupa.

4. Neka je dat neusmereni graf G = (V, E) prirodan broj k. Dokazati NP -kompletnost problema koji ustanovljuje da li u G postoji dominirajući skup sa najviše k čvorova. Smatrati da skup D ⊂ V je dominirajući ako svaki čvor grafa G se nalazi u skupu D ili je susedan bar jednom čvoru iz skupa D.

PRIMENE RAČUNARA - oktobar 2003.

1.Zadat je graf G = (V, E). Konstruisati algoritam složenosti O(|E|+|V |) koji u slučaju acikličkog grafa G daje topološko uredjenje čvorova grafa, a u suprotnom pronalazi neki ciklus u grafu G.

2. Odrediti edit rastojanje stringova abbcba i babbcb i naći bar jedan niz edit operacija najmanje cene koji prvi string transformiše u drugi string. Dozvoljene su tri vrste edit operacija koje imaju cenu 1: umetanje karaktera, brisanje karaktera i zamena jednog karaktera drugim.

3. Dat je skup od n duži koje pripadaju jednoj pravoj. (Duži su predstavljene svojim krajnjim tačkama). Konstruisati algoritam složenosti O(n log n) za odredjivanje svih duži koje nisu sadržane u nekoj drugoj duži iz skupa.

4. Neka je dat neusmereni graf G = (V, E) prirodan broj k. Dokazati NP -kompletnost problema koji ustanovljuje da li u G postoji dominirajući skup sa najviše k čvorova. Smatrati da skup D ⊂ V je dominirajući ako svaki čvor grafa G se nalazi u skupu D ili je susedan bar jednom čvoru iz skupa D. z skupa.am složenosti O(n log n) za document pth @ ... Ωȷ*ffi*ıΘΔD@input twocolum.sty