Seuraa 
Viestejä919
Liittynyt19.3.2005

Löysin tällaisen kombinatorisen ongelman: https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=noppak On siis annettu joukko, jossa on kaikki n-pituiset nopanheiton tulokset ja on myös annettu tietyt merkkijonot, jotka esiintyvät joissakin jonoissa. Miten lasketaan, monessako merkkijonossa esiintyy jokin annettu merkkijono? Yritin vääntää tätä monisteen http://matematiikkakilpailut.fi/kirjallisuus/kilpmatopas.pdf kaavalla 68 mutta lausekkeesta tuli liian sotkuinen.

Kommentit (3)

Retromake
Seuraa 
Viestejä41
Liittynyt1.12.2017

Ketjusta löytyi melko vaativa vanha tehtävä, joka  on jäänyt ilman kommentteja. Tehtävässä oli annettu 12  nopanheittokuviota  {123456, 112233, 445566, 111222, 333444,555666, 111111, 222222, 333333, 444444, 5555555, 666666}. Kuvio syntyy satunnaisesti, kun yhtä noppaa heitetään 6 kertaa peräkkäin. Tavoitteena on selvittää, kuinka monta sellaista erilaista heittosarjaa on, jossa esiityy vähintään yksi näistä kahdestatoista kuviosta.
Ratkaisu tulisi hakea heittosarjoille, joiden  pituudet ovat 6, 7, 8, ....,27 heittoa. 

Laskentaa mutkistaa, että  annetut 12 kuviota muodostavat keskenään monia sellaisia leikkauskuvioita, jotka kuuluvat samaan 12 kuvion perusjoukkoon. Esimerkiksi 22:n heiton  sarja 1111112233344455666666 sisältää 5 hyväksyttyä kuviota {111111, 112233, 333444, 445566, 666666}.  Pisimmässä 27 heiton sarjassa pelkkiä ykkösiä sisältävä jono sisältää 22 leikkausta. On tietysti luontevaa ajatella, että ratkaisu löytyy inkluusio-ekskluusio -kaavalla,  jossa parillisen joukkomäärän leikkaukset lasketaan negatiivisena ja parittoman positiivisena, mutta sen ohjelmointi  on työläs, koska todennäköisyyksien laskenta edellyttää kaikkien leikkausten selvittämistä jokaisesta eripituisesta sarjasta. 

Vaihtoehtoinen tapa on tarkastella nopanheittoa satunnaisprosessina, jota kuvataan tilakaaviolla. Sitä havainnollistaa suunnattu verkko, jossa solmut ovat tiloja ja nuolet siirtymiä tilojen välillä. Kun jokaisesta tilasta tiedetään muihin tiloihin siirtymisen todennäköisyydet, kyseessä on ns. Markovin ketju. Nämä todennäköisyydet esitetään neliömuotoisella  transitio- eli tilasiirtymämatriisilla P, joka on myös stokastinen, eli sen alkiot ovat positiivisia tai 0, ja jokaisella rivillä alkioiden summa on 1. Jos prosessissa on m tilaa, matriisin dimensio on m x m. Lisäksi tarvitaan prosessin tilajakaumavektori V = [p1,p2,...,pm], jossa pj  tarkoittaa todennäköisyyttä olla tilassa j. Tämän noppatehtävän alkutilassa  V(0) alkioiden p1-p6 todennäköisyyksiksi asetetaan 1/6, ja muut tilat ovat nollia.

Retromake
Seuraa 
Viestejä41
Liittynyt1.12.2017

Markov-ketjun tilajakauma, kun heittosarjan pituus on n saadaan laskettua kaavalla V(n) = V(0)P^n, jossa P^n on siirtymämatriisin n:s potenssi ja V(0) on prosessin alkutila. Laskenta on teknisesti helppo, koska siinä tarvitaan vain matriisin kertolaskua. Ensin on kuitenkin arvioitava, mitkä ovat prosessin tilat, siirtymät ja niiden todennäköisyydet.           

Jokainen nopanheitto tarkoittaa tilakaaviossa siirtymistä tilasta toiseen. Tilojen voidaan ajatella edustavan 1-6 heiton mittaisia heittokuvioita. Esimerkiksi tilaan 333444 johtaa lyhimpänä polku, jossa on 6 tilaa: 3 - 33- 333 - 3334 - 33344  ja 333444. Prosessiin tarvittavat tilat voi siis selvittää tutkimalla annettujen 12 heittokuvion alusta lähtien kaikki erilaiset 1:n - 6:n heiton kuviot. Näin saadaan 6+7+9+12+12+12=58 tilaa, joista 12 on absorboivia ja 46 transientteja. Absorboivaan tilaan voidaan tulla, mutta siitä ei siirrytä pois. Tässä noppatehtävässä jokaisesta transientista tilasta voidaan siirtyä kuuteen muuhun. Kunkin siirtymän todennäköisyys on 1/6. Absorboivista tiloista (nieluista) voi siirtyä vain tilaan itseensä, joten niiden siirtymätodennäköisyys on 1. Näin voidaan asettaa P-matriisiin siirtymätodennäköisyydet. Tämän jälkeen ohjelma laskee muutamassa sekunnissa tilajakaumavektorin kaikilla vaadituilla heittomäärillä 6-27. Annettujen 12 kuvion todennäköisyydet poimitaan vektorista V ja lasketaan yhteeen. Koska tehtävässä kysyttiin lukumäärää, saatu todennäköisyys on kerrottava luvulla 6^n.

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat