General information
Kurs je namenjen studentima akademskih master studija programa Matematika i prirodno se nadovezuje na kurseve Matematičko programiranje i Operaciona istraživanja osnovnih studija modula Primenjena matematika. Akcenat je na naprednim algoritmima konstruisanim na prostim i srodnim tipovima grafova. Od studenta se očekuje da obradi i u vidu seminarskog rada prikaže nekoliko algoritama namenjenih rešavanju jednog problema.Svi koji su upisali kurs neka se jave i-mejlom radi dogovora o njegovoj organizaciji.
Sadržaj kursa
1. Minimalna razapinjuća stabla i najkraći putevi - napredni algoritmi.
2. Protoci u mrežama - Edmonds-Karpov, Goldberg-Tardžanov i ostali algoritmi. Problem minimalne cene.
3. Problem konstrukcije mreža. Algoritmi Robins-Zelikovskog i primalno-dualne aproksimacije i Džeina.
3. Problem trgovačkog putnika - osnovna formulacija i modifikacije problema. Aproksimativni algoritmi, lokalno pretraživanje, metod grananja i ograničavanja.
4. Lokacijski problemi. Primalno-dualni algoritmi i lokalno pretraživanje.
Literatura
- B. Korte, J. Vygen: Combinatorial Optimization, Springer, Berlin, 2005.
- D. Cvetković, M. Čangalović, ...: Kombinatorna optimizacija - matematička teorija i algoritmi, DOPIS, Beograd, 1996.
Način formiranja ocene
- Predispitne obaveze
Seminarski rad, 70 poena
- Završni ispit
Usmeni ispit, 30 poena