| dc.contributor.author | Luoto, Antti | |
| dc.date.accessioned | 2013-09-20T09:11:37Z | |
| dc.date.available | 2013-09-20T09:11:37Z | |
| dc.date.issued | 2013 | |
| dc.identifier.other | oai:jykdok.linneanet.fi:1280453 | |
| dc.identifier.uri | https://jyx.jyu.fi/handle/123456789/42193 | |
| dc.description.abstract | Tämä pro gradu -tutkielma käsittelee simuloitu jäähdytys -nimisen kombinatorisen
optimointimenetelmän teoriaa ja käytäntöä. Esimerkiksi kuvankäsittelyssä sovelletun
algoritmin ideana on löytää annetulla joukolla määritellyn reaaliarvoisen energiafunktion
globaali minimikohta sallimalla - ei pelkästään energiaa vähentäviä -
vaan myös energiaa kasvattavia siirtymiä lähtöjoukon alkioiden välillä. Tilastolliseen
fysiikkaan analogian omaavan, Gibbsin jakauman ominaisuuksiin pohjautuvan menetelm
än matemaattisena perustana toimivat epähomogeeniset Markovin ketjut, joiden
suppenemista tarkastellaan Dobrushinin kontraktiokerroinmenetelmän avulla.
Simuloidun jäähdytyksen suppenemislause, joka takaa epähomogeenisen Markov
Chain Monte Carlo -ketjun suppenemisen minimienergiatilojen joukkoon, todistetaan
aluksi Gibbs-otannan tapauksessa sekä deterministisille että satunnaisille päivitysjonoille.
Tätä varten tehdään katsaus satunnaiskenttien, naapurustojärjestelmien, klikkien
ja potentiaalien teoriaan.
Suppenemislause todistetaan myös yleisempiin tilanteisiin soveltuvan Metropolis-otannan
tapauksessa. Metropolis-algoritmilla ajettavaa simuloitua jäähdytystä sovelletaan
lopuksi konkreettiseen ongelmaan, jossa pyritään muodostamaan suorakulmion
muotoiselle tenttisalille vilpin estämiseksi optimaalinen istumajärjestys. Simulointikokeiden
yhteydessä pohditaan menetelmän käytännön soveltamiseen liittyvää problematiikkaa
ja pohditaan lopuksi sitä, kuinka hyvin jäähdytys soveltuu tenttisaliongelman
ratkaisemiseen. | fi |
| dc.format.extent | 1 verkkoaineisto. | |
| dc.language.iso | fin | |
| dc.rights | This publication is copyrighted. You may download, display and
print it for Your own personal use. Commercial use is
prohibited. | en |
| dc.rights | Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. | fi |
| dc.subject.other | Gibbs-otanta | |
| dc.subject.other | epähomogeeninen Markovin ketju | |
| dc.subject.other | Metropolis-algoritmi | |
| dc.subject.other | satunnaiskenttä | |
| dc.subject.other | simuloitu jäähdytys | |
| dc.title | Simuloidun jäähdytyksen suppenemislause | |
| dc.identifier.urn | URN:NBN:fi:jyu-201309202331 | |
| dc.type.ontasot | Pro gradu | fi |
| dc.type.ontasot | Master's thesis | en |
| dc.contributor.tiedekunta | Matemaattis-luonnontieteellinen tiedekunta | fi |
| dc.contributor.tiedekunta | Faculty of Sciences | en |
| dc.contributor.laitos | Matematiikan ja tilastotieteen laitos | fi |
| dc.contributor.laitos | Department of Mathematics and Statistics | en |
| dc.contributor.yliopisto | University of Jyväskylä | en |
| dc.contributor.yliopisto | Jyväskylän yliopisto | fi |
| dc.contributor.oppiaine | Matematiikka | fi |
| dc.contributor.oppiaine | Mathematics | en |
| dc.date.updated | 2013-09-20T09:11:37Z | |
| dc.rights.accesslevel | openAccess | fi |
| dc.contributor.oppiainekoodi | 4041 | |
| dc.subject.yso | optimointi | |
| dc.subject.yso | algoritmit | |
