26 juli, 2022

Heilt på kanten, del 2 - Monte Carlo til unnsetning!

 Over til problemet vårt. 

Vi skulle altså løyse oppgåva


Kor stor del av eit kvadrat ligg nærmare sentrum enn kanten?


Umiddelbart klarte eg ikkje å sjå for meg korleis dette arealet ser ut, så eg brukte da Monte Carlo-metoden igjen for å få ein peikepinn.


I prosjektet over, teiknast det eit kvadrat, som eg så hivar mange prikkar inni! Ved å trykke på mellomrom kastar du tusen til. Det blir så rekna ut kor mange som ligg nærmare sentrum enn ein av sidekantane. Dette var litt meir møysommeleg å rekne ut enn når det gjaldt å estimere pi, ein måtte sjå på avstanden til alle sidekantane og avstand til sentrum og så finne ut kva som var minst. Så fargelegges punktet raudt om det ligg nærmast sentrum og lilla om det ligg nærmare ein sidekant. Kast nokre tusen prikkar på kvadratet og du vil sjå at området som blir definert som nærmare sentrum både har litt form av eit kvadrat og litt form av ein sirkel. Naturleg nok kanskje, men ikkje heilt enkelt å sjå for seg umiddelbart (iallfall ikkje for meg!). 

Til slutt kan du trykke K for å teikne kurva som omsluttar det raude arealet. Men kor stort er det? Kva form har det? Og korleis kan ein finne ut arealet av det?

Heilt på kanten - del 1 - Monte Carlo

 Ei uskyldig lita oppgåve dukka opp ein dag. 


Kor stor del av eit kvadrat ligg nærare sentrum enn kanten?


Oppgåva kan løysast eksakt eller tilnærma/numerisk. Det er jo freistande å berre stoppe der ("I think I'll stop there!"), men eg tenkte å lage eit forslag til løysing her så om du vil prøva sjølv så er det iallfall her du må stoppe og lese. 

Simulering

Først ville eg sjå korleis dette området eigentleg såg ut. Ein velkjend "brute force"-metode er Monte Carlo-metoden. Det vil seie at ein bruker gjentatte tilfeldige eksperiment til å simulere utfall for å kunne estimere noko numerisk. Du har kanskje sett korleis ein kan bruke ein slik måte til å estimere pi med. La oss ta det først. 


I Scratch-prosjektet over blir det kaste ei mengd med prikkar på skjermen. Prikkane som havnar innafor ein gitt sirkel får ei farge (lilla) og dei som havnar utafor får ei anna farge (grøn). Når ein kastar svært mange prikkar på skjermen vil andelen prikkar inni sirkelen delt på talet på prikker totalt bli meir og meir likt andelen sirkelarealet utgjer. Ved å køyre simulatoren over så ser du at ein så kan bruke dette til estimere pi. 

For å klårgjere det litt meir: Ein kan gjere det litt lettare ved å tenkje seg sirkelen med radius 1. Då vil kvadratet rundt ha areal 4, medan sirkelen vil ha areal pi. Talet på prikkar inni sirkelen delt på talet på prikkar totalt vil gi eit estimatet på forholdet pi/4. Eit estimat for pi vil da bli andelen 4*prikkar inni /prikkar totalt. Ved å la simulatoren gå ei stund ser du korleis dette vil nærma seg pi etter kvart.