Algoritme provabiliste

Un algoritme provabiliste (o provabilístic) és un algoritme que basa el seu resultat en la pren d'algunes decisions a l'encert, de tal forma que, en promig, obté una bona solució al problema plantejat per a qualsevol distribució de les senyes d'entrada. És dir, al contrari que un algoritme determinista, a partir d'unes mateixes senyes es poden obtindre distintes solucions i, en alguns casos, solucions errònees.

Existixen varis tipos d'algoritmes provabilístics depenent del seu funcionament, podent-se distinguir:

• Algoritmes numèrics, que proporcionen una solució aproximada del problema.
• Algoritmes de Montecarlo, que poden donar la resposta correcta o resposta errònees (en provabilitat baixa).
• Algoritmes de Las Vegas, que mai donen una resposta incorrecta: o be no troben la resposta correcta i informen del fallo.

Consideracions

Es pot optar per l'elecció aleatòria si es té un problema l'elecció òptima del qual és massa costosa front a la decisió aleatòria. Un algoritme provabiliste pot comportar-se de distinta forma aplicant la mateixa entrada.

• A un algoritme determinista mai se li permet que no termine: fer una divisió per 0, entrar en un bucle infinit, etc. mentres que a un algoritme provabiliste se li permeten estos casos sempre que la provabilitat de que ocórreguen siga baixa.
• Si existix més d'una solució per a unes senyes donades, un algoritme determinista sempre troba la mateixa solució (a no ser que es programe per a trobar vàries o totes).
• Un algoritme provabiliste pot trobar solucions diferents eixecutant-se vàries voltes en les mateixes senyes.
• A un algoritme determinista no se li permet que calcule una solució incorrecta per a cap senya.
• Un algoritme provabiliste pot equivocar-se sempre que açò ocórrega en una provabilitat chicoteta per a cada senya d'entrada.
• Repetint l'eixecució un número suficient de voltes per a la mateixa senya, pot aumentar-se tant com es vullga el grau de confiança en obtindre la solució correcta.
• L'anàlisis de l'eficiència d'un algoritme determinista és, en determinades ocasions, difícil.
• L'anàlisis dels algoritmes provabilistes és, a sovint, molt difícil.

Algoritmes numèrics

La solució obtinguda és sempre aproximada pero la seua precisió esperada millora aumentant el temps d'eixecució. Normalment, l'error és inversamente proporcional a la raïl quadrada de l'esforç invertit en el càlcul.

Eixemple: L'agulla de Buffon

Artícul principal → Agulla de Buffon.

En el XVIII, Georges Louis Leclerc, comte de Buffon va enunciar la Teorema de Buffon

Si es tira una agulla de llongitut μ a un sol fet en tires de fusta d'esgambi w (w≥μ), la provabilitat de que l'agulla toque més d'una tira de fusta és p=2μ/wπ.

Aplicació:

Una aplicació de la teorema de Buffon és utilisar-ho per a predir el valor de π. Siga μ=w/2, llavors p=1/π. Si es tira l'agulla un número de voltes n suficientment gran i es conta el número k de voltes que l'agulla toca més d'una tira de fusta, es pot estimar el valor de p: k n/p → p n/k.

En la pràctica, no és un algoritme útil, perque es poden obtindre aproximacions de π molt millors amprant métodos determinista. A pesar d'açò, va ser molt utilisada en el XIX, fent d'este un dels primers algoritmes provabilistes que es varen utilisar.

Eixemple: Integració numèrica

Artícul principal → Integració de Montecarlo.

L'algoritme provabiliste numèric més conegut és l'integració de Mont Carlo. cal destacar que a pesar del seu nom, no és un algoritme provabiliste de Mont Carlo.

L'algoritme de Mont Carlo pot ser representat pel següent pseudocódigo, en a on s'integra la funció f entre a i b utilisant n iteraciones.

funció Monte Carlo(f,n,a,b)
suma = 0
per a i=1 fins a
 n x = uniforme(a,b)
 suma = suma + f(x)
tornar (b-a)(suma/n)

La varianza de l'estimació calculada per mig d'este algoritme és inversamente proporcional al número de punts de la mostra. L'error esperat en l'estimació és inversamente proporcional a la raïl quadrada de n, de manera que es requerixen 100 iteraciones més per a obtindre un dígit adicional de precisió.

En general, es poden obtindre estimacions d'integrals per mig de métodos determinista en major precisió i en menys iteraciones. No obstant, a tot algoritme determinista d'integració, inclús als més complexos, li corresponen funcions contínues dissenyades expressament per a enganyar a l'algoritme. Açò no ocorre en el método de Mont Carlo, encara que existix una provabilitat chicoteta de que l'algoritme poguera cometre un error similar aun cuando integre una funció completament comuna.

L'aplicació de l'integració de Mont Carlo té més sentit quan es té que evaluar una integral múltiple, ya que la dimensió de l'integral sol tindre poc efecte sobre la precisió obtinguda, encara que la cantitat de treball aumente en la dimensió. En la pràctica, s'utilisa per a evaluar integrals de dimensions majors que tres ya que no hi ha una atra tècnica que siga competitiva. Es pot millorar la precisió de les respostes amprant tècniques híbrides.