Упознавање са прецизном дефиницијом алгоритма и машинама које потврђују његову исправност. Детерминистички и недетерминистички алгоритми и њихова терминалност. Полазници ће бити упознати са сличним меморијским захтевима. Посебно ће бити обрађене алгоритамске функције ( ефентивне и израчунљиве ).

Различити проблеми могу се једноставно класификовати као они за које знамо поступке решавања и самим тим су можда и алгоритамски решиви. Постоји могућност да нисмо у стању да дамо решење. Полазници курса ће добити основе за препознавање субјективне неспособности давања решења или се ради о потенцијалној немогућности решавања.

1. Историјски преглед израчунљивости. Интуитивни појам алгоритма 2. Тјурингова машина - ТМ. Неформални опис ТМ. ТМ и функције. Тјуринг неизрачунљиве функције. 3. Класификација Тјурингових машина и њихова реализација у C++. 4. Рекурзивне фунције и њихова веза са интуитивно израчунљивим функцијама. 5. Парцијално рекурзивне фуинкције. 6. Тјуринг израчунљиве и парцијално рекурзивне функције. 7. Черчова теза. 8. Релативна израчунљивост. 9. Предикатски рачун. Одлучиви предикати. 10. О Парцијално одлучивим предикатима.

1. Делови Тјурингове машине. Програм Тјурингове машине. 2. Покретање симулатора Тјурингове машине и разликовање детерминистичких и недетерминистичких наредби. 3. Конфигурација Тјурингове машине и програми. 4. Аритметичке функције и Тјурингова машина. 5. Примитивно рекурзивне фунције. Факторијел и f(0)=m, општи случај дефинисања f(n+1)=g(f(n),n). 6. Примери општег случаја. 7. Диофантске једначине. 8. Десети Хилбертов проблем.

Нема услова.

gcc, C, C++

укупан фонд часова: 65

ново градиво: 45
разрада и примери (рекапитулација): 5

аудиторне вежбе: 0
лабораторијске вежбе: 0
рачунски задаци: 0
семинарски рад: 0
пројекат: 0
консултације: 0
дискусија/радионица: 0
студијски истраживачки рад: 0

преглед и оцена рачунских задатака: 0
преглед и оцена лабораторијских извештаја: 0
преглед и оцена семинарских радова: 15
преглед и оцена пројекта: 0
колоквијум са оцењивањем: 0
тест са оцењивањем: 0
завршни испит: 0

активност у току предавања: 0
тест/колоквијум: 0
лабораторијска вежбања: 0
рачунски задаци: 0
семинарски рад: 70
пројекат: 0
завршни испит: 30
услов за излазак на испит (потребан број поена): 0

Z. Ognjanović, N. Krdžavac, Uvod u teorijsko računarstvo, FON, Beograd, 2004.; C. Papadimitriou, Computational complexity, Addison-Wesley, 1995.; Ž. Mijajlović, Z. Marković, K. Došen, Hilbertovi problemi i logika, Zavod za udžbenike i nastavna sredstva, Beograd, 1986.; J.Hopcroft, J.Ullman, Formal languages and their relation to automata, Addison-Wesley, 1969.; N. Cutland, Computability, an introduction to recursive function theory, Cambridge university press, 1986.;