U letnjem semestru 2011/12 održaće se doktorski kurs iz Teorije kompleksnosti. Predavanja će se održavati svake druge nedelje četvrtkom od 10:00 do 14:00 u učionici 8 na Računarskom fakultetu (Knez Mihailova 6/6, Beograd). Prvo predavanje zakazano je za četvrtak 22. mart 2012. godine. Reč je o besplatnom kursu koji je otvoren svim postdiplomskim studentima. Kurs je dizajniran tako da ne podrazumeva predznanje iz oblasti teorije kompleksnosti, već da na uvodnom, doktorskom nivou upozna studente sa terminologijom, metodama i osnovnim dostignućima te oblasti. Organizator kursa je dr Kristina Vušković, profesor Računarskog fakulteta.
Svi zainteresovani studenti mogu da se prijave slanjem poruke na kvuskovic @ raf.edu.rs.
Kurs: Teorija kompleksnosti
Predavač (letnji semestar 2011/12): Dragan Urošević, Računarski fakultet, Beograd i Matematički institut SANU
Sadržaj:
Rekurzivne funkcije. Turingove mašine i njihovi jezici. Definicija kompleksnosti algoritma. Vremenska i prostorna kompleksnost. Klase kompleksnosti. Primeri polinomnih algoritama. Redukcije. P=NP pitanje. NP-kompletni problemi, primeri. Klasa coNP. Prostorna kompleksnost. Savičeva teorema. Klase L i NL. Klasa Pscape, pobedničke strategije. Problemi prebrajanja. Verovatnosni algoritmi. Klase BPP, RP, coRP. Derandomizacija. Mali uzorački prostori. Aproksimativni algoritmi. Klasa NPO.
Literatura:
- 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.