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

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

Рачунарски факултет Рачунарски факултет 011-33-48-079