Дискретне структуре

Циљ и исход предмета

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

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

Исказни рачун – (прост и сложен) исказ, истинитосна вредност, логички везници (оператори) и њихов приоритет, таблице истинитости, логички еквивалентни искази. Аргументи и докази – ваљан аргумент, испитивање ваљаности аргумента уз помоћ таблица истинитости и доказом свођења на контрадикцију, доказивање ваљаности аргумента употребом правила извођења. Примери доказа. Комплетност у исказној логици и Карноове мапе. Скупови – скуповне операције, партитивни скуп, Декартов производ скупова, Венови дијаграми. Релације – домен и опсег релације, инверзна релација, композиција релација, особине релације на скупу, репрезентација релације, релација поретка и релација еквиваленције. Функције – ињективна, сурјективна и бијективна функција, композиција функција. Математичка индукција. Дељивост – најмањи заједнички садржалац и највећи заједнички делилац. Еуклидов алгоритам. Диофантске једначине са две непознате. Прости бројеви – теорема о јединствености факторизације на просте бројеве. Релација конгруенције. Конгруенцијске једначине. Системи конгруенцијских једначина и Кинеска теорема о остацима. Рекурзија – рекурзивне функције и хомогене и нехомогене линеарне рекурентне релације (једначине). Комбинаторика – основни принципи пребројавања (правило збира и правило производа), принцип укључења – искључења, принцип голубарника, пермутације, комбинације, уопштене пермутације и комбинације, пермутације и комбинације са понављањем.

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

Решавање репрезентативних задатака на табли, из области са којима су студенти упознати на теоријској настави.

2931-diskretne-strukture