Дизајн и анализа алгоритама

Циљ и исход предмета

Стицање знања из дизајна и анализе алгоритама.. Студент је у стању да у даљем образовању у стручним предметима решава алгоритамске проблеме. Зна да користи основне и сложеније структуре података и алгоритме. Разуме проблеме доказа исправности алгоритама и математичке алате за њихово показивање. Познаје алгоритамске парадигме и препознаје класе проблема које оне решавају. Разуме време извршавања алгоритама и познаје начине за њихово одређивање.

Теоријска настава

Анализа алгоритама. Примери доказа исправности алгоритама. Асимптотска анализа најгорег и/или просечног случаја. Асимптотске ознаке О, о, , , . Временска и просторна сложеност. Израчунавање коначних сума, рекурентне релације, мастер теорема. Динамичко програмирање. Алгоритми грубе силе. Похлепни (greedy) алгоритми. Рекурзивна стратегија заснована на разлагању (divide-and-conquer). Претрага са враћањем (backtracking), гранање са одсецањем (branch-and-bound), хеуристике. Тражење узорка у тексту. Проточне мреже и одређивање максималног протока у мрежи. Упаривање у графовима. Примери нумеричких алгоритама. Имплементација рекурзије. Свођење репне рекурзије (tail recursion) на итерацију.

Практична настава

Имплементација некох од алгоритама који су приказани на предавањима. Дизајн и анализа алгоритама за разне алгоритамске проблеме. Посебан акценат на препознавању алгоритамске парадигме (динамичко програмирање, похлепни алгоритми, подели па владај, бектрек, итд.) која може бити примењена при решавању алгоритамских проблема. Развој (ако је могуће) разних алгоритама за решавање једног истог алгоритамског проблема, уз поређење сложености (временске и просторне/меморијске).