• Šifra predmeta:63283
  • Kreditne točke:6
  • Semester: zimski
  • Vsebina

1. Uvod: Algoritem intuitivno.

2. Zgodovina: Kriza v osnovah matematike 20. stoletja. Reševanje iz krize. Formalni sistemi. Hilbertov program. Godlova izreka.

3. Uvod v izračunljivost: Kaj je algoritem in računanje? Računski modeli. ChurchTuringova teza. Turingov stroj in različice. Nedeterminizem.

4. Univerzalni TS. Model RAM in splošno namenski računalniki. Izrek o rekurziji, rekurzivno definiranje in računanje.

5. 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.)

6. 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.

7. 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.

8. Obvladovanje težkih problemov: Osnovno o verjetnostnem, aproksimativnem in paralelnem računanju. Osnovno o interaktivnem dokazovanju. Primeri v praksi.

9. Novejši pristopi: Osnovno o kvantnem računanju. 

 

Cilji in kompetence: Cilj predmeta je dvojen: 1) študenta opremiti s sodobnim znanjem s področja teoretičnega računalništva in 2) študenta usposobiti, da bo lahko to znanje uspešno uporabljal pri reševanju problemov v praksi.

 

Metode poučevanja in učenja: Predavanja, domače naloge, seminarski način dela pri vajah. Poudarek je na sprotnem študiju in samostojnem delu pri vajah, seminarskih in domačih nalogah.

 

Načini ocenjevanja: Način (pisni izpit, ustno izpraševanje, naloge, projekt): Oceno sestavljata dva dela: prvi (50%) je za sprotno delo, drugi (50%) pa za ustni in pisni izpit. Obveznosti predmeta so uspešno opravljene le, če sta oba dela pozitivna. V sprotno delo sodijo vaje in seminarske naloge. Ocene: 6-10 pozitivno, 5 negativno (v skladu s Statutom UL). 

  • Študijski programi
  • Porazdelitev ur na semester
45
ur
predavanj
30
ur
avditornih vaj
  • Izvajalci
Nosilec predmeta
Prostor:R2.05
Asistent
Prostor:R2.30-LALG
Asistent
Prostor:R2.30