Teorija izračunljivosti

Matematika u tehnici

Predmetni nastavnik: dr Ivan Prokić

Termin nastave: letnji semestar, utorak, 13:15-16:45

Nastavnik: Ivan Prokić, kabinet 117, F blok, e-mail: ivan.prokic90@gmail.com

NAČIN POLAGANJA

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

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

Jun 2022.

K1 i Seminarski 2022.

Primeri zadataka

Zadaci-Maj 2022.