Cilj i ishod predmeta
Sticanje znanja iz dizajna i analize algoritama. Student je u stanju da u daljem obrazovanju u stručnim predmetima rešava algoritamske probleme. Zna da koristi osnovne i složenije strukture podataka i algoritme. Razume probleme dokaza ispravnosti algoritama i matematičke alate za njihovo pokazivanje. Poznaje algoritamske paradigme i prepoznaje klase problema koje one rešavaju. Razume vreme izvršavanja algoritama i poznaje načine za njihovo određivanje.
Teorijska nastava
Analiza algoritama. Primeri dokaza ispravnosti algoritama. Asimptotska analiza najgoreg i/ili prosečnog slučaja. Asimptotske oznake O, o, , , . Vremenska i prostorna složenost. Izračunavanje konačnih suma, rekurentne relacije, master teorema. Dinamičko programiranje. Algoritmi grube sile. Pohlepni (greedy) algoritmi. Rekurzivna strategija zasnovana na razlaganju (divide-and-conquer). Pretraga sa vraćanjem (backtracking), grananje sa odsecanjem (branch-and-bound), heuristike. Traženje uzorka u tekstu. Protočne mreže i određivanje maksimalnog protoka u mreži. Uparivanje u grafovima. Primeri numeričkih algoritama. Implementacija rekurzije. Svođenje repne rekurzije (tail recursion) na iteraciju.
Praktična nastava
Implementacija nekog od algoritama koji su prikazani na predavanjima. Dizajn i analiza algoritama za razne algoritamske probleme. Poseban akcenat na prepoznavanju algoritamske paradigme (dinamičko programiranje, pohlepni algoritmi, podeli pa vladaj, bektrek, itd.) koja može biti primenjena pri rešavanju algoritamskih problema. Razvoj (ako je moguće) raznih algoritama za rešavanje jednog istog algoritamskog problema, uz poređenje složenosti (vremenske i prostorne/memorijske).