Ekstremalna kombinatorika

Opis predmeta

Primjene klasične kombinatorike na rješavanje ekstremalnih problema u diskretnoj matematici. Ekstremalna teorija skupova. Ramseyeva teorija. Vjerojatnosna metoda. Metoda linearne algebre.

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

  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.

Oblici nastave

Predavanja

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 znanja

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

Konzultacije

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

Ostali oblici skupnog ili samostalnog učenja

Rješavanje domaćih zadaća

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Napomena / komentar 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

  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.

Studijski programi

Sveučilišni diplomski
Automatika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Bežične komunikacijske tehnologije (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektroenergetika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektroničko i računalno inženjerstvo (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektronika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Elektrotehnički sustavi i tehnologija (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Obradba informacija (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Računalno inženjerstvo (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Računarska znanost (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Radiokomunikacijske tehnologije (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)
Telekomunikacije i informatika (profil)
Predmeti matematike, fizike i prirodoslovlja (1. semestar)

Literatura

Stasys Jukna (2001.), Extremal Combinatorics With Applications in Computer Science, Springer
Miklos Bona (2006.), A Walk Through Combinatorics, World scientific
B. Stechin, V. Baranov (1995.), Extremal Combinatorial Problems and Their Applications, Kluwer Academic Publishers
J. H. van Lint, R. M. Wilson (1992.), A course in combinatorics, Cambridge University Press
L. Lovász (2007.), Combinatorial Problems and Exercises, AMS Chelsea Publishing

Izvedba

ID 72538
  Zimski semestar
4 ECTS
R1 Engleski jezik
R1 E-učenje
45 Predavanja
0 Auditorne vježbe
0 Laboratorijske vježbe

Ocjenjivanje

85 izvrstan
70 vrlo dobar
55 dobar
45 dovoljan