Študenta želimo opremiti s sodobnim znanjem s področja teoretičnega računalništva. Snov bo podana strogo, toda s primerno mnogo podrobnostmi. Posebna skrb bo namenjena motiviranju, intuitivni razlagi in uporabi v praktičnem računalništvu.

Uvod: Algoritem intuitivno. Zgodovina: Kriza v matematiki 20. stoletja. Reševanje iz krize. Formalni sistemi. Hilbertov program. Godlova teorema. Uvod v izračunljivost: Kaj je algoritem in računanje? Računski modeli. Church-Turingova teza. Turingov stroj in univerzalni stroj. Neizračunljivost: Neizračunljivi problemi obstajajo. Primeri, uporaba in posledice na raznih področjih. Relativna izračunljivost in hierarhije. Avtomati, gramatike, jeziki: Končni avtomat, regularna gramatika in jezik. Skladovni avtomat, kontekstno neodvisna gramatika in jezik. Linearno omejeni avtomat, kontekstno odvisna gramatika in jezik. Hierarhija Chomskega. Primeri, uporaba in posledice na raznih področjih. Uvod v računsko zahtevnost: Prostorska, časovna in druge zahtevnosti. Lahki in težki problemi v praksi. Razreda P, NP in drugi. NP-polnost in njeno dokazovanje. Primeri, uporaba in posledice na raznih področjih. Obvladovanje težkih računskih problemov: Verjetnostno, aproksimativno in paralelno računanje. Interaktivno dokazovanje. Primeri, uporaba in posledice v praksi. Novejši pristopi: Kvantno računanje, obeti in težave.