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

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

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.