Циљ предмета je oвладавање оним математичким знањима која су неопходна за развој и реализацију високог нивоа различитих врста формализације у области информационих система и рачунарских наука.
Теоријска настава
- Формалне теорије:
- Основна дефиниција.
- Појам извођења и теореме у формалној теорији.
- Одлучиве формалне теорије.
- Примери формалних теорија.
- Принцип резолуције.
- Хебрандова теорема.
- Рекурзивне и израчунљиве функције:
- Основна дефиниција.
- Аритметизација формалних теорија и проблем одлучивости.
- Ламбда рачун и његова примена у приказивању рекурзивних функција.
- Рекурзивне процесиране листе.
- Релацијска алгебра:
- Појам релације.
- Операције над једном и више релација.
- Функционалне зависности међу релацијама.
- Кључ релације.
- Вишезначне функционалне зависности.
- Елементи теорије нумеричке сложености:
- Мерење сложености проблема и алгоритама.
- Полиномијално решиви проблеми.
- Тјурингова машина.
- Черчова хипотеза.
- Класа НП. НП-потпуни и НП-тешки проблеми.
- Примене у криптографији:
- Класична криптографија.
- Случајна шифра.
- DES и RSA алгоритми.
Студијски истраживачки рад
- Израда семинарског рада на тему примене алата дискретне математике на изабрани проблем из области информационих система и рачунарских наука.
Литература
- Д. Цветковић, С. Симић, Дискретна математика, Математика за компјутерске науке, Либра, Београд, 2000.
- П. Јаничић, Математичка логика у рачунарству, Математички факултет, Београд, 2004
- З. Огњановић, Н. Крџавац, Увод у теоријско рачунарство, ФОН, Београд 2004.
- М. Чангаловић, В. Манојловић, В. Балтић, Дискретне математичке структуре, ФОН, Београд, 2009
- А.Ј. Андерсон, Дискретна математика са комбинаториком, Рачунарски факултет, Београд, 2005
- J.A. Dossey, A.D. Otto, L.E. Spence, C. Vanden Eynden, Discrete mathematics, Pearson, Addison Wesley, Boston, 2006
