Cilj predmeta
Sticanje opšteg znanja iz struktura podataka i algoritama.
Ishod predmeta
Student je u stanju da rešava algoritamske probleme. Zna da koristi osnovne strukture podataka i algoritme. Poznaje algoritamske paradigme i prepoznaje klase problema koje one rešavaju. Razume vreme izvršavanja algoritama i poznaje načine za njihovo određivanje.
Sadržaj predmeta
Teorijska nastava
Linearne strukture. Nelinearne strukture. Stabla. Grafovi. Pretraživanje. Osnovni metod i poboljšanja. Stablo binarnog pretraživanja, AVL stabla, optimalno stablo. Stablo m-arnog pretraživanja. B, B* i B+ stabla, stabla digitalnog pretraživanja. Sortiranje. Vremenska i prostorna složenost. Izračunavanje konačnih suma, rekurentne relacije, master teorema. Dinamičko programiranje. Algoritmi grube sile. Pohlepni algoritmi. Rekurzivna strategija zasnovana na razlaganju. Pretraga sa vraćanjem, grananje sa odsecanjem, heuristike. Traženje uzorka u tekstu. Protočne mreže i određivanje maksimalnog protoka u mreži. Primeri numeričkih algoritama. Implementacija rekurzije. Svođenje repne rekurzije na iteraciju. Distribuirani i paralelni algoritmi. Algoritmi (protokoli) komunikacije, sinhroni i asinhroni algoritmi. Algoritmi sinhronzacije
Praktična nastava
Implementacija struktura koje su prikazane na predavanjima: povezane liste, stek, red, binarno stablo, prioritetni red, binarno pretraživačko stablo, AVL stablo, B stablo, heš tabele. Implementacija nekih od algoritama koji su prikazani na predavanjima. Prepoznavanje algoritamske paradigme (dinamičko programiranje, pohlepni algoritmi, podeli pa vladaj, bektrek, itd.) koja može biti primenjena pri rešavanju algoritamskih problema. Razvoj raznih algoritama za rešavanje jednog istog algoritamskog problema, uz poređenje složenosti. Neki algoritmi za rešavanje NP teških problema.