FOI Nastava - Strukture podataka i algoritmi

Sadržaj se učitava...

FOI Nastava

apps

mdi-login

Strukture podataka i algoritmi

Data Structures and Algorithms
2022/2023

6 ECTSa

Informacijski i poslovni sustavi 1.2 (IPS)

Katedra za teorijske i primijenjene osnove informacijskih znanosti

3. semestar

Osnovne informacijemdi-information-variant

Izvođači nastavemdi-account-group

Nastavni plan i programmdi-clipboard-text-outline

Model praćenjamdi-human-male-board

Ispitni rokovimdi-clipboard-check-outline

Rasporedmdi-calendar-clock

Konzultacijemdi-account-voice

Izvođenje kolegija

Studij	Studijski program	Semestar	Obavezan
Informacijski i poslovni sustavi 1.2 (IPS)		3	obavezan

Cilj kolegija

Razviti kod studenata algoritamsko razmišljanje, upoznati ih sa uobičajenim načinima organizacije podataka u programiranju te sa različitim implementacijama apstraktnih tipova podataka. Upoznati ih s osnovama složenosti algoritama i struktura podataka te razviti kritičko mišljenje potrebno za izbor adekvatnog algoritma i strukture podataka.

Preduvjeti

Informacijski i računalni sustavi (IPS 1.2)
Matematika 1 (IPS 1.2)
Programiranje 1 (IPS 1.2)
Programiranje 2 (IPS 1.2)
Matematika 2 (IPS 1.2)

Norma kolegija

Predavanja

30 sati

Vježbe u praktikumu

30 sati

Nastavnik	Uloga na kolegiju	Oblik nastave	Tjedana	Sati	Grupa
Lovrenčić Alen	Nositelj	Predavanja	15	2	2
Novaković Miljenko	Suradnik	Vježbe u praktikumu	15	2	13

Sadržaj predavanja

Uvod. (2 sata)
Definicija algoritma. Elementarni i složeni tipovi podataka. Strukture podataka.
Osnove složenosti algoritama i struktura. (2 sata)
Asimptotski rast funkcija. O notacija. Amortizirana složenost strukture podataka - agregatna analiza, računovodstvena metoda i metoda energetskih potencijala.
Apstraktni tip podataka općenita lista. (4 sata)
Implementacija pomoću polja. Implementacija pomoću pokazivača. Implementacija pomoću kursora.
Apstraktni tip podataka stog. (2 sata)
Implementacija pomoću polja. Implementacija pomoću pokazivača. Algoritam pretvorbe infiksnog u postfiksni zapis algebarskog izraza. Izračunavanje vrijednosti izraza zapisanog u postfiksnom zapisu.
Apstraktni tip podataka red.(2 sata)
Implementacija pomoću cirkularnog polja. Implementacija pomoću pokazivača.
Apstraktni tip podatka binarno stablo.(4 sata)
Implementacija pomoću polja. Implementacija pomoću pokazivača. Implementacija pomoću kursora. Ophodnje i pretraživanja binarnih stabala. Hrpa. Sortiranje pomoću hrpe.
Binarna stabla pretraživanja. (2 sata)
Implementacija pomoću pokazivača. Sortiranje pomoću binarnog stabla pretraživanja.
Apstraktni tip podataka općenito stablo. (4 sata)
Implementacija prvo dijete – sljedeći brat. Pomoću pokazivača. Pomoću kursora. Digitalno stablo.
Apstraktni tip podataka skup. (3 sata)
Implementacija pomoću sortiranog polja. Implementacija pomoću binarnog stabla pretraživanja. Implementacija pomoću tablice sažetaka.
Apstraktni tip podataka prioritetni red. (1 sat)
Implementacija pomoću sortiranog polja. Implementacija pomoću binarnog stabla pretraživanja. Implementacija pomoću hrpe.
Apstraktni tip podataka matematički graf. (2 sata)
Implementacija pomoću matrice susjednosti. Implementacija pomoću listi susjednosti.

Sadržaj seminara/vježbi

Ishodi učenja kolegija

Odrediti operacije po vrstama (konstruktori, opservatori, iteratori, transformatori) za opisno zadani apstraktni tip podataka.
Implementirati odgovarajuće linearne ili stablaste apstraktne tipove podataka za zadani programski problem.
Izgraditi programsko rješenje zadanog problema odabirom odgovarajućih linearnih i/ili stablastih apstraktnih tipova podataka.
Odrediti vremensku i prostornu složenost operacija za zadanu implementaciju apstraktnog tipa podataka te amortiziranu složenost strukture podataka.
Odabrati odgovarajući stablasti apstraktni tip podataka za pretraživanje i sortiranje podatka i izgraditi efikasan algoritam pretraživanja, odnosno sortiranja podataka za zadani problem.
Odrediti i argumentirati vremensku složenost a priori i a posteriori za zadani algoritam izveden u programskom jeziku.
Odrediti vremensku i prostornu složenost zadanog nerekurzivnog algoritma korištenjem metoda ocjene rasta funkcije složenosti.
Odrediti amortiziranu složenost strukture podataka metodom agregatne analize, računovodstvenom metodom ili metodom energetskog potencijala.
Izgraditi algoritam za zadani problem primjenom odgovarajuće metode izgradnje algoritama.
Izraditi iterativnu inačicu rekurzivno zadanog algoritma u imperativnom programskom jeziku korištenjem tipa podataka - stog.

Ishodi učenja programa

razumjeti stanje i trendove razvoja suvremenih informacijskih i komunikacijskih tehnologija (ICT), razumjeti njihov utjecaj na pojedinca, organizaciju i društvo te procijeniti njihovu primjenjivost u zadanom kontekstu
razumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanja
analizirati stanje, identificirati prilike i definirati probleme s kojima se susreću organizacije i pojedinci u primjeni ICT, te formulirati rješenja uz primjenu ICT

Osnovna literatura

A. Lovrenčić: Apstraktni tipovi podataka i algoritmi, dio 1., FOI, 2018.
A. Lovrenčić: Apstraktni tipovi podataka i algoritmi, dio 2., FOI, 2020. (u pripremi)

Dopunska literatura

Karumanachi. Data Structures and Algorithms Made Easy, Career Monk, 2008
Sedgewick. Algorithms in C++, Part I-IV, Addison-Wesley, 1992.
Thareja. Data Structures Using C, Oxford University Press, 2011.
Weiss. Data Structures and Algorithm Analysis in C++, Pearson Education, 2013.
Lieserson, Stein, Rivest, Cormen. Introduction to Algorithms, MIT Press, 2009.
Levitin. Introduction to Design and Analysis of Algorithms, McGraw-Hill, 2011.

Slični kolegiji

Redoviti studenti

Izvanredni studenti

izvanredni rok

Datum: 17.04.2026.

Vrijeme: 16:00

Opis: Na Fakultetu

U kalendaru ispod se nalaze konzultacije predmetnih nastavnika, no za detalje o konzultacijama možete provjeriti na profilu pojedinog predmetnog nastavnika.