Øktene 26. april til 11. mai
11. mai
19.7. 11. mai
19.7.1. Felles
Desse to oppgåvene handlar slumptal og -testen som ikkje har vore pensum før. Dei er formulerte som typiske eksamensoppgåver, og liknande oppgåver er sannsynleg på eksamen.
Oppgåve 19.1 Mange dataprogram treng tilfeldige tal. Ein vanleg måte å generera slike slumptal er den lineære kongruensgeneratoren
For eit gjeve frø , gjev rekurrensen ei fylgje som vert brukt som tilfeldige tal.
- 1.
- Forklar kva me meiner med at eit tal (eller hending) er tilfeldig.
- 2.
- Under kva omstende gjev den lineære kongruensgeneratoren tilfredsstillande slumptal?
Ta , , og , og studer generatoren
- 3.
- Kva er perioden til denne generatoren med frøet ?
- 4.
- På kva måtar lyt ein ta omsyn til perioden ved praktisk bruk av generatoren?
Oppgåve 19.2 Det er vanleg å testa kvaliteten på ein slumptalsgenerator ved hjelp av statistisk hypotesetesting. Lat vera ein heiltalsfylgje frå slumptalsgeneratoren. For å testa at dei fire siste bitsa er uniformt fordelte kan me bruka -statistikken
der , er frekvensen av kvar mogleg verdi av og er forventa frekvens.
- 1.
- Dei fleste slumptalsgeneratorar leverer heiltal på 31 bits eller meir, men i testen over testar me berre fire bits frå kvart slumptal. Kvifor testar me aldri alle 31 samstundes?
- 2.
- Kva er nullhypotesen for testen?
- 3.
- Kva fordeling har under nullhypotesen?
- 4.
- Kva er den kritiske verdien for testen ved 5% signifikansnivå?
- 5.
- Sett at me observerer slumptal og observerer . Kan me forkasta nullhypotesen?
19.7.2. Løysingsforslag
- 1.
- Der finst ingen enkel definisjon på tilfeldig. Me seier at ei hending er tilfeldig dersom
me ikkje kan forutseia utfallet. Det treng ikkje tyda 50-50 sannsyn (uniform fordeling),
sjølv om ein rimeleg kan seia at uniform fordeling er meir tilfeldig enn andre fordelingar.
Hasardspel som rullett er eit godt døme. Føresetnaden er at kula landar med uniform fordeling på ulike tal. Dersom kulen faktisk landar tilfeldig, vil spelarane i lengda vinna (dvs. tapa) like mykje. Dersom nokon kan forutseia kula og slå banken i lengda, so er kula ikkje tilfeldig.
- 2.
- Dette spørsmålet kan tolkast på to ulike måtar.
- a)
- Korleis skal ein velja parametra
slik at slumptala vert gode?
Dette er eit vanskeleg spørsmål, og eit fullstendig svar ligg utanfor pensum. Ein skal likevel vita at er ei øvre grense for perioden, og må difor vera stor. Dersom er ein potens av to får ein dårleg statisk fordeling. Parametra må veljast samla for å få gode statistiske eigenskapar (inkl. stor periode). Der er få gode val, og vilkårlege parametre vert sjelden gode.
- b)
- For kva bruk er den lineære generatoren god nok med beste moglege parameterval?
Det er godt kjent at den lineære generatoren er sårbar for kryptologiske åtak. Dvs. ein åtakar som investerer ressursar i det, vil kunne forutseia fylgja berre ved å observera nokre av tala. Den lineære generatoren kan difor ikke brukast i nokon samanheng der der står store pengar på spel (pengetransaksjonar, nettbank, hasardspel).
- 3.
- Me skriv ned fylgja,
Me ser at me har maksimal periode, dvs. 25.
- 4.
- Me kan aldri bruka meir enn ein brøkdel av perioden. Når me har brukt opp ein del av perioden, tek det til å påverka sannsynsfordeling på dei attståande tala. Når me har brukt opp heile perioden, for me eksakt repetisjon.
- 1.
- Fordi utfallsrommet då vert svært stort, mykje større enn det utvalet som me i praksis kan testa. Resultatet då er at endringar i gjev minimale endringar , og me klarer ikkje å skilja ulike fordelingar. Dersom testen skal fungera, må utvalet vera svært stort samanlikna med utfallsrommet.
- 2.
- for alle og
- 3.
- er -fordelt med 15 fridomsgradar
19.7.3. Eigenarbeid
- 1.
- Haust 2016, oppgåve 3
- 2.
- Vår 2016, oppgåve 2
- 3.
- Haust 2016, oppgåve 2