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

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
razumjeti i primijeniti suvremene tehničke koncepte i prakse u informacijskim tehnologijama (arhitektura računala, operacijski sustavi, mreže računala)
razumjeti i primijeniti matematičke metode, modele i tehnike primjerene rješavanju problema iz područja informacijskih i poslovnih sustava
razumjeti bitne čimbenike koji utječu na poslovanje organizacije i pojedinaca te primijeniti osnovne metode i koncepte planiranja, upravljanja i obračuna poslovanja
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
razumjeti osnovna vertikalna područja primjene ICT (industrija, zdravstvo, promet, turizam, država i sl.), te horizontalne aplikacije (uredski sustavi, DSS, CRM, ERP, DMS i sl.)
razumjeti i primijeniti suvremene metodološke pristupe razvoja organizacijskih i informacijskih sustava, te oblikovanja organizacije i organizacijske strukture
razumjeti suvremene organizacijske koncepte i upravljati organizacijskom kulturom
modelirati poslovne procese i podatke u organizacijama i primijeniti modele u razvoju informacijskih i poslovnih sustava
razumjeti i primijeniti metode, tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama
razumjeti i primijeniti procese, metode i tehnologije upravljanja IT uslugama i resursima te podrške i pružanja različitih vrsta usluga vezanih uz ICT
razumjeti i primijeniti etička načela, zakonsku regulativu i norme koje se primjenjuju u struci
razumjeti osnovna načela i metode upravljanja organizacijom i uspješno raditi u timu
uspješno komunicirati s klijentima, korisnicima i kolegama na verbalan i pisani način uz primjenu odgovarajuće terminologije uključujući i sposobnost komunikacije o struci na stranom jeziku
pratiti stručnu literaturu na hrvatskom i stranom jeziku, pripremiti i samostalno održati prezentacije na hrvatskom i stranom jeziku stručnoj i općoj publici, te kritičku evaluaciju prezentirane stručne teme
razumjeti i primijeniti vještine učenja potrebne za cjeloživotno učenje i nastavak obrazovanja na diplomskom studiju.
razumjeti i primijeniti osnovne principe planiranja i razvoja karijere u struci i vlastitih poduzetničkih poduhvata

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: 22.11.2024.

Vrijeme: 16:00

Opis: Na Fakultetu

izvanredni rok

Datum: 16.04.2025.

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.