Табела 5.2 Спецификација  предмета

Студијски програм/студијски програми : Информатика
Врста и ниво студија: И141 - Основне академске студије
Назив предмета: Дизајн и анализа алгоритама
Наставник (Презиме, средње слово, име): Ћирић Д. Мирослав
Статус предмета: обавезан
Број ЕСПБ: 8
Услов: нема
Циљ предмета Упознавање са најважнијим алгоритмима који се користе за решавање практичних проблема који се јављају у рачунарским наукама, упоређивање разних алгоритама у погледу њихове ефикасности у разним конкретним ситуацијама.
Исход предмета На крају курса студент треба да буде у стању да разуме математичке концепте који се користе у дизајнирању и анализи алгоритама, да буде способан да изабере и употреби алгоритме који су најпогоднији у датој конкретној ситуацији, као и да имплементира те алгоритме.
Садржај предмета Алгоритамске стратегије, алгоритми грубе силе (brute force), алгоритми са повратком (back-tracking), подели-и-владај алгоритми (divide and conquer), сортирање поделом, динамичко програмирање, оптимална подструктура, преклапајући потпроблеми, чување резултата, проблем ранца, производ матрица, проблем максималног збира, најбрже степеновање, најдужи заједнички подниз, најдужи растући подниз, оптимална триангулација полигона, похлепни алгоритми (greedy), oсобина похлепног избора, oптимална подструктура, поређење похлепних алгоритама са динамичким програмирањем, проблем избора активности, Хaфманов код, алгоритми на графовима, BFS и DFS алгоритми, тополошко сортирање, јако повезане компоненте, најкраћи путеви кроз граф, Дијкстрин алгоритам, најкраћи путеви и множење матрица, Floyd-Warshall-ов алгоритам, максимални проток, геометријски алгоритми, особине дужи, пресек дужи, налажење конвексног омотача, налажење најближег пара тачака, алгоритми у математици, случајни бројеви, алгоритми са полиномима, великим бројевима и матрицама, интерполација кривих, интеграција, полино-мијално време извршења алгоритма, алгоритми који се извршавају у неполиномијалном времену, Кукова теорема, NP-комплетни проблеми, технике решавања NP проблема – backtracking и branch-and-bound, апроксимативни алгоритми, проблем трговачког путника.
Литература 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	Вежбе: 3	Други облици наставе:			Студијски истраживачки рад:
Методе извођења наставе На предавањима се користе класичне методе наставе уз коришћење пројектора и интеракцију са студентима. Током практичне наставе, која се обавља на рачунарима, студенти самостално приме-њују стечена знања. Знање студената се тестира кроз домаће задатке и колоквијуме. На завршном усменом делу испита студент треба да покаже да је успешно овладао изложеним градивом.
Оцена  знања (максимални број поена 100)
Предиспитне обавезе			поена	Завршни испит			поена
активност у току предавања			5	писмени испит
домаћи задаци			10 (5x2)	усмени испт			45
колоквијум-и			40 (2x20)
семинар-и