Download
PDF 851 KB
undergraduate thesis
99   51
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 20 November 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 November 20] 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
Title (english)Dynamic programming
AuthorDavid Tkalčec
MentorAlfonzo Baumgartner (mentor)
Committee memberAlfonzo Baumgartner (predsjednik povjerenstva)
Committee memberZdravko Krpić (član povjerenstva)
Committee memberMirko Köhler (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
(Department of Software Engineering)
(Chair of Visual Computing)
Osijek
Defense date and country2017-09-11, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Data Processing
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
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:200:140262
Study programmeTitle: Undergraduate University Study Programme in Computer Engineering
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
Created on2017-11-03 13:16:14