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