Vés al contingut

Algorisme probabilístic

De la Viquipèdia, l'enciclopèdia lliure

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

[modifica]

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

[modifica]

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.

Teorema de Buffon : si es tira una agulla de longitud a un sòl fet amb tires de fusta d'amplada , la probabilitat que l'agulla toqui més d'una tira de fusta és .

Aplicació :

  • Si , llavors .
  • Si es tira l'agulla un nombre de vegades prou gran i es compta el nombre de cops que l'agulla toca més d'una tira de fusta, es pot estimar el valor de p:
  • É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 durant el segle xix.

Algorismes de Monte Carlo

[modifica]

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 un nombre real tal que . Un algorisme de Monte Carlo és p-correcte si:

  • Retorna una solució correcta amb probabilitat més gran o igual que , qualssevol que siguin les dades d'entrada.
  • De vegades, 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 primer. Llavors, per a tot enter tal que .

Exemple: .

Enunciat contrarecíproc del mateix teorema: si a i n són enters tals que , i si , llavors 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

[modifica]

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.