Опште информације
Теоријско рачунарство 24/25
Теоријско рачунарство
Литература
[1] Н. Икодиновић, Теорија алгоритама, белешке (стране 1--108)
[2] Juraj Hromkovič, Algotimic Adventures, from Knowledge to Magic (прва четири поглавља књиге)
Консултативна настава
средом, 14.00 (Студ. трг), уз претходну најаву мејлом; долазак на консултације треба најавити дан раније
Полагање испита
Предиспитне обавезе: Семинарски рад из два дела, на основу књиге [2]
1. део: направити избор задатака из првих пет поглавља књиге (најмање 50% по поглављу) и детаљно их решити. Семинарски треба да садржи и поставке и решења задатака.
2. део: изабрати једну напреднију тему из другог дела књиге [2] (једно од поглавља 6-10) и детаљно га приказати користећи евентуално и додатну литературу.
Семинаски рад треба предати у електронској форми, пре испитног рока у коме се планира полагање. Уколико је семинарски коректан, организује се усмени испит.
Усмени део: одбрана семинарског рада и дискусија о теоријском делу (додатно, очекује се познавање садржаја из [1], стр 1--108.) Усмени део испита биће организован у испитним роковима по договору мејлом.
Основне информације о курсу
Студ. програм МАС Математика (акредитација 2015/2022)
Модули: Професор математике и рачунарства; Теријска математика и примене
Предмет је сродан предметима Теорија алгоритама/израчунљивости на основним студијама математике/информатике, као и предмету Теорија рекурзија на докторским студијама математике.
Укратко: Од давнина, математика обилује алгоритмима за решавање разноврсних класа проблема. Ипак, на појаву и развој савременог рачунара суштински је утицало откриће проблема који се не могу алгоритамски решити.
Садржај, исходи и полагање предмета:
1. Основни концепти теорије израчунљивости
* Формално и неформално разумевање концепта израчунљивости и одлучивости Апстрактне машине (Регистар машине, Тјурингове машине)
2. Неодлучивост (Диофантов проблем, проблем заустављања, проблем речи, проблем ваљаности, проблем пополочавања итд.)
* Примена методе свођења једног проблема на други, са елементима класификације проблема по „тежини“)
3. Одабране напредне теме (пробабилистички алгоритми, квантна израчунљивост, ДНК израчунавање итд. у складу са предзнањем и интересовањима слушалаца)
* самостална обрада и приказ једне теме, уз консултације и упутства
Предиспитне обавезе: 70 поена
Домаћи задаци [за теме 1,2], одн. семинарски рад [за тему 3] и њихова одбрана на вежбама
Усмени испит: 30 поена
Оцена се формира на основу броја стечених поена:
51 – 60 = оцена 6
61 – 70 = оцена 7
71 – 80 = оцена 8
81 – 90 = оцена 9
91 – 100 = оцена 10
Теоријско рачунарство 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
ТР 2022/23
Литература
прва четири поглавља књиге: Juraj Hromkovič, Algotimic Adventures (from Knowledge to Magic) link
Консултативна настава
уторком, 10.00 у учионици Н206 (Св. Никола), уз претходну најаву мејлом; долазак на консултације треба најавити дан раније
Полагање испита
· Семинарски рад: направити избор задатака из прва четири поглавља књиге (довољно је око 50% по поглављу) и детаљно их решити. Поставке задатака и решења припремити у облику семинарског рада и предати у писаној или електронској форми.
· Усмени део: дискусија о решењима задатака и разговор о теоријском делу. Усмени део испита биће организован у испитним роковима по договору.