Студијски програм:

ИС_ТИ, ОАС ИТ

Назив предмета:

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

Наставник:

Дамљановић Ж. Нада

Статус предмета:

И, И

Број ЕСПБ:

6

Услов:

Нема

Циљ предмета

Упознавање са основним концептима дискретне математике.

Исход предмета

Стечена знања користе се у даљем образовању и у стручним предметима, повезују се знања из дискретне математике са разним  областима информатике.

Садржај предмета

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

Исказна логика: искази, логички везници, исказне формуле, логичка еквивалентност, таутологије и контрадикције, логичка аргументација, правила закључивања, грешке у закључивању. Предикатска логика: предикати, квантификатори, логичка аргументација са квантификаторима. Технике доказивања: методе доказивања, директни и индиректни докази, грешке у доказивању, стратегије доказивања, резоновање унапред и уназад, математичка индукција, рекурзивне дефиниције, структурна индукција. Скупови: једнакост и инклузија, скуповне операције, уређене n-торке, Декартов производ. Релације: релације еквиваленције, партиције скупа, уређени скупови. Функције: кореспонденције и функције, бијекције, инверзна функција, операције, низови и матрице. Кардинали и пребројавање: кардиналност скупа, коначни и бесконачни скупови, пребројиви и непребројиви скупови, принципи пребројавања, пермутације, принцип укључења-искључења. Алгебарске структуре: групоиди, полугрупе, групе, полупрстени, прстени, поља, конгруенције и количнички скупови, Булове алгебре, минимизација Булових функција, бинарни дијаграми одлучивања. Формални језици: Операције и комбинаторика на речима, формални језици, генеративне граматике, класификација граматика. Аутомати: Детерминистички и недетерминистички аутомати, минимални аутомат језика, регуларни изрази и њихове примене, аутомати са излазом, аутомати Mealyevog и Mooreovog типа, еквивалентни аутомати, минимизација аутомата са излазом. Тјурингове машине: њихови језици, питања одлучивости, израчунљивости и комплексности. Графови: планарност, Ојлерова шетња, Хамилтонов циклус и проблем трговачког путника, упаривање у бипартитним графовима, хроматски број графа, стабла, директни графови, означени графови.

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

Аудиторне вежбе прате садржај предавања, на вежбама се разрађује практичан део предмета, кроз израду задатака из сваке области.

Литература:

1.

М. Ћирић, Ј. Игњатовић, Теорија алгоритама, језика и аутомата, збирка задатака, ПМФ у Нишу, 2012.

2.

В. Лазаревић, Збирка задатака из математике информатике, Технички факултет у  Чачку, 2004.

3.

Цветковић, С. Симић, Дискретна математика, Просвета, Ниш, 1996.

4.

З. Огњановић, Н. Крџавац, Увод у теоријско рачунарство, ФОН Београд FON, 2004.

(http://www.mi.sanu.ac.rs/~zorano/ti/TeorijskoRacunarstvo.pdf).

5.

     

Број часова  активне наставе

Предавања:

2

Вежбе:

3

Други облици наставе:

0

Остали часови:

  

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

  

Методе извођења наставе

На предавањима и вежбама се користе класичне методе наставе уз коришћење видео пројектора и интеракцију са студентима. Знање студената се тестира преко израде домаћих задатака, колоквијума и завршног (писменог и усменог) испита. На завршном испиту се проверава свеобухватно разумевање изложеног градива.

Оцена  знања (максимални број поена 100)

Предиспитне обавезе

поена

Завршни испит

поена

активност у току предавања

3

писмени испит

35

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

3

усмени испит

25

колоквијум-и

30

..........

     

семинар-и

4