×
Универзитет у Новом Саду

Предмет: Дискретне вероватносне структуре (17.DOM65L)

Основне информације:
 
Категорија Научно-стручни
Ужа научна област
  • Примењене рачунарске науке и информатика
  • Теоријска и примењена математика
ЕСПБ 10

Усвајање знања и техника примене теорије вероватноће на дискретне структуре и комбинаторне проблеме.

Очекује се да успешан студент усвоји основне концепте теорије вероватноће над дискретним структурама и основних метода у њеној примени на решавање комбинаторних проблема, са посебним акцентом на случајне графове.

Основи вероватносног метода. Примена линеарности очекивања и метод првог момента, дељење графова, Рамзејеви бројеви, независни скуп чворова, бојења. Метод другог момента. Концентрација параметра. Чернофова ограничења. Случајни графови. Појављивање подграфа, повезаност графа, највећа клика, хроматски број, гигантска компонента, фазна транзиција. Позиционе игре на случајним графовима. Псеудо-случајни графови. Ловасова локална лема, примене. Дискрепанца, линеарна и наследна. Кодирање, теорија игара, игра лажова. Дерандомизација, мали узорачки простори. Случајне шетње. Ентропија.

Предавања су аудиторна. На предавањима се излажу основни принципи и могућности коришћења усвојених техника на решавање конкретних комбинаторних проблема, са посебним акцентом на теорију случајних графова.

Аутори Назив Година Издавач Језик
Svante Janson, Tomasz Luczak, Andrzej Rucinsky Random Graphs 2000 Wiley & Sons, Inc. Енглески
M. Mitzenmacher, E. Upfal Probability and computing: Randomized algorithms and probabilistic analysis 2005 Cambridge Uinversity Press Енглески
Noga Alon, Joel Spencer The Probabilistic Method 2015 John Wiley & Sons, Inc Енглески
Предметна активност Предиспитна Обавезна Број поена
Предметна активност
Усмени део испита
Предиспитна
Не
Обавезна
Да
Број поена
70.00
Предметна активност
Присуство на предавањима
Предиспитна
Да
Обавезна
Да
Број поена
10.00
Предметна активност
Семинарски рад
Предиспитна
Да
Обавезна
Да
Број поена
20.00