Post on 27-Jul-2020
Técnicas de diseño de algoritmos
Algoritmos aleatorizados
Dra. Elisa Schaeffer
elisa.schaeffer@gmail.com
PISIS / FIME / UANL
Algoritmos aleatorizados– p. 1
Algoritmos aleatorizados
= algoritmos que incorporan además de instruccionesdeterministas algunas elecciones al azar
Un ejemplo simple de un algoritmo aleatorio sería unaversión de la ordenación rápida donde el elemento pivoteestá elegido uniformemente al azar entre los elementospara ordenar.
Algoritmos aleatorizados– p. 2
Notaciones de probabilidad
X y Y son variables aleatorias, x y y son algunasvaloresque pueden tomar estas variables
Algoritmos aleatorizados– p. 3
Notaciones de probabilidad
X y Y son variables aleatorias, x y y son algunasvaloresque pueden tomar estas variables
Pr [X = x] es la probabilidad que X tenga el valor x
Algoritmos aleatorizados– p. 3
Notaciones de probabilidad
X y Y son variables aleatorias, x y y son algunasvaloresque pueden tomar estas variables
Pr [X = x] es la probabilidad que X tenga el valor x
la esperanzaE [X] =∑
x
xPr [X = x]
Algoritmos aleatorizados– p. 3
Notaciones de probabilidad
X y Y son variables aleatorias, x y y son algunasvaloresque pueden tomar estas variables
Pr [X = x] es la probabilidad que X tenga el valor x
la esperanzaE [X] =∑
x
xPr [X = x]
la varianzaVar [X] = E [(X − E [X])2] = E [X2]− (E [X])2
Algoritmos aleatorizados– p. 3
Análisis
¿Con qué probabilidad el algoritmo da el resultadocorrecto?
Algoritmos aleatorizados– p. 4
Análisis
¿Con qué probabilidad el algoritmo da el resultadocorrecto?
¿Qué es la esperanza del número de los pasos decomputación necesarios para su ejecución?
Algoritmos aleatorizados– p. 4
Análisis
¿Con qué probabilidad el algoritmo da el resultadocorrecto?
¿Qué es la esperanza del número de los pasos decomputación necesarios para su ejecución?
(En el caso de algoritmos de aproximaciónaleatorizadas:) ¿Qué es la deviación esperada de lasolución óptima?
Algoritmos aleatorizados– p. 4
Resultados incorrectos
Una definición más “flexible” de algoritmo: un algoritmoaleatorizado tiene “permiso” para dar una salidaincorrecta, mientras al definir algoritmos (deterministas)exigimos que siempre termine su ejecución y que elresultado sea el deseado.
Sin embargo, no todos los algoritmos aleatorizados danresultados incorrectos — el caso ideal sería que unresultado incorrecto sea imposible o que ocurra conprobabilidad muy pequeña.
Algoritmos aleatorizados– p. 5
Algoritmos Monte Carlo
Algoritmos con una probabilidad no cero de fallar (yprobabilidad no cero de dar el resultado correcto) sellaman algoritmos Monte Carlo.
Un algoritmo MC tiene error bilateral si la probabilidadde error es no cero para los ámbos casos: con larespuesta “si” y con la respuesta “no”.
Un algoritmo MC tiene error unilateral si siemprecontesta correctamente en uno de los dos casos perotiene probabilidad no cero de equivocarse en el otro.
Algoritmos aleatorizados– p. 6
Algoritmo Las Vegas
Un algoritmo que siempre da el resultado correcto se diceun algoritmo Las Vegas.
En tal algoritmo, la parte aleatoria está limitada al tiempode ejecución del algoritmo, mientras los algoritmos MonteCarlo tienen hasta sus salidas “aleatorias”.
Algoritmos aleatorizados– p. 7
Mejora por iterar
Si tenemos un algoritmo Monte Carlo con probabilidad deerror 0 < p < 1, lo podemos convertir a un algoritmo MonteCarlo con probabilidad de error arbitrariamente pequeña0 < q ≤ p:
Repetir ejecuciones independientes del algoritmo originalk veces tal que pk ≤ q.
Algoritmos aleatorizados– p. 8
Conversión MC 7→ LV
Cada algoritmo Monte Carlo que sabe distinguir entrehaberse equivocado se puede convertir a un algoritmo LasVegas por repertilo hasta obtener éxito — este tieneobviamente efectos en su tiempo de ejecución.
También si tenemos un algoritmo rápido para verificar siuna dada “solución” es correcta (cf. los certificadosconcisos de los problemas NP), podemos convertir unalgoritmo Monte Carlo a un algoritmo Las Vegas porrepetirlo.
Algoritmos aleatorizados– p. 9
Resultados útiles
Desigualdad de JensenSi f es una función convexa,E [f(X)] ≥ f(E [X]).
Desigualdad de Markov Sea X una variable aleatoria nonegativa. Para todo α > 0, Pr [X ≥ α] ≤ α−1 E [X].
Desigualdad de ChebyshevPara todo α > 0,Pr [|X − E [X]| ≥ α] ≤ α−2Var [X].
Algoritmos aleatorizados– p. 10
Más resultados útiles
Cotas de Chernoff Para α > 0, para todo t > 0 aplica quePr [X ≥ α] ≤ e−tα E
[
etX]
y para todo t < 0 aplica quePr [X ≤ α] ≤ e−tα E
[
etX]
.
El metodo probabilista Sea X una variable aleatoriadefinida en el espacio de probabilidad S tal queE [X] = µ. Entonces Pr [X ≥ µ] > 0 y Pr [X ≤ µ] > 0.
El metodo del momentum segundoSea X una variablealeatoria entera. EntoncesPr [X = 0] ≤ (E [X])−2Var [X].
Algoritmos aleatorizados– p. 11
Complejidad computacional
La clase RP (tiempo polinomial aleatorizado, inglés:randomized polynomial time) es la clase de todos loslenguajes L que cuenten con un algoritmo aleatorizado Acon tiempo de ejecución polinomial del peor caso tal quepara cada entrada x ∈ Σ∗
x ∈ L =⇒ Pr [A(x) = “sí”] ≥ p,
x /∈ L =⇒ Pr [A(x) = “sí”] = 0,donde p > 0
(comúnmente se define p = 0,5, pero la elección del valorde p es de verdad arbitraria).
Algoritmos aleatorizados– p. 12
RP y Monte Carlo
El algoritmo A es entonces un algoritmo Monte Carlo conerror unilateral.
La clase coRP es la clase con error unilateral en el casox /∈ L pero sin error con las entradas x ∈ L.
Algoritmos aleatorizados– p. 13
ZPP y Las Vegas
La existencia de un algoritmo Las Vegas polinomialmuestra que un lenguaje pertenece a las clases RP ycoRP las dos.
De hecho, esta clase de lenguajes con algoritmos LasVegas polinomiales se denota por ZPP (zero-errorprobabilistic polynomial time)
ZPP = RP ∩ coRP
Algoritmos aleatorizados– p. 14
PP
Una clase más débil es la PP (probabilistic polynomial time)que consiste de los lenguajes L para las cuales existe unalgoritmo aleatorizado A con tiempo de ejecución de peorcaso polinomial y para todo x ∈ Σ∗ aplica que
x ∈ L =⇒ Pr [A(x) = “sí”] > 12,
x /∈ L =⇒ Pr [A(x) = “sí”] < 12.
Por ejecutar A varias veces, podemos reducir la probabilidad deerror, pero no podemos garantizar que un número pequeño derepeticiones basta para mejorar significativamente la situación.
Algoritmos aleatorizados– p. 15
BPP
Una versión más estricta de PP se llama BPP (tiempopolinomial aleatorizado, inglés: bounded-error probabilisticpolynomial time) que es la clase de los lenguajes L paralas cuales existe un algoritmo aleatorizado A con tiempode ejecución de peor caso polinomial y para todo x ∈ Σ∗
aplica que
x ∈ L =⇒ Pr [A(x) = “sí”] ≥ 34,
x /∈ L =⇒ Pr [A(x) = “sí”] ≤ 14.
Para esta clase se puede demostrar que la probabilidad deerror se puede bajar a 2−n con p(n) iteraciones donde p()es un polinomio.
Algoritmos aleatorizados– p. 16
Más información
Problemas abiertos interesantes incluyen por ejemplo siBPP es un subclase de NP.
Libros:
Papadimitriou, 1994
Motwani y Raghavan, 1995
Mitzenmacher y Upfal, 2005
Algoritmos aleatorizados– p. 17
Ejemplo: M INCUT
Vamos a considerar multigrafos, o sea, permitimos queentre un par de vértices exista más que una arista en elgrafo de entrada G.
Considerando que un grafo simple es un caso especial deun multigrafo, el resultado del algoritmo que presentamosaplica igual a grafos simples.
Algoritmos aleatorizados– p. 18
Repaso de M INCUT
M INCUT ∈ P
Algoritmos aleatorizados– p. 19
Repaso de M INCUT
M INCUT ∈ P
Estamos buscando un corte C ⊆ V de G.
Algoritmos aleatorizados– p. 19
Repaso de M INCUT
M INCUT ∈ P
Estamos buscando un corte C ⊆ V de G.
La capacidad del corte es el número de aristas que locrucen.
Algoritmos aleatorizados– p. 19
Repaso de M INCUT
M INCUT ∈ P
Estamos buscando un corte C ⊆ V de G.
La capacidad del corte es el número de aristas que locrucen.
Suponemos que la entrada G sea conexo.
Algoritmos aleatorizados– p. 19
Repaso de M INCUT
M INCUT ∈ P
Estamos buscando un corte C ⊆ V de G.
La capacidad del corte es el número de aristas que locrucen.
Suponemos que la entrada G sea conexo.
Todo lo que mostramos aplicaría también para grafos(simples o multigrafos) ponderados con pesos nonegativos.
Algoritmos aleatorizados– p. 19
Algoritmos deterministas
Através de flujo maximo: O (nm log(n2/m))
Algoritmos aleatorizados– p. 20
Algoritmos deterministas
Através de flujo maximo: O (nm log(n2/m))
Habría que repetirlo para considerar todos los paresde fuente-sumidero.
Algoritmos aleatorizados– p. 20
Algoritmos deterministas
Através de flujo maximo: O (nm log(n2/m))
Habría que repetirlo para considerar todos los paresde fuente-sumidero.Se puede demostrar que basta con (n− 1)repeticiones.
Algoritmos aleatorizados– p. 20
Algoritmos deterministas
Através de flujo maximo: O (nm log(n2/m))
Habría que repetirlo para considerar todos los paresde fuente-sumidero.Se puede demostrar que basta con (n− 1)repeticiones.
=⇒ M INCUT ∈ Ω (n2m)
Algoritmos aleatorizados– p. 20
Algoritmos deterministas
Através de flujo maximo: O (nm log(n2/m))
Habría que repetirlo para considerar todos los paresde fuente-sumidero.Se puede demostrar que basta con (n− 1)repeticiones.
=⇒ M INCUT ∈ Ω (n2m)
Con unos trucos: mincut ∈ O (nm log(n2/m))
Algoritmos aleatorizados– p. 20
Algoritmos deterministas
Através de flujo maximo: O (nm log(n2/m))
Habría que repetirlo para considerar todos los paresde fuente-sumidero.Se puede demostrar que basta con (n− 1)repeticiones.
=⇒ M INCUT ∈ Ω (n2m)
Con unos trucos: mincut ∈ O (nm log(n2/m))
Grafos densos: m ∈ O (n2)
Algoritmos aleatorizados– p. 20
Contracción
Al contraer la arista u, v reemplazamos los dos vérticesu u v por un vértice nuevo w.
La arista contraída desaparece, y para toda arista s, u talque s /∈ u, v, “movemos” la arista a apuntar a w porreemplazarla por s, w.
Igualmente reemplazamos aristas s, u por aristas s, wpara todo s /∈ u, v.
Algoritmos aleatorizados– p. 21
Ejemplo
Algoritmos aleatorizados– p. 22
Contracción iterativa
Si contraemos un conjunto F ⊆ E, el resultado nodepende del orden de contracción.
Después de las contracciones, los vértices que quedanrepresentan subgrafos conexos del grafo original.
Empezando con el grafo de entraga G, si elegimositerativamente al azar entre las aristas presentes una paracontracción hasta que quedan sólo dos vértices, el númerode aristas en el multigrafo final entre esos dos vérticescorresponde a un corte de G.
Algoritmos aleatorizados– p. 23
Implementación
Con una estructura unir-encontrar , podemos fácilmentemantener información sobre los subgrafos representados.
Algoritmos aleatorizados– p. 24
Implementación
Con una estructura unir-encontrar , podemos fácilmentemantener información sobre los subgrafos representados.
Al contraer la arista u, v, el nombre del conjuntocombinado en la estructura será w y sus miembros son u uw; originalmente cada vértice tiene su propio conjunto.
Algoritmos aleatorizados– p. 24
Implementación
Con una estructura unir-encontrar , podemos fácilmentemantener información sobre los subgrafos representados.
Al contraer la arista u, v, el nombre del conjuntocombinado en la estructura será w y sus miembros son u uw; originalmente cada vértice tiene su propio conjunto.
Entonces, podemos imprimir los conjuntos C y V \ C quecorresponden a los dos vértices que quedan en la últimaiteración.
Algoritmos aleatorizados– p. 24
Análisis parcial
La elección uniforme de una arista para contraer sepuede lograr en O (n).
Algoritmos aleatorizados– p. 25
Análisis parcial
La elección uniforme de una arista para contraer sepuede lograr en O (n).
En cada iteración eliminamos un vértice, por lo cual elalgoritmo de contracción tiene complejidad cuadráticaen n.
Algoritmos aleatorizados– p. 25
Análisis parcial
La elección uniforme de una arista para contraer sepuede lograr en O (n).
En cada iteración eliminamos un vértice, por lo cual elalgoritmo de contracción tiene complejidad cuadráticaen n.
Lo que queda mostrar es que el corte así producidosea el mínimo con una probabilidad no cero.
Algoritmos aleatorizados– p. 25
Análisis parcial
La elección uniforme de una arista para contraer sepuede lograr en O (n).
En cada iteración eliminamos un vértice, por lo cual elalgoritmo de contracción tiene complejidad cuadráticaen n.
Lo que queda mostrar es que el corte así producidosea el mínimo con una probabilidad no cero.
Así por repetir el algoritmo, podríamos aumentar laprobabilidad de haber encontrado el corte mínimo.
Algoritmos aleatorizados– p. 25
Observaciones
Si la capacidad del corte mínimo es k, ningún vérticepuede tener grado menor a k.
El número de aristas satisface m ≥ 12nk si la
capacidad del corte mínimo es k.
La capacidad del corte mínimo en G después de lacontracción de una arista es mayor o igual a lacapacidad del corte mínimo en G.
Algoritmos aleatorizados– p. 26
Más análisis
Fijamos un corte mínimo de G = (V,E) con las aristasF ⊆ E siendo las aristas que cruzan de C a V \ C.
Denotamos |F | = k.
Suponemos que estamos en la iteración i del algoritmo decontracción y que ninguna arista en F ha sido contraidatodavía.
Algoritmos aleatorizados– p. 27
Estructura a la iteración i
Quedan ni = n− i+ 1 vértices en el grafo actual Gi.
El conjunto de aristas F todavía define un corte mínimo enel grafo actual Gi.
Los vértices de los dos lados del corte definido por lasaristas en F corresponden a los conjuntos C y V \ C,aunque (posiblemente) en forma contraida.
Algoritmos aleatorizados– p. 28
Probabilidad
El grafo Gi tiene, por la segunda observación, por lomenos 1
2nik aristas, por lo cual la probabilidad que la
siguiente iteración contraiga una de las aristas de F esmenor o igual a 2ni
−1.
Podemos acotar la probabilidad p que ninguna arista de Fsea contraida durante la ejecución del algoritmo:
p ≥n−2∏
i=1
(1− 2(n− i+ 1)−1) =
(
n
2
)−1
=2
n(n− 1)
Algoritmos aleatorizados– p. 29
Aún más análisis
Hemos establecido que un corte mínimo específido de Gcorresponde al resultado del algoritmo de contracción conprobabilidad p ∈ Ω (n−2).
Como cada grafo tiene por lo menos un corte mínimo, laprobabilidad de éxito del algoritmo es por lo menosΩ (n−2).
Si repetimos el algoritmo, digamos O (n2 log n) veces ya darazón de esperar que el corte de capacidad mínimaencontrado sea el corte mínimo del grafo de entreda.
Algoritmos aleatorizados– p. 30
Mejoramiento
Para hacer que el algoritmo Monte Carlo resultante seamás rápida, hay que aumentar la probabilidad de que uncorte mínimo pase por el algoritmo sin ser contraido.
Una posibilidad de mejora está basada en la observaciónque la probabilidad de contraer una arista del corte mínimocrece hacía el final del algoritmo.
Algoritmos aleatorizados– p. 31
Resultado
Si en vez de contraer hasta que queden dos vértices,contraemos primero hasta aproximadamente n/
√2
vértices y después hacemos dos llamadas recursivasindependientes del mismo algoritmo con el grafo Gi quenos queda, un análisis detallado muestra que llegamos ala complejidad O
(
n2(log n)O(1))
.
Algoritmos aleatorizados– p. 32
Tarea para entregar el martes
Dada una formula 3SAT φ con m cláusulas, demuestra quesiempre existe una asignación de verdad T que satisfacepor lo menos 87.5 % de las clausulasde φ.
(Sí, la idea es que utilizen argumentos probabilistas.
Algoritmos aleatorizados– p. 33