×
Универзитет у Новом Саду

Предмет: Теорија израчунљивости (17.0M537)

Основне информације:
 
Категорија Научно-стручни
Ужа научна област Теоријска и примењена математика
ЕСПБ 5

Основни циљ предмета јесте стицање основних знања из теорије алгоритама, укључујући појам алгоритма, рекурзивних функција, Тјурингове машине и временске сложености. Студенти ће бити упознати са овим фундаменталним појмовима, али и са њиховом применом у разним гранама рачунарства (пре свега на развој програмских језика и модела за конкурентне системе). Током извођења предмета, биће проучаване наведене формалне методе и технике, кроз примере и дискусију. Коначни циљ јесте да студенти развију вештине за анализирање понашања алгоритама.

Као исход предмета, студент ће поседовати основна знања из теорије алгоритама и њихове комплексности. Поред тога, студенти ће овладати вештином анализирања сложености алгоритма, користећи познате методе.

Појам алгоритма и израчунљивости. Рекурзивне функције. Тјурингове машине. Черч-Тјурингова теза. Одлучивост и процедуре одлучивања. Временска сложеност.

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

Аутори Назив Година Издавач Језик
Игор Долинка Кратак увод у анализу алгоритама 2008 Футура, Нови Сад Српски језик
Јаничић, П. Математичка логика у рачунарству 2009 Математички факултет, Београд Српски језик
Epstein, R.L., Carnielli, W.A. Computability. Computable Functions, Logic, and the Foundations of Mathematics 1989 Wadsworth & Brooks, Pacific Grove Енглески
Pippinger, N. Theories of computability 1997 Cambridge University Press, Cambridge Енглески
Р.Тошић, С.Црвенковић Збирка задатака из теорије алгоритама 1980 Институт за математику, Нови Сад Српски језик
Sipser, M. Introduction to the Theory of Computation 2006 Thomson Course Technology, Boston Енглески
Предметна активност Предиспитна Обавезна Број поена
Предметна активност
Присуство на предавањима
Предиспитна
Да
Обавезна
Да
Број поена
5.00
Предметна активност
Тест
Предиспитна
Да
Обавезна
Да
Број поена
10.00
Предметна активност
Присуство на вежбама
Предиспитна
Да
Обавезна
Да
Број поена
5.00
Предметна активност
Теоријски део испита
Предиспитна
Не
Обавезна
Да
Број поена
30.00
Предметна активност
Писмени део испита - комбиновани задаци и теорија
Предиспитна
Не
Обавезна
Да
Број поена
40.00
Предметна активност
Тест
Предиспитна
Да
Обавезна
Да
Број поена
10.00

Предавања

Аудиторне вежбе

Рачунарске вежбе