Cilj i ishod predmeta
Upoznavanje sa logičkom organizacijom i memorijskom reprezentacijom linearnih i nelinearnih struktura podataka, osnovnim operacijama i tipičnim primenama ovih struktura. Studenti su osposobljeni za programsku implementaciju linearnih i nelinearnih struktura podataka, kao i algoritama za rad sa njima u tipičnim primenama, kao što su pretraživanje i sortiranje.
Teorijska nastava
Linearne strukture. Nizovi. Liste. Stekovi. Redovi čekanja. Nelinearne strukture. Stabla: binarna stabla, obilazak stabla, minimizacija dužine puta. Grafovi. Načini predstavljanja, obilazak grafa po širini i po dubini, određivanje artikulacionih tačaka povezanog grafa, određivanje mostova grafa, izdvajanje dvostruko povezanih komponenti, izdvajanje komponenti jake povezanosti. određivanje topološkog poretka i kritičnog puta, povezujuća stabla i minimalna povezujuća stabla, određivanje dostižnosti i najkraćih rastojanja. 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. Heširanje. Heš funkcije, razrešavanje kolizija, spoljašnje heširanje. Sortiranje. Sortiranje poređenjem – metodi umetanja, selekcije, zamene, metodi linearne složenosti. Algoritmi sortiranja vremenske složenosti O(N log N). Donja granica složenosti sortiranja.
Praktična nastava
Implementacija nekih od 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 algoritama za sortiranje. Dizajn i analiza algoritama za razne algoritamske probleme uz primenu struktura podataka i algoritama koji su prikazani na predavanjima (pri analizi poseban akcenat staviti na proceni najmanje povoljnog slučaja, kao i prosečnog slučaja).