Теорија израчунљивости

ID: 3225
врста предмета: научно-стручни
носилац предмета: Радојевић Љ. Слободан
извођачи: Бенгин Ч. Александар, Митровић Б. Часлав, Радојевић Љ. Слободан
контакт особа: Радојевић Љ. Слободан
ниво студија: докторске студије
ЕСПБ: 5
облик завршног испита: писмени+усмени

извођења

  • 3. семестар, позиција 1

циљ

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

исход

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

садржај теоријске наставе

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

садржај практичне наставе

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

услов похађања

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

ресурси

Tabla i kreda.

фонд часова

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

активна настава (теоријска)

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

активна настава (практична)

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

провера знања

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

провера знања (укупно 100 поена)

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

литература

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