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