PRIMENE RAČUNARA - septembar 2004.

1. Dat je aciklički usmereni graf G = (V, E). Konstruisati algoritam linearne složenosti koji utvrdjuje da li u grafu G postoji neki prost put koji sadrži sve čvorove grafa.

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 koordinatama svojih krajnjih tačaka). 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 F je ma koji ulaz za problem 3SAT. Da li se može u polinomijalnom vremenu konstruisati graf G = (V, E) tako da važi da G jeste 3-obojiv akko F jeste zadovoljiv. Odgovor obrazložiti.

PRIMENE RAČUNARA - septembar 2004.

1. Dat je aciklički usmereni graf G = (V, E). Konstruisati algoritam linearne složenosti koji utvrdjuje da li u grafu G postoji neki prost put koji sadrži sve čvorove grafa.

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 koordinatama svojih krajnjih tačaka). 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 F je ma koji ulaz za problem 3SAT. Da li se može u polinomijalnom vremenu konstruisati graf G = (V, E) tako da važi da G jeste 3-obojiv akko F jeste zadovoljiv. Odgovor obrazložiti.

PRIMENE RAČUNARA - septembar 2004.

1. Dat je aciklički usmereni graf G = (V, E). Konstruisati algoritam linearne složenosti koji utvrdjuje da li u grafu G postoji neki prost put koji sadrži sve čvorove grafa.

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 koordinatama svojih krajnjih tačaka). 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 F je ma koji ulaz za problem 3SAT. Da li se može u polinomijalnom vremenu konstruisati graf G = (V, E) tako da važi da G jeste 3-obojiv akko F jeste zadovoljiv. Odgovor obrazložiti.

PRIMENE RAČUNARA - septembar 2004.

1. Dat je aciklički usmereni graf G = (V, E). Konstruisati algoritam linearne složenosti koji utvrdjuje da li u grafu G postoji neki prost put koji sadrži sve čvorove grafa.

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 koordinatama svojih krajnjih tačaka). 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 F je ma koji ulaz za problem 3SAT. Da li se može u polinomijalnom vremenu konstruisati graf G = (V, E) tako da važi da G jeste 3-obojiv akko F jeste zadovoljiv. Odgovor obrazložiti.