General information
Teorijsko računarstvo 24/25
Teorijsko računarstvo
Literatura
[1] N. Ikodinović, Teorija algoritama, beleške (strane 1--108)
[2] Juraj Hromkovič, Algotimic Adventures, from Knowledge to Magic (prva četiri poglavlja knjige)
Konsultativna nastava
sredom, 14.00 (Stud. trg), uz prethodnu najavu mejlom; dolazak na konsultacije treba najaviti dan ranije
Polaganje ispita
Predispitne obaveze: Seminarski rad iz dva dela, na osnovu knjige [2]
1. deo: napraviti izbor zadataka iz prvih pet poglavlja knjige (najmanje 50% po poglavlju) i detaljno ih rešiti. Seminarski treba da sadrži i postavke i rešenja zadataka.
2. deo: izabrati jednu napredniju temu iz drugog dela knjige [2] (jedno od poglavlja 6-10) i detaljno ga prikazati koristeći eventualno i dodatnu literaturu.
Seminaski rad treba predati u elektronskoj formi, pre ispitnog roka u kome se planira polaganje. Ukoliko je seminarski korektan, organizuje se usmeni ispit.
Usmeni deo: odbrana seminarskog rada i diskusija o teorijskom delu (dodatno, očekuje se poznavanje sadržaja iz [1], str 1--108.) Usmeni deo ispita biće organizovan u ispitnim rokovima po dogovoru mejlom.
Osnovne informacije o kursu
Stud. program MAS Matematika (akreditacija 2015/2022)
Moduli: Profesor matematike i računarstva; Terijska matematika i primene
Predmet je srodan predmetima Teorija algoritama/izračunljivosti na osnovnim studijama matematike/informatike, kao i predmetu Teorija rekurzija na doktorskim studijama matematike.
Ukratko: Od davnina, matematika obiluje algoritmima za rešavanje raznovrsnih klasa problema. Ipak, na pojavu i razvoj savremenog računara suštinski je uticalo otkriće problema koji se ne mogu algoritamski rešiti.
Sadržaj, ishodi i polaganje predmeta:
1. Osnovni koncepti teorije izračunljivosti
* Formalno i neformalno razumevanje koncepta izračunljivosti i odlučivosti Apstraktne mašine (Registar mašine, Tjuringove mašine)
2. Neodlučivost (Diofantov problem, problem zaustavljanja, problem reči, problem valjanosti, problem popoločavanja itd.)
* Primena metode svođenja jednog problema na drugi, sa elementima klasifikacije problema po „težini“)
3. Odabrane napredne teme (probabilistički algoritmi, kvantna izračunljivost, DNK izračunavanje itd. u skladu sa predznanjem i interesovanjima slušalaca)
* samostalna obrada i prikaz jedne teme, uz konsultacije i uputstva
Predispitne obaveze: 70 poena
Domaći zadaci [za teme 1,2], odn. seminarski rad [za temu 3] i njihova odbrana na vežbama
Usmeni ispit: 30 poena
Ocena se formira na osnovu broja stečenih poena:
51 – 60 = ocena 6
61 – 70 = ocena 7
71 – 80 = ocena 8
81 – 90 = ocena 9
91 – 100 = ocena 10
Teorijsko računarstvo 2023/24
Teorijsko računarstvo
Literatura
[1] N. Ikodinović, Teorija algoritama, beleške (strane 1--108)
[2] Juraj Hromkovič, Algotimic Adventures, from Knowledge to Magic (prva četiri poglavlja knjige: )
Konsultativna nastava
ponedeljkom, 15.00 (Stud. trg), uz prethodnu najavu mejlom; dolazak na konsultacije treba najaviti dan ranije
Polaganje ispita
· Seminarski rad
1. mogućnost: napraviti izbor zadataka iz prva četiri poglavlja knjige (najmanje 50% po poglavlju) i detaljno ih rešiti. Postavke zadataka i rešenja pripremiti u obliku seminarskog rada i predati u pisanoj ili elektronskoj formi.
2. mogućnost: izabrati jednu napredniju temu (npr. jednu od tema iz drugog dela knjige [2], poput: kvantna izračunljivost, probabilistički algoritmi, složenost izračunavanja, DNK izračunavanje itd.); struktura, sadržaj i litaratura rada za izabranu temu se naknadno dogovaraju.
· Usmeni deo: odbrana seminarskog rada i diskusija o teorijskom delu (dodatno, očekuje se poznavanje sadržaja iz [1], str 1--108.) Usmeni deo ispita biće organizovan u ispitnim rokovima po dogovoru.
Obaveštenje poslato na adrese iz StudInfo sistema: U petak, 20. 10. biće održano uvodno predavanje, prema važećem raspredu: od 18:15 u učionici RLAB. Vežbe iz TR neće biti održane u četvrtak 19. 10. 2023.
Stud. program MAS Matematika (akreditacija 2015/2022)
Moduli: Profesor matematike i računarstva; Terijska matematika i primene
Predmet je srodan predmetima Teorija algoritama/izračunljivosti na osnovnim studijama matematike/informatike, kao i predmetu Teorija rekurzija na doktorskim studijama matematike.
Ukratko: Od davnina, matematika obiluje algoritmima za rešavanje raznovrsnih klasa problema. Ipak, na pojavu i razvoj savremenog računara suštinski je uticalo otkriće problema koji se ne mogu algoritamski rešiti.
Sadržaj, ishodi i polaganje predmeta:
1. Osnovni koncepti teorije izračunljivosti
* Formalno i neformalno razumevanje koncepta izračunljivosti i odlučivosti Apstraktne mašine (Registar mašine, Tjuringove mašine)
2. Neodlučivost (Diofantov problem, problem zaustavljanja, problem reči, problem valjanosti, problem popoločavanja itd.)
* Primena metode svođenja jednog problema na drugi, sa elementima klasifikacije problema po „težini“)
3. Odabrane napredne teme (problem P=?NP, probabilistički algoritmi, kvantna izračunljivost itd. u skladu sa predznanjem i interesovanjima slušalaca)
* samostalna obrada i prikaz jedne teme, uz konsultacije i uputstva
Predispitne obaveze: 70 poena
Domaći zadaci [za teme 1,2], odn. seminarski rad [za temu 3] i njihova odbrana na vežbama
Usmeni ispit: 30 poena
Ocena se formira na osnovu broja stečenih poena:
51 – 60 = ocena 6
61 – 70 = ocena 7
71 – 80 = ocena 8
81 – 90 = ocena 9
91 – 100 = ocena 10
TR 2022/23
Literatura
prva četiri poglavlja knjige: Juraj Hromkovič, Algotimic Adventures (from Knowledge to Magic) link
Konsultativna nastava
utorkom, 10.00 u učionici N206 (Sv. Nikola), uz prethodnu najavu mejlom; dolazak na konsultacije treba najaviti dan ranije
Polaganje ispita
· Seminarski rad: napraviti izbor zadataka iz prva četiri poglavlja knjige (dovoljno je oko 50% po poglavlju) i detaljno ih rešiti. Postavke zadataka i rešenja pripremiti u obliku seminarskog rada i predati u pisanoj ili elektronskoj formi.
· Usmeni deo: diskusija o rešenjima zadataka i razgovor o teorijskom delu. Usmeni deo ispita biće organizovan u ispitnim rokovima po dogovoru.