Algoritmi i strukture podataka

Prikazani su podaci za akademsku godinu: 2023./2024.

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.

Studijski programi

Sveučilišni preddiplomski
(3. semestar)

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

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).,

Za studente

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