Diskretna matematika 1

Ishodi učenja

  1. Riješiti homogenu i nehomogenu linearnu rekurziju.
  2. Primijeniti rekurzivni način razmišljanja na odgovarajuće kombinatorne probleme.
  3. Opisati i baratati s osnovnim pojmovima teorije grafova.
  4. Opisati i riješiti prikladne inženjerske probleme u jeziku teorije grafova.
  5. Riješiti probleme algoritamski pomoću računala.

Oblici nastave

Predavanja

4 sata predavanja tjedno. Nastavnik će pratiti nastavne materijale.

Samostalni zadaci

Tijekom 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

  1. Fibonaccijev niz, Homogene rekurzivne relacije
  2. Homogene rekurzivne relacije
  3. Nehomogene rekurzivne relacije
  4. Pojam grafa. Glavne definicije i primjeri. Izomorfizam grafova
  5. Povezanost. Šetnje. Eulerovski i hamiltonovski grafovi, Algoritmi optimizacije. Problem najkraćeg puta. Kineski problem poštara. Problem trgovačkog putnika
  6. Različite karakterizacije stabala
  7. Obilježena stabla. Prüferov kod, Minimalno razapinjuće stablo. Algoritmi
  8. Međuispit
  9. Kuratowskijev teorem, Eulerova formula
  10. Dualni grafovi, Algoritmi za testiranje planarnosti
  11. Bojanja vrhova. Brooksov teorem, Bojanja bridova
  12. Bojanja strana planarnih grafova. Teorem o četiri boje
  13. Pojam usmjerenog grafa. Povezanost i jaka povezanost, Problem kritičnog puta. Algoritmi, Turniri
  14. Ženidbeni problem, Hallov teorem, Transverzale, Primjena na latinske kvadrate
  15. 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