20.500.12556/RUL-148431 Markovske verige in Metropolis-Hastingsov algoritem delo diplomskega seminarja Markov chains and Metropolis-Hastings algorithm Markovske verige so slučajni procesi, kjer so verjetnosti za prihodnje dogodke odvisne le od trenutnega stanja. Kadar je markovska veriga ergodična, opazujemo njeno limitno vedenje. Limitni izrek, ki je opisan v tem diplomskem delu, je ključnega pomena pri nadaljnjem delu z markovskimi verigami in Monte Carlo markovskimi verigami (MCMV), ki jih uporabljamo pri določanju lastnosti porazdelitev, ki jih sicer ne poznamo natančno. Primer MCMV algoritma je tudi Metropolis-Hastingsov, s katerim rešujemo problem nahrbtnika, ki je poznan kot “NP-težek” optimizacijski problem. V tem delu je opisano iskanje rešitve problema s konstrukcijo Metropolis-Hastingsove verige, katere členi so elementi množice dopustnih rešitev. Z večanjem števila korakov, ki jih algoritem naredi, in s tem števila najdenih primernih kandidatov, pa se veča tudi verjetnost, da smo našli najboljši možni izbor predmetov, ki jih še lahko zložimo v nahrbtnik z določeno omejitvijo teže. Markov chains are random processes where the probabilities of future events depend only on the current state of the process and not on events that have occurred in the past. When the Markov chain is ergodic, we observe its limiting behaviour. The limit theorem described in this paper is important in all further work with Markov chains and Monte Carlo Markov chains (MCMC), which are used in finding the properties of distributions that are otherwise not precisely known. An example of the MCMC algorithm is a Metropolis-Hastings one, which is used to solve the knapsack problem, known as an “NP-hard” problem in optimization. This paper describes the search for a solution with the construction of the Metropolis-Hastings chain, whose elements belong to the set of feasible solutions. As we increase the number of steps of the algorithm, and thus the number of suitable candidates found, the probability that we have found the best possible selection of items, that fit into a knapsack with a certain weight limit, increases as well. markovske verige slučajni proces Monte Carlo markovske verige Metropolis-Hastingsov algoritem problem nahrbtnika Markov chains stochastic process Monte Carlo Markov chains Metropolis-Hastings algorithm the knapsack problem true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2023-08-23 08:15:03 2023-08-23 08:15:06 2024-05-29 10:44:10 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.2 134676 162120451 9178.pdf 9178.pdf 1 0BA674F9E1930D5BC9F046512977BFE7 ecc66a965bf64f3ff077043b895a24f1ff564f2cb19c7dde4a667e5977393dcb 5c2f5e1e-417c-11ee-b9d7-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=172656 Fakulteta za matematiko in fiziko 0 0 0