Algoritmi i strukture podataka

Upoznavanje studenata sa osnovnim strukturama podataka, principima za njihovu efikasnu implementaciju na računaru, kao i sa osnovnim algoritmima i algoritamskim strategijama za rad sa tim strukturama.

Na kraju kursa studenti treba da ovladaju osnovnim strukturama podataka, kriterijumima za njihovu implementaciju i osnovnim algoritmima za rad sa tim strukturama, kao i da steknu sposobnost da samostalno analiziraju, izaberu i primene strukture podataka i algoritme i optimalno reše kompleksne probleme korišćenjem usvojenih znanja.

Teorijska nastava

Istorijski pregled i definicije algoritma. Argumentacija. Analiza kompleksnosti. Apstrakcije u programiranju. Klasifikacija objekata. Pojam struktura podataka. Vrste struktura podataka. Linearne strukture. Stak, red, lista, osnovne rečnik operacije na njima i njihova implementacija preko nizova i dinamičkih struktura. Strategija „podeli i savladaj“. Osnovni algoritmi sortiranja. Uređena binarna stabla i rečnik operacije na njima. Balansirana stabala. Rotacija stabala. Grafovi (liste susedstva i matrice susedstva). BFS algoritam i DFS algoritam za otkrivanje grafova, Dijkstrin algoritam. Pohlepni algoritmi, Kruskalov i Primov algoritam, Hafmanovo kodiranje. Dinamičko programiranje, edit distanca, problem trgovačkog putnika. Linearno programiranje, planiranje proizvodnje, protok u mrežama, matrične igre.

Praktična nastava

Stečeno teorijsko znanje u ovoj oblasti primenjuje se u rešavanju konkretnih zadataka.