Алгоритми и сложеност

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

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

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

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

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

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


Литература

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

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