Naslov
Aproksimacijski algoritmi za NP-teške probleme
(Approximation Algorithms for NP-hard Problems)

Autori
Vresk, Damir

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad

Fakultet
Prirodoslovno matematički fakultet - Matematički odjel

Mjesto
Zagreb

Datum
22.10

Godina
2004

Stranica
93

Mentor
Manger, Robert

Ključne riječi
NP-teški problemi; aproksimacijski algoritmi; računska složenost
(NP-hard problems; approximation algorithms; computational complexity)

Sažetak
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.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA