PREDMETI

Cilji

Cilj predmeta je nadgraditi znanje programiranja ter pridobiti poglobljeno znanje s področja načrtovanja algoritmov, analize algoritmov in uporabe zahtevnejših podatkovnih struktur. Kompetence študenta z uspešno zaključenim predmetom bodo vključevale poglobljeno znanje programiranja v izbranem programskem jeziku, poznavanje zahtevnejših podatkovnih struktur in algoritmov, zmožnost uporabe obstoječih algoritmov pri reševanju problemov.

Predmetnik

Uvod: matematične osnove, modeli računanja in tehnike programiranja, pregled programskih jezikov in izbranega programskega jezika. Analiza algoritmov: računska zahtevnost algoritmov deli in vladaj, amortizirana analiza algoritmov. Seznami in skladi: seznami, dvosmerno povezani seznami, krožni seznami, osnovne operacije nad seznami, model sklada, izvedbe sklada, uporaba sklada, obrnjeni poljski zapis. Drevesa: definicija drevesa, dvojiška drevesa, operacije v drevesih, iskalna drevesa, uravnotežena drevesa, samonastavljiva drevesa, B-drevesa, uporaba dreves. Razpršene tabele: funkcija razprševanja, trčenja, popolno razprševanje, univerzalno razprševanje. Vrste in prednostne vrste: model vrste, uporaba vrst, prednostne vrste, dvojiška kopica, leve kopice, izmaknjene kopice, binomske prioritetne vrste, uporaba prednostnih vrst. Grafi: definicija grafov, usmerjeni in neusmerjeni grafi, predstavitev grafov, problem najkrajše poti, določanje najmanjšega vpetega drevesa, določanje pretoka v omrežju, iskanje v globino, NP-polni problemi. Tehnike načrtovanja algoritmov: požrešna metoda, deli in vladaj, dinamično programiranje, sestopanje. Praktični primeri: računalniške komunikacije, vgradne aplikacije, velika podatkovja.