Algoritmos Probabilfsticos

Algoritmos Probabilfsticos

Los algoritmos probabilísticos han atraído el interés de los investigadores de manera creciente en los últimos 20 años, y actualmente son un tema central de investigación en Ciencias de la Computación, Investigación Operativa, y Matemática Discreta. El poder de la “randomización” para resolver problemas proviene de que un algoritmo probabilístico es una distribución probabilística sobre una clase de algoritmos determinísticos. Para cualquier instancia dada de un problema, algunos de los algoritmos determinísticos en la base del algoritmo probabilístico pueden comportarse pobremente, pero eso puede ser compensado con buenas prestaciones de otros en forma tal que el comportamiento esperado sea bastante bueno.

Otra aplicación quizás inesperada de los algoritmos probabilísticos es en pruebas de teoremas de existencia relativos a propiedades de objetos combinatorios.

El uso de números aleatorios para simular o aproximar procesos no aleatorios es muy natural en la práctica de la computación. Sin embargo, la idea de que las entradas aleatorias pueden servir para resolver problemas combinatorios determinísticos ha penetrado más lentamente en la comuninidad de las Ciencias de la Computación. Aquí, centraremos la atención en los algoritmos probabilísticos de tiempo polinomial que “resuelven” (en un sentido razonable) un problema para el que no se conoce ningún algoritmo deterministico en tiempo polinomial.

El primer ejemplo de estos algoritmos es el de Berlekamp (1970), para factorizar un polinomio f sobre el cuerpo de p elementos. Este algoritmo corre en tiempo polinomial sobre el grado de f y , y con probabilidad de al menos un medio de encontrar una factorización correcta. Dado que el algoritmo se puede repetir cualquier número de veces, y la probabilidad de fallo es siempre independiente, en la práctica el algoritmo siempre factoriza f en tiempo polinomial.

Otro ejemplo es el algoritmo para el reconocimiento de números primos de Slovay y Strassen (1977). Este algoritmo corre en tiempo polinomial sobre la longitud de la entrada m, y la salida es o bien “primo” o bien “compuesto”. Si m es realmente primo, entonces la salida es primo, pero si m es compuesto, la salida puede ser primo con probabilidad a lo más un medio. El algoritmo puede ser repetido cualquier número de veces con resultados independientes. Así, si la respueta alguna vez es compuesto, sabemos que es compuesto, mientras que si la respuesta es siempre primo, despues de por ejemplo 100 veces, entonces podemos decir sin apenas riesgo de equivocarnos que es primo, dado que fijado un compuesto cualquiera m, la probabilidad de que se diera ese resultado es menor que Rabin (1976) encontró un algoritmo similar pero más rapido. ¡Identificó como primo al número en pocos minutos!

Una aplicación interesante del reconocedor probabilístico de primos en el sentido de Solovay y Strassen se conoce como R (a veces RP) . Un conjunto estará en R si y solo si tiene un algoritmo reconocedor probabilístico que siempre para en tiempo polinomial y nunca comete un error para entradas que no estén en R, y tal que para cada entrada que esté en R la probabilidad de acertar sea de al menos . Así el conjunto de números compuestos está en R, y en general . Hay ejemplos de conjuntos interesantes que están en R, pero que no se ha podido demostrar que estén en P. Por ejemplo, Schwartz (1980) demostró que el conjunto de matrices no singulares cuyos elementos son polinomios en muchas variables esta en R.

La igualdad R=P es un interesante problema abierto. Si la respuesta fuese positiva, nos diría que el uso que los algoritmos probabilísticos no aportan nada nuevo en la computación. Una cuestión relacionada con esto es si un algoritmo probabilístico es, desde el punto de vista práctico, tan bueno como un algoritmo determinístico.

Finalizamos esta sección con un interesante teorema de Adleman (1978) sobre la clase R. Es fácil ver que si un conjunto está en P, entonces para cada n hay un circuito booleano de tamaño acotado por un polinomio fijo sobre n que determina si una entrada arbitraria de tamaño n está o no en el conjunto. Lo que Adleman provó es que lo mismo ocurre para la clase R.

por chelita…

Los algoritmos probabilisticos son los que hacen algunas opciones aleatoriamente (o pseudo-al azar); para algunos problemas, puede en hecho ser probado que las soluciones más rápidas deben implicar una cierta aleatoriedad.

El algoritmo utiliza típicamente los pedacitos al azar como entrada auxiliar para dirigir su comportamiento, en la esperanza de alcanzar buen funcionamiento en el “caso medio”. Formalmente, el funcionamiento del algoritmo será una variable al azar determinada por los pedacitos al azar, con (esperanzadamente) buen valor previsto. El “caso peor” es típicamente tan poco probable de ocurrir que puede ser no hecho caso.

The source of this article is Wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad