Predavanja:
Uvod: Algoritem intuitivno.
Zgodovina: Kriza v osnovah matematike 20. stoletja. Reševanje iz krize. Formalni sistemi. Hilbertov program. Godlova izreka.
Uvod v izračunljivost: Kaj je algoritem in računanje? Računski modeli. Church-Turingova teza. Turingov stroj in različice. Nedeterminizem.
Univerzalni TS. Model RAM in splošno namenski računalniki. Izrek o rekurziji, rekurzivno definiranje in računanje.
Neizračunljivost. Jezik in množica. Odločitveni problemi. Neizračunljivi problemi obstajajo. Metode za dokazovanje neizračunljivosti (diagonalizacija, prevedbe, Riceov izrek) Primeri neizr. problemov in praktične posledice na raznih področjih.(Osnovno o relat. izračunljivosti in hieararhijah.)
Avtomati, gramatike, jeziki: Končni avtomat, regularna gramatika, izraz in jezik. Skladovni avtomat, kontekstno neodvisna gramatika in jezik. Linearno omejeni avtomat, kontekstno odvisna gramatika in jezik. Primeri in uporaba.
Uvod v računsko zahtevnost: Časovna, prostorska, in druge zahtevnosti. Lahki in težki problemi. Razreda P, NP, EXP in drugi. NP-polnost/težkost in njeno dokazovanje. Primeri in uporaba.
Obvladovanje težkih problemov: Osnovno o verjetnostnem, aproksimativnem in paralelnem računanju. Osnovno o interaktivnem dokazovanju. Primeri v praksi.
Novejši pristopi: Osnovno o kvantnem računanju.
Vaje: Na vajah bodo študentje utrjevali snov, podano na predavanjih. Snov bodo uporabili za reševanje praktičnih problemov, pri čemer bo poudarek na samostojnem delu ob pomoči asistentov. Implementirali bodo več manjših programov (kot domače naloge) in obsežnejše programe (kot seminarske naloge), ki jih bodo zagovarjali na vajah.
Domače in seminarske naloge:
Namen domačih nalog je ponuditi študentom priložnost za samostojno reševanje zahtevnejših nalog s področja izračunljivost in računske zahtevnosti, ki poleg domiselnosti zahtevajo nekoliko temeljitejši teoretični premislek. Oboje presega možnosti pri vajah in navaja k samostojnemu delu.