Algoritmi i strukture podataka

Ishodi učenja

  1. Opisati upotrebu različitih podatkovnih struktura
  2. Opisati veći broj osnovnih algoritama
  3. Primijeniti odgovarajuće podatkovne strukture i algoritme pri rješavanju konkretnih problema
  4. Razviti računalne programe u kojima će biti implementirane odgovarajuće podatkovne strukture i algoritmi
  5. Ocijeniti složenost algoritama i računalnih programa
  6. Identificirati odgovarajuće podatkovne strukture i algoritme pri rješavanju konkretnih problema

Oblici nastave

Predavanja

Nastava je organizirana u dva ciklusa ukupnog trajanja 15 tjedana, u što su uračunata dva tjedna za međuispite. Predavanja traju četiri sata tjedno, a podijeljena su u dva dana, dakle 2+2 sata.

Samostalni zadaci

Nastavnici zadaju zadatke koje studenti samostalno rješavaju.

Laboratorij

Organiziraju se dvije do tri laboratorijske vježbe.

Tjedni plan nastave

  1. Pojam i svojstva algoritama, Razlike između najboljeg. očekivanog i najgoreg slučaja ponašanja nekog algoritma, Označavanje velikim O: formalna definicija i uporaba, Jednostavni numerički algoritmi. kao što su izračun prosjeka liste brojeva. pronalaženje minimuma. maksimuma i moda u listi. približni izračun kvadratnog korijena broja. ili određivanje najveće zajedničke mjere, Zapisi/struktovi (raznorodne nakupine), Referenciranje i višestruko imenovanje
  2. Asimptotska analiza gornjih i očekivanih granica složenosti, Konstantna. logaritamska. linearna. kvadratna i eksponencijalna klasa složenosti, Iskustvena mjerenja ponašanja, Razmjena vremena i prostora u algoritmima , Oznake malo o. veliko omega i veliko theta, Algoritmi slijednog i binarnog pretraživanja, Strategije odabira prikladne podatkovne strukture
  3. Rekurzivni postupci, Analiza iterativnih i rekurzivnih algoritama, Redukcija: transformiraj i zavladaj
  4. Podijeli pa vladaj, Rekurzivno vraćanje, Dinamičko programiranje
  5. Najgori slučaj kvadratičnih algoritama sortiranja (sortiranje odabirom. sortiranje ubacivanjem), Najgori ili prosječni slučaj O(N log N) algoritama sortiranja (brzo sortiranje. sortiranje gomilom. sortranje uparivanjem)
  6. Linearne podatkovne strukture: polja i liste, Povezane liste
  7. Apstraktni tipovi podataka i njihova ugradnja (stogovi. redovi. prioritetni redovi. skupovi. mape)
  8. Međuispit
  9. Tablice raspršenog adresiranja. uključivo strategije za izbjegavanje i rješavanje kolizija
  10. Napredne strukture podataka: višestruka stabla i grafovi, Prikaz grafova (npr. lista susjednosti. matrica susjednosti) i pretraživanja prvo u dubinu i prvo u širinu
  11. Algoritmi zasnovani na gruboj sili, Pohlepni algoritmi, Grananje i ograničavanje, Algoritmi najkraćeg puta (Dijkstrin i Floydov algoritam); minimalno stablo razapinjanja (Primov i Kruskalov algoritam)
  12. Binarna stabla za traženje i zajedničke operacije na binarnim stablima za traženje. kao što su odabir najmanjega. najvećega. ubacivanje. uklanjanje. obilazak stabla
  13. Gomile
  14. Nizovi i obrada nizova, Podudarnost uzoraka i algoritmi za obradu nizova/teksta (npr. podudarnost podnizova. podudarnost regularnih izraza. algoritmi za određivanje najduljeg zajedničkog podniza)
  15. Završni ispit

Studijski programi

Sveučilišni preddiplomski
Računarstvo (studij)
(3. semestar)

Literatura

(.), Predavanja iz predmeta,
(.), Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 3rd ed. MIT Press, 2009.,
(.), Sedgewick and Wayne. Algorithms (4th Edition). Addison-Wesley Professional; 4th edition (2011).,

Predavanja

Laboratorijske vježbe

Izvedba

ID 183381
  Zimski semestar
6 ECTS
R3 Engleski jezik
R1 E-učenje
60 Predavanja
0 Auditorne vježbe
6 Laboratorijske vježbe
0 Konstrukcijske vježbe

Ocjenjivanje

izvrstan
vrlo dobar
dobar
dovoljan