Teorija izračunljivosti, Matematika u tehnici


Termin nastave: letnji semestar, utorak, 13:15-16:45
Nastavnik: Ivan Prokić, kabinet 117, F blok, e-mail: ivan.prokic90@gmail.com


Plan rada i sadržaj kursa

1. Uvodni čas. Pojam algoritma. Analiza algoritama. Vremenska složenost. slajdovi
2. Asimptotske notacije. Merge sort algoritam. slajdovi
3. Sistemi za obračunavanje složenosti. Metod substitucije. Rekurzivna stabla. slajdovi
4. Master metoda. Linearne rekurentne relacije sa konstantnim koeficijentima. slajdovi
5. Neki algoritmi polinomne složenosti. slajdovi
6. Prosto rekurzivne, rekurzivne i parcijalno rekurzivne funkcije. slajdovi
7. Rekurzivni i rekurzivno nabrojivi skupovi. slajdovi
8. Tjuringove mašine. slajdovi
9. Univerzalna Tjuringova mašina. Odlučivost. Redukcije. slajdovi
10. Nedeterministička Tjuringova mašina. NP klasa i NP-kompletnost. Polinomne redukcije. slajdovi


Literatura

1. I. Dolinka, Kratak uvod u analizu algoritama, Prirodno-matematički fakultet, Novi Sad, 2008. link
2. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, 2009.
3. M. Sipser, Introduction to the Theory of Computation, Cengage, 2013.
4. Z. Ognjanović, N. Krdžavac, Uvod u teorijsko računarstvo, Beograd-Kragujevac, 2004. link
5. K. Rosen, Discrete Mathematics and Its Applications, 2012.
6. C. Leiserson, E. Demaine, Introduction to Algorithms, MIT, kurs održan 2005. link
7. M. Sipser. Theory of Computation, MIT, kurs održan 2020. link


Rezultati


Primeri zadataka


Način polaganja ispita

Pismeni deo 1: Pojam i definicija algoritma, analiza algoritama, rast funkcija, asimptotske notacije, analiza vremena rada algoritma: 30 bodova (min. 15 bodova)
Pismeni deo 2: Rekurzivne funkcije, Tjuringove mašine, klase složenosti P i NP: 30 bodova (min. 15 bodova)
Seminarski i prezentacija: 30 bodova
Usmeni: 10 bodova