Опште информације
Курс је намењен студентима академских мастер студија програма Математика и природно се надовезује на курсеве Математичко програмирање и Операциона истраживања основних студија модула Примењена математика. Акценат је на напредним алгоритмима конструисаним на простим и сродним типовима графова. Од студента се очекује да обради и у виду семинарског рада прикаже неколико алгоритама намењених решавању једног проблема.Сви који су уписали курс нека се јаве и-мејлом ради договора о његовој организацији.
Садржај курса
1. Минимална разапињућа стабла и најкраћи путеви - напредни алгоритми.
2. Протоци у мрежама - Едмондс-Карпов, Голдберг-Тарџанов и остали алгоритми. Проблем минималне цене.
3. Проблем конструкције мрежа. Алгоритми Робинс-Зеликовског и примално-дуалне апроксимације и Џеина.
3. Проблем трговачког путника - основна формулација и модификације проблема. Апроксимативни алгоритми, локално претраживање, метод гранања и ограничавања.
4. Локацијски проблеми. Примално-дуални алгоритми и локално претраживање.
Литература
- B. Korte, J. Vygen: Combinatorial Optimization, Springer, Berlin, 2005.
- Д. Цветковић, М. Чангаловић, ...: Комбинаторна оптимизација - математичка теорија и алгоритми, ДОПИС, Београд, 1996.
Начин формирања оцене
- Предиспитне обавезе
Семинарски рад, 70 поена
- Завршни испит
Усмени испит, 30 поена