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

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

Циљ предмета је упознавање и савлађивање неких стандардних садржаја дискретне математике (као што су елементи математичке логике и теорије графова, релацијске структуре, коначни аутомати и формални језици) који су предвиђени за профил инжењера-информатичара.

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

  1. Уводни појмови. 
  2. Исказни рачун. Исказна формула. 
  3. Конјунктивна и дисјунктивна нормална форма. Правила закључивања у исказном рачуну. 
  4. Предикатски рачун. Предикатска формула. 
  5. Истинитосна вредност предикатске формуле. Правила закључивања у предикатском рачуну 
  6. Релацијске структуре. Парцијално уређени скуп, ланац и решетка. 
  7. Елементи теорије графова. Оријентисани и неоријентисани граф. Путеви у графу. 
  8. Стабло. 
  9. Припрема за колоквијум. 
  10. Коначна машина и коначни аутомат. 
  11. Минимизација аутомата. Спајање аутомата. 
  12. Формални језици и граматике. 
  13. Језик генерисан граматиком. 
  14. Веза између коначних аутомата и регуларних граматика. 
  15. Тјурингова машина

Практична настава

  1. Особине логичких везника. 
  2. Елиминација неких логичких операција. Таутологије 
  3. Примене исказног рачуна 
  4. Дисјунктивна и конјунктивна нормална форма. 
  5. Особине квантификатора.  
  6. Истинитосна вредност предикатске формуле. 
  7. Релације на коначном скупу 
  8. Парцијално уређен скуп. Супремум. Инфимум. Решетка. Хасеов дијаграм.
  9. Релације еквиваленције. 
  10. Графови. Представљање графова. Путеви у графу 
  11. Стабла. Примене стабала у рачунарству 
  12. Коначни аутомати. 
  13. Минимизација коначних аутомата. 
  14. Регуларне граматике и веза са коначним аутоматима.
  15. Испитни задаци.


Литература

  • Чангаловић М., Којић В., Балтић В., Дискретне математичке структуре, уџбеник, ФОН, Београд 2009.
  • Манојловић В., Чангаловић М., Збирка задатака из Дискретних математичких структура, ФОН, Београд, 2012.
  • Балтић В., Дискретне математичке структуре - збирка испитних и домаћих задатака из 2008. и 2009.
  • Стевановић Д., Балтић В., Симић С., Ћирић М., Дискретна математика - основе комбинаторике и теорије графова, ДМС, 2008.
  • Цветковић Д., Симић С., Дискретна математика, Либра, Београд, 2000.
  • Rosen K.H., Discrete Mathematics and Its Applications, fourth edition, McGraw-Hill, 1999.


Материјали

Отворене су пријаве!
Први усмени колоквијум

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