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
  6. Sintetizirati, integrirati i predlagati primjenu informatičkih, informacijskih i logičkih modela u procesu jezičnog inženjeringa, računalne obrade jezika, leksikografije i strojnog i strojno potpomognutog prevođenja
  7. Sintetizirati, integrirati i predlagati primjenu informatičkih, informacijskih i logičkih modela u procesu jezičnog inženjeringa, računalne obrade jezika, leksikografije i strojnog i strojno potpomognutog prevođenja te prenosi u nastavni proces
  8. Analizirati i rješavati informatičke potrebe korisnika
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