Matematička teorija računarstva

Cilj kolegija je studente upoznati s fundamentalnim konceptima i rezultatima teorije izračunljivosti kao i teorije složenosti algoritama. Što neki problem čini računalno složenim a drugi pak jednostavnim? Na to pitanje ne znamo odgovoriti no studenti trebaju naučiti klasificirati probleme u skladu s njihovom složenošću. Usko vezan uz pojam složenosti je pojam izračunljivosti: studenti uče razlučiti odlučive probleme od neodlučivih. Na samom kraju studenti bi trebali razumjeti u čemu se sastoji rješenje Hilbertovog desetog problema te ideju dokaza Gödelovih teorema nepotpunosti.