|
|
|
|
· Algoritamske strategije
· Hofmanov kôd
· Trazenje uzorka u tekstu
A. Hofmanov kôd je prefiksni kôd.
B. Slozenost algoritma KMP zavisi od broja simbola u azbuci teksta i uzorka.
C. Obilazak binarnog stabla po nivoima ne moze se implementirati iterativno.
D. Nalazenje n-tog clana Fibonacijevog clana niza ne moze se implementirati rekurzivno.
E. Eliminacija repne rekurzije ne moze se realizovati bez upotrebe steka.
F. Algoritam merge-sort je primer strategije “podeli-pa-vladaj”.
G. U Hafmanovom stablu, dva lista sa najmanjim frekvencijama imaju istog roditelja.
H. Algoritam binarne pretrage je primer backtracking strategije.
I. Za mnozenje kvadratne matrice reda 2 samom sobom mora se upotrebiti bar 2*2*2 mnozenja.
J. Hafmanov .kôd se jedinstveno desifruje.
Zadatak 2. Modifikovati algoritam KMP tako da za dati tekst S i uzorak P pronalazi najveci moguci prefiks uzorka P koji kao podstring postoji u tekstu S.
Zadatak 3. Odredite pomocni niz za KMP algoritam za uzorak P=acggca iz 3 slovne azbuke {a,c,g}.
Zadatak 4. Optimalnim binarnim prefiksnim kôdom kôdirati rečenicu: BEZ MUKE NEMA NAUKE.
Zadatak 5: Ako je data tabela simbola sa frekvencijama
|
simbol |
1 |
2 |
3 |
4 |
|
fi |
8 |
6 |
4 |
3 |
konstruisite Hafmanovo stablo, odredite Hafmanov kôd, kodirajte recenicu 234431
Zadatak 6. Ako je dat algoritam za množenje dve n * n donje trougaone matrice čije vreme izvršavanja je O(T(n)), dokazati da postoji algoritam za mnozenje dve proizvoljne n *n matrice čije vreme izvršavanja je O(T(n)+n2 ). (Može se pretpostaviti da je T(cn)=O(T(n)) za svaku konstantu c)
Zadatak 7: Konstruisati algoritam koji ce za niz sa standardnog ulaza ispisati indekse onih elemenata niza ciji je zbir jednak broju koji se takodje unosi sa standardnog ulaza.
Zadatak 8: Konstruisati algoritam koji za datu sumu S i dati niz v koji sadrzi vrednosti novcanica pronalazi sva resenja za rasitnjavanja sume S. Pretpostaviti da svake novcanice ima proizvoljno mnogo.
|
|
|
|
