Markovske verige in Metropolis-Hastingsov algoritemZupan, Iza (Avtor) Bernik, Janez (Mentor) markovske verigeslučajni procesMonte Carlo markovske verigeMetropolis-Hastingsov algoritemproblem nahrbtnikaMarkovske 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. 20232023-08-23 08:15:03Delo diplomskega seminarja/zaključno seminarsko delo/naloga148431UDK: 519.2VisID: 134676COBISS_ID: 162120451sl