FOI Nastava - Algoritmi

Sadržaj se učitava...

FOI Nastava

apps

mdi-login

Algoritmi

Algorithms
2023/2024

6 ECTSa

Informacijski i poslovni sustavi 1.1 (PDS)

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.1 (PDS)	Poslovni sustavi	5	izborni
Informacijski i poslovni sustavi 1.1 (PDS)	Informacijski sustavi	5	izborni

Cilj kolegija

Ovaj predmet studentima daje metode izgradnje algoritama, kao i značajnije primjere gotovih algoritama, koji su važni kako kao primjeri korištenja standardnih metoda izgradnje algoritama, tako i kao gotova rješenja važnijih problema, koji se često susreću u programerskoj praksi.

Preduvjeti

Kolegij nema definirane preduvjete

Norma kolegija

Predavanja

30 sati

Vježbe u praktikumu

30 sati

Nastavnik	Uloga na kolegiju	Oblik nastave	Tjedana	Sati	Grupa
Lovrenčić Alen	Nositelj	Seminar Seminar	7 1	2 1	1 1
Konecki Mladen	Suradnik
Novaković Miljenko	Suradnik

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.

Ishodi učenja kolegija

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
poznati kritičan broj gotovih algoritama te ih može primijeniti u istoj situaciji ili ih metodom analogije prilagoditi za sličnu situaciju.
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.

Ishodi učenja programa

razumjeti 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
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 i primijeniti metode, tehnike razvoja informacijskih i programskih sustava u suvremenim razvojnim okolinama
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

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.

Slični kolegiji

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

Redoviti studenti

Izvanredni studenti

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