Циљ предмета је упознавање студената са основним елементима теорије нумеричке сложености и анализе алгоритама, као и принципима формирања алгоритама за решавање проблема у различитим областима (теорији графова, алгебри, геометрији, области низова и скупова).
Теоријска настава
- Временска и просторна сложеност алгоритма и проблема. Полиномијални алгоритми.
- Детерминистичка и недетерминистичка Тјурингова машина.
- NP класа проблема.
- NP комплетност и NP тешки проблеми.
- Конструкција алгоритама индукцијом; примери.
- Доказивање исправности алгоритма.
- Алгоритми на графовима: обиласци графова; најкраћи путеви.
- Транспортне мреже; Хамилтонове контуре.
- Геометријски алгоритми: проблеми са многоуглом.
- Конвексни омотач.
- Алгебарски алгоритми: проблеми са полиномима.
- Проблеми са матрицама
- Алгоритми сортирања и упоређивања низова.
- Израда семинарског рада.
Практична настава
- Самостално креирање алгоритама из области која се изучава на предавању и провера сложености алгоритама.
Литература
- М. Живковић, Алгоритми, Математички факултет, Београд 2000.
- З. Огњановић, Н. Крџавац, Увод у теоријско рачунарство, ФОН, Београд 2004.
