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

Студије
Докторске академске студије (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 

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