Елементи теорије алгоритама

Студије
Основне академске студије (7. семестар)
Предавања
Милица Стојановић, Весна Манојловић, Небојша Николић
Вежбе
Небојша Николић, Марија Боричић, Нада Младеновић, Душан Џамић

Циљ предмета је упознавање студената са основним елементима теорије нумеричке сложености и анализе алгоритама, као и принципима формирања алгоритама за решавање проблема у различитим областима (теорији графова, алгебри, геометрији, области низова и скупова).

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

  1. Временска и просторна сложеност алгоритма и проблема. Полиномијални алгоритми. 
  2. Детерминистичка и недетерминистичка Тјурингова машина. 
  3. NP класа проблема. 
  4. NP комплетност и NP тешки проблеми. 
  5. Конструкција алгоритама индукцијом; примери.  
  6. Доказивање исправности алгоритма. 
  7. Алгоритми на графовима: обиласци графова; најкраћи путеви. 
  8. Транспортне мреже; Хамилтонове контуре. 
  9. Геометријски алгоритми: проблеми са многоуглом. 
  10. Конвексни омотач. 
  11. Алгебарски алгоритми: проблеми са полиномима. 
  12. Проблеми са матрицама 
  13. Алгоритми сортирања и упоређивања низова. 
  14. Израда семинарског рада.

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

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


Литература

  • М. Живковић, Алгоритми, Математички факултет, Београд 2000.
  • З. Огњановић, Н. Крџавац, Увод у теоријско рачунарство,  ФОН, Београд 2004.

© 2017 Катедра за математику| Факултет организационих наука | Универзитет у Београду