Aproksimacijski algoritmi - klase složenosti i dizajn

master's thesis

• Author: Marko Dujić
• Mentor: Mladen Vuković (mentor)
• Committee member: Mladen Vuković (predsjednik povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Committee member: Zvonko Iljazović (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-11-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: 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
• Keywords (english): optimization problems; decision problem; travelling salesman problem; maximum knapsack problem; greedy method; sequential method for partitioning the problem; local search; linear programming; dynamic programming
• Language: croatian
• URN:NBN: urn:nbn:hr:217:906846
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-03-28 12:44:00