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

Студије
Основне академске студије (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.
  • Тодорчевић В., Балтић В., Чангаловић М., Збирка задатака из дискретних математичких структура, ФОН, Београд 2016.
  • Стевановић Д., Балтић В., Симић С., Ћирић М., Дискретна математика - основе комбинаторике и теорије графова, ДМС, 2008.
  • Цветковић Д., Симић С., Дискретна математика, Либра, Београд, 2000.
  • Rosen K.H., Discrete Mathematics and Its Applications, fourth edition, McGraw-Hill, 1999
    ПРАВИЛА ПОЛАГАЊА
  • Правила полагања у школској 2021/22. години.


Материјали

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