Стицање основних знања о теорији израчунљивости.

По завршетку курса, студент разуме појмове теорије израчунљивости, разуме формални и неформални појам алгоритма, разуме појмове одлучивих и неодлучивих проблема и њихову улогу у рачунарству.

1. Тјурингова машина. 2. УР машина. 3. Примитивно рекурзивне функције, рекурзивне функције. 4. Енумерација, универзалне функције. 5. Одлучивост, неодлучивост, парцијална одлучивост. 6. Рекурзивни и рекурзивно набројиви скупови. 7. Сводљивост и степени. 8. Теореме рекурзије.

Прати теоријску наставу.

Програмирање и знање C или C++.

Tabla i kreda.

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

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

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

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

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

N. Cutland: Computability: an introduction to recursive function theory, Cambridge University Press, 1980.;