Nebojša Ikodinović
Univerzitet u Beogradu, Matematički fakultet
-
МНМР јануар1/2
16. Februar, 2024Komentari (0) -
Јануар 1/2/ПС термини усмених испита
04. Februar, 2024Komentari (0) -
UML 1o1/1o2 JAN1/2
04. Februar, 2024Komentari (0)
Теоријско рачунарство 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
- Увод у математичку логику
- Методика наставе математике и рачунарства
- Теорија алгоритама Р
- Теоријско рачунарство (изборни, мастер)
- Теорија алгоритама (изборни)
- Logic and Probability