Теорија комбинаторних алгоритама

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

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

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

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

Студијски истраживачки рад

  1. Имплементација стечених теоретских знања на конкретним комбинаторним проблемима. 
  2. Семинарски рад.


Литература

  • Jiri Fiala, Jan Kratochvil, Mirka Miller, Combinatorial Algorithms, Springer, 2009.
  • Donald E. Knuth, The Art of Computer Programming, Volume 4, Addison-Wesley, 2005.
  • Donald Kreher, Douglas Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, CRC Press, 1998.
  • Edward M. Reingold, Jurg Nievergelt, Narsingh Deo, Combinatorial Algorithms, Prentice-Hall, 1977.
  • Dennis Stanton, Dennis White, Constructive Combinatorics, Springer-Verlag, 1986.
  • 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, Dopis, 1996.
  • М. Вујошевић, Методе оптимизације у инжењерском менаџменту, АНИС – ФОН, Београд, 2012.

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