Newsgroup: it.scienza.informatica
Titolo: Algoritmo "Las Vegas"

Vorrei sapere di cosa si tratta. Ringrazio anticipatamente chiunque voglia
illuminarmi su questo argomento.

 illuminarmi su questo argomento.
Non sara' il buon vecchio Montecarlo? [se non lo sapessi metodo di
integrazione
statistico]
Ciao, Roberto

 wrote in message
newscache$k5vozf$55o$1...@traminer.inferentia.it...

Si, il metodo MonteCarlo è annoverato tra gli algoritmi LasVegas.... quello
che voglio sapere però è il perchè  questii algoritmi vengono etichettati
con questo nome?

etichettati con questo nome?
Perche' si basano sull'estrazione di sequenze di numeri casuali.
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun


Se non ricordo male il Metodo Montecarlo vero e proprio é nato all'epoca del
progetto Manhattan (Bomba Atomica)
presso i laboratori di Los Alamos da Neumann, Fermi, e Ulam per risolvere
numericamente le eq. alle derv. parziali
descriventi il comportamento di svariati fenomeni che analiticamente era
praticamente impossibile trattare.
In realtà gia nel (700?) il naturalista Buffon aveva scoperta una via
"statistica" in grado di valutare 2/pigreco
....
Sia data una regione piana, abbastanza estesa, suddividiamola mediante
segmenti rettilinei paralleli in tante
striscie che abbiano tutte una uguale larghezza L e su tale griglia lanciamo
*casualmente* un ago
anch'esso di lunghezza L. La probabilità che tale ago cadendo si disponga in
modo da tagliare uno dei segmenti é
data da 2/pigreco.
....
Il ragionamento che sta dietro a tale affermazione é il seguente, detto A il
punto di mezzo dell'ago e x la distanza da A
al più prossimo segmento della griglia ed alpha l'angolo formato dalla
direzione dell'ago con la direzione dei segmenti si ha
che la circostanza che l'ago tagli uno di tali segmenti corrisponde al
verificarsi della relazione:
             sin(alpha)
   L * -------------- > x
                   2
introducendo un sistema di coordinate alpha (ascisse) e x (ordinate)  si
vede che la probabilità che si verifichi l'evento
sopra riportato é data dal rapporto K/H, dove H é l'area del rettangolo
compreso tra l'asse (alpha), la retta x = L/2, l'asse x
e la retta alpha=pigreco/2, mentre K é l'area di quella parte del rettangolo
nella quale risulta x < 1/2 * L * sin(alpha).
La probabilità richiesta é dunque data da:
            1    |pigreco/2
           --- |      l * sin(alpha) d alpha
            2 |0
2
------------------------------------------------------- = --------
                L      pigreco
pigreco
              ---  * --------
               2           2
Bene in *pratica* o si calcola l'integrale o si fanno molti lanci e quindi
si divide il numero dei lanci *positivi* (che tagliano un segmento) ed il
numero totale dei lanci.... (cosa che un computer fa in qualche minuto di
elaborazione).
L'idea quindi che sta alla base dei Metodi Montecarlo (Metodi di Simulazione
stocastica) é quella di stimare una quantità determinata, assumendola come
valor medio di una opportuna variabile casuale e cercando poi di
approssimarla attraverso l'esame di un campione di convenienti dimensioni.
Bah... magari non interessa nessuno...
Saluti
Dario

[...]
Bella, non la conoscevo 'sta cosa. Ma Buffon e' Leclerc de Buffon? Quello della 
"Storia Naturale"? 
-- 
God is Real, unless declared Integer.
ObjectZone - 
http://space.tin.it/computer/csadun/