Kolegij Diskretna matematika slušaju studenti druge godine preddiplomskog studija Matematika. Nastava se odvija u zimskom semestru i sastoji se od dva sata predavanja i dva sata vježbi svakog tjedna. Kolegij nosi 5 ECTS bodova.

Cilj kolegija

Upoznavanje studenata s osnovnim pojmovima kombinatorike i teorije grafova.
Studente bi kolegij trebao osposobiti za prepoznavanje i rješavanje osnovnih kombinatornih problema / problema iz teorije grafova na koje će naići u nastavku studiranja / u budućem poslu.
Također, kolegij bi im trebao razviti vještinu da raznorodne probleme vezane uz diskretne stukture mogu preformulirati u probleme iz kombinatorike ili teorije grafova.

Sadržaj kolegija

  1. Uvod. Motivacijski primjeri.
  2. Prebrojavanja. Osnovni principi. Prebrojavanja podskupova. Binomni teorem i primjene. Permutacije. Multiskupovi i multinomni koeficijenti. Particije skupova. Generiranje kombinatornih objekata.
  3. Rekurzije, funkcije izvodnice i formula uključivanja-isključivanja. Uvodne napomene. Fibonaccijevi brojevi. Linearne rekurzije. Funkcije izvodnice. Složenost algoritama za sortiranje. Formula uključivanja-isključivanja.
  4. Teorija grafova. Uvod i osnovne definicije. Stabla i šume. Planarnost. Eulerovi i Hamiltonovi grafovi. Bojanje grafova.

Kolegiji prethodnici


Obavezna literatura

Predavanja

Vježbe

Dopunska literatura



Ovdje možete naći bilješke o stereografskoj projekciji.
Ovdje možete naći bilješke o formalnim redovima kao dodatak gradivu obrađenom na nastavi.