Algoritmi za rješavanje NP-teških problema
kombinatorne optimizacije

Osnovni podaci o kolegiju

Opći kolegij na Poslijediplomskom studiju matematike.
Predaje se jedan semestar (zimski).
Satnica: ukupno 30 sati predavanja.

Opis i sadržaj

U kombinatornoj optimizaciji često se pojavljuju NP-teški problemi. Riječ je o zadaćama koje se prema općem uvjerenju ne mogu rješavati u polinomijalnom vremenu. Cilj kolegija je: predstaviti, klasificirati i usporediti metode za rješavanje NP-teških problema. Metode su podijeljene u tri skupine: egzaktni algoritmi, aproksimacijski algoritmi i heuristike. Egzaktni algoritam daje točno rješenje, no zbog velike računske složenosti primjenjiv je samo na relativno male primjerke problema. Aproksimacijski algoritam daje u polinomijalnom vremenu približno rješenje, te također i garanciju da je to rješenje "blizu" egzaktnom. Heuristika je brzi približni algoritam koji se pokazao upotrebljivim unatoč nedostatku garancije "dobrote". Kolegij se sastoji od sljedećih poglavlja.

Uvod: kombinatorna optimizacija, cjelobrojno programiranje, računska složenost.
NP-teški problemi: osnovne definicije, Cookov teorem, problemi na grafovima, problemi raspoređivanja.
Egzaktni algoritmi: dinamičko programiranje, backtracking, branch-and-bound.
Aproksimacijski algoritmi: apsolutne aproksimacije, relativne aproksimacije, polinomijalne aproksimacijske sheme.
Heuristike: pohlepni pristup, lokalno traženje, evolucijski algoritmi.

Literatura

E. Horowitz, S. Sahni, S. Rajasekaran: Algorithms / C++. Computer Science Press, New York, 1997.
C.H. Papadimitrou, K. Steiglitz: Combinatorial Optimization - Algorithms and Complexity, Second Edition. Prentice-Hall, Englewood Cliffs NJ, 1998.
G. Ausiello et al.: Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Properties. Springer Verlag, Berlin and Heidelberg, 1999.
D.S. Hochbaum (editor): Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, Boston MA, 1997.
V.V. Vazirani: Approximation Algorithms. Springer Verlag, Berlin and Heidelberg, 1999.
Z. Michalewicz and D.B. Fogel: How to Solve It - Modern Heuristics. Springer Verlag, Berlin and Heidelberg, 1999.

Obveze tijekom semestra

Pohađanje predavanja.
Odabir teme za seminar.

Način polaganja ispita

Ispit se sastoji od seminara i od usmenog dijela.
Seminar mora biti odabran tako se uklapa u temu kolegija te da proširuje gradivo izloženo na predavanjima.
Student je dužan održati seminar pred auditorijem i predati njegov sadržaj u pismenom obliku.
Uspješno održani seminar je uvjet za pristupanje usmenom dijelu ispita.
Usmeni dio ispita odnosi se isključivo na gradivo s predavanja.
Konačna ocjena oblikuje se na osnovu ocjene seminara i ocjene usmenog dijela.

Red predavanja u školskoj godini 2003/2004

Predavač: prof.dr.sc Robert Manger.
Predavanja: četvrtak 14-17h, soba 203.
Konzultacije u vezi seminara: petkom 10-12h.