PRIMENE RAČUNARA - oktobar 2003.

1. Posmatrajmo nizove prirodnih brojeva dužine n, takve da broj različitih elemenata u njima je O(log n). Konstruisati algoritam za sortiranje niza takav da se u okviru njega izvršava najviše O(n log log n) uporedjivanja brojeva. Da li je složenost ovog algoritma manja od donje granice Ω(n log n) za sortiranje? Obrazložiti odgovor.

2. Polazeći od Grejovog kôda dužine 2: 0 1 konstruisati Grejov kôd dužine 6 i 10 sa minimalnom dužinom blokova bita.

3. 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.

4. Nezavisan skup u grafu G = (V, E) je podskup čvorova grafa u kome izmedju ma koja dva njegova elementa ne postoji grana. Neka je dat neusmereni povezan graf G = (V, E) i prirodan broj k. Potrebno je ustanoviti da li G sadrži kliku veličine k i nezavisni skup veličine k. Dokazati da je ovaj problem NP -kompletan.

PRIMENE RAČUNARA - oktobar 2003.

1. Posmatrajmo nizove prirodnih brojeva dužine n, takve da broj različitih elemenata u njima je O(log n). Konstruisati algoritam za sortiranje niza takav da se u okviru njega izvršava najviše O(n log log n) uporedjivanja brojeva. Da li je složenost ovog algoritma manja od donje granice Ω(n log n) za sortiranje? Obrazložiti odgovor.

2. Polazeći od Grejovog kôda dužine 2: 0 1 konstruisati Grejov kôd dužine 6 i 10 sa minimalnom dužinom blokova bita.

3. 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.

4. Nezavisan skup u grafu G = (V, E) je podskup čvorova grafa u kome izmedju ma koja dva njegova elementa ne postoji grana. Neka je dat neusmereni povezan graf G = (V, E) i prirodan broj k. Potrebno je ustanoviti da li G sadrži kliku veličine k i nezavisni skup veličine k. Dokazati da je ovaj problem NP -kompletan.

PRIMENE RAČUNARA - oktobar 2003.

1. Posmatrajmo nizove prirodnih brojeva dužine n, takve da broj različitih elemenata u njima je O(log n). Konstruisati algoritam za sortiranje niza takav da se u okviru njega izvršava najviše O(n log log n) uporedjivanja brojeva. Da li je složenost ovog algoritma manja od donje granice Ω(n log n) za sortiranje? Obrazložiti odgovor.

2. Polazeći od Grejovog kôda dužine 2: 0 1 konstruisati Grejov kôd dužine 6 i 10 sa minimalnom dužinom blokova bita.

3. 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.

4. Nezavisan skup u grafu G = (V, E) je podskup čvorova grafa u kome izmedju ma koja dva njegova elementa ne postoji grana. Neka je dat neusmereni povezan graf G = (V, E) i prirodan broj k. Potrebno je ustanoviti da li G sadrži kliku veličine k i nezavisni skup veličine k. Dokazati da je ovaj problem NP -kompletan.

PRIMENE RAČUNARA - oktobar 2003.

1. Posmatrajmo nizove prirodnih brojeva dužine n, takve da broj različitih elemenata u njima je O(log n). Konstruisati algoritam za sortiranje niza takav da se u okviru njega izvršava najviše O(n log log n) uporedjivanja brojeva. Da li je složenost ovog algoritma manja od donje granice Ω(n log n) za sortiranje? Obrazložiti odgovor.

2. Polazeći od Grejovog kôda dužine 2: 0 1 konstruisati Grejov kôd dužine 6 i 10 sa minimalnom dužinom blokova bita.

3. 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.

4. Nezavisan skup u grafu G = (V, E) je podskup čvorova grafa u kome izmedju ma koja dva njegova elementa ne postoji grana. Neka je dat neusmereni povezan graf G = (V, E) i prirodan broj k. Potrebno je ustanoviti da li G sadrži kliku veličine k i nezavisni skup veličine k. Dokazati da je ovaj problem NP -kompletan.