Комбинаторни алгоритми

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

Циљ предмета је упознавање са основним комбинаторним објектима и преглед алгоритама за њихово генерисање и рад са њима. Упознавање са основним појмовима теорије графова и преглед алгоритама за решавање најважнијих графовских проблема.

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

  1. Историјски увод. Рачунска сложеност алгоритма. 
  2. Основни комбинаторни објекти – алгоритамски приступ. Сортирање и претраживање. Представљање комбинаторних објеката у рачунару. 
  3. Алгоритми за генерисање свих подскупова. 
  4. Алгоритми за генерисање свих комбинација. 
  5. Алгоритми за генерисање свих пермутација. 
  6. Алгоритми за генерисање свих партиција броја. 
  7. Алгоритми за генерисање свих партиција скупа. 
  8. Основни појмови и дефиниције теорије графова. 
  9. Основни графовски проблеми. Представљање графова у рачунару. 
  10. Алгоритми за одређивање најкраћих растојања и најкраћих путева у графу. 
  11. Алгоритми за генерисање свих разапињућих стабала.
  12. Ојлерови и Хамилтонови графови и проблем трговачког путника – алгоритамски приступ. 
  13. Протоци у мрежама – алгоритамски приступ. 
  14. Остали комбинаторни проблеми. Поглед у будућност.

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

  1. Примена стечених теоретских знања на конкретним комбинаторним проблемима, коришћењем познатих програмских језика и/или пакета.


Литература

  • Jiri Fiala, Jan Kratochvil, Mirka Miller, Combinatorial Algorithms, Springer, 2009.
  • Donald Kreher, Douglas Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, CRC Press, 1998.
  • Albert Nijenhuis, Herbert S. Wilf, Combinatorial Algorithms, Academic Press, 1978.
  • Donald E. Knuth, The Art of Computer Programming, Volume 4, Addison-Wesley, 2005.
  • Alan Tucker, Applied combinatorics, John Wiley & Sons, 2002.
  • Nicos Christofides, Graph Theory - an Algorithmic Approach, Academic Press, 1975.
  • D. Cvetković, М. Čangalović, Đ. Dugošija, V. Kovačević-Vujčić, S. Simić, J. Vuleta, Kombinatorna optimizacija, Drustvo operacionih istraživača Jugoslavije, 1996.

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