hrvatski

Aproksimacijski algoritmi za NP-teške probleme

U kombinatornoj optimizaciji često se pojavljuju NP-teški problemi. Riječ je o zadaćama koje se prema općem uvjerenju ne mogu egzaktno rješavati u polinomijalnom vremenu. Tema diplomskog rada su aproksimacijski algoritmi za rješavanje NP-teških problema. Aproksimacijski algoritam je takav algoritam koji daje u polinomijalnom vremenu približno rješenje, te također i garanciju da je to rješenje "blizu" egzaktnom. U radu se najprije ukratko izlaže teorija o NP-teškim problemima. Zatim se razmatraju neki konkretni NP-teški problemi na grafovima te NP-teški problemi raspoređivanja. Dalje se definira nekoliko aproksimacijskih algoritama za razmatrane probleme te se analizira njihova točnost i računska složenost. Rad završava studijskim primjerom koji se sastoji od eksperimentalne evaluacije jednog od analiziranih algoritama na računalu.

NP-teški problemi; aproksimacijski algoritmi; računska složenost

nije evidentirano