Теорија алгоритама 2023/24

Теорија алгоритама 2023/24

Студ. програм ОАС Математика (акредитација 2015)

Модули: (Л) Професор математике и рачунарства

Укратко: Од давнина, математика обилује алгоритмима за решавање разноврсних класа проблема. Ипак, на појаву и развој савременог рачунара суштински је утицало откриће проблема који се не могу алгоритамски решити.

Садржај, исходи и полагање предмета:

1. Формална аритметика

* Разноврсна примена принципа математичке индукције и рекурзије, посебно у развоју вештачких (формалних) језика

2. Апстрактне машине (Регистар машине, Тјурингове машине)

* Формално и неформално разумевање концепта израчунљивости и одлучивости  

3. Бесконачност (пребројиви и непребројиви скупови)

* Разумевање и примена метода дијагонализације

4. Неодлучивост (проблем заустављања, проблем речи, проблем ваљаности, проблем пополочавања итд.)

* Примена методе свођења једног проблема на други, са елементима класификације проблема по „тежини“)

Предиспитне обавезе: 70 поена

Домаћи задаци (задати на предавањима) и њихова одбрана на вежбама

Писмени испит: 30 поена

Оцена се формира на основу броја стечених поена:

51 – 60 = оцена 6

61 – 70 = оцена 7

71 – 80 = оцена 8

81 – 90 = оцена 9

91 – 100 = оцена 10

Литература:

Н. Икодиновић, Теорија алгоритама (скрипта)

J. Hromkovič, Algoritmic Adventures (from Konowledge to Magic), Springer, 2009


Tekući kursevi