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.,

Nositelji

Doc. dr. sc.
Domagoj Kovačević
Prof. dr. sc.
Mario Krnić
Doc. dr. sc.
Anamari Nakić
Prof. dr. sc.
Mario Osvin Pavčević

Laboratorijske vježbe

Prof. dr. sc.
Mario Osvin Pavčević
Doc. dr. sc.
Domagoj Kovačević
Kristijan Kilassa Kvaternik
mag. math.
Renato Babojelić
mag. inf. et math.
Doc. dr. sc.
Anamari Nakić
Prof. dr. sc.
Mario Krnić

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

Sličan predmet