Програм се примењује од 16.05.2014..
Предмети предуслови
Предмети којима је предуслов предмет Теорија алгоритама
Образовни циљ предмета је развој алгоритамске културе савременог инжењера, као важног чиниоца опште инжењерске културе. Конкретни образовни циљеви су оспособљавање студената за а) разумевање основних појмова из области теорије алгоритама и рачунарске сложености, б) одређивање алгоритамске тежине проблема, ц) одабир алгоритамских поступака који су адекватни тежини решаваног проблема и д) примену одговарајућих алгоритама у решавању проблема од интереса.
Основна стечена знања су разумевање и одређивање алгоритамске тежине проблема и комплексности алгоритма, као и способност за самостално алгоритамско решавање инжењерских проблема од интереса.
Увод у теорију алгоритама и рачунарске сложености. Одређивање алгоритамске тежине проблема. Редукције међу проблемима. Асимптотска нотација, временска и просторна комплексност. Основне класе комплексности. Врсте алгоритама. Похлепни алгоритми, алгоритми типа подели-па-реши, претрага у дубину и ширину, динамичко програмирање, алгоритми ограниченог гранања. Рандомизовани и пробабилистички алгоритми. Параметризовани и апроксимативни алгоритми. Алгоритамске хеуристике и мета-хеуристике. Математичко програмирање. Алгоритми за решавање проблема са једним и више циљева оптимизације. Паралелни и дистрибуирани алгоритми.
Предавања. Аудиторне и рачунарске вежбе. Консултације. На предавањима се студенти упознају са општим алгоритамским поступцима, који су адекватни решавању проблема различитих алгоритамских тежина. Излагања на предавањима су праћена одговарајућим примерима на аудиторним и рачунарским вежбама, која доприносе разумевању градива. Поред предавања и вежби, редовно се одржавају и консултације.
Аутори | Назив | Година | Издавач | Језик |
---|
Christos H. Papadimitriou | Computational Complexity | 1995 | Addison Wesley Longman | Енглески |
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 | Енглески |
Cormen, T.H. et al. | Introduction to Algorithms | 2009 | MIT Press, Cambridge | Енглески |
Zbigniew Michalewicz, David B. Fogel | How to Solve It: Modern Heuristics | 2010 | Springer, 2nd Rev&Ext. edition | Енглески |
R. Sedgewick, K. Wayne | Algorithms (4th Edition) | 2011 | Пеарсон Едуцатион, Инц. | Енглески |
Kozen, Dexter, C | Theory of computation | 2006 | Springer | Енглески |
Предметна активност | Предиспитна | Обавезна | Број поена |
---|
Сложени облици вежби | да | да | 30.00 |
Сложени облици вежби | да | да | 20.00 |
Тест | да | да | 10.00 |
Тест | да | да | 10.00 |
Усмени део испита | не | да | 30.00 |
| Име и презиме | Вид наставе |
---|
| | Предавања |
| | Предавања |
| | Рачунарске вежбе |
| | Рачунарске вежбе |
| | Рачунарске вежбе |