FOI Nastava - Napredne strukture podataka i metode izgradnje algoritama

Sadržaj se učitava...

FOI Nastava

apps

mdi-login

Napredne strukture podataka i metode izgradnje algoritama

Advanced Data Structures and Aglorithm Design Methods
2022/2023

4 ECTSa

Informacijski i poslovni sustavi 1.2 (IPS)

Katedra za teorijske i primijenjene osnove informacijskih znanosti

5. 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)	Analiza i dizajn poslovnih sustava	5	izborni
Informacijski i poslovni sustavi 1.2 (IPS)	Umjetna inteligencija u poslovanju	5	izborni
Informacijski i poslovni sustavi 1.2 (IPS)	Umreženi sustavi i računalne igre	5	izborni
Informacijski i poslovni sustavi 1.2 (IPS)	Razvoj programskih sustava	5	izborni

Cilj kolegija

Upoznati studente sa standardnim metodama izgradnje algoritama te korpusom signifikantnih algoritama kako bi se kod njih razvile vještine potrebne za izgradnji algoritama. Upoznati ih sa specifičnim strukturama podataka vezanim uz odrežene algoritme. Upoznati studente s značajnijim domenama kojima se standardno definiraju agloritmi, kao što su algoritmi nad grafovima, numerički algoritmi, algoritmi kriptografije.

Preduvjeti

Matematika 2 (IPS 1.2)
Programiranje 2 (IPS 1.2)
Strukture podataka i algoritmi (IPS 1.2)

Norma kolegija

Predavanja

30 sati

Vježbe u praktikumu

15 sati

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

Sadržaj predavanja

Pojam problema i algoritma
Optimizacijski problemi i problemi odlučivanja. Stablo stanja problema za optimizacijske probleme i probleme odlučivanja. Složenost algoritama. (2 sata)
Matematičke osnove
Nizovi brojeva. Sume članova niza brojeva. Matematička indukcija. Rješavanje linearnih rekurzivnih jednadžbi i rekurzivnih jednadžbi tipa podijeli pa ovladaj. (2 sata)
Metoda pohlepe
Princip pohlepe. Problemi rješivi pohlepnim algoritmima (2 sata)
Metoda podijeli pa ovladaj
Metoda smanji pa ovladaj. Problemi rješivi metodom podijeli pa ovladaj (2 sata)
Metoda pretraživanja s vraćanjem
Rješavanje problema metodom pretraživanja s vraćanjem. Eliminacija neperspektivnih grana stabla stanja problema. (2 sata)
Metoda grananja i ograničenja
Funkcija isplativosti i perspektivnosti. LC pretraživanje stabla stanja problema. Rješavanje problema metodom grananja i ograničenja. (4 sata)
Metoda dinamičkog programiranja
Princip očuvanja optimalnosti. Razvoj iterativnih rješenja metodom dinamičkog programiranja i transformacija algoritma temeljenog na metodi pretraživanja s vraćanjem u algoritam temeljen na metodi dinamičkog programiranja. Problemi rješivi metodom dinamičkog programiranja (4 sata)
Apstraktni tip podataka matematički graf i implementacije
Minimalno razapinjuće stablo grafa. Eulerovi putevi i ciklusi u grafu. Fleuryjv algoritam. Hamiltonovi ciklusi. Problem trgovačkog putnika. (2 sata)
Problem najkraćeg puta
Dijkstrin algoritam. Bellman-Fordov algoritam. Floyd-Warshallov algoritam. Problem maksimalnog protoka grafa. Ford-Fulkursonov algoritam. (4 sati)
Samouređujuća binarna stabla pretraživanja
AVL stabla. Rotacije nad AVL stablima. Složenost operacija nad AVL stablima u najgorem slučaju. Crno-crvena stabla. Rotacije na B-stablima. Složenost operacja nad crno-crvenim stablima u najgorem slučaju. (2 sata)
B-stabla
B'-stabla. B+-stabla. algoritmi nad B-stablima. Rotacije i transformacije nad B-stablima. Dvoprolazni i jednoprolazni algoritmi ažuriranja vrijednosti u B-stablima. (4 sata)

Sadržaj seminara/vježbi

Ishodi učenja kolegija

Definirati funkcije procjene isplativosti i perspektivnosti za algoritam temeljen na metodi pretraživanja s vraćanjem te razviti algoritam temeljen na metodi grananja i ograničenja.
Ocijeniti vremensku složenost zadanog rekurzivnog algoritma korištenjem metode karakterističnog polinoma i Master teorema.
Dokazati rješivost zadanog problema metodom pohlepe te razviti algoritam temeljen na metodi pohlepe za zadani problem
Osmisliti za zadani problem algoritam temeljen na metodi podijeli pa ovladaj ili metodi smanji pa ovladaj.
Odabrati pogodni apstraktni tip podataka i implementaciju za pretraživanje podataka i implementirati pretraživanje podataka
Modelirati zadani problem pomoću teorije grafova, izabrati pogodnu implemmentaciju apstraktnog tipa podataka matematički graf te napraviti algoritam za rješavanje zadanog progrlema
Dokazati da zadani problem zadovoljava princip očuvanja optimalnosti te razviti iterativni algoritam temeljen na metodi dinamičkog programiranja
Osmisliti za zadani problem polinomno svođenje na problem s poznatim rješenjem
Modelirati zadani problem pomoću teorije grafova, izabrati pogodnu implemmentaciju apstraktnog tipa podataka matematički graf te napraviti algoritam za rješavanje zadanog problema

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

Lovrenčić, A. Apstraktni tipovi podataka i algoritmi. Dio 1. Uvod u složenost algoritama i struktura podataka s primjerima pretraživanja i sortiranja, Vol. 3, FOI, 2018.
Levitin, Anany V., Introduction to the design and analysis of algorithms. 3nd ed., Pearson, 2011.

Dopunska literatura

Cormen, T. et al., Introduction to Algorithms. 3rd ed. MIT Press, Cambridge, 2009.
Skiena, S., Aglorithm Design Manual, 2. Ed., Springer, London, 2008.
Sedgewick, R., Algorithms, 4th ed., Addison-Wesley, 2011.

Slični kolegiji

Redoviti studenti

Izvanredni studenti

izvanredni rok

Datum: 14.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.