Diskretna matematika 1

Opis predmeta

Homogene linearne rekurzivne relacije. Nehomogene rekurzivne relacije. Osnovni pojmovi teorije grafova. Povezanost. Algoritmi optimizacije na grafovima. Stabla. Planarnost. Bojanja grafova. Usmjereni grafovi. Sparivanja u grafovima.

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

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

Laboratorijske vježbe

Prof. dr. sc.
Mario Krnić
Matija Livaić
mag. phys.
Izv. prof. dr. sc.
Anamari Nakić
Vlatko Crnković
mag. math.
Prof. dr. sc.
Mario Osvin Pavčević
Izv. prof. dr. sc.
Domagoj Kovačević
Kristijan Kilassa Kvaternik
mag. math.

Za studente

Izvedba

ID 183396
  Zimski semestar
6 ECTS
R1 Engleski jezik
R1 E-učenje
60 Predavanja
6 Laboratorijske vježbe

Ocjenjivanje

85 izvrstan
70 vrlo dobar
55 dobar
45 dovoljan

Sličan predmet