Naziv
Kombinatorika i grafovi
Organizacijska jedinica
Odsjek za informacijske i komunikacijske znanosti
ECTS bodovi
6
Šifra
117584
Semestri izvođenja
zimski
Satnica
Predavanja
30
Vježbe u praktikumu
30

Cilj
U kolegiju su teme iz kombinatorike i teorije grafova. Na početku se uvode pojamovi multiskupa, relacije i matematičke indukcije. U kombinatorici su teme prebrojavanja skupova, multiskupova i funkcija. Iz teorije grafova su opisani osnovni pojmovi grafa i stabla.
Sadržaj
  1. Uvodno predavanje
  2. Multiskup i operacije s multiskupovima.
  3. Dirichleteov princip. Uvod u Ramseyevu teoriju.
  4. Matematička indukcija. Prirodni brojevi i matematička indukcija. Niz i rekurzija.
  5. Pravila prebrojavanja. Pravilo uključivanja-isključivanja.
  6. Prebrojavanje funkcija i injekcija.
  7. Permutacije skupova i multiskupova.
  8. Kombinacije. Kombinacije skupa i multiskupa.
  9. Kolokvij
  10. Particije broja i skupa.
  11. Graf i matrice grafa. Graf, podgraf i nadgraf.
  12. Šetnja, staza, put i ciklus. Šetnja, duljina šetnje i zatvorena šetnja.
  13. Digraf. Eulerovi i Hamiltonovi obilasci.
  14. Mreža. Optimizacije na mreži.
  15. Kolokvij

Ishodi učenja
  1. Demonstrirati dokazivanje matematičkom indukcijom
  2. Usporediti permutacije i kombinacije
  3. Primijeniti Dirichletov princip
  4. Razlikovati osnovne pojmove iz teorije grafova
  5. Analizirati osnovne operacije nad grafom
Metode podučavanja
Predavanja i vježbe koje kroz praktične primjere prate predavanja.
Metode ocjenjivanja
Tijekom semestra studenti će imati dva kolokvija s kojima se mogu osloboditi pismenog dijela ispita. Usmeni ispit.

Obavezna literatura
  1. D. Veljan, Kombinatorna i diskretna matematika, Algoritam, Zagreb 2001.
  2. B. Tepeš, Kombinatorika i grafovi (predavanja i vježbe)
Dopunska literatura

Obavezan predmet na studijima
  1. Informacijske znanosti, sveučilišni diplomski jednopredmetni studij
  2. Informacijske znanosti, sveučilišni diplomski dvopredmetni studij
Izborni predmet na studijima
  1. Informacijske znanosti, sveučilišni diplomski jednopredmetni studij
  2. Informacijske znanosti, sveučilišni diplomski dvopredmetni studij