Post on 21-Sep-2018
transcript
COMPUTACIÓN ALEATORIZADAProbabilidad y algoritmos
Dra. Elisa SchaefferProfesora del Posgrado de Ing. de Sistemas (PISIS)en la Facultad de Ing. Mecánica y Eléctrica (FIME),Coordinador del área de TI & Software del CIIDIT
Conferencia magistral
CONTENIDO
Probabilidad en el mundo real
Computación como herramienta
Debilidades del determinismo
Aproximaciones y heurísticas
PROBABILIDAD
Intuición: la frecuencia con la cual obtengamos una cierta salida entre un conjunto de posibles salidas cuando estamos repetiendo un experimento
Ejemplos: lanzamiento de monedas o dados, fallas de componentes electrónicos
Asignándoles nombres
a las posibles salidas, podemos denotar con el experimento y por la probabilidad de que la salida sea .
Para que tengamos cubiertos todas las salidas posibles, es necesario que
VARIABLE ALEATORIA
X
P (X = xi)xi
{x1, x2, . . . , xn}
n!
i=1
P (X = xi) = 1
VALOR ESPERADO
Supongamos que cada salida tiene asociado un valor numérico y denotamos este valor por .
El valor esperado de un experimento es
xi
Exp(X) =n!
i=1
"xi · P (X = xi)
#
COMPUTACIÓN
Algoritmo = un método de solución que permite siempre llegar a la respuesta correcta a una pregunta específica en un número finito de pasos deterministas de cómputo
Algoritmo aleatorizado = un método de solución que permite con probabilidad no-cero llegar a la respuesta correcta a una pregunta específica en un número esperado finito de pasos probabilistas de cómputo
ALGORITMO EFICIENTE
La calidad de un algoritmo se mide por el número de pasos de cómputo que necesita: lo más rápido lo mejor.
Se dice que un algoritmo es eficiente si el número de pasos requiridos crece polinomialmente con respeto al tamaño de la instancia.
Se denota por la complejidad asintótica: el número de pasos siempre comporta igual o mejor que la función .
O(f(n))
f(n)
ORDENAMIENTO RÁPIDO
El mejor algoritmo de ordenamiento de datos es el órdenamiento rápido (inglés: quicksort)
1. Elegimos un elemento para ser el pivote
2. Movemos todos los elementos menores o iguales al pivote a la izquierda y los mayores a la derecha
3. Repetimos recursivamente
entre los a la izquierdaentre los a la derecha
COMPLEJIDAD
El ordenamiento rápido puede alcanzar una complejidad buena: ordenar elementos en solamente pasos de cómputo.
Los algoritmos ingenuos como ordenamiento de burbuja toman más tiempo, .
Si son muchos datos, la diferencia es muy significativa.
O(n log n)n
O(n2)
QUADRÁTICO VS. LOG-LINEAL
0
50
100
150
200
250
300
350
400
0 5 10 15 20 1
10
100
1000
10000
0 20 40 60 80 100
Escala lineal Escala logarítmica
ELECCIÓN DE PIVOTE
Meta: alcanzar la complejidad buena .
Para que el algoritmo sea eficiente, no podemos perder tiempo en elegir el pivote de alguna manera muy sofisticada.
Pero si lo elegimos el elemento pivote por una regla determinista simple, el algoritmo tarda en el peor caso .
O(n log n)
O(n2)
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
✘
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77 ✘
✘
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
✘
✘
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77 ✘
✘
✘
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
✘
✘
✘
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77 ✔
✘
✘
✘
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
✔
✘
✘
✘
EJEMPLO
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
13 37 17 34 48 11 23 53 25 65 77
✔
✘
✔
✘
✘
PIVOTE ALEATORIO
En vez de meternos a calculaciones como estimar la mediana de los datos para asegurar que la división sea “balanceada”, simplemente elegimos el pivote al azar.
En la práctica esto implica que uso de números pseudoaleatorios generados por computadora.
Se puede demostrar que si el pivote está seleccionado aleatoriamente entre los datos, el tiempo esperado será .O(n log n)
LÓGICA BOOLEANA CNF
Átomo: una variable binaria que puede tomar el valor “verdad” o “falso”.
Literal: un átomo , posiblemente negado: .
Cláusula: un conjunto de literales combinados por el operador “o” .
Expresión: un conjunto de cláusulas combinados por el operador “y” .
a ¬a
!
!
MAX3SAT
Instancia: una expresión booleana (en CNF) con tres literales por cláusula.
Pregunta: ¿cuántas cláusulas una asignación de valores de verdad puede satisfacer por máximo?
!
MAX3SAT
Instancia: una expresión booleana (en CNF) con tres literales por cláusula.
Pregunta: ¿cuántas cláusulas una asignación de valores de verdad puede satisfacer por máximo?
!
! = (a ! ¬b ! c) " (¬a ! ¬c ! d) " . . . " (¬e ! f ! ¬g)
MAX3SAT
Instancia: una expresión booleana (en CNF) con tres literales por cláusula.
Pregunta: ¿cuántas cláusulas una asignación de valores de verdad puede satisfacer por máximo?
!
! = (a ! ¬b ! c) " (¬a ! ¬c ! d) " . . . " (¬e ! f ! ¬g)
Resolver esto exactamente es NP-duro (o sea, toma mucho tiempo en el peor caso).
APROXIMACIÓN
Simplificando la situación, podemos llegar a una solución aproximada para una expresión con cláusulas.
Si asignamos los valores de verdad a los átomos de una maneta aleatoria, cada literal tiene probabilidad de ser verdadera.
Cada cláusula contiene tres literales; son ocho combinaciones.
Para que se satisfaga la cláusula, basta con tener un literal que evalua a verdad. Solamente un caso de ocho no lo tiene.
La probabilidad de satisfacer una claúsula es .
Si las cláusulas son independientes, el número esperado de cláusulas satisfachas es .
1/2
7/8
n
7n/8
MÉTODOS HEURÍSTICOS
En situaciones donde métodos exactos toman demasiado tiempo y no es indispensable contar con la solución exacta, usamos heurísticas.
Heurísticas son algoritmos que “adivinan” un candidato inicial de solución y lo mejoran iterativamente hasta que su calidad sea satisfactoria o cuando el tiempo permitido se acaba.
La iteración, igual como la generación del candidato inicial, suelen incorporar elementos aleatorizados.
CONCLUSIONES
El no deteminismo ayuda a mejorar la eficiencia de algunos algoritmos exactos y provee aproximaciones eficientes para problemas difíciles de resolver que no cuentan con algoritmos exactos eficientes.
En un algoritmo aleatorizado, las medidas de interés son el tiempo esperado de ejecucición y la calidad esperada de la solución obtenida.
Su punto débil puede ser el generador de números pseudoaleatorios que nunca alcanzará aleatoridad perfecta.
INFORMACIÓN ADICIONAL
Recomiendo el libro de Mitzenmacher y Upfal (2005).
Para dudas y preguntas: elisa@yalma.fime.uanl.mx
Ofrecemos una maestría y un doctorado en Ingeniería de Sistemas en la UANL; también recibimos cada año alumnos de verano científico.
¡Gracias por su atención!