Табела 5.1 Спецификација  предмета  на студијском програму докторских студија

Назив предмета: И373 - Дизајн и анализа алгоритама
Наставник или наставници (презиме, средње слово име):     Долинка В. Игор
Статус предмета:    изборни
Број ЕСПБ:    12
Услов:    нема
Циљ предмета Упознавање са напреднијим техникама дизајна и анализе алгоритама и њиховим применама у реша-вању конкретних проблема у рачунарским и другим наукама.
Исход предмета На крају курса студент треба да овлада напреднијим техникама дизајна и анализе алгоритама и да буде оспособњен да те алгоритме употреби у својим научним истраживањима.
Садржај предмета Основе. Улога алгоритама у рачунарству. Раст функција. Рекурентне релације. Анализа помоћу веро-ватноће и алгоритми који користе случајне бројеве. Сортирање. Heapsort. Quicksort. Сортирање у ли-неарном времену. Медијане и статистике о реду величине. Структуре података. Елементарне струк-туре података. Хеш табеле. Бинарна стабла претраживања. Црвено-црна стабла. Увећавање структура података. Напредне технике дизајна и анализе. Динамичко програмирање. Похлепни алгоритми. Амортизована анализа.  Напредне структуре података. B-стабла. Биномијалне гомиле. Фибоначијеве гомиле. Структуре података за дисјунктне скупове. Алгоритми на графовима. Елементарни алгоритми на графовима. Минимално разапињуће стабло. Најкраћи путеви из једног чвора. Најкраћи путеви из-међу свих парова чворова. Максимални проток. Изабране теме. Сортирајуће мреже. Матричне опе-рације. Линеарно програмирање. Полиноми и FFT. Алгоритми из теорије бројева. Поређење стрин-гова. Рачунарска геометрија. NP-комплетност. Апроксимациони алгоритми.
Препоручена литература 1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and  C. Stein, Introduction to Algorithms, McGraw-Hill Book Company, 2001. 2. R. Sedgewick, Аlgorithms, Addison-Wesley Publishing Company, 1984. 3. M. J. Atallah (ed.), Algorithms and Theory of Computation Handbook, CRC Press, Boca Raton, 1999.
Број часова  активне наставе		Предавања: 4		Студијски истраживачки рад:
Методе извођења наставе На предавањима се користе класичне методе наставе уз коришћење видео пројектора и интеракцију са студентима. Знање студената се тестира преко израде домаћих задатака и одбране семинарских радова. На завршном усменом испиту се проверава свеобухватно разумевање изложеног градива.
Оцена  знања (максимални број поена 100)
Предиспитне обавезе	поена		Завршни испит		поена
домаћи задаци	10 (2x5)		усмени испит		70
семинарски рад	20		..........