Ekstremalna kombinatorika
Opis predmeta
Opće kompetencije
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.
Ishodi učenja
- analizirati različite kombinatoričke identitete.
- primijeniti osnove klasične kombinatorike na rješavanje ekstremalnih problema.
- prepoznati teoriju i neke primjene ekstremalne teorije skupova.
- prepoznati osnove i neke primjene Ramseyeve teorije.
- prepoznati osnove i neke primjene vjerojatnosne metode.
- prepoznati osnove i neke primjene metode linearne algebre.
Oblici nastave
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.
Provjere znanjaMeđuispit u 7. tjednu nastave i završni ispit u 15. tjednu nastave.
KonzultacijeKonzultacije se održavaju jedan sat tjedno prema dogovoru sa studentima.
Ostali oblici skupnog ili samostalnog učenjaRješavanje domaćih zadaća
Način ocjenjivanja
Kontinuirana nastava | Ispitni rok | |||||
---|---|---|---|---|---|---|
Vrsta provjere | Prag | Udio u ocjeni | Prag | Udio u ocjeni | ||
Domaće zadaće | 0 % | 10 % | 0 % | 10 % | ||
Međuispit: Pismeni | 0 % | 45 % | 0 % | |||
Završni ispit: Pismeni | 0 % | 45 % | ||||
Ispit: Pismeni | 0 % | 90 % |
Tjedni plan nastave
- 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.
- Kombinatorički rasoporedi "n" objekata u "k" kutija. Slabi rasporedi. Rasporedi. Particije skupa. Stirlingovi brojevi druge vrste. Bellov broj. Particije broja.
- 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.
- 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.
- 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.
- Sustavi izrazitih predstavnika. Hallov teorem o ženidbi. Primjena za latinske pravokutnike. Primjena za dvostruko stohastičke matrice. Min-max teoremi.
- Provjera znanja: međuispit.
- 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.
- Presijecajuće familije skupova. Erdos-Ko-Radoov teorem. Konačni ultrafilteri. Maksimalne presijecajuće familije. Rezultat Hellyjevog tipa.
- 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.
- 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.
- 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.
- 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.
- 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.
- Provjera znanja: završni ispit.