Циљ предмета је упознавање са основним комбинаторним структурама, основним појмовима теорије графова и са проблемима комбинаторне оптимизације. Преглед постојећих алгоритама за рад са комбинаторним структурама (генерисање, претраживање, сортирање) и за решавање најважнијих комбинаторних проблема (проблем најкраћег пута, проблем трговачког путника).
Теоријска настава
- Рачунарска сложеност алгоритма.
- Основне комбинаторне структуре (коначни скупови, листе, комбинације, пермутације, ...).
- Представљање комбинаторних структура помоћу рачунара и манипулисање са њима.
- Алгоритми за генерисање, сортирање и претраживање.
- Алгоритми за генерисање свих комбинација и пермутација.
- Алгоритми за генерисање свих партиција броја и партиција скупа.
- Основни појмови теорије графова (графови, хиперграфови, пут, клика, ...).
- Најважнији проблеми на графу. Представљање графова помоћу рачунара.
- Алгоритми за одређивање најкраћих растојања и најкраћих путева.
- Алгоритми за генерисање свих разапињућих стабала.
- Алгоритми за одређивање максималне клике.
- Ојлерови и Хамилтонови графови. Алгоритми за решавање проблема трговачког путника.
- Протоци у мрежама. Алгоритми за решавање проблема максималног протока у мрежи.
- Комбинаторни дизајни. Алгоритми за генерисање Steiner-ових тројки.
- Остали комбинаторни проблеми и њихово решавање помоћу комбинаторних алгоритама.
Студијски истраживачки рад
- Имплементација стечених теоретских знања на конкретним комбинаторним проблемима.
- Семинарски рад.
Литература
- 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.
