Алгоритми

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

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

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

Методи дизајнирања алоритама: похлепни алгоритам (Huffman-ови кодови), динамичко програмирање (најдужа заједничка подсеквенца), завади па владај (множење матрица, транзитивно затворење). Анализа алгоритама: рекурентне методе, анализа најгорег случаја, анализа просечног случаја (пример: quicksort), амортизована комплексност. Алгоритми из теорије бројева: целобројни (највећи заједнички делилац, модуларна аритметика), FFT, полиномска и целобројна аритметика. Алгоритми на графовима (обилазак графа, најкраћа растојања, стабла разапињања). Алгоритми везани за проток у мрежама. Алгоритми за упаривање речи. Остале алгоритамске парадигме: паралелни алгоритми (Pointer Jumping, префиксне суме, рангирање листи, сортирање), дистрибуирани алгоритми (Byzantine Agreement).

Студијски истраживачки рад

Део наставе на предмету се одвија кроз самостални студијски истраживачки рад који обухвата евентуално писање рада из области теорије алгоритама.