Теорија комплексности

Рекурзивне функције. Тјурингове машине и њихови језици. Дефиниција комплексности алгоритма. Временска и просторна комплексност. Класе комплексности. Примери полиномних алгоритама. Редукције. P=NP питање. NP-комплетни проблеми, примери. Класа coNP. Просторна комплексност. Савичева теорема. Класе L и NL. Класа Pspace, победничке стратегије. Проблеми пребрајања. Вероватносни алгоритми. Класе BPP, RP и coRP. Дерандомизација. Мали узорачки простори. Апроксимативни алгоритми. Класа NPO. Део наставе на предмету се одвија кроз самостални студијски истраживачки рад.

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