PRIMENE RAČUNARA - septembar 2003.

1. Zadata su dva niza znakova iz konačnog alfabeta A = a_{1}a_{2}...a_{n} (tekst) i B = b_{1}b_{2}...b_{m} (uzorak). Konstruisati algoritam čija vremenska složenost ne zavisi od veličine alfabeta, a koji u tekstu A pronalazi najveći mogući prefiks uzorka B i odrediti vremensku složenost konstruisanog algoritma.

2. Konstruisati algoritam koji za data dva binarna stabla testira njihovu jednakost.

3. Dokazati da ako postoji algoritam složenosti O(T (n)) za množenje dve n × n donje trougaone matrice, onda postoji algoritam složenosti O(T (n) + n^{2}) za množenje dve proizvoljne n × n matrice. Pri tome se može koristiti pretpostavka da je T (cn) = O(T (n)) za proizvoljnu konstant c > 0.

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. Dokazati NP -kompletnost problema koji ustanovljuje da li G sadrži kliku veličine k i nezavisni skup veličine k.

PRIMENE RAČUNARA - septembar 2003.

1. Zadata su dva niza znakova iz konačnog alfabeta A = a_{1}a_{2}...a_{n} (tekst) i B = b_{1}b_{2}...b_{m} (uzorak). Konstruisati algoritam čija vremenska složenost ne zavisi od veličine alfabeta, a koji u tekstu A pronalazi najveći mogući prefiks uzorka B i odrediti vremensku složenost konstruisanog algoritma.

2. Konstruisati algoritam koji za data dva binarna stabla testira njihovu jednakost.

3. Dokazati da ako postoji algoritam složenosti O(T (n)) za množenje dve n × n donje trougaone matrice, onda postoji algoritam složenosti O(T (n) + n^{2}) za množenje dve proizvoljne n × n matrice. Pri tome se može koristiti pretpostavka da je T (cn) = O(T (n)) za proizvoljnu konstant c > 0.

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. Dokazati NP -kompletnost problema koji ustanovljuje da li G sadrži kliku veličine k i nezavisni skup veličine k.

PRIMENE RAČUNARA - septembar 2003.

1. Zadata su dva niza znakova iz konačnog alfabeta A = a_{1}a_{2}...a_{n} (tekst) i B = b_{1}b_{2}...b_{m} (uzorak). Konstruisati algoritam čija vremenska složenost ne zavisi od veličine alfabeta, a koji u tekstu A pronalazi najveći mogući prefiks uzorka B i odrediti vremensku složenost konstruisanog algoritma.

2. Konstruisati algoritam koji za data dva binarna stabla testira njihovu jednakost.

3. Dokazati da ako postoji algoritam složenosti O(T (n)) za množenje dve n × n donje trougaone matrice, onda postoji algoritam složenosti O(T (n) + n^{2}) za množenje dve proizvoljne n × n matrice. Pri tome se može koristiti pretpostavka da je T (cn) = O(T (n)) za proizvoljnu konstant c > 0.

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. Dokazati NP -kompletnost problema koji ustanovljuje da li G sadrži kliku veličine k i nezavisni skup veličine k.

PRIMENE RAČUNARA - septembar 2003.

1. Zadata su dva niza znakova iz konačnog alfabeta A = a_{1}a_{2}...a_{n} (tekst) i B = b_{1}b_{2}...b_{m} (uzorak). Konstruisati algoritam čija vremenska složenost ne zavisi od veličine alfabeta, a koji u tekstu A pronalazi najveći mogući prefiks uzorka B i odrediti vremensku složenost konstruisanog algoritma.

2. Konstruisati algoritam koji za data dva binarna stabla testira njihovu jednakost.

3. Dokazati da ako postoji algoritam složenosti O(T (n)) za množenje dve n × n donje trougaone matrice, onda postoji algoritam složenosti O(T (n) + n^{2}) za množenje dve proizvoljne n × n matrice. Pri tome se može koristiti pretpostavka da je T (cn) = O(T (n)) za proizvoljnu konstant c > 0.

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. Dokazati NP -kompletnost problema koji ustanovljuje da li G sadrži kliku veličine k i nezavisni skup veličine k.

2