temas integradores algoritmos eficientes para una … · temas integradores diseño de algoritmos...
TRANSCRIPT
Temas integradoresDiseño de algoritmos
Algoritmos de aproximación, aleatorizados & heurísticos
Diseño de algoritmos
! Las mismas ideas buenas sirven para desarrollar algoritmos eficientes para una gran variedad de problemas
! Por eso es útil estudiar las estratégias clásicas del diseño algorítmico para no tener que reinventar la rueda
Dividir y conquistar
! Divide el problema a uno o más subproblemas (recursivamente)
! Resuelve a los subproblemas cuando llegan a ser suficientemente fáciles (pequeños)
! Combina sus soluciones para obtener la solución al problema original
Algoritmo euclideano
! Ejemplo clásico donde hay un sólo subproblema! Encuentra el máximo común divisor de dos
números enteros! Opera a base de la operación módulo
! c = a % b! Muy utilizado en criptografía
Ejemplo simplegcd(56, 35) = 756 (mod 35) = 2135 (mod 21) = 1421 (mod 14) = 7 14 (mod 7) = 0
7 = 21 - 14= 21 - (35 - 21)= 2 x 21 - 35 = 2 (56 - 35) - 35= 2 x 56 - 2 x 35 - 35= 2 x 56 - 3 x 35
⇒ 2× 56− 3× 357
= 1 =7× (. . .)
7donde (. . .) ≡ 1
Ejemplomayor
a = cb + d b d = a % b
1234567890 54321 1452354321 14523 1075214523 10752 377110752 3771 32103771 3210 5613210 561 405561 405 156405 156 93156 93 6393 63 3063 30 330 3 0
Programación dinámica
! También opera a través de subproblemas
! Sus soluciones parciales se almacenan para “reciclar” y combinar entre ellos, típicamente usando alguna estructura de datos
! Suelen ser arreglos
Distancia de edición! Una medida de similitud para cadenas de símbolos! Mide la cantidad de cambios que se requiere para
convertir una cadena a la otra! Añadir, eliminar o cambiar un símbolo! Se puede asignar costos a los tipos de operaciones
Distancia de edición
La distancia de edicion (inglés: edit distance) es unamedida de similitud de sucesiones de símbolos (o sea,palabras formadas por un alfabeto).Se define como el numero mınimo de operaciones deedicion que uno necesita aplicar a palabra P para llegar ala palabra Q.
dist (P,Q) = dist (Q,P )
dist (P, P ) = 0
Programacion dinamica– p. 14
Desigualdad de triángulo
dist (P,Q) ! dist (P,R) + dist (R,Q)
En el caso básico aplica, pero existen variaciones de lamedida que no lo cumplen.
Programacion dinamica– p. 16
Desigualdad de triángulo
Pseudocódigo
DP: inicialización
procedure editdist(P = [p1, p2, . . . , pk], Q = [q1, q2, . . . , q!)for i ! [0, k]
dist (i, 0) := i
for j ! [0, !]
dist (0, j) := j
. . .
Programacion dinamica– p. 17
DP: Calculación
procedure editdist(P = [p1, p2, . . . , pk], Q = [q1, q1, . . . , q!). . .
for i ! [1, k]
for j ! [1, !]
if pi = qj : c := 0;else : c := 1;del := dist (i " 1, j) + 1;ins := dist (i, j " 1) + 1;rep := dist (i " 1, j " 1) + c;dist (i, j) := mın {del, ins, rep};
return dist (k, !);
Programacion dinamica– p. 18
D I F I C I L
0 1 2 3 4 5 6 7
F 1 1 2 2 3 4 5 6
A 2 2 2 3 3 4 5 6
C 3 3 3 3 4 3 4 5
I 4 4 3 4 3 4 3 4
L 5 5 4 4 4 4 4 3
Ejemplo
Manipulación de textos! Similitud y búsqueda de patrones
! Muchos algoritmos famosos! Boyer-Moore! Knuth-Morris-Pratt
! Compresión de datos ! Archivos .zip, etc.
! Bioinformática
! Manipulación de datos biológicos y químicos con métodos algorítmicos
! Alineación de secuencias genéticas
Algoritmos de línea de barrerEjemplo
Lınea de barrer– p. 7
Algoritmo ingenuo
Procesar cada uno de los n(n ! 1) = ! (n2) pares desegmentos si " S y sj " S tal que i #= j y computa suintersección.El el peor caso, esto es el comportamiento óptimo: si todoslos segmentos se intersectan, habrá que calcular todas lasintersecciones en cualquier caso y solamente imprimir lalista de las instrucciones ya toma ! (n2) tiempo.
Lınea de barrer– p. 8
Instancias típicas
Sin embargo, en una instancia promedia o típica, elnúmero de puntos de intersección k es mucho menor quen(n ! 1).El algoritmo mejor imaginable tuviera complejidadasintótica O (n + k), porque se necesita tiempo O (n) paraleer la entrada y tiempo O (k) para imprimir la salida.Ahora veremos un algoritmo de línea de barrer que correen tiempo O ((n + k) log n).
Lınea de barrer– p. 9
Diagramas de Voronoi
http://www.cs.cornell.edu/home/chew/Delaunay.htmlhttp://www.diku.dk/hjemmesider/studerende/duff/Fortune/
Algoritmos de aproximación! A veces no es necesario o práctico calcular la solución
exacta a un problema
! Posiblemente por el tiempo computacional
! También es posible que ni los datos de entrada son exactos
! Lo importante es llegar a conocer qué tan lejana al óptimo exacto puede ser en el peor caso la solución aproximada
Factor de aproximación! Análisis formal de la calidad de la solución
! Medida de la diferencia entre la solución aproximada y la solución óptima
! Se mide en términos multiplicativos
! Su valor extremo es la tasa de aproximación
Factor de aproximación
Un algoritmo de aproximación bien diseñado cuenta conun analisis formal que muestra que la diferenciaentre su solucion y la solucion optima es de unfactor constante.Este factor se llama el factor de aproximacion.
< 1 para maximización
> 1 para minimización
Depende de la aplicación qué tan cerca debería ser la soluciónaproximada a la solución óptima.
Algoritmos de aproximacion– p. 4
Problema de viajanteAlgoritmo de aproximación
1. Construye un árbol de expansión mínimo en tiempoO (m log n).
2. Elige un vértice de inicio cualquiera v.3. Recorre el árbol con DFS en tiempo O (m + n) e
imprime cada vértice a la primera visita (o sea, enpreorden).
4. Imprime v en tiempo O (1).
Algoritmos de aproximacion– p. 13
Entrada: un grafo completo ponderado con pesos no negativos que respetan la desigualdad de triángulo
Cobertura con vértices! Encuentra un subconjunto S de vértices en un grafo G = (V,
E) así que la cardinalidad de S sea mínima y que cada arista (u, v) en E tenga por lo menos un punto final suyo incluido en S
! Problema de optimización NP-duro
! Muy relacionado al problema de acoplamiento maximal
! En ese problema se elige un conjunto máximo de aristas así que ningún punto final se repite y que no exista ninguna arista que se le pueda añadir sin violar esta regla
Algoritmo de aproximación
¡Funciona ambos para cubierto mínimo y acoplamiento maximal!
S = conjunto vacíomientras E no es vació elige (al azar) una arista (u, v) en E añade los vértices u y v al conjunto S elimina de E todas las aristas incidentes a u o v
! La selección de aristas utilizadas define un acoplamiento maximal M! Fijarse en la diferencia entre maximal (no se puede crecer) y máximo (no existe ninguno mayor)
! Si una arista no estuviera en M, se pudiera añadir y M ya no estuviera maximal
! La cardinalidad obtenida es por máximo el doble de su valor óptimo! Una cubierta debe por definición cubrir cada arista en M! En el caso ideal, únicamente uno de sus puntos finales se incluye! Esto crearía un cubierto con la misma cardinalidad que M! El óptimo debe tener por lo menos esta cardinalidad ideal! El algoritmo de aproximación elige ambos puntos finales! La cardinalidad es entonces
Análisis
|S| = 2|M |
Probabilidad
! Intuición: la &ecuencia 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
Supongamos que cada salida tiene asociado un valor numérico y denotamos este valor por .
El valor esperado de un experimento es
Valor esperado
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
Ordenamiento rápidoEl 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
3.1. entre los a la izquierda
3.2. entre los a la derecha
! 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 .
Elección de pivote
O(n log n)
O(n2)
Peor y mejor caso de quicksort
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
Complejidad cuadrática vs. log-lineal
Pivotes malos y buenos
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á log-lineal.
! 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
ϕ
ϕ = (a ∨ ¬b ∨ c) ∧ (¬a ∨ ¬c ∨ d) ∧ . . . ∧ (¬e ∨ f ∨ ¬g)
Resolver esto exactamente es NP-duro (o sea, toma mucho tiempo en el peor caso).
! 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 .
Aproximación
1/2
7/8
n
7n/8
! Algoritmos con una probabilidad no cero de fallar (y una probabilidad no cero de dar el resultado correcto) se llaman algoritmos Monte Carlo (MC)! Error bilateral: la probabilidad de error es no cero ambos para
el caso “sí” y para el caso “no”
! Error unilateral: únicamente se equivoca en uno de los dos casos
! Algoritmos aleatorizados que nunca fallan se llaman algoritmos Las Vegas
! A un algoritmo MC que sabe detectar éxito o fracaso se puede convertir en un algoritmo Las Vegas
! Repetirlo una cantidad no limitada de veces
Complejidad aleatorizadaComplejidad computacional: RP
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
Complejidad computacional: ZPP
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
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
Complejidad computacional: PPPP
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
Complejidad computacional: BPPBPP
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
Ejemplo: MINCUT! Para multigrafos (generalización de grafos simples)! Corte = una agrupación de los vértices V a dos conjuntos B
y C que ambos sean subgrafos conexos G
! Capacidad del corte = número de aristas que lo cruzan
! Dado: un multigrafo G
! Pregunta: hay un corte con capacidad menor o igual a k! Optimización: minimizar la capacidad de corte
! El problema de decisión pertenece a P
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.=" MINCUT # ! (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.=" MINCUT # ! (n2m)
Con unos trucos: mincut # O (nm log(n2/m))
Grafos densos: m # O (n2)
Algoritmos aleatorizados– p. 20
vs.
Idea base: contracciónContracció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, w}para todo s /! {u, v}.
Algoritmos aleatorizados– p. 21
EjemploEjemplo
Algoritmos aleatorizados– p. 22
Ejemplo
Algoritmos aleatorizados– p. 22
Ejemplo AlgoritmoContracció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ónImplementació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
Estructuras unir-encontrar
1
2
3
5
4
0
67
9
8
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 90 1 2 3 1 5 6 7 8 90 1 2 3 1 5 6 7 8 80 1 2 2 1 5 6 7 8 80 1 2 2 1 5 6 7 1 10 1 2 2 1 5 1 7 1 10 0 2 2 0 5 0 7 0 00 0 0 0 0 5 0 7 0 00 0 0 0 0 5 0 0 0 00 0 0 0 0 0 0 0 0 0
MST
Análisis parcial de MINCUTAná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
Algoritmos 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.
Búsqueda local! Algoritmos voraces
! Basados en vecindarios
! Construcción de una solución inicial (semilla)! Escalada de cerro (hill-climbing)
! A un vecino que mejora (al azar)! Al mejor vecino
Ejemplo con vecindario unidimensional
Minimizar la función objetivo
Búsquedas sofisticadas! Mecanismos populares para escapar de óptimos locales
! Recuerdan la mejor solución visitada en toda la búsqueda! Búsqueda tabú
! Mantener un listado de soluciones recientemente visitadas! Ir al mejor vecino que no esté en la lista tabú
! Recocido simulado! Permitir la exploración de vecinos de peor calidad! La probabilidad de ir a un vecino peor va disminuyendo
mientras el algoritmo avanza! En función de la diferencia de calidad
Algoritmos evolutivos
! Algoritmos genéticos
! Codificación (binaria) + cruzamientos + mutaciones por varias generaciones
! Optimización por enjambre de partículas! Búsqueda local “paralelo”
! Algoritmos de colonias de hormigas / abejas! Búsqueda local cooperativo distribuido
! Muchísimas unidades de aprendizaje que permiten aplicar este conocimiento! Matemáticas
! Discretas! Estocásticas
! Probabilidad! Experimentos! Simulación
! Optimización! Programación
! Sistemas adaptativos, dinámicos, distribuidos, paralelos
! Sistemas operativos! Telecomunicaciones! Cómputo integrado
! Prácticamente todas las optativas
! Trabajo
! Desarrollo
! Investigación
! Posgrados
! Maestrías
! Doctorados
¿Qué sigue?