Algoritmi

Cilj i ishod predmeta

Obrazovni cilj predmeta je analiza i primena koncepata teorije algoritama. Algoritmi se pojavljuju u gotovo svakoj grani informatike, kao i inženjerskim naukama, biologiji, itd. Svaki problem koji se pojavi u naučnom procesu i treba da bude rešen zahteva algoritam koji je u stanju da na osnovu datih podataka nađe rešenje. Zbog toga navedene teme imaju i teorijski i praktičan značaj. Sposobnost kritičke analize postojećih rešenja i sinteze originalnih rešenja u oblasti algoritama.

Teorijska nastava

Metodi dizajniranja aloritama: pohlepni algoritam (Huffman-ovi kodovi), dinamičko programiranje (najduža zajednička podsekvenca), zavadi pa vladaj (množenje matrica, tranzitivno zatvorenje). Analiza algoritama: rekurentne metode, analiza najgoreg slučaja, analiza prosečnog slučaja (primer: quicksort), amortizovana kompleksnost. Algoritmi iz teorije brojeva: celobrojni (najveći zajednički delilac, modularna aritmetika), FFT, polinomska i celobrojna aritmetika. Algoritmi na grafovima (obilazak grafa, najkraća rastojanja, stabla razapinjanja). Algoritmi vezani za protok u mrežama. Algoritmi za uparivanje reči. Ostale algoritamske paradigme: paralelni algoritmi (Pointer Jumping, prefiksne sume, rangiranje listi, sortiranje), distribuirani algoritmi (Byzantine Agreement).

Studijski istraživački rad

Deo nastave na predmetu se odvija kroz samostalni studijski istraživački rad koji obuhvata eventualno pisanje rada iz oblasti teorije algoritama.