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. Pretraživanje u dubinu i primjene na ispitivanje povezanosti, ciklusa i topološkog sortiranja. Pretraživanje 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 te metodama pohlepnog i dinamičkog programiranja.

Ishodi učenja:

Studenti će nakon polaganja ovog predmeta moći: 1.Analizirati, formulirati i riješiti problem rekurzivnim tehnikama te indukcijom dokazivati svojstva dobivenih rješenja. 2.Opisati osnove rekurzije i rekurzivnih i nerekurzivnih algoritama. 3. Opisati osnove teorije grafova. 4.Koristiti rekurziju i grafove u modeliranju problema iz struke. 5.Koristiti pojmove teorije rekurzije i teorije grafova u formulaciji problema. Navedeni ishodi učenja doprinose ishodima učenja studijskog programa: - Primijeniti teorijske osnove matematike, fizike i elektrotehnike u računalstvu (1).