Temeljna znanja klasične kombinatorike s primjenama na rješavanje ekstremalnih problema u diskretnoj matematici. Osnove ekstremalne teorije skupova, Ramseyeve teorije, kao i dviju novijih metoda: vjerojatnosne metode i metode linearne algebre. Iskustvo u povezivanju različitih područja matematike (kombinatorike, vjerojatnosti i linearne algebre) i primjenama novih matematičkih tehnika koje se u današnje vrijeme koriste u teoriji računarstva.

1. analizirati različite kombinatoričke identitete.
2. primijeniti osnove klasične kombinatorike na rješavanje ekstremalnih problema.
3. prepoznati teoriju i neke primjene ekstremalne teorije skupova.
4. prepoznati osnove i neke primjene Ramseyeve teorije.
5. prepoznati osnove i neke primjene vjerojatnosne metode.
6. prepoznati osnove i neke primjene metode linearne algebre.

Nastava na predmetu je organizirana kroz dva nastavna ciklusa. Prvi ciklus se sastoji od 6 tjedana nastave i međuispita, drugi ciklus od 7 tjedana nastave i završnog ispita. Nastava se provodi kroz ukupno 15 tjedana s tjednim opterećenjem od 3 sata.

Međuispit u 7. tjednu nastave i završni ispit u 15. tjednu nastave.

Konzultacije se održavaju jedan sat tjedno prema dogovoru sa studentima.

Rješavanje domaćih zadaća

1. KLASIČNA KOMBINATORIKA. Osnovni pojmovi kombinatorike. Binomni teorem. Identiteti s binomnim koeficijentima. Metoda dvostrukog prebrojavanja. Asimptotska formula za binomne koeficijente. Binomni koeficijenti za realni "n". Multinomni teorem.
2. Kombinatorički rasoporedi "n" objekata u "k" kutija. Slabi rasporedi. Rasporedi. Particije skupa. Stirlingovi brojevi druge vrste. Bellov broj. Particije broja.
3. Permutacije. Ciklusi u permutacijama. Broj svih n-permutacija s zadanim brojem ciklusa. Stirlingovi brojevi prve vrste. Veza Stirlingovih brojeva prve i druge vrste. Lema o rukovanju. Eulerov teorem. Turanov broj.
4. Načelo usrednjavanja. Jensenova nejednakost i primjena za binarna stabla, odnosno prefix-free kodove. Ocjene veličine presjeka. Načelo uključivanja-isključivanja za skupove i za funkcije na skupovima. Primjena za broj deranžmana. Primjena za Stirlingove brojeve druge vrste.
5. Dirichletovo načelo. Neke primjene za grafove. Erdos-Szekeresov teorem. Mantelov teorem. Turanov teorem. Dirichletov teorem o aproksimaciji iracionalnih brojeva racionalnim. Dokazivanje prebacivanjem težine.
6. Sustavi izrazitih predstavnika. Hallov teorem o ženidbi. Primjena za latinske pravokutnike. Primjena za dvostruko stohastičke matrice. Min-max teoremi.
7. Provjera znanja: međuispit.
8. EKSTREMALNA TEORIJA SKUPOVA. Suncokretova lema. Inačice: oslabljen uvjet za jezgru suncokreta, osljabljen uvjet za razdvojenost latica. Primjena za broj minterma Booleovih funkcija. Primjena za formule male dubine.
9. Presijecajuće familije skupova. Erdos-Ko-Radoov teorem. Konačni ultrafilteri. Maksimalne presijecajuće familije. Rezultat Hellyjevog tipa.
10. Parcijalno uređeni skupovi. Lanci i antilanci. Dekompozicija parcijalno uređenih skupova. Simetrični lanci u partitivnim skupovima. Primjena za problem alokacije memorije. Spernerov teorem za antilance u partitivnim skupovima. LYM nejednakost. Bollobasov teorem.
11. OSNOVE RAMSEYEVE TEORIJE. Bojanja i Ramseyevi brojevi. Ramseyevi teoremi za konačne grafove. Poopćenja. Ramseyevi teoremi za skupove. Shurov teorem. Primjene u geometriji: Erdos-Szekeresov teorem za konveksne poligone i neke primjene u kombinatornoj geometriji.
12. OSNOVE VJEROJATNOSNE METODE. Primjene vjerojatnosti zbroja događaja: donja ogradu za Ramseyeve brojeve, Van der Waerdenov teorem, turniri, 2-bojanja bridova bipartitnih grafova, 2-bojanja hipergrafova, Erdos-Ko-Radov teorem.
13. Primjene Dirichletovog svojstva za očekivanje: Hamiltonovi putevi, cijepanja grafova, 'sum-free' skupovi, broj nezavisnosti grafa. Silvesterova formula. Metoda drugog momenta: procjena središšnjeg binomnog koe…cijenta. Funkcije praga za klike. Metoda izmjene i primjene Markovljeve nejednakosti.
14. OSNOVE METODE LINEARNE ALGEBRE. Prostori vektora incidencije. Fisherova nejednakost. Prostori polinoma. Skupovi točaka s dvije različite međusobne udaljenosti. Kombinatorika vektorskih prostora. Ortogonalnost i argument ranga.
15. Provjera znanja: završni ispit.