Tietojenkäsittelytieteen laitos

581264 Tutkimustiedonhallinnan peruskurssi, 3 ov, kevät 2004

Laskuharjoitus 5 (4.5., 6.5.)

1. Toteuta tasajakautuneiden satunnaislukujen generointiin yleisesti käytetty yksinkertainen menetelmä (linear congruential method); olkoon m=100 eli satunnaisluvut ovat välillä [0,99].
   • Testaa menetelmää seuraavasti: generoi 10000 arvoa ja tutki niiden tasajakautuneisuutta piirtämällä histgrammi (pylväs per arvo; ks. alla). Toista testi erilaisilla a:n ja c:n arvoilla, ja yritä löytää mahdollisimman hyvin toimivat arvot.
     Histogrammin voi piirtää esim. seuraavasti. Unixissa syötä satunnaisluvut (yksi per rivi) seuraavaan putkeen (ohjeita korjattu 30.4.2004):
     $ (oma komento) | sort -n | uniq -c | \
     awk -v m=100 'BEGIN {riveja=0} \
     {while (riveja < $2) {print riveja,0; riveja++} print $2,$1; riveja++} \
     END {while(riveja < m) {print riveja,0;riveja++}}' > temp
     Sitten gnuplotissa:
     gnuplot> plot "temp" with hist
   • Vertaa jonkin valmiin satunnaislukugeneraattorin (esim. käyttämäsi ohjelmointikielen sopivan funktion) tuottamaan vastaavaan jakaumaan kokonaisluvuille [0,99].
     awkilla esim:
     awk 'BEGIN{for (i=1;i<=10000;i++) print int(rand()*100)}'
2. Kolmiojakauma on jatkuva jakauma, jonka tiheysfunktio muodostaa (geometrisesti tulkittuna) tasakylkisen kolmion kyljet. Kirjoita ohjelma, joka generoi transformaatiomenetelmällä satunnaislukuja kolmiojakaumasta, joka saa arvoja väliltä -1,...,1. (Tiheysfunktio on siis lineaarinen pisteestä (-1,0) pisteeseen (0,1), ja siitä taas pisteeseen (1,0).) Piirrä myös kuva jakaumasta ja sen kertymäfunktiosta.
3. Kirjoita ohjelma, joka generoi hylkäysmenetelmällä satunnaislukuja edellä mainitusta kolmiojakaumasta. Käytä apujakaumana sopivaa tasaista jakaumaa (mitä?).
4. Vertaile edellisten tehtävien toteutuksia tuottamalla kummallakin 10000 satunnaislukua. Tee kummastakin histogrammi.
   • Kuinka samanlaisia jakaumia menetelmät tuottavat? Mistä ero johtuu?
   • Millainen ero on suoritusajoissa, ja mistä ero johtuu? (Käytä tarvittaessa suurempaa satunnaislukujen määrää, jotta suoritusaikamittaukset ovat luotettavampia. Unixissa ajan mittaus esim. lisäämällä komento time ajastettavan komennon eteen.)
5. Laske Vitterin artikkelissa ja luennolla esitetyn algoritmin S mukainen toisen tietueen valintatodennäköisyys. Käytä hyväksi sitä, että
   P(2) = P(2|1) * P(1) + P(2|-1) * P(-1),
   missä i (i=1 tai i=2) on tapahtuma "i:s tietue valitaan otokseen" ja -i on tapahtuma "i:ttä tietuetta ei valita otokseen".
6. Toteuta Vitterin artikkelissa ja luennoilla esitetty algoritmi A otantaan tietokannasta. Keksi sopiva tapa testata, että algoritmi näyttää toimivan oikein.

Ole ystävällinen ja täytä kurssipalaute. Autat kehittämään laitoksen opetusta!