Predmet: Teorija izračunljivosti (17.0M537 )
Matične organizacione jedinice predmeta:
Studijski programi predmeta:
| Stepen i vrsta studija | Naziv |
|---|---|
| Master akademske studije | Matematika u tehnici ( |
| Master akademske studije | Informacioni inženjering (Godina: 1, Letnji) |
| Master akademske studije | Informacioni i analitički inženjering (Godina: 1, Letnji) |
Cilj:
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.
Ishod:
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.
Sadržaj:
Pojam algoritma i izračunljivosti. Rekurzivne funkcije. Tjuringove mašine. Čerč-Tjuringova teza. Odlučivost i procedure odlučivanja. Vremenska složenost.
Metodologija izvođenja nastave:
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.
Literatura:
| Autori | Naziv | Godina | Izdavač | Jezik |
|---|---|---|---|---|
| 2006 | Engleski | |||
| Janičić, P. | Matematička logika u računarstvu | 2009 | Matematički fakultet, Beograd | Srpski jezik |
| R.Tošić, S.Crvenković | Zbirka zadataka iz teorije algoritama | 1980 | Institut za matematiku, Novi Sad | Srpski jezik |
| Igor Dolinka | Kratak uvod u analizu algoritama | 2008 | Futura, Novi Sad | Srpski jezik |
| 1989 | Engleski | |||
| 1997 | Engleski |
Formiranje ocene:
| Predmetna aktivnost | Predispitna | Obavezna | Broj poena |
|---|---|---|---|
| Pismeni deo ispita - kombinovani zadaci i teorija | Ne | Da | 40.00 |
| Test | Da | Da | 10.00 |
| Prisustvo na vežbama | Da | Da | 5.00 |
| Prisustvo na predavanjima | Da | Da | 5.00 |
| Teorijski deo ispita | Ne | Da | 30.00 |
| Test | Da | Da | 10.00 |
Izvođači nastave:
doc. Prokić Ivan
Docent
Računarske vežbe
doc. Prokić Ivan
Docent
Auditorne vežbe
doc. Ilić Vladimir
Docent
