Algoritmi i strukture podataka
Prikazani su podaci za akademsku godinu: 2024./2025.
Predavanja
Laboratorijske vježbe
Opis predmeta
Nastavljajući na gradivo usvojeno na predmetu Uvod u programiranje, obrađuju se najšire primjenjivani algoritmi i strukture podataka. Uvodi se pojam složenosti algoritma te osnovne tehnike pretraživanja. Objašnjava se i ilustrira rekurzija te potom slijede svi važniji algoritmi sortiranja. Uvode se dinamičke strukture podataka: jednostruke i višestruko povezane liste. Grade se osnovne strukture podataka poput stoga i reda. Zatim se uvodi tehnika raspršenog adresiranja, binarna stabla te gomila kao posebni slučaj binarnog stabla. Uporaba gomile kao prioritetnog reda se pokazuje na primjeru heap sorta. Slijedi uvod u grafove i osnovni algoritmi nad grafovima. Uvode se osnovni algoritmi za pretraživanje teksta.
Preduvjeti
Programiranje
Studijski programi
Ishodi učenja
- Opisati upotrebu različitih podatkovnih struktura
- Opisati veći broj osnovnih algoritama
- Primijeniti odgovarajuće podatkovne strukture i algoritme pri rješavanju konkretnih problema
- Razviti računalne programe u kojima će biti implementirane odgovarajuće podatkovne strukture i algoritmi
- Ocijeniti složenost algoritama i računalnih programa
- 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 zadaciNastavnici zadaju zadatke koje studenti samostalno rješavaju.
LaboratorijOrganiziraju se dvije do tri laboratorijske vježbe.
Tjedni plan nastave
- 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
- 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
- Rekurzivni postupci, Analiza iterativnih i rekurzivnih algoritama, Redukcija: transformiraj i zavladaj
- Podijeli pa vladaj, Rekurzivno vraćanje, Dinamičko programiranje
- 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)
- Linearne podatkovne strukture: polja i liste, Povezane liste
- Apstraktni tipovi podataka i njihova ugradnja (stogovi. redovi. prioritetni redovi. skupovi. mape)
- Međuispit
- Tablice raspršenog adresiranja. uključivo strategije za izbjegavanje i rješavanje kolizija
- 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
- 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)
- 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
- Gomile
- 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)
- Završni ispit
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).,
Izvedba
ID 183381
Zimski semestar
6 ECTS
R2 Engleski jezik
R1 E-učenje
60 Predavanja
0 Seminar
0 Auditorne vježbe
6 Laboratorijske vježbe
0 Konstrukcijske vježbe
0 Vježbe tjelesnog odgoja
Ocjenjivanje
izvrstan
vrlo dobar
dobar
dovoljan