Download
PDF 851 KB
undergraduate thesis
27   14
Dynamic programming
David Tkalčec (2017)
Josip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
Department of Software Engineering
Chair of Visual Computing
Cite this document...

Tkalčec, D. (2017). Dinamičko programiranje (Undergraduate thesis). Retrieved from https://urn.nsk.hr/urn:nbn:hr:200:140262

Tkalčec, David. "Dinamičko programiranje." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2017. https://urn.nsk.hr/urn:nbn:hr:200:140262

Tkalčec, David. "Dinamičko programiranje." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2017. https://urn.nsk.hr/urn:nbn:hr:200:140262

Tkalčec, D. (2017). 'Dinamičko programiranje', Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, accessed 16 February 2019, https://urn.nsk.hr/urn:nbn:hr:200:140262

Tkalčec D. Dinamičko programiranje [Undergraduate thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek; 2017 [cited 2019 February 16] Available at: https://urn.nsk.hr/urn:nbn:hr:200:140262

D. Tkalčec, "Dinamičko programiranje", Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, Osijek, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:200:140262

Metadata
TitleDinamičko programiranje
AuthorDavid Tkalčec
Mentor(s)Alfonzo Baumgartner (thesis advisor)
Abstract
Zadatak ovog rada bio je opisati i na konkretnom primjeru implementirati tehniku dinamičkog programiranja, Ovom tehnikom početni složeni problem rastavljamo na podprobleme manje složenosti koji su međusobno zavisni. Svaki podproblem se rješava najviše jednom, čime možemo izbjeći višestruko računanje numeričkih karakteristika istog stanja. Osnovna ideja na koju se oslanjaju algoritmi dinamičkog programiranja je da se svaki dobiveni međurezultat, odnosno rješenje podproblema, spremi te zatim kada se sljedeći puta naiđe na taj isti podproblem, izbjegne njegovo ponovno rješavanje. Ovakva tehnika pohrane rješenja podproblema naziva se memoizacija. Dva osnovna pristupa pomoću kojih možemo rješavati probleme dinamičkim programiranjem su: pristup „Odozgo prema dolje“ i pristup „Odozdo prema gore“. U glavnom dijelu rada navedeni pristupi su implementirani na primjeru „Rezanje drva“ te je izmjereno vrijeme izvođenja dobivenih funkcija. Na kraju smo zaključili da problem riješen ovom tehnikom ima znatno brže vrijeme izvođenja od onog riješenog nedinamičkom metodom
KeywordsC++ implementation dynamic programming memorization optimal substructure subproblem.
Parallel title (English)Dynamic programming
Committee MembersAlfonzo Baumgartner (committee chairperson)
Zdravko Krpić (committee member)
Mirko Köhler (committee member)
GranterJosip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
Lower level organizational unitsDepartment of Software Engineering
Chair of Visual Computing
PlaceOsijek
StateCroatia
Scientific field, discipline, subdisciplineTECHNICAL SCIENCES
Computing
Data Processing
Study programme typeuniversity
Study levelundergraduate
Study programmeUndergraduate University Study Programme in Computer Engineering
Academic title abbreviationuniv.bacc.ing.comp.
Genreundergraduate thesis
Language Croatian
Defense date2017-09-11
Parallel abstract (English)
The task of this paper was to describe a dynamic programming technique and then implement solution for specific problem. Using this technique, we break down the initial complex problem into a collection of simpler subproblems. Each subproblem is solved once and its solution had been stored. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution. The technique of storing solutions to subproblems instead of recomputing them is called "memoization". There are two ways of doing this: with Top-down approach and with Bottom-up approach. In the main part of this paper these approaches were implemented in the example "Rod cutting" and the time taken to perform the obtained functions was measured. In the end, we have concluded that the problem solved by this technique has much faster execution time than one solved with other method.
Parallel keywords (Croatian)C++ implementacija dinamičko programiranje memoizacija optimalna struktura podproblem.
Resource typetext
Access conditionOpen access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
URN:NBNhttps://urn.nsk.hr/urn:nbn:hr:200:140262