Циљ предмета је упознавање студената са основним елементима теорије нумеричке сложености и анализе алгоритама, као и принципима формирања алгоритама за решавање проблема у различитим областима (теорији графова, алгебри, геометрији, области низова и скупова).
Теоријска настава
- Временска и просторна сложеност алгоритма и проблема. Полиномијални алгоритми.
- Детерминистичка и недетерминистичка Тјурингова машина.
- НП класа проблема. НП комплетност и НП тврди проблеми.
- Конструкција алгоритама индукцијом; примери.
- Појачавање индуктивне хипотезе. Доказивање исправности алгоритма.
- Алгоритми на графовима: обиласци графова; најкраћи путеви, проблеми упаривања у графу.
- Транспортне мреже; Хамилтонове контуре.
- Геометријски алгоритми: триангулација полигона; конвексни омотач, највећи конвексни подскуп.
- Алгебарски алгоритми: проблеми са полиномима.
- Проблеми са матрицама.
- Проблеми са скуповима.
- Алгоритми сортирања и упоређивања низова.
- Паралелни алгоритми; алгоритми за мреже рачунара.
- Неки алгоритми криптографије.
Практична настава
- Самостално креирање алгоритама из области која се изучава на предавању и провера сложености алгоритама.
- Израда семинарског рада.
Литература
- М. Живковић, Алгоритми, Математички факултет, Београд 2000.
- З. Огњановић, Н. Крџавац, Увод у теоријско рачунарство, ФОН, Београд 2004.
- Leung Joseph, ed., Handbook of scheduling : algorithms, models, performance analysis, Boca Raton [etc.] : Chapman and Hall/CRC, 2004.
- М. Вујошевић, Методе оптимизације у инжењерском менаџменту, АИНС – ФОН, Београд, 2012.
