====== Esercitazione numeri casuali ======
Per gli esercizi che seguono ricordatevi di includere gli //header// corretti
#include
per ''rand()'', ''srand()'' e
#include
per la funzione ''time()''.
Gli header corretti e le eventuali opzioni di compilazione da aggiungere per usare una funzione di libreria si trovano sempre nella sezione 3 del manuale
man 3 time
===== Esercizio 0: Generazione di numero casuali in C e ''RAND_MAX'' =====
In alcuni casi e' importante riuscire a generare casualmente dei valori all'intero di programmi C per modellare situazioni reali o per testare opportunamente i programmi scritti.
In realta' il computer non riesce a generare eventi realmente "a caso" in quanto tutti i programma si basano su una determinata sequenza di azioni. Tuttavia e' possibile avere un comportamento vicino alla casualita' con le //sequenze pseudocasuali//, che vengono generate con un procedimento deterministico ma mantengono proprieta' statistiche simili a quelle di una vera sequenza casuale.
Inoltre le sequenze pseudocasuali possono, su richiesta, rigenerare la stessa sequenza di numeri. Questo e' molto utile ad esempio in fase di testing del codice.
La generazione di numeri pseudocasuali e' molto complessa. Tutti i linguaggi di programmazione ad alto livello mettono a disposizione delle opportune funzioni per generare una sequenza. In C, per generare una sequenza pseudocasuale si utilizzano due funzioni di stdlib.h: la funzione
''srand()'' serve a fissare il seme (//seed//) ovvero il valore **iniziale** della sequenza. E la funzione ''rand()'' che deve essere chiamata più volte e ogni volta genera **il valore successivo della sequenza**.
I valori generati sono //valori interi all'interno dell'intervallo// ''[0,RAND_MAX]''.
Stabilire il valore di ''RAND_MAX'' attraverso un opportuno programma C che la stampa a video.
===== Esercizio 1: Generazione di numero casuali interi in un intervallo =====
Utilizzare le funzioni ''srand()'' e ''rand()'' per scrivere un programma C
che legge due valori dallo standard input:
* ''N'' (numero degli interi da generare) e
* ''seed'' (seme da utilizzare)
e stampa sullo standard output ''N'' valori casuali nell'intervallo ''[0,2]'' generati con seme ''seed''. Un esempio di funzionamento del programma e' il seguente
$./generatore
Inserisci N e seed:
3 42
Generati 3 valori interi nell'intervallo [0,2] con seed 42:
1
0
2
===== Esercizio 2: Generazione di numeri casuali con seed diversi =====
Modificare l'esercizio 1 in modo da generare un //seed// diverso ad ogni esecuzione utilizzando la funzione time().
===== Esercizio 3: Generazione di numero casuali reali =====
Scrivere un programma C che legge dallo standard input un numero N di reali da generare e stampa sullo standard output una sequenza di N numeri casuali reali nell'intervallo ''[0,1)'' utilizzando le funzioni ''srand()'' e ''rand()'' introdotte nell'esercizio precedente.
===== Esercizio 5: Ma quanto siamo casuali ? =====
Per restringersi all'intervallo [A,B] intero possiamo utilizzare anche la seguente formula
A+(int)((B-A)*rand()/(RAND_MAX+1.0))
oltre a
A+rand()%(B-A + 1)
Utilizzare entrambe per generare sequenze di interi nell'intervallo ''[0,20)'',
ci sono differenze nella distribuzione valori ottenuti ?
===== Esercizio 6: Realizziamo un generatore di numeri pseudo-casuali =====
Un semplice (ma efficace) generatore di sequenze di numeri pseudo-casuali utilizza il metodo della congruenza lineare. Questo metodo genera una sequenza di numeri $x_i$ a partire da un valore iniziale noto (il //seme)// $x_0$.
In generale, l’elemento $x_{i + 1}$ della sequenza è dato dalla formula:
\begin{align}\label{eq:generatore}
x_{i + 1} &= (a * x_i + b) \% M\\
\end{align}
i parametri $a$ (motiplicatore), $b$ (incremento) e $M$ (modulo) sono parametri interi e sono definiti a priori. Questo metodo genera una sequenza pseudo-casuale di numeri interi compresi tra 0 e $M$. Normalmente si fissa M come il massimo intero rappresentabile.
Alcuni valori per $M$, $a$ e $b$ consigliati in letteratura sono:
* $M=2^{31}$, $ a = (int) (\pi * 10^8)$, $b= 453806245$ (D. Knuth)
* $M=2^{31} – 1$, $a = 7^5$, $b=0$ (Goodman e Miller)
* $M=2^{31}$, $a = 5^{13}$, $b=0$ (Gordon)
* $M=2^{31}$, $a = 2^{16} + 3$, $b=0$ (Leormont e Lewis)
Scrivere un programma C che inizializza i parametri $a$, $b$, $M$ (a scelta dello studente), legge in input il seme $x_0$, e stampa i primi 100 numeri pseudo casuali della sequenza.
//Nota: Attenzione all'overflow .....//
===== Esercizio 7: Usiamo il generatore =====
Sulla base dell'esercizio 6, scrivere un programma C che genera 100 numeri double casuali e li stampa su stdout. I numeri devono essere compresi nell’intervallo [0,1) e stampati con precisione limitata alla quarta cifra decimale e partire da un seme $x_0$ letto da tastiera.
===== Esercizio 8: La macchina di Galton =====
La macchina di Galton (Galton Board) e' un dispositivo ideato nella seconda meta dell'Ottocento
per illustrare in modo semplice il teorema del limite centrale.
Qui vogliamo realizzare una versione virtuale della macchina, che utilizzi un
generatore di numeri pseudocasuali. Le regole sono semplici: dato un opportuno
sistema di riferimento (illustrato in Figura sotto) ed un intero n > 0 una pallina parte
dall'alto nella posizione n/2+1 e si muove di n passi verso il basso, spostandosi
contestualmente verso destra o verso sinistra (in modo casuale) di +0.5 o -0.5 con
uguali probabilita' (pd = ps = 0.5).
n = 8
...1.2.3.4.5.6.7.8.9
=====================
0|........o........|
1|.........o.......|
2|..........o......|
3|.........o.......|
4|........o........|
5|.......o.........|
6|......o..........|
7|.....o...........|
8| | | |o| | | | | |
=====================
...1.2.3.4.5.6.7.8.9
Figura 1 La macchina di Galton per n = 8
E' facile convincersi che la posizione di arrivo nel punto piu' basso puo' assumere tutti i valori tra 1 e n+1 (non con la stessa probabilita'!).
Realizzare un programma C che letto il numero di passi da standard input generi e visualizzi sullo schermo possibili percorsi della pallina. Si puo' utilizzare una grafica a piacere o quella della Figura 1.
===== Esercizio 9: Simulazione di un moto Browniano discreto =====
Scrivere un programma C che simula il moto di una particella che si muove di moto casuale su un piano, in un’area quadrata delimitata dagli assi $x=0$, $y=0$ e dalle rette $x=200$, $y=200$. All'istante 0 la particella è posta alle coordinate $x_0=100, y_0=100$.
All’istante $i+1$, le coordinate della particella sono calcolate come:
\begin{align}
x_{i+1} = x_i + A\\
y_{i+1} = y_i + B
\end{align}
Dove A e B sono due numeri double pseudo-casuali compresi nell’intervallo [-1,1]. Per la generazione di A e di B il programma usa separatamente due semi A0 e B0 letti da tastiera (invece, se si usa il generatore dell'esercizio 6, i parametri $a,b, M$ per la generazione delle due sequenze di numeri pseudo casuali sono gli stessi).
Il programma C termina quando la particella raggiunge (o supera) gli estremi dell’area, e stampa la posizione raggiunta dalla particella.
//Nota: bisogna avere pazienza....//