Назив предмета: Дискретна математика (Логика, графови и алгоритми )

Наставник или наставници (презиме, средње слово име): Борисављевић П. Мирјана

Статус предмета: изборни

Број ЕСПБ: 7

Услов: курсеви Математика 1 и  Математика 2, Вероватноћа и статистика, пожељан и курс Математика 3.

Циљ предмета

Детаљно упознавање са појмовима и резултатима теорије графова и конструкцијaмa ефикасних графовских алгоритама за решавање проблема у саобраћају и транспорту.

Исход предмета

Студенти ће бити оспособљени да применом теорије графова решавају проблеме у саобраћају и транспорту.

Садржај предмета

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

Препоручена литература

 1. P. Janičić, Matematička logika u računarstvu (Matematički fakultet, Beograd, 2004), нека поглавља;
 2. M. Živković, Algoritmi (Matematički fakultet, Beograd, 2000), нека поглавља;
 3. R. J. Wilson, Introduction to Graph Theory (Oliver & Boyd, Edinburgh, 1972), нека поглавља;
 4. R. Bellman, K. L. Cooke, J. A. Lockett, Algorithms, Graphs and Computers (Academic Press New York and London, 1970), нека поглавља

Број часова  активне наставе

предавања:

3

Студијски истраживачки рад:

3

Методе извођења наставе

Предавања ex-катедра и студијски истраживачки рад.

Оцена  знања (максимални број поена 100)

семинарски радови - 50, усмени испит - 50