Kombinatorika i teorija grafova (mladenovic)

КОМБИНАТОРИКА И ТЕОРИЈА ГРАФОВА


Општи преглег предмета
Већина инжењерских проблема се може дефинисати над дискретним просторима. Дисциплина која испитује и нуди детаљне оговоре
на питања распореда и свакаквог пребројаванја елемената над дискретним скуповима јесте комбинаторика.
Са друге стране, основу за моделирање ових проблема можемо потражити у теорији графова. Оног тренутка када је модел коретно
постављен можемо уз постојеће алате (алгоритме) решити врло комплексне задатке. Утврдити којој категорији разматрани проблем
припада представља део вештине за који овај курс нуди основу уз неке напредније примере.
Пошто у пракси често постављамо за циљ да минимизујемо (максимизујемо) издатке (добит) над разматраним проблемом, природна
екстензија домена комбинаторике и теорије графова јесте комбинаторна оптимизација.


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

Практична настава
На часовима вежби фокус ће бити на присутности графова у свакодневном животу (практични проблеми) и како их можемо
моделирати и решити. Теоретски оквири ће бити дискутовани на предавањима.

Пожељна предзнања
Овај курс садржи појмове и методе које са којима су студенти требали да се упознају у ранијим курсевима: алгоритми и структуре
података и математичка анализа. Поред ових предмета корисно би било да су пратили курсеве генетски алгоритми и машинско
учење.

Kreatori kursa: Marko Mladenovic