Fakultet tehničkih nauka

Predmet: Diskretne verovatnosne strukture (17.DOM65L)

Osnovne informacije:
 
Kategorija Naučno-stručni
Uža naučna oblast
  • Primenjene računarske nauke i informatika
  • Teorijska i primenjena matematika
ESPB 10

Usvajanje znanja i tehnika primene teorije verovatnoće na diskretne strukture i kombinatorne probleme.

Očekuje se da uspešan student usvoji osnovne koncepte teorije verovatnoće nad diskretnim strukturama i osnovnih metoda u njenoj primeni na rešavanje kombinatornih problema, sa posebnim akcentom na slučajne grafove.

Osnovi verovatnosnog metoda. Primena linearnosti očekivanja i metod prvog momenta, deljenje grafova, Ramzejevi brojevi, nezavisni skup čvorova, bojenja. Metod drugog momenta. Koncentracija parametra. Černofova ograničenja. Slučajni grafovi. Pojavljivanje podgrafa, povezanost grafa, najveća klika, hromatski broj, gigantska komponenta, fazna tranzicija. Pozicione igre na slučajnim grafovima. Pseudo-slučajni grafovi. Lovasova lokalna lema, primene. Diskrepanca, linearna i nasledna. Kodiranje, teorija igara, igra lažova. Derandomizacija, mali uzorački prostori. Slučajne šetnje. Entropija.

Predavanja su auditorna. Na predavanjima se izlažu osnovni principi i mogućnosti korišćenja usvojenih tehnika na rešavanje konkretnih kombinatornih problema, sa posebnim akcentom na teoriju slučajnih grafova.

Autori Naziv Godina Izdavač Jezik
Noga Alon, Joel Spencer The Probabilistic Method 2015 John Wiley & Sons, Inc Engleski
M. Mitzenmacher, E. Upfal Probability and computing: Randomized algorithms and probabilistic analysis 2005 Cambridge Uinversity Press Engleski
Svante Janson, Tomasz Luczak, Andrzej Rucinsky Random Graphs 2000 Wiley & Sons, Inc. Engleski
Predmetna aktivnost Predispitna Obavezna Broj poena
Predmetna aktivnost
Prisustvo na predavanjima
Predispitna
Da
Obavezna
Da
Broj poena
10.00
Predmetna aktivnost
Seminarski rad
Predispitna
Da
Obavezna
Da
Broj poena
20.00
Predmetna aktivnost
Usmeni deo ispita
Predispitna
Ne
Obavezna
Da
Broj poena
70.00