У летњем семестру 2011/12 одржаће се докторски курс из Теорије комплексности. Предавања ће се одржавати сваке друге недеље четвртком од 10:00 до 14:00 у учионици 8 на Рачунарском факултету (Кнез Михаилова 6/6, Београд). Прво предавање заказано је за четвртак 22. март 2012. године. Реч је о бесплатном курсу који је отворен свим постдипломским студентима. Курс је дизајниран тако да не подразумева предзнање из области теорије комплексности, већ да на уводном, докторском нивоу упозна студенте са терминологијом, методама и основним достигнућима те области. Организатор курса је др Кристина Вушковић, професор Рачунарског факултета.
Сви заинтересовани студенти могу да се пријаве слањем поруке на kvuskovic @ raf.edu.rs.
Курс: Теорија комплексности
Предавач (летњи семестар 2011/12): Драган Урошевић, Рачунарски факултет, Београд и Математички институт САНУ
Садржај:
Рекурзивне функције. Турингове машине и њихови језици. Дефиниција комплексности алгоритма. Временска и просторна комплексност. Класе комплексности. Примери полиномних алгоритама. Редукције. P=NP питање. NP-комплетни проблеми, примери. Класа coNP. Просторна комплексност. Савичева теорема. Класе L и NL. Класа Pscape, победничке стратегије. Проблеми пребрајања. Вероватносни алгоритми. Класе BPP, RP, coRP. Дерандомизација. Мали узорачки простори. Апроксимативни алгоритми. Класа NPO.
Литература:
- C. Papadimitriou, Computational Complexity, Addison Wesley Longman, 1995.
2. L.A. Hemaspaandra amd M. Ogihara, The Complexity Theory Companion, Springer, 2002.
3. D.P. Bovet and P. Crescenzi, Theory of Computational Complexity, Prentice Hall, 1994.