Ishodi učenja predmeta

• izabrati između nekoliko ponuđenih programskih rješenja zadanog rješenja ono koje je najbolje prema kriterijima ocjene kvalitete programskog rješenja
• koristiti različite izvore te u njima tražiti rješenja svog problema, te je (vidi ishod) u stanju kritički ocijeniti njihovu kvalitetu i izabrati onaj koji mu je najbolji.
• poznati kritičan broj gotovih algoritama te ih može primijeniti u istoj situaciji ili ih metodom analogije prilagoditi za sličnu situaciju.
• primijeniti metode izrade algoritama i pomoću njih izgraditi algoritam za zadani problem
• procijeniti složenost zadanog problema i ocijeniti kvalitetu dobijenog programskog rješenja

Ishodi učenja programa

• 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 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
• 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 temepratiti 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 ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanjarazumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanja
• razumjeti i primijeniti matematičke metode, modele i tehnike primjerene rješavanju problema iz područja informacijskih i poslovnih sustava razumjeti i primijeniti matematičke metode, modele i tehnike primjerene rješavanju problema iz područja informacijskih i poslovnih sustava
• razumjeti i primijeniti metode, tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama razumjeti i primijeniti metode, tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama

Sadržaj predavanja

• Uvod. Matematičke osnove.
  Programiranje i programski jezici. Problemi. Zadavanje problema. Intuitivni pojam algoritma. Svojstva algoritma. Vremenska i prostorna složenost algoritma. Definicija algoritma kao rješenja optimizacijskog problema i problema odlučivanja. Asimptotske ocjene složenosti algoritma (notacije O, o, Ω, ω i Θ). Propozicije vezane uz asimptotske osnove složenosti algoritama. Važniji redovi brojeva. Faktorijeli. Stirlingova formula. Binomni koeficijenti. Binomni poučak. Matematička indukcija.
• Matematičke osnove (cont.)
  Rekurzivne jednadžbe. Homogene linearne rekurzivne jednadžbe. Rješavanje rekurzivnih jednadžbi pomoću karakteristične jednadžbe - homogeni slučaj. Rješavanje rekurzivnih jednadžbi pomoću karakteristične jednadžbe - nehomogeni slučaj. Neki slučajevi nelinearni rekurzivnih jednadžbi i njihovo rješavanje. Rekurzivni računalni programi Izračunavanje složenosti rekurzivnih programa.
• Metode izgradnje algoritama. Metoda pohlepe
  Definicija metode pohlepe. Dokazivanje korektnosti pohlepnog algoritma za dani problem. Problem realnog ranca (problem skladištenja rasutog tereta), dokaz korektnosti i ocjena složenosti. Dokaz da pohlepni algoritam ne daje optimalno rješenje problema cjelobrojnog ranca. Huffmanov algoritam optimalnog spajanja datoteka, dokaz korektnosti i ocjena složenosti. Problem dostupnosti datoteka na sekvencijalnom mediju u minimalnom vremenu, dokaz korektnosti i ocjena složenosti.
• Metode izgradnje algoritama. Metoda podijeli pa ovladaj.
  Metoda podijeli pa ovladaj. Metoda smanji pa ovladaj. Rekurzivne jednadžbe koje nastaju pri izračunu složenosti algoritama temeljenih na metodi podijeli pa ovladaj. Rješavanje Josephusovog problema metodom smanji pa ovladaj i ocjena složenosti Pronalaženje maksimuma metodom podijeli pa ovladaj i ocjena složenosti Rješavanje problema udaljenosti dvije točke u ravnini metodom podijeli pa ovladaj i ocjena složenosti.
• Metode izgradnje algoritama. Metoda pretraživanja s vraćanjem
  Opis backtracking metode. Stablo prostora stanja problema. Pretraživanje prvo u dubinu i prvo u širinu Pretraživanje prvo u dubinu rekurzivno i pomoću stoga. Problem kraljica i ocjena složenosti.
• Metode izgradnje algoritama. Metoda pretraživanja s vraćanjem (cont.)
  Problem 0-1 ranca, ocjena složenosti. Poboljšanje algoritma za problem 0-1 ranca. Rješavanje problema sume podskupova metodom pretraživanja s vraćanjem. Ocjena složenosti. Poboljšanje algoritma za pronalaženje sume podskupova
• Metode izgradnje algoritama. Metoda grananja i ograničenja
  Metoda grananja i ograničenja. LC pretraživanje stabla prostora stanja problema. Problem skakača na šahovskoj ploči. Rješenje metodom pretraživanja s vraćanjem i metodom grananja i ograničenja. Problem 0-1 ranca. Rješenje metodom grananja i ograničenja. Ocjena složenosti.
• Metode izgradnje algoritama. Metoda dinamičkog programiranja
  Opis metode dinamičkog programiranja. Uvjet optimalnosti. Eliminacija višestrukog izračunavanja istih podproblema. Koraci izgradnje programskog rješenja metodom dinamičkog programiranja Problem cjelobrojnog ranca. Dokaz zadovoljenja principa optimalnosti. Ocjena složenosti
• Metode izgradnje algoritama. Metoda dinamičkor programiranja (cont.)
  Problem proizvodnih traka. Dokaz zadovoljenja uvjeta optimalnosti. Ocjena složenosti Problem optimalnog množenja niza matrica. Dokaz zadovoljenja uvjeta optimalnosti. Algoritam za određivanje optimalnog redosljeda množenja matrica dinamičkim programiranjem. Ocjena složenosti. Problem optimalnog binarnog stabla pretraživanja. Dokaz zadovoljena principa optimanlosti. Ocjena složenosti.
• Algoritmi na grafovima
  Apstraktni tip podataka matematički graf. Usmjereni i neusmjereni grafovi. Implementacija grafa pomoćumatrice susjednosti. Implementacija grafa pomoću ortogonalne liste. Pretraživanja grafa prvo u širinu i prvo u dubinu.
• Algoritmi na grafovima (cont.)
  Razapinjuće stablo grafa. Kruskalov i Primov algoritam za minimalno razapinjuće stablo grafa. Izračun složenosti za algoritme za minimalno razapinjuće stablo grafa. Dijkstrin algoritam. Složenost Dijkstrinog algoritma. Eulerovi putevi i ciklusi u grafu. Algoritam za nalaženje Eulerovih ciklusa i složenost.
• Algoritmi na grafovima (cont.)
  Topološko sortiranje Maksimalni protok u grafu. Ford-Fulkersonov algoritam i njegova složenost. Hamiltonovi ciklusi Problem trgovačkog putnika. Algoritam za bojenje vrhova grafa i njegova složenost. Pokrivač vrhova grafa, algoritam i složenost.
• Numerički algoritmi
  Metode pronalaženja nul-točaka funkcije. Metoda bisekcije. Newtonova metoda tangente. Metoda sekante Hornerov algoritam za izračunavanje vrijednosti polinoma. Dijeljenje polinoma Euklidov algoritam za najveći zajednički djelitelj dvaju prirodnih brojeva.
• Numerički algoritmi (cont.)
  Numerička integracija. Trapezna formula. Simpsonova formula. Uopćena trapezna i Simpsonova formula. Rombergov algoritam.
• NP-teški i NP-potpuni problemi
  Definicija klasa NP-teških i NP-potpunih problema. Cookov teorem. SAT i 3SAT problem. Dokaz NP-potpunosti nekih problema. Problem particije skupa brojeva. Problem maksimalne klike grafa. Problem pokrivača vrhova grafa. Problem Hamiltonovih ciklusa. Problem particije skupa. NP-teški problemi rasporeda. Problem 0-1 ranca.

Sadržaj seminara/vježbi

• Uvod
  Osnovni algoritmi pretraživanja i sortiranja
• Rekurzija
  Korištenje rekurzije za rješavanje problema. Ocjena složenosti rekurzivnih programa
• Pohlepni algoritmi
  Primjeri algoritama temeljenih na metodi pohlepe. Dokaz korektnosti.
• Pohlepni algoritmi (cont.)
  Primjeri algoritama temeljenih na metodi pohlepe. Dokaz korektnosti.
• Programski zadatak 1
  Studenti samostalno rješavaju programski zadatak.
• Podijeli pa ovladaj
  Primjeri algoritama temeljeni na metodi podijeli pa ovladaj
• Podijeli pa ovladaj (cont.)
  Primjeri algoritama temeljeni na metodi podijeli pa ovladaj
• Programski zadatak 2
  Studenti samostalno rješavaju programski zadatak
• Pretraživanje s vraćanjem
  Primjeri algoritam temeljeni na metodi pretraživanja s vraćanjem (backtracking)
• Metoda grananja i ograničenja
  Primjeri algoritama temeljeni na metodi grananja i ograničenja (banch and bound)
• Programski zadatak 3
  Studenti samostalno rješavaju programski zadatak
• Dinamičko programiranje
  Primjeri algoritama temeljeni na metodi dinamičkog programiranja
• Dinamičko programiranje (cont.)
  Primjeri algoritama temeljeni na metodi dinamičkog programiranja
• Programski zadatak 4
  Studenti samostalno rješavaju programski zadatak.

Alati koji se koriste na predmetu

• DEV-C++
  Open-source C++ programming environment Bloodshed DEV-C++

Osnovna literatura

• Cormen, T. et al., Introduction to Algorithms. MIT Press, Cambridge, 2001.
• Levitin, Anany V., Introduction to the design and analysis of algorithms. 2nd ed., Addison-Wesley, Boston, 2007.

Dopunska literatura

• Skiena, S. S. The Algorithm Design Manual. 2nd ed. London, Springer, 2008.
• Sedgewick, R. Algorithms in C++. Vol 1, parts 1-4: Fundamentals data structers, sorting, searching. 3rd ed. Boston, Addison-Wesley, 2008.
• Sedgewick, R. Algorithms in C++. Vol 2, part 5: Graph algorithms. 3rd ed. Boston, Addison-Wesley, 2002.

Preduvjeti

• Matematika 1
  Cilj predmeta Matematika I je upoznavanje studenata s osnovnim pojmovima diskretne matematike (kao što su matematički modeli, matematička logika te skupovi i relacije) i linearne algebre (matrice, determinante, sustavi linearnih jednadžbi i nejednadžbi) koji su neophodni za prihvaćanje kvantitativnih aspekata znanja u informacijskim i organizacijskim znanostima te priprema studenata za logičko razmišljanje u znanosti i poslovanju. Predmet ima i generičke ciljeve kao što su timski rad, prezentacijske vještine (usmeno i pismeno izražavanje), razumijevanje modela, upotreba literature i razvoj ICT vještina, te posebno strategije rješavanja problemskih zadataka. Nadalje, koncepcija rada omogućava razvoj vještina apstrakcije kod studenata
• Programiranje 2
  Kolegij se nastavlja na Programiranje I s kojim predstavlja cjelinu. Po završetku, studenti trebaju biti sposobni oblikovati, kodirati, testirati, ispravljati i dokumentirati programska, prije svega objektno orijentirana rješenja problema algoritamskog tipa. Ciljna razina složenosti programa jesu programi koji rade s više datoteka i više klasa
• Strukture podataka
  Cilj kolegija Modeliranje poslovnih pravila je upoznavanje studenata s osnovnim teorijskim postavkama i praktičnim metodama i postupcima konceptualnog i formalnog oblikovanja i implementacije poslovnih pravila i sustava poslovnih pravila, u kontekstu suvremenih alata za razvoj informacijskih sustava, kako klasičnih, tako i suvremenih (sustavi ontologija, sustavi baza znanja i sustavi semantičkog Weba).

Slični predmeti

• Algoritmi i strukture podataka, Fakultet elektrotehnike i računarstva, Sveučilište uu Zagrebu
• Strukture podataka i algoritmi, Prirodoslovno matematički fakultet – matematički odjel, Sveučilište u Zagrebu
• Algoritmi i strukture podataka, Odjel za fiziku, Sveučilište Josipa Juraja Strossmayera u Osijeku
• Algoritmi i strukture podataka, Elektrotehnički fakultet Osijek, Sveučilište Josipa Juraja Strossmayera u Osijeku