Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmo Probabilístico

No description
by

Andrés Rivera

on 21 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmo Probabilístico

Ventajas:
son aquellos en los que en algún punto del algoritmo hay que tomar una decisión y esta, se elige basandose en el azar
Diferentes soluciones
Aumentar la posibilidad de encontrar la solución correcta
Complejidad Computacional
Camilo Ospina
Andrés Rivera
Los algoritmos probabilísticos se clasifican en tres tipos:

No siempre la respuesta es correcta.
* Algoritmo numérico
* Algoritmos de Monte Carlo

Siempre da una respuesta correcta
* Algoritmo de la vegas

Clasificación
Mayor eficiencia en tiempo y/o memoria.
Algoritmo Probabilístico
Zero-error Probabilistic Polynomial Time
(tiempo polinómico probabilístico de error nulo).
ZPP
Bounded-error Probabilistic Polynomial Time
(tiempo polinómico probabilístico con error acotado).

p>1/2 tiempo polinómico.
BPP
Randomized polynomial time
(tiempo polinómico aleatorio)

p>0 tiempo polinómico.
RP
Algoritmo
Probabilístico
Fundamentos de la algoritmia: G.Brassard & P.Bratley.

http://webdiis.unizar.es/asignaturas/EDA/ea/slides/8-Algoritmos%20probabilistas.pdf

http://exa.unne.edu.ar/informatica/programacion1/public_html/archivos/tema10_algoritmos.pdf


Biografía
Dan una solución aproximada

Dan un intervalo de confianza (“con probabilidad del 90%”)

a mayor tiempo de ejecución, mejor es la aproximación.

Ejemplo: la aguja de buffon
Algoritmo numérico
Si se tira una aguja de longitud
x
a un suelo hecho con tiras de madera, distanciadas entre si en
y
unidades
(y>x)

Si la aguja se lanza
n
veces y
c
de esas cruza una linea

pi=2nx/cy
Aguja de buffon
Dan la respuesta exacta con una alta probabilidad

No se puede saber con seguridad si la respuesta es la correcta

Se reduce la probabilidad de error alargando la ejecución

Ejemplo: como decir si un numero impar es primo o compuesto

Algoritmo de Monte Carlo
Si el numero impar es primo o compuesto
Si el algoritmo no encuentra solución aparece error

Es posible volver a intentar con los mismos datos hasta obtener la solución correcta

Ejemplo: el problema de las 8 reinas

Algoritmo de las vegas
El problema consiste en colocar 8 reinas en tablero de ajedrez pero que no se ataquen entre ellas.
El problema de las 8 reinas
Los algoritmos probabilísticos dan lugar a clases de complejidad probabilistas. Que son los problemas de decisión, tales como.

-BPP: Monte Carlo.
-ZPP: Las Vegas.
-RP
Introducción al algoritmo probabilístico
Gracias!!
Full transcript