KOMBINATORIKA I DISKRETNA MATEMATIKA M014 (2+2+0) - 5 ECTS bodova



CILJEVI KOLEGIJA Osnovni cilj kolegija jest upoznati studente s kombinatornim načinom razmišljanja i dokazivanja. U tu je svrhu u okviru kolegija potrebno:
- opisati i usporediti različite forme Dirichletovog principa te njegovo poopćenje,
- analizirati osnovna načela prebrojavanja elemenata konačnih skupova te kombinatorna prebrojavanja,
- definirati binomne i multinomne koeficijente i analizirati njihova svojstva
- usvojiti osnovne pojmove teorije grafova
OČEKIVANI ISHODI Očekuje se da nakon odslušanog kolegija studenti razlikuju navedene forme Dirichletovog principa te da mogu argumentirano primijeniti odgovarajuće postupke u rješavanju zadataka;
- mogu analizirati i razlikovati primjene pojedinih načina prebrojavanja odnosno da argumentirano primjenjuju odgovarajući postupak
- budu osposobljeni za analizu rekurzivnih problema i njihovo rješavanje temeljeno na argumentiranim postupcima
- budu osposobljeni za argumentiranu uporabu svojstava binomnih i multinomnih koeficijenata u rješavanju zadataka
- mogu matematički dokazati utemeljenost svih postupaka i formula kojima se služe u okviru ovog kolegija
POTREBNO PREDZNANJE Matematički kolegiji s prve godine studija.
SADRŽAJ KOLEGIJA
DIRICHLETOV PRINCIP I RAMSEYEV TEOREM Slaba i jaka forma Disrichletovog principa, Ramseyev teorem
PREBROJAVANJA, PERMUTACIJE, KOMBINACIJE Osnovni principi prebrojavanja, permutacije skupova i multiskupova, kombinacije skupova i multiskupova
BINOMNI KOEFICIJENTI binomni i multinomni koeficijenti te njihova svojstva, binomna i multinomna formula
REKURZIJE formula uključivanja-isključivanja, jednostavni primjeri rekurzija, Fibonaccijevi brojevi, linearne homogene rekurzije s konstantnim koeficijentima: različiti i višestruki korijeni, linearne nehomogene rekurzije s konstantnim koeficijentima
FUNKCIJE IZVODNICE osnovna svojstva i primjeri funkcija izvodnica, rekurzivne relacije i funckije izvodnice
TEORIJA GRAFOVA Uvod i osnovne definicije, stabla i šume, planarnost, Eulerovi i Hamiltonovi grafovi, bojanje grafova.
IZVOĐENJE KOLEGIJA Izvedbeni program kolegija Kombinatorika i diskretna matematika realizira se u trećem semestru preddiplomskog studija matematike s fondom od 60 sati (tjedno 2 sata predavanja i 2 sata vježbi). Predavanja i vježbe su obavezne.
VREDNOVANJE ZNANJA
1. KOLOKVIJI I DOMAĆE ZADAĆE Kolokvij 1 - Dirichletov princip, principi prebrojavanja, permutacije i kombinacije, binomni i multinomni teorem.
Kolokvij 2 - Formula uključivanja-isključivanja, Rekurzivne relacije, funckje izvodnice, grafovi.
(Potrebno je ostvariti najmanje 90 bodova od ukupno 200.) Domaće zadaće - pokrivaju cijelo gradivo kolegija (max. 10 bodova)
2. PISMENI ISPIT Bodovni prag za polaganje pismenog ispita je 45 bodova.
45 - 57 dovoljan (2)
58 - 72 dobar (3)
73 - 87 vrlo dobar (4)
88 - 100 izvrstan (5)
3. USMENI ISPIT Usmeni ispit je obavezan za sve studente. Na usmenom ispitu se, u ovisnosti od ocjene s pismenog ispita ili kolokvija, formira konačna ocjena.



  1. D.Veljan - Kombinatorna i diskretna matematika, Algoritam, Zagreb 2001
  2. M.Cvitković - Kombinatorika, Element, Zagreb, 1994.

LITERATURA KOJA SE PREPORUČUJE



    Diskretna matematika (Zbirka riješenih zadataka.)