Циљ предмета је упознавање и савлађивање неких стандардних садржаја дискретне математике (као што су елементи математичке логике и теорије графова, релацијске структуре, коначни аутомати и формални језици) који су предвиђени за профил инжењера-информатичара.
Теоријска настава
- Уводни појмови.
- Исказни рачун. Исказна формула.
- Конјунктивна и дисјунктивна нормална форма. Правила закључивања у исказном рачуну.
- Предикатски рачун. Предикатска формула.
- Истинитосна вредност предикатске формуле. Правила закључивања у предикатском рачуну
- Релацијске структуре. Парцијално уређени скуп, ланац и решетка.
- Елементи теорије графова. Оријентисани и неоријентисани граф. Путеви у графу.
- Стабло.
- Припрема за колоквијум.
- Коначна машина и коначни аутомат.
- Минимизација аутомата. Спајање аутомата.
- Формални језици и граматике.
- Језик генерисан граматиком.
- Веза између коначних аутомата и регуларних граматика.
- Тјурингова машина
Практична настава
- Особине логичких везника.
- Елиминација неких логичких операција. Таутологије
- Примене исказног рачуна
- Дисјунктивна и конјунктивна нормална форма.
- Особине квантификатора.
- Истинитосна вредност предикатске формуле.
- Релације на коначном скупу
- Парцијално уређен скуп. Супремум. Инфимум. Решетка. Хасеов дијаграм.
- Релације еквиваленције.
- Графови. Представљање графова. Путеви у графу
- Стабла. Примене стабала у рачунарству
- Коначни аутомати.
- Минимизација коначних аутомата.
- Регуларне граматике и веза са коначним аутоматима.
- Испитни задаци.
Литература
- Чангаловић М., Тодорчевић В., Балтић В., Дискретне математичке структуре, уџбеник, ФОН, Београд 2009.
- Тодорчевић В., Балтић В., Чангаловић М., Збирка задатака из дискретних математичких структура, ФОН, Београд 2016.
- Стевановић Д., Балтић В., Симић С., Ћирић М., Дискретна математика - основе комбинаторике и теорије графова, ДМС, 2008.
- Цветковић Д., Симић С., Дискретна математика, Либра, Београд, 2000.
- Rosen K.H., Discrete Mathematics and Its Applications, fourth edition, McGraw-Hill, 1999
Материјали
