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

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

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

Jun 2022.

K1 i Seminarski 2022.

Zadaci-Maj 2022.

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