prikaz prve stranice dokumenta Aproksimacijski algoritmi - klase složenosti i dizajn
  Preuzmi
PDF 299.39 KB
diplomski rad
Aproksimacijski algoritmi - klase složenosti i dizajn
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2018. urn:nbn:hr:217:906846
Dujić, Marko
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Dujić, M. (2018). Aproksimacijski algoritmi - klase složenosti i dizajn (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:906846

Dujić, Marko. "Aproksimacijski algoritmi - klase složenosti i dizajn." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:217:906846

Dujić, Marko. "Aproksimacijski algoritmi - klase složenosti i dizajn." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:217:906846

Dujić, M. (2018). 'Aproksimacijski algoritmi - klase složenosti i dizajn', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 10.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:906846

Dujić M. Aproksimacijski algoritmi - klase složenosti i dizajn [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2018 [pristupljeno 10.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:906846

M. Dujić, "Aproksimacijski algoritmi - klase složenosti i dizajn", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2018. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:906846

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:906846
Podaci o radu
NaslovAproksimacijski algoritmi - klase složenosti i dizajn
AutorMarko Dujić
MentorMladen Vuković (mentor)
Član povjerenstvaMladen Vuković (predsjednik povjerenstva)
Član povjerenstvaVedran Čačić (član povjerenstva)
Član povjerenstvaZvonko Iljazović (član povjerenstva)
Član povjerenstvaMiljenko 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 obrane2018-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
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:906846
Studijski programNaziv: 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 resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2019-03-28 12:44:00