Diskretna matematika 1
Ishodi učenja
- Riješiti homogenu i nehomogenu linearnu rekurziju.
- Primijeniti rekurzivni način razmišljanja na odgovarajuće kombinatorne probleme.
- Opisati i baratati s osnovnim pojmovima teorije grafova.
- Opisati i riješiti prikladne inženjerske probleme u jeziku teorije grafova.
- Riješiti probleme algoritamski pomoću računala.
Oblici nastave
Predavanja
4 sata predavanja tjedno. Nastavnik će pratiti nastavne materijale.
Samostalni zadaciTijekom semestra zadat će se 3 programska zadatka koje će studenti samostalno izraditi i predati u okviru laboratorijskih vježbi.
Način ocjenjivanja
Kontinuirana nastava | Ispitni rok | |||||
---|---|---|---|---|---|---|
Vrsta provjere | Prag | Udio u ocjeni | Prag | Udio u ocjeni | ||
Laboratorijske vježbe | 0 % | 15 % | 0 % | 15 % | ||
Domaće zadaće | 0 % | 5 % | 0 % | 5 % | ||
Međuispit: Pismeni | 0 % | 40 % | 0 % | |||
Završni ispit: Pismeni | 0 % | 40 % | ||||
Ispit: Pismeni | 0 % | 80 % |
Tjedni plan nastave
- Fibonaccijev niz. Homogene rekurzivne relacije.
- Homogene rekurzivne relacije.
- Nehomogene rekurzivne relacije.
- Pojam grafa. Glavne definicije i primjeri. Izomorfizam grafova.
- Povezanost. Šetnje. Eulerovski i hamiltonovski grafovi. Algoritmi optimizacije. Problem najkraćeg puta. Kineski problem poštara. Problem trgovačkog putnika.
- Različite karakterizacije stabala.
- Obilježena stabla. Prüferov kod. Minimalno razapinjuće stablo. Algoritmi.
- Međuispit.
- Kuratowskijev teorem. Eulerova formula.
- Dualni grafovi. Algoritmi za testiranje planarnosti.
- Bojanja vrhova. Brooksov teorem. Bojanja bridova.
- Bojanja strana planarnih grafova. Teorem o četiri boje.
- Pojam usmjerenog grafa. Povezanost i jaka povezanost. Problem kritičnog puta. Algoritmi. Turniri.
- Ženidbeni problem. Hallov teorem. Transverzale. Primjena na latinske kvadrate.
- Završni ispit.
Studijski programi
Sveučilišni preddiplomski
Računarstvo (studij)
(3. semestar)
Literatura
(.), D. Kovačević, D. Žubrinić, Uvod u diskretnu matematiku, Element, Zagreb, 2014.,
(.), A. Nakić, M.-O. Pavčević, Uvod u teoriju grafova, Element, Zagreb, 2014.,
(.), J.M. Aldous, R.J. Wilson, Graphs and Applications - An Introductory Approach, Springer, 2004.,
(.), G. Chartrand, L. Lesniak, Graphs and Digraphs, CRC Press, 2005.,
Laboratorijske vježbe
Izvedba
ID 183396
Zimski semestar
6 ECTS
R1 Engleski jezik
R1 E-učenje
60 Predavanja
0 Auditorne vježbe
6 Laboratorijske vježbe
0 Konstrukcijske vježbe
Ocjenjivanje
85 izvrstan
70 vrlo dobar
55 dobar
45 dovoljan