Дискретна математика

Студије
Докторске академске студије (1. семестар)
Предавања
Мирјана Чангаловић, Весна Тодорчевић
Вежбе
Небојша Николић, Марија Боричић, Нада Младеновић, Душан Џамић

Циљ предмета je oвладавање оним математичким знањима која су неопходна за развој и реализацију високог нивоа различитих врста формализације у области информационих система и рачунарских наука.

Теоријска настава

  1. Формалне теорије: 
    1. Основна дефиниција. 
    2. Појам извођења и теореме у формалној теорији. 
    3. Одлучиве формалне теорије. 
    4. Примери формалних теорија. 
    5. Принцип резолуције. 
    6. Хебрандова теорема.
  2. Рекурзивне и израчунљиве функције:
    1. Основна дефиниција. 
    2. Аритметизација формалних теорија и проблем одлучивости. 
    3. Ламбда рачун и његова примена у приказивању рекурзивних функција. 
    4. Рекурзивне процесиране листе.
  3. Релацијска алгебра:  
    1. Појам релације. 
    2. Операције над једном и више релација. 
    3. Функционалне зависности међу релацијама. 
    4. Кључ релације.
    5. Вишезначне функционалне зависности.
  4. Елементи теорије нумеричке сложености: 
    1. Мерење сложености проблема и алгоритама. 
    2. Полиномијално решиви проблеми. 
    3. Тјурингова машина. 
    4. Черчова хипотеза. 
    5. Класа НП. НП-потпуни и НП-тешки проблеми.
  5. Примене у криптографији: 
    1. Класична криптографија. 
    2. Случајна шифра. 
    3. DES и RSA алгоритми.  

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

  1. Израда семинарског рада на тему примене алата дискретне математике на изабрани проблем из области информационих система и рачунарских наука.


Литература

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

© 2017 Катедра за математику| Факултет организационих наука | Универзитет у Београду