Fakultet tehničkih nauka

Predmet: Teorija izračunljivosti (17.0M537)

Osnovne informacije:
 
Kategorija Naučno-stručni
Uža naučna oblast Teorijska i primenjena matematika
ESPB 5

Osnovni cilj predmeta jeste sticanje osnovnih znanja iz teorije algoritama, uključujući pojam algoritma, rekurzivnih funkcija, Tjuringove mašine i vremenske složenosti. Studenti će biti upoznati sa ovim fundamentalnim pojmovima, ali i sa njihovom primenom u raznim granama računarstva (pre svega na razvoj programskih jezika i modela za konkurentne sisteme). Tokom izvođenja predmeta, biće proučavane navedene formalne metode i tehnike, kroz primere i diskusiju. Konačni cilj jeste da studenti razviju veštine za analiziranje ponašanja algoritama.

Kao ishod predmeta, student će posedovati osnovna znanja iz teorije algoritama i njihove kompleksnosti. Pored toga, studenti će ovladati veštinom analiziranja složenosti algoritma, koristeći poznate metode.

Pojam algoritma i izračunljivosti. Rekurzivne funkcije. Tjuringove mašine. Čerč-Tjuringova teza. Odlučivost i procedure odlučivanja. Vremenska složenost.

Na predavanjima se izlaže teoretski deo gradiva propraćen karakterističnim primerima radi lakšeg razumevanja gradiva. Student samostalno proučava dodatnu literaturu i diskutuje je sa nastavnikom na konsultacijama.

Autori Naziv Godina Izdavač Jezik
Pippinger, N. Theories of computability 1997 Cambridge University Press, Cambridge Engleski
Janičić, P. Matematička logika u računarstvu 2009 Matematički fakultet, Beograd Srpski jezik
Igor Dolinka Kratak uvod u analizu algoritama 2008 Futura, Novi Sad Srpski jezik
R.Tošić, S.Crvenković Zbirka zadataka iz teorije algoritama 1980 Institut za matematiku, Novi Sad Srpski jezik
Sipser, M. Introduction to the Theory of Computation 2006 Thomson Course Technology, Boston Engleski
Epstein, R.L., Carnielli, W.A. Computability. Computable Functions, Logic, and the Foundations of Mathematics 1989 Wadsworth & Brooks, Pacific Grove Engleski
Predmetna aktivnost Predispitna Obavezna Broj poena
Predmetna aktivnost
Test
Predispitna
Da
Obavezna
Da
Broj poena
10.00
Predmetna aktivnost
Teorijski deo ispita
Predispitna
Ne
Obavezna
Da
Broj poena
30.00
Predmetna aktivnost
Prisustvo na predavanjima
Predispitna
Da
Obavezna
Da
Broj poena
5.00
Predmetna aktivnost
Prisustvo na vežbama
Predispitna
Da
Obavezna
Da
Broj poena
5.00
Predmetna aktivnost
Pismeni deo ispita - kombinovani zadaci i teorija
Predispitna
Ne
Obavezna
Da
Broj poena
40.00
Predmetna aktivnost
Test
Predispitna
Da
Obavezna
Da
Broj poena
10.00
Predavanja
Auditorne vežbe
Računarske vežbe