Diskretna matematika 1
Prikazani su podaci za akademsku godinu: 2023./2024.
Laboratorijske vježbe
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.
Studijski programi
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
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.,
Za studente
Izvedba
ID 183396
Zimski semestar
6 ECTS
R1 Engleski jezik
R1 E-učenje
60 Predavanja
0 Seminar
0 Auditorne vježbe
6 Laboratorijske vježbe
0 Konstrukcijske vježbe
0 Vježbe tjelesnog odgoja
Ocjenjivanje
85 izvrstan
70 vrlo dobar
55 dobar
45 dovoljan