| Спецификација предмета за књигу предмета | ||||||||||
| Студијски програм | Саобраћај | |||||||||
| Изборно подручје (модул) | ||||||||||
| Врста и ниво студија | докторске академске студије | |||||||||
| Назив предмета | Дискретна математика (логика, графови, алгоритми) | |||||||||
| Број ЕСПБ | 7 | Статус предмета (обавезни/изборни) | изборни | |||||||
| Услов | Математика 1, Математика 2, Математика 3, пожељан курс Вероватноћа и статистика | |||||||||
| Циљ предмета |
Стицање знања из дискретне математике ради решавања проблема из области истраживања студента | |||||||||
| Исход предмета |
По завршетку курса студент познаје основне појмове исказног и предикатског рачуна, има основна знања из теорије графова и теорије алгоритама. Разуме основне резултате теорије графова и уме да их примени за решавање конкретних проблема. Разуме појам израчунљивости и уме да пише једноставне програме за Тјурингову машину и покаже рекурзивност неких функција. Студент разуме формални и неформални појам алгоритма и појмове одлучивих и неодлучивих проблема. Студент је оспособљен је да примени стечено знање у областима у којима се користе појмови и технике којима је овладао међу којима је и област рачунарства. | |||||||||
| Садржај предмета | ||||||||||
| Теоријска настава |
Oснове математичке логике: исказни рачун (појам
исказа, основне операције са исказима, исказне формуле, таутологије; важни
примери и методе доказивања. СДНФ и СКНФ); предикатски рачун првог реда (језик првог реда, терми и формуле, ваљане формуле, важни примери и примене; појам формалног система; једноставни примери. Основе теорије графова: граф; врсте графова; операције над графовима; разни начини представљања графова; повезаност графова; планарни графови; Ојлерови и Хамилтонови графови; проблем трговачког путника; проблем најкраћег пута. Основе теорије израчунљивости: УР-машина, Тјурингова машина; израчунљивост; рекурзивне функције. Алгоритми: појам алгоритма; најједноставнији примери; детерминистички и недетерминистички алгоритми; дефиниције П и НП тешких проблема и НП-комплетних проблема; примери НП-тешких и НП-комплетних проблема. |
|||||||||
| Практична настава (вежбе, ДОН, студијски истражива-чки рад) | Студијски истраживачки рад у договору са наставником. | |||||||||
| Литература | ||||||||||
| 1 | П. Јаничић, Математичка логика у рачунарству Математички факултет, Београд, 2004, нека поглавља | |||||||||
| 2 | М.
Борисављевић, Увод у логику, први део, Саобраћајни факултет, Београд, 2009, нека поглавља |
|||||||||
| 3 | N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge University Press, 1980, нека поглавља | |||||||||
| 4 | М. Живковић, Алгоритми, Математички факултет, Београд, 2000, нека поглавља | |||||||||
| 5 | R.J. Wilson, Introduction to Graph Theory, 1999, Longman Group Ltd, нека поглавља | |||||||||
| Број часова активне наставе недељно током семестра/триместра/године | ||||||||||
| Предавања | Вежбе | ДОН | Студијски истраживачки рад | Остали часови | ||||||
| 3 | 3 | 8 | ||||||||
| Методе извођења наставе |
Предавања и студијски истраживачки рад у договору са наставником. | |||||||||
| Оцена знања (максимални број поена 100) | ||||||||||
| Предиспитне обавезе | поена | Завршни испит | поена | |||||||
| активност у току предавања |
писмени испит | 30 | ||||||||
| практична настава | усмени испит | 50 | ||||||||
| колоквијуми | ||||||||||
| семинари | 20 | |||||||||