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