General information
Teorija algoritama 2023/24
Teorija algoritama 2023/24
Stud. program OAS Matematika (akreditacija 2015)
Moduli: (L) Profesor matematike i računarstva
Ukratko: Od davnina, matematika obiluje algoritmima za rešavanje raznovrsnih klasa problema. Ipak, na pojavu i razvoj savremenog računara suštinski je uticalo otkriće problema koji se ne mogu algoritamski rešiti.
Sadržaj, ishodi i polaganje predmeta:
1. Formalna aritmetika
* Raznovrsna primena principa matematičke indukcije i rekurzije, posebno u razvoju veštačkih (formalnih) jezika
2. Apstraktne mašine (Registar mašine, Tjuringove mašine)
* Formalno i neformalno razumevanje koncepta izračunljivosti i odlučivosti
3. Beskonačnost (prebrojivi i neprebrojivi skupovi)
* Razumevanje i primena metoda dijagonalizacije
4. Neodlučivost (problem zaustavljanja, problem reči, problem valjanosti, problem popoločavanja itd.)
* Primena metode svođenja jednog problema na drugi, sa elementima klasifikacije problema po „težini“)
Predispitne obaveze: 70 poena
Domaći zadaci (zadati na predavanjima) i njihova odbrana na vežbama
Pismeni ispit: 30 poena
Ocena se formira na osnovu broja stečenih poena:
51 – 60 = ocena 6
61 – 70 = ocena 7
71 – 80 = ocena 8
81 – 90 = ocena 9
91 – 100 = ocena 10
Literatura:
N. Ikodinović, Teorija algoritama (skripta)
J. Hromkovič, Algoritmic Adventures (from Konowledge to Magic), Springer, 2009