Cilj i ishod predmeta
Razumevanje koncepta kompleksnosti algoritma. Poznavanje nekoliko osnovnih klasa kompleksnosti sa poznatim primerima koji ih reprezentuju. Razumevanje standardnih metoda za rešavanje kompleksnih problema, kao što je korišćenje aproksimativnih i verovatnosnih algoritama.
Teorijska nastava
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 Pspace, pobedničke strategije. Problemi prebrajanja. Verovatnosni algoritmi. Klase BPP, RP i coRP. Derandomizacija. Mali uzorački prostori. Aproksimativni algoritmi. Klasa NPO.
Studijski istraživački rad
Deo nastave na predmetu se odvija kroz samostalni studijski istraživački rad kroz koji student, proučavajući naučne časopise i ostalu literaturu, samostalno produbljuje gradivo sa predavanja.