Теоријско рачунарство 2023/24

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

Литература

[1] Н. Икодиновић, Теорија алгоритама, белешке (стране 1--108)

[2] Juraj Hromkovič, Algotimic Adventures, from Knowledge to Magic (прва четири поглавља књиге: )

Консултативна настава

понедељком, 15.00 (Студ. трг), уз претходну најаву мејлом; долазак на консултације треба најавити дан раније

Полагање испита

·  Семинарски рад

1. могућност: направити избор задатака из прва четири поглавља књиге (најмање 50% по поглављу) и детаљно их решити. Поставке  задатака и решења припремити у облику семинарског рада и предати у писаној или електронској форми.

2. могућност: изабрати једну напреднију тему (нпр. једну од тема из другог дела књиге [2], попут: квантна израчунљивост, пробабилистички алгоритми, сложеност израчунавања, ДНК израчунавање итд.); структура, садржај и литаратура рада за изабрану тему се накнадно договарају.

·  Усмени део: одбрана семинарског рада и дискусија о теоријском делу (додатно, очекује се познавање садржаја из [1], стр 1--108.) Усмени део испита биће организован у испитним роковима по договору.

Обавештење послато на адресе из СтудИнфо система: У петак, 20. 10. биће одржано уводно предавање, према важећем распреду: од 18:15 у учионици РЛАБ. Вежбе из ТР неће бити одржане у четвртак 19. 10. 2023.

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

Модули: Професор математике и рачунарства; Теријска математика и примене

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

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

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

1. Основни концепти теорије израчунљивости

* Формално и неформално разумевање концепта израчунљивости и одлучивости Апстрактне машине (Регистар машине, Тјурингове машине)

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

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

3. Одабране напредне теме (проблем P=?NP, пробабилистички алгоритми, квантна израчунљивост итд. у складу са предзнањем и интересовањима слушалаца)

* самостална обрада и приказ једне теме, уз консултације и упутства

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

Домаћи задаци [за теме 1,2], одн. семинарски рад [за тему 3]  и њихова одбрана на вежбама

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

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

51 – 60 = оцена 6

61 – 70 = оцена 7

71 – 80 = оцена 8

81 – 90 = оцена 9

91 – 100 = оцена 10


Tekući kursevi