Ects: 4
Predavanja: 2
Vježbi: 1
Cilj predmeta:
Razumijevanje rekurzivnih struktura i primjena na rekurzivno modeliranje, usvajanje osnovnih principa prebrajanja i primjena na analizu složenosti algoritama, usvajanje osnovnih pojmova teorije grafova i primjena na probleme iz računarstva.
Sadržaj predmeta:
REKURZIVNE STRUKTURE. Rekurzivno rješavanje problema i rekurzivne strukture. Rekurzija i indukcija na skupu prirodnih brojeva. Primjena rekurzije i indukcije na analizu algoritama. Rekurzija i indukcija na drugim oblastima: liste i stabla. GRAFOVI. Modeliranje pomoću grafova i osnovni pojmovi teorije grafova. Obilaženje u dubinu i primjene na ispitivanje povezanosti, ciklusa i topološkog sortiranja. Obilaženje u širinu i primjene na ispitivanje povezanosti i najkraćih puteva. Pohlepno i dinamičko programiranje (Primov algoritam nalaženja minimalnog razapinjućeg stabla i Dijkstrin algoritam nalaženja najkraćeg puta u težinskom grafu).
Kompetencije:
rekurzivno modeliranje i rješavanje problema, modeliranje problema pomoću grafova i njihovo rješavanje tehnikama obilaženja grafova i metodama pohlepnog i dinamičkog programiranja.
Ishodi učenja:
Student će, nakon polaganja ovog predmeta moći: 1) analizirati, formulirati i riješiti problem rekurzivnim tehnikama, te dokazivati indukcijom svojstva dobivenih rješenja 2) izračunati eksplicitne formule za rekurzije 3) izračunati broj elemenata određenih struktura 4) izračunati red složenosti nerekurzivnih i rekurzivnih algoritama 5) identificirati određene probleme na grafovima 6) ispitati povezanost grafa 7) izračunati najkraći put između dva čvora grafa 8) izračunati minimalno stablo grafa. 9) koristiti rekurziju i grafove u modeliranju problema iz struke (ishod na nivou studija) 10 koristiti pojmove teorije rekurzije i teorije grafova u formulaciji problema (generički ishod) Navedeni ishodi učenja doprinose ishodima učenja studijskog programa: – Razumjeti matematičke funkcije, jednadžbe, derivacije i integrale i njihovu matematiku. – Koristit stručnu literaturu i pretraživanje dostupnih baza informacija i baza znanja (knjižnice, e-knjižnice, Internet).