Utente:J.J. Alan/Sandbox III

In informatica, con il termine algoritmo probabilistico (probabilistic o randomized algorithm in inglese) si intende una particolare classe di algoritmi che introducono nel loro comportamento una componente di casualità.

Studio della complessità

In un algoritmo non probabilistico, fornendo in ingresso gli stessi dati si ottiene sempre il medesimo risultato. A causa della componente stocastica introdotta negli algoritmi probabilistici questo non è più vero ed è possibile che la complessità (computazionale e spaziale) cambi sensibilmente anche di fronte agli stessi dati. Questo ne rende più difficile lo studio e costringe ad introdurre tecniche di analisi alternative.

Analisi del costo medio

Per una data sequenza di input si analizzano tutti i possibili casi e se ne effettua la media pesata con le relative probabilità. È anche possibile studiare il costo medio eseguendo solo la media aritmetica tra il peggiore e il migliore ma solamente sotto l'ipotesi che i valori casuali utilizzati siano uniformemente distribuiti, ovvero che ogni caso dell'algoritmo abbia la stessa probabilità di verificarsi. Questa assunzione è fatta nella maggioranza dei casi ammettendo la possibilità di introdurre un errore trascurabile.

Riduzione ad un algoritmo probabilistico

Se l'obiettivo è stimare le prestazioni di possibili varianti di uno stesso algoritmo, la presenza della componente casuale può essere "spostata" e trattata come un qualsiasi dato di ingresso. Ai parametri è aggiunta una sequenza ordinata di numeri casuali da usare, o un seme con cui generarli. Utilizzando la stessa sequenza (o lo stesso seme) su una medesima serie di dati si otterranno sempre gli stessi risultati, riconducendoci così ad un algoritmo non più probabilistico.

Nel primo caso la componente casuale è fornita in ingresso mentre nel secondo ci si avvale di un generatore di numeri pseudo-casuali, che da origine alle stesse sequenze sotto lo stesso seme.

Utilizzo

La scelta di un algoritmo probabilistico è molto spesso obbligata dal fatto che il problema che si cerca di risolve contiene naturalmente una qualche componente stocastica, o così difficile da prevedere che può essere considerata tale (ad esempio, il lancio di un dado o le mutazioni di un filamento di DNA).

Le simulazioni, soprattutto quelle biologiche o metereologiche, ne sono un esempio.

Altre volte la componente casuale non ha strettamente a che fare con la risoluzione diretta del problema, ma può aiutare a introdurre un certo grado di imprevedibilità all'interno del contesto. Si tratta di una tecnica molto usata soprattutto nei videogiochi (per non rendere troppo meccanici i movimenti di un avversario), o in ambito grafico (per creare varianti di una stessa texture e non dare la spiacevole illusione di una ripetizione troppo esatta).

Gli algoritmi probabilistici (spesso poco utilizzati nel campo dell'informatica puramente teorica) svolgono un ruolo chiave nella risoluzione di moltissimi problemi pratici. Qualora il problema sia di fatto intrattabile dal punto di vista computazionale, non esista un metodo di risoluzione esatto (oppure la sua applicazione sia numericamente instabile), un algoritmo probabilistico può avvicinarsi alla soluzione in modo arbitrariamente preciso. Sotto questa ottica gli algoritmi probabilistici possono essere suddivisi in tre categorie: Las Vegas, Atantic City e Monte Carlo.

Queste tre classi di algoritmi prendono il nome da altrettante città in cui si trovano famosi casinò. In particolare il termine Monte Carlo fu scelto per la prima volta da John von Neumann come nome in codice per uno studio sulla radioprotezione, svolto in segreto presso il Los Alamos Scientific Laboratory.

Las Vegas

Un algoritmo probabilistico di tipo Las Vegas fornisce un risultato corretto in un tempo ragionevolmente piccolo.

Sono usati soprattutto per problemi comuni, ma che richiedono di essere eseguiti su un insieme molto grande di dati.

L'algoritmo Las Vegas più conosciuto è certamente l'ordinamento veloce (o QuickSort) che dopo aver partizionato l'insieme da ordinare sceglie casualmente un perno per avviare il meccanismo ricorsivo. Nonostante la sua complessità sia (nel caso peggiore) quadratica nel numero $n$ di elementi da ordinare, richiede mediamente $n\log n\!$ passi.

Questa classe di algoritmi garantisce un risultato corretto ed esente da errore (a meno di instabilità numerica) ma non fornisce alcuna garanzia sulla finitezza del tempo di esecuzione. Perfino l'ordinamento veloce se applicato su una collezione molto vasta può richiedere un tempo indefinitamente lungo, anche se sicuramente finito. In questi casi è possibile interrompere anticipatamente un algoritmo Las Vegas imponendo di fatto una limitazione superiore al tempo di esecuzione ed accettando un risultato quasi sicuramente affetto da errore.

Atlantic City

Un algoritmo probabilistico di tipo Atlantic City fornisce un risultato probabilmente corretto in un tempo ragionevolmente piccolo.

La loro applicazione è rilegata principalmente ai modelli che richiedono un risultato discreto (vero o falso, classe di appartenenza, classificazione, ...) ma la cui soluzione esatta richiederebbe un tempo proibitivo. Di tutti i controlli da effettuare ne vengono eseguiti (casualmente) solo un certo numero finito: se l'algoritmo fallisce il risultato è certo ma in caso contrario può solo congetturare (con una certa probabilità) che la soluzione fornita sia esatta.

Un'applicazione classica per questo tipo di algoritmo sono i test di primalità. L'esecuzione di tutti i controlli necessari per stabilire se un determinato numero è (o meno) primo, è altamente proibitiva per valori molto grandi. Restringersi su un sottoinsieme limitato fornisce invece un risultato tanto più corretto quanti più test sono eseguiti. L'esecuzione può anche terminare anticipatamente: se uno dei test fallisce il numero in esame non è primo ed il risultato è esente da errore.

Rientrano in questa categoria sia il test di Miller-Rabin che quello di Fermat.

Monte Carlo

Un algoritmo probabilistico di tipo Monte Carlo fornisce un risultato probabilmente scorretto in un tempo finito.

Quando il problema da risolvere passa da un contesto discreto ad uno continuo, lo spazio delle soluzioni contiene un insieme potenzialmente infinito di stati. Gli algoritmi Atlantic City (che solitamente lavorano "per esclusione" su un numero limitato di possibilità) diventano altamente inefficaci ed il risultato perde la caratteristica principale di "probabilmente corretto" diventando anzi quasi sicuramente sbagliato.

Nonostante questo gli algoritmi di tipo Monte Carlo trovano una vastissima applicazione in tutti quei campi in cui è possibile lavorare con risultati approssimati. Il tempo di esecuzione di questi algoritmi è sicuramente finito, ma prolungandolo si riesce solitamente a trovare un risultato che meglio approssima la soluzione effettiva.

La loro applicazione più teorica riguarda il calcolo integrale ma stanno trovando sempre maggiore applicazione nel mondo della computer grafica dove la resa di un'immagine può essere approssimata non oltre la definizione massima del mezzo sul quale deve essere rappresentata (ovvero fino al pixel). Recenti implementazioni delle tecniche di ray tracing e di scattering fanno uso di algoritmi Monte Carlo.

Quando questa filosofia approccia il metodo sperimentale si tende a parlare di metodo di Monte Carlo piuttosto che di algoritmo. La critica che più spesso viene mossa è che un procedimento che non porta ad una soluzione corretta non può essere definito algoritmo.

Esempio

Stima della superficie del lago grazie a dei tiri di cannone casuali

Un'applicazione classica del metodo di Monte Carlo riguarda il calcolo di una superficie più o meno irregolare. Se la formula diretta per il calcolo dell'area è difficile da ricavare, si esegue una stima approssimata mediante un metodo probabilistico.

L'area (che può essere quella di un lago, di una montagna, di una funziona da integrare...) è iscritta in un quadrato del quale si conoscono i lati. Vengono successivamente scelti un numero di punti casuali al suo interno, alcuni dei quali apparterranno alla superficie in esame. Se il numero di punti è molto alto e se la loro distribuzione è normale, tenderanno a ricoprire le due superfici in modo uniforme: il rapporto tra i punti totali e quelli interni può essere usato come approssimazione del rapporto tra le due aree.

${\frac {Area_{totale}}{Area_{lago}}}={\frac {Punti_{totali}}{Punti_{interni}}},Area_{lago}=Area_{totale}*{\frac {Punti_{interni}}{Punti_{totali}}}$

Nonostante all'aumentare dei punti, tenda ad aumentare anche la precisione con la quale si riesce ad approssimare l'area della superficie, non è sempre vero che è possibile ottenere una soluzione esente da errore. Per esempio, applicare la tecnica dei punti ad un cerchio significa cercarne l'area nello spazio delle soluzioni formato da numeri razionali (ovvero, ottenuti tramite divisione di due numeri interi). Ma la soluzione reale (data dalla formula $\pi r^{2}\!$) introduce una quantità irrazionale $\pi$ che con ogni probabilità non potrà mai essere calcolata in questo modo.

Il modello scelto per approssimare la soluzione è errato in quanto non la contiene, ma questo non comporta un problema. Operando su calcolatori con memoria superiormente limitata e precisione finita, la soluzione reale sarebbe stata ugualmente affetta da errore. Aumentando il tempo di esecuzione del metodo di Monte Carlo si otterrà quindi una stima che tende non tanto al risultato reale, quanto all'approssimazione che sarebbe stata possibile calcolare con le risorse disponibili.

Bibliografia

• Thoas H. Cormen, Charles E. Leiserson; Ronald L. Rivest; Clifford Stein, ntroduction to Algorithms, 2ª ed., McGraw-Hill, 1990, pp. 91-122, ISBN 0-262-03293-7.
• Ping Sheng, Introduction to Wave Scattering, Localization, and Mesoscopic Phenomena, Springer, 1995, ISBN 3-540-29155-5.

Voci correlate

• Algoritmo
• Informatica
• Metodo Monte Carlo
• Quicksort
• Statistica
• Test di Miller-Rabin

Collegamenti esterni

• (EN) Probabilistic Algorithms: Abstract, su users.abo.fi. URL consultato il 14-02-2010.
• (EN) probabilistic algorithm, su itl.nist.gov. URL consultato il 14-02-2010.
• Algoritmi, Programmi, Teoremi (PDF), su di.unipi.it, 34-35. URL consultato il 14-02-2010.