| Предмет | Елементи теорије алгоритама |
|---|---|
| Модул | Информациони системи и технологије |
| Статус предмета | Изборни предмет |
| Катедра | Катедра за математику |
| Број ЕСПБ бодова | 5 |
Приказивање основних елемената теорије алгоритама и принципа креирања алгоритама за решавање проблема у различитим областима (теорији графова, алгебри, геометрији, области низова и скупова) као и анализа сложености.
Студенти ће баратати стратегијама за конструкцију и анализу алгоритама и препознавати NP комплетне проблеме.
Теоријска настава
1. Уводни појмови и примери алгоритама. 2. Конструкција алгоритама коришћењем математичке индукције. 3. Анализа алгоритама. 4. Провера исправности. 5. Временска и просторна сложеност алгоритама. Полиномијални алгоритми. 6. Детерминистичка и недетерминистичка Тјурингова машина. 7. P и NP класа проблема. 8. Алгоритми на графовима: обиласци и најкраћи путеви. 9. Хамилтонове контуре и транспортне мреже. 10. Геометријски алгоритми: проблеми са многоуглом. 11. Проблеми бојења области и равни 12. Алгебарски алгоритми: проблеми са полиномима.13. Алгоритми сортирања и упоређивања низова. 14. Компресија података
Практична настава:Вежбе, Други облици наставе, Студијски истраживачки рад Самостално креирање и имплементација алгоритама из области која се изучава на предавању. Спровођење анализе сложености различитих алгоритама.
1. М. Живковић Алгоритми Математички факултет, Београд 2000
2. A.A. Markov, N.M. Nagorny The Theory of Algorithms Springer 2010
3. З. Огњановић, Н. Крџавац Увод у теоријско рачунарство ФОН, Београд 2004
