Предмет: Теорија алгоритама (14 - IFE211)


Основне информације

КатегоријаНаучно-стручни
Научна областПримењене рачунарске науке и информатика
МултидисциплинарнаНе
ЕСПБ5
Матичне организационе јединице предмета

Одсек за примењене рачунарске науке и информатику
Програм предмета

Програм се примењује од 16.05.2014..

Образовни циљ предмета је развој алгоритамске културе савременог инжењера, као важног чиниоца опште инжењерске културе. Конкретни образовни циљеви су оспособљавање студената за а) разумевање основних појмова из области теорије алгоритама и рачунарске сложености, б) одређивање алгоритамске тежине проблема, ц) одабир алгоритамских поступака који су адекватни тежини решаваног проблема и д) примену одговарајућих алгоритама у решавању проблема од интереса.
Основна стечена знања су разумевање и одређивање алгоритамске тежине проблема и комплексности алгоритма, као и способност за самостално алгоритамско решавање инжењерских проблема од интереса.
Увод у теорију алгоритама и рачунарске сложености. Одређивање алгоритамске тежине проблема. Редукције међу проблемима. Асимптотска нотација, временска и просторна комплексност. Основне класе комплексности. Врсте алгоритама. Похлепни алгоритми, алгоритми типа подели-па-реши, претрага у дубину и ширину, динамичко програмирање, алгоритми ограниченог гранања. Рандомизовани и пробабилистички алгоритми. Параметризовани и апроксимативни алгоритми. Алгоритамске хеуристике и мета-хеуристике. Математичко програмирање. Алгоритми за решавање проблема са једним и више циљева оптимизације. Паралелни и дистрибуирани алгоритми.
Предавања. Аудиторне и рачунарске вежбе. Консултације. На предавањима се студенти упознају са општим алгоритамским поступцима, који су адекватни решавању проблема различитих алгоритамских тежина. Излагања на предавањима су праћена одговарајућим примерима на аудиторним и рачунарским вежбама, која доприносе разумевању градива. Поред предавања и вежби, редовно се одржавају и консултације.
АуториНазивГодинаИздавачЈезик
Christos H. PapadimitriouComputational Complexity1995Addison Wesley LongmanЕнглески
G. Ausiello, P. Crescenzi, V. Kann, Marchetti-sp, Giorgio Gambosi, Alberto M. SpaccamelaComplexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties1999SpringerЕнглески
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford SteinIntroduction to Algorithms, Third Edition1999The MIT PressЕнглески
Zbigniew Michalewicz, David B. FogelHow to Solve It: Modern Heuristics2010Springer, 2nd Rev&Ext. editionЕнглески
Предметна активностПредиспитнаОбавезнаБрој поена
Одбрањене рачунарске вежбедада30.00
Домаћи задатакдада20.00
Колоквијумдада20.00
Усмени део испитанеда30.00
Име и презимеВид наставе
Недостаје слика

Даутовић др Станиша
Доцент

Предавања
Недостаје слика

Купусинац др Александар
Ванредни професор

Предавања
Недостаје слика

Кнежевић Марко

Рачунарске вежбе
Недостаје слика

Димитриески др Владимир
Доцент

Рачунарске вежбе