Теорија алгоритама

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

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

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


Литература

  1. З. Огњановић, Н. Крџавац, Увод у теоријско рачунарство,  ФОН, Београд 2004.
  2. Leung Joseph, ed., Handbook of Scheduling : Algorithms, Models, Performance Analysis, Boca Raton [etc.] : Chapman and Hall/CRC, 2004.

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