×
Универзитет у Новом Саду

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

Матичне организационе јединице предмета: Катедра за примењене рачунарске науке

Основне информације:
 
Категорија Теоријско-методолошки
Ужа научна област Примењене рачунарске науке и информатика
ЕСПБ 5

Образовни циљ предмета је развој алгоритамске културе савременог инжењера, као важног чиниоца опште инжењерске културе. Конкретни образовни циљеви су оспособљавање студената за а) разумевање основних појмова из области теорије алгоритама и рачунарске сложености, б) одређивање алгоритамске тежине проблема, ц) одабир алгоритамских поступака који су адекватни тежини решаваног проблема и д) примену одговарајућих алгоритама у решавању проблема од интереса.

Основна стечена знања су разумевање и одређивање алгоритамске тежине проблема и комплексности алгоритма, као и способност за самостално алгоритамско решавање инжењерских проблема од интереса.

Увод у теорију алгоритама и рачунарске сложености. Одређивање алгоритамске тежине проблема. Редукције међу проблемима. Асимптотска нотација, временска и просторна комплексност. Основне класе комплексности. Врсте алгоритама. Похлепни алгоритми, алгоритми типа подели-па-реши, претрага у дубину и ширину, динамичко програмирање, алгоритми ограниченог гранања. Рандомизовани и пробабилистички алгоритми. Параметризовани и апроксимативни алгоритми. Алгоритамске хеуристике и мета-хеуристике. Математичко програмирање. Алгоритми за решавање проблема са једним и више циљева оптимизације. Паралелни и дистрибуирани алгоритми.

Предавања. Аудиторне и рачунарске вежбе. Консултације. На предавањима се студенти упознају са општим алгоритамским поступцима, који су адекватни решавању проблема различитих алгоритамских тежина. Излагања на предавањима су праћена одговарајућим примерима на аудиторним и рачунарским вежбама, која доприносе разумевању градива. Поред предавања и вежби, редовно се одржавају и консултације.

Аутори Назив Година Издавач Језик
Christos H. Papadimitriou Computational Complexity 1995 Addison Wesley Longman Енглески
Zbigniew Michalewicz, David B. Fogel How to Solve It: Modern Heuristics 2010 Springer, 2nd Rev&Ext. edition Енглески
G. Ausiello, P. Crescenzi, V. Kann, Marchetti-sp, Giorgio Gambosi, Alberto M. Spaccamela Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties 1999 Springer Енглески
R. Sedgewick, K. Wayne Algorithms (4th Edition) 2011 Пеарсон Едуцатион, Инц. Енглески
Kozen, Dexter, C Theory of computation 2006 Springer Енглески
Cormen, T.H. et al. Introduction to Algorithms 2009 MIT Press, Cambridge Енглески
Предметна активност Предиспитна Обавезна Број поена
Предметна активност
Усмени део испита
Предиспитна
Не
Обавезна
Да
Број поена
30.00
Предметна активност
Тест
Предиспитна
Да
Обавезна
Да
Број поена
10.00
Предметна активност
Тест
Предиспитна
Да
Обавезна
Да
Број поена
10.00
Предметна активност
Сложени облици вежби
Предиспитна
Да
Обавезна
Да
Број поена
30.00
Предметна активност
Сложени облици вежби
Предиспитна
Да
Обавезна
Да
Број поена
20.00

ванр. проф. др Дину Драган

Ванредни професор

Предавања

Предавања

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

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

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