Algorisme probabilístic

Un algorisme probabilista (o probabilístic) és un algorisme que basa el seu resultat en la presa d'algunes decisions a l'atzar, de tal manera que, de mitjana, obté una bona solució al problema plantejat per a qualsevol distribució de les dades d'entrada. És a dir, al contrari que un algorisme determinista, a partir d'uns mateixes dades es poden obtenir diferents solucions i, en alguns casos, solucions errònies.

Hi ha diversos tipus d'algorismes probabilístics depenent del seu funcionament, es poden distingir:

Algorismes numèrics, que proporcionen una solució aproximada del problema.
Algorismes de Monte Carlo, que poden donar la resposta correcta o resposta errònies (amb probabilitat baixa).
Algorismes de Las Vegas, que mai no donen una resposta incorrecta: o bé donen la resposta correcta o informen de la decisió.

Consideracions

Es pot optar per l'elecció aleatòria si es té un problema en què l'elecció òptima és massa costosa davant la decisió aleatòria. Un algorisme probabilista pot comportar-se de manera diferent aplicant la mateixa entrada.

A un algorisme determinista mai se li permet que no s'acabi: fer una divisió per 0, entrar en un bucle infinit, etc.
Si hi ha més d'una solució per a unes dades donades, un algorisme determinista sempre troba la mateixa solució (llevat que es programi per trobar diverses o totes).
Un algorisme probabilista pot trobar solucions diferents executant diverses vegades amb les mateixes dades.
A un algorisme determinista no se li permet que calculi una solució incorrecta per cap dada.
Un algorisme probabilista pot equivocar-se sempre que això passi amb una probabilitat petita per cada dada d'entrada.
Repetint l'execució un nombre suficient de vegades per la mateixa dada, pot augmentar tant com es vulgui el grau de confiança en obtenir la solució correcta.
L'anàlisi de l'eficiència d'un algorisme determinista és, en determinades ocasions, difícil.
L'anàlisi dels algorismes probabilistes és, sovint, molt difícil.

Algorismes numèrics

La solució obtinguda és sempre aproximada però la seva precisió esperada millora augmentant el temps d'execució. Normalment, l'error és inversament proporcional a l'arrel quadrada de l'esforç invertit en el càlcul.

Exemple: L'agulla de Buffon

Teorema de Buffon : si es tira una agulla de longitud $\mu$ a un sòl fet amb tires de fusta d'amplada $w(w\geq \mu )$ , la probabilitat que l'agulla toqui més d'una tira de fusta és $p=2\mu /w\pi$ .

Aplicació :

Si $\mu =w/2$ , llavors $p=1/\pi$ .
Si es tira l'agulla un nombre de vegades $n$ prou gran i es compta el nombre $k$ de cops que l'agulla toca més d'una tira de fusta, es pot estimar el valor de p: $k\sim n/p\rightarrow p\sim n/k$

És (probablement) el primer algorisme probabilista de la història.

És útil aquest mètode?

Com és de ràpida la convergència? → quantes vegades s'ha de llençar l'agulla?

Molt lenta: n = 1500000 per obtenir un valor de p ± 0,01 amb probabilitat 0,9. De totes maneres, es va utilitzar força per aproximar el valor de $\pi$ durant el segle xix.

Algorismes de Monte Carlo

Hi ha problemes per als quals no es coneixen solucions deterministes ni probabilistes que donen sempre una solució correcta (ni tan sols una solució aproximada).

Algorisme de Monte Carlo :

A vegades dona una solució incorrecta.
Amb una alta probabilitat troba una solució correcta sigui quina sigui l'entrada.

Definició : Sigui $p$ un nombre real tal que $0,5<p<1$ . Un algorisme de Monte Carlo és p-correcte si:

Retorna una solució correcta amb probabilitat més gran o igual que $p$ , qualssevol que siguin les dades d'entrada.
De vegades, $p$ dependrà de la mida de l'entrada, però mai de les dades de l'entrada en si.

Un exemple d'algorisme de Monte Carlo (el més conegut): decidir si un nombre senar és primer o compost.

Cap algorisme determinista conegut pot respondre en un temps "raonable" si el nombre té centenars de xifres.

La utilització de nombres primers de centenars de xifres és fonamental en criptografia.

Pierre Fermat va postular el 1640 el petit teorema de Fermat: Sigui $n$ primer. Llavors, $a^{(n-1)}mod\ n=1$ per a tot enter $a$ tal que $1\leq a\leq n-1$ .

Exemple: $n=7,a=5\rightarrow 5^{6}mod\ 7=1$ .

Enunciat contrarecíproc del mateix teorema: si a i n són enters tals que $1\leq a\leq n-1$ , i si $a^{(n-1)}mod\ n\neq 1$ , llavors $n$ no és primer.

Fermat va formular la hipòtesi: "Fn = 2^(2^n)+1 és primer per a tot n"

El comprovar per: F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65.537.
Però no va poder comprovar si F5 = 4294967297 ho era.

Utilització del petit teorema de Fermat per a comprovar la primalitat: en el cas de F5, Fermat n'hauria tingut prou de veure que hi ha un 'a' tal que 1 ≤ a ≤ F5-1 tal que a^(F5 - 1) mod F5 <> 1) (a = 3). Amb aquestes premisses, es pot desenvolupar el següent algorisme:

 funció  Fermat (n: enter)  retorna  booleà
 variable  a: sencer
 principi 
a: = uniforme_enter (1, n-1);
 si  a ^n-1 mod n = 1
 llavors retorna  veritat
 sinó retorna  fals
 fsi 
 fi

Estudi de l'algorisme basat en el petit teorema de Fermat:

Si torna el valor fals, és segur que el nombre no és primer (pel teorema de Fermat).
Si torna el valor veritat: No podem concloure.

Algorismes de Las Vegas

Un algorisme de Las Vegas mai dona una solució falsa.

Presa de decisions a l'atzar per trobar una solució abans que un algorisme determinista.
Si no troba solució, ho admet.

Hi ha dos tipus d'algorismes de Las Vegas, segons la possibilitat de no trobar una solució:

Els que sempre troben una solució correcta, encara que les decisions a l'atzar no siguin afortunades i l'eficiència disminueixi.

Els que de vegades, a causa de decisions desafortunades, no troben una solució.

Tipus a: Algorismes de Sherwood

Hi ha una solució determinista que és molt més ràpida en mitjana que en el pitjor cas.

Exemple: quicksort.

Cost pitjor Ω (n^2) i cost mitjà O (nlog n).

Cost mitjà: es calcula sota la hipòtesi d'equiprobabilitat de l'entrada.
En aplicacions concretes, l'equiprobabilitat és falsa: entrades catastròfiques poden ser molt freqüents.
Degradació del rendiment en la pràctica.

Els algorismes de Sherwood poden reduir o eliminar la diferència d'eficiència per a diferents dades d'entrada:

Uniformització del temps d'execució per a totes les entrades de la mateixa mida.
De mitjana (pres sobre tots els exemplars de la mateixa mida) no es millora el cost.
Amb alta probabilitat, exemplars que eren molt costosos (amb algorisme determinista) ara es resolen molt més ràpid.
Altres exemplars per als quals l'algorisme determinista era molt eficient, es resolen ara amb més cost.

Tipus b: Algorismes que, de vegades, no donen resposta .

Són acceptables si fallen amb probabilitat baixa.
Si fallen, es tornen a executar amb la mateixa entrada.
Resolen problemes per als quals no es coneixen algorismes deterministes eficients (exemple: la factorització d'enters grans).
El temps d'execució no està fitat però sí que és raonable amb la probabilitat desitjada per a tota entrada.

Consideracions sobre el cost :

Sigui LV un algorisme de Las Vegas que pot fallar i sigui p (x) la probabilitat d'èxit si l'entrada és x.

 algorisme  LV ( ent  x: tpx;  sal  s: tpsolución;
 sal  èxit: booleà)

{èxit retorna veritat si LV troba la solució

i en aquest cas es torna la solució trobada}

S'exigeix que p (x)> 0 per a tot x.
És millor encara si hi ha d> 0: p (x)> = d per tot x (així, la probabilitat d'èxit no tendeix a 0 amb la mida de l'entrada).

Ara repetim l'algorisme anterior per guanyar en eficàcia:

 funció  repe_LV (x: tpx)  retorna  tpsolución
 variables  s: tpsolución; èxit: booleà
 principi 
 repetir 
LV (x, s, èxit)
 hastaQue  èxit;
 retorna  s
 fi

El nombre d'execucions del bucle és 1/p (x).
Sigui v (x) el temps esperat d'execució de LV si èxit = veritat if (x) el temps esperat si èxit = fals.
el temps esperat de repe_LV () = v (x)+((1 - p (x))/p (x)) f (x).

Exemple: El problema de les 8 reines en el tauler d'escacs .

Algorisme determinista: N º de nodes visitats: 114 dels 2.057 nodes de l'arbre)
Algorisme de Las Vegas voraç: col·locar cada reina aleatòriament en un dels escacs possibles de la següent fila. L'algorisme pot acabar amb èxit o fracàs (quan no hi ha forma de col·locar la següent reina). N º de nodes visitats si hi ha èxit: v = 9, nombre esperat de nodes visitats si hi ha fracàs: f = 6,971, Probabilitat d'èxit: p = 0,1293 (més d'1 cop de cada 8)

Nombre esperat de nodes visitats repetint fins a obtenir un èxit: t = v+f (1-p)/p = 55,93, menys de la meitat.