Aproksimacijski algoritmi - klase složenosti i dizajn

diplomski rad

• Autor: Marko Dujić
• Mentor: Mladen Vuković (mentor)
• Član povjerenstva: Mladen Vuković (predsjednik povjerenstva)
• Član povjerenstva: Vedran Čačić (član povjerenstva)
• Član povjerenstva: Zvonko Iljazović (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2018-11-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom diplomskom radu definirali smo optimizacijske probleme i objasnili neke od metoda za rješavanje tih problema. Da bismo mogli bolje proučiti i razumjeti optimizacijske probleme, potrebni su nam bili problemi odluke. Svakom se optimizacijskom problemu može pridružiti odgovarajući problem odluke. Ta nam je činjenica bila korisna u većini dokaza vezanih za klase složenosti za optimizacijske probleme: PO i NPO. Kao što probleme odluke možemo klasificirati u određenu klasu složenosti, tako i optimizacijske probleme svrstavamo u jednu od navedenih klasa. Definirali smo i opisali neke od poznatih optimizacijskih problema među kojima su problem TRGOVAČKOG PUTNIKA i 0 - 1 PROBLEM RUKSAKA. Ti problemi su NP-teški te za njih postoji određena aproksimacijska tehnika rješavanja kojom pokušavamo doći do optimalnog rješenja. Među tim tehnikama opisali smo sljedeće: pohlepna metoda, sekvencijalna metoda za problem particije, lokalno pretraživanje, linearno programiranje i dinamičko programiranje. Ovdje je opisan samo jedan dio optimizacijskih problema te za njih postoji još dublja podjela i analiza. Postoji mnogo optimizacijskih problema međutim ovdje su dani primjeri s kojima se uglavnom susrećemo u svakodnevnom životu.

Sažetak (engleski)

In this graduation paper we defined optimization problems and explained some of the methods for solving those problems. For better understanding and exploring of optimization problems, we first introduced the decision problems. There is a way how some decision problem could be joined with an optimization problem. This statement was useful in many theorems and proofs related to the complexity classes for optimization problems : PO and NPO. We defined and explained some of the well-known optimization problems like travelling salesman problem and maximum knapsack problem. This problems are NP-hard and there exist certain approximation techniques for getting the optimal solution. Some of the methods we explained are: greedy method, sequential method for partitioning the problem, local search, linear programming and dynamic programming. In this paper we covered just a part of the optimisation problems suggesting there exists a deeper analysis regarding optimisation problems. Although there are many optimisation problems, in this paper we focused on explaining some of the examples from the daily life.

• Ključne riječi: optimizacijski problemi; problem odluke; problem trgovačkog putnika; problem ruksaka; pohlepna metoda; sekvencijalna metoda za problem particije; lokalno pretraživanje; linearno programiranje; dinamičko programiranje
• Ključne riječi (engleski): optimization problems; decision problem; travelling salesman problem; maximum knapsack problem; greedy method; sequential method for partitioning the problem; local search; linear programming; dynamic programming
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:906846
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-03-28 12:44:00