Sadržaj se učitava...
mdi-home Početna mdi-account-multiple Djelatnici mdi-script Studiji mdi-layers Katedre mdi-calendar-clock Raspored sati FOI Nastava search apps mdi-login
Napredne strukture podataka i metode izgradnje algoritama
Advanced Data Structures and Aglorithm Design Methods
2024/2025
4 ECTSa
Informacijski i poslovni sustavi 1.2 (IPS)
Katedra za teorijske i primijenjene osnove informacijskih znanosti
M2
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
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.
2024 © Fakultet organizacije i informatike, Centar za razvoj programskih proizvoda