Download - algoritmosIII2do2007
-
Algoritmos y Estructuras de Datos III
2do cuatrimestre 2007
Irene Loiseau
(transparencias preparadas con la colaboracin deMin Chih Lin)
-
Observaciones y advertencias:
Estas transparencias pueden cambiar un poco antes o despus de la clase correspondiente a cada tema.
La presentacin NO INCLUYE las demostraciones dadas en clase. En la mayora de los casos se incluyen slo los enunciados de los teoremas.
Tambin puede haber algn ejemplo o resultado que se de en clase y no est las transparencias.
Parte de los temas del prctico 7 (PERT_ CPM) todava no estn incluidos en la presentacin.
-
PROGRAMA
1. ALGORITMOS: Definicin de algoritmo. Modelos de computacin: modelo RAM, Mquina de Turing.
Complejidad, definicin, complejidad en el peor caso, en el caso promedio. Algoritmos de tiempo polinomial y no polinomial. Lmite inferior. Ejemplo: anlisis de algoritmos de ordenamiento. Algortimos recursivos. Anlisis de la complejidad de algoritmos recursivos.
Tcnicas de diseo de algoritmos: dividir y conquistar, backtracking, algoritmos golosos, programacin dinmica.
Algoritmos probabilsticos. Algoritmos aproximados Algoritmos heursticos: ejemplos. Metaheursticas. Nociones de evaluacin de heursticas.
2. GRAFOS: Definiciones bsicas. Adyacencia, grado de un nodo, isomorfismos, caminos, conexin, etc.
Grafos eulerianos y hamiltonianos. Grafos bipartitos. Arboles: caracterizacin, rboles orientados, rbol generador. Enumeracin. Planaridad. Coloreo. Nmero cromtico. Matching, conjunto independiente, recubrimiento. Recubrimiento de aristas y vrtices.
-
3. ALGORITMOS EN GRAFOS Y APLICACIONES:Representacin de un grafo en la computadora: matrices de incidencia y adyacencia, listas.Algoritmos de bsqueda en grafos: BFS, DFS, A*. Mnimo rbol generador, algoritmos de Prim
y Kruskal. Arboles ordenados: cdigos unvocamente descifrables. Algoritmos para deteccin de circuitos. Algoritmos para encontrar el camino mnimo en un grafo: Dijkstra, Ford, Floyd, Dantzig. Planificacin de procesos: PERT/CPM.
. Heursticas para el problema del viajante de comercio. Algoritmos para determinar si un grafo es planar. Algoritmos para coloreo de grafos.
Algoritmos para encontrar el flujo mximo en una red: Ford y Fulkerson. Matching: algoritmos para correspondencias mximas en grafos bipartitos. Otras aplicaciones.
4. PROBLEMAS NP-COMPLETOS:Problemas tratables e intratables. Problemas de decisin. P y NP. Maquinas de Turing no
determinsticas. Problemas NP-completos. Relacin entre P y NP. Problemas de grafos NP-completos: coloreo de grafos, grafos hamiltonianos, recubrimiento mnimo de las aristas, corte mximo, etc.
-
BIBLIOGRAFIA
BIBLIOGRAFA BSICA :
Brassard,G., Bratley,P.Fundamental of Algorithmics, Prentice Hall,1996. Cormen, T.,Leiserson, C.,Rivest,R.,Stein, C.,Introduction to Algorithms, The
MIT Press, McGraw-Hill,2001. Garey M.R. and Johnson D.S.: Computers and intractability: a guide to the
theory of NP- Completeness, W. Freeman and Co., 1979. Gross,J., and Yellen, J. ,Graph theory and its applications, CRC, 1999 Harary F., Graph theory, Addison-Wesley, 1969.
BIBLIOGRAFA DE CONSULTA : ver en la pgina WEB de la materia y en el el archivo de las prcticas.
-
ALGORITMOS
Qu es un algoritmo ? Qu es un buen algoritmo? Dados dos algoritmos para resolver un mismo problema, cul
es mejor? Cundo un problema est bien resuelto? Cmo se hace para inventar un nuevo algoritmo?
-
Qu es un algoritmo?
Nocin informal:
Un algoritmo es una sucesin finita de instrucciones bien definidas tal que:
i) No hay ambigedad en las instrucciones. ii) Despus de ejecutar una instruccin no hay ambigedad respecto de
cual es la instruccin que debe ejecutarse a continuacin. iii) Despus de un nmero finito de instrucciones ejecutadas se llega
siempre a la instruccin STOP (Un algoritmo siempre para).
-
PROBLEMA
instancia de un problema datos de entrada de una instancia (E) solucin (S)
ALGORITMO:
tcnica para la resolucin de un problema funcin f tal que f (E) = S
-
Problema de Collatz
Paso 1: z nmero entero positivoPaso 2: mientras z 1 hacer Paso 3: Si z es par poner z = : z / 2 En caso contrario poner z =: 3 z +1
Paso 4: parar =====================================es esto un algoritmo?
-
Cunto tarda un algoritmo en resolver un problema?
Cundo un algoritmo que resuelve un problema es mejor que otro que resuelve el mismo problema?
Complejidad Computacional
-
Complejidad
La complejidad de un algoritmo es una funcin que calcula el tiempo de ejecucin en funcin del tamao de la entrada de un problema.
Historia
Complejidad en el peor caso (es siempre significativo el peor caso?)
Complejidad en el caso promedio (porqu no usamos este enfoque siempre?)
-
Cmo medir el tiempo de ejecucin en funcin del tamao de la entrada de los datos del problema?
MODELOS DE COMPUTACION
RAM MAQUINA DE TURING
-
RANDOM ACCESS MACHINE
Es el modelo que usamos implcitamente en la prctica para evaluar la complejidad de un algoritmo.
================================================== unidad de memoria unidad de entrada procesador unidad de salida conjunto de instrucciones ====================================================
Un programa RAM es una secuencia finita de estas instrucciones
-
Esquema de una mquina RAM
memoria
entrada procesadorSalida
-
En este modelo suponemos que:
La unidad es una cinta de cuadrados en cada uno de los cuales se puede almacenar un entero.
La memorias es una sucecin de registros, cada uno de los cuales puede almacenar un entero de tamao arbitrario. Los clculos se hacen en el primero de ellos, r0.
El programa no se almacena en en la memoria y no se modifica a si mismo.
El conjunto de instrucciones es similar al de las computadoras reales
Este modelo sirve para modelar situacines donde tenemos memoria suficiente para almacenar el problema y donde los enteros que se usan en los clculos entran en una palabra.
-
Ejemplo( sacado del libro de Aho, Hopcroft y Ullmann)
Ejemplo de tabla de instrucciones de una mquina RAM
LOAD operadorSTORE operadorADD operadorSUB operadorMULT operadorDIV operadorREAD operadorWRITE operadorJUMP labelJGTZ labelJZERO labelHALT
-
Ejemplo de un programa para calcula n n en esta mquina RAM ===================== READ 1 leer r1 LOAD 1 si r1 0 entonces write 0 JGTZ pos WRITE = 0 JUMP endifpos LOAD 1 r2 -- r1 STORE 2 LOAD 1 r3 -- r1 -1 . SUB = 1 STORE 3 while LOAD 3 mientras r3 > 0 hacer . JGTZ continue JUMP endwhile continue LOAD 2 r2 -- r2 * r1 . MULT 1 STORE 2 LOAD 3 r2 -- r2 * r1 SUB = 1 STORE 3 JUMP whileendwhile WRITE 2 write r2endif HALT========================================
-
Cmo calculamos la complejidad de un algoritmo con este modelo?
tj : tiempo de ejecucin de la instruccin j.T: tiempo de ejecucin de un programa que ejecuta nj instrucciones de
tipo j.
T = j nj tj
Si suponemos que todos los tj son iguales tenemos
T = j nj
----------------------------------------------------------------------------Esta es el modelo que usamos implcitamente cuando calculamos
la complejidad de un algoritmo en la prctica
-
Mquina de Turing (determinstica)
Componentes de una mquina de Turing=========================================================== Cinta infinita dividida en celdas iguales que pueden contener un nico smbolo
de un alfabeto finito T. Cabeza de lectura escritura que apunta a una de las celdas. lista finita de estados posibles {qi}. Hay al menos un estado final. operaciones: i) lectura del smbolo ti inscripto en la celda sealada por la cabeza. ii) guardar en esta celda el smbolo tf determinado por qi. iii) transicin al estado qf determinado por ti y qi . iv) movimiento de la cabeza de lectura/escritura a izquierda o derecha. V) inicio de un nuevo ciclo,. Para cuando llega a un estado final.==========================================================
-
Un programa correspondiente a esta mquina de Turing es un conjunto finito de quintuplas (qi,ti,qf, tf, m).
La instruccin (qi,ti,qf, tf, m) se interpreta como:
si la mquina est en el estado qi y lee en la posicin actual de la cabeza de lectora el smbolo del alfabeto ti , entonces escribe en dicha posicin el smbolo ts , pasa al estado qs y se mueve a la izquierda o a la derecha segn el valor de m sea -1 +1 .
-
Ejemplo
Mquina de Turing para resolver el problema de determinar si dados N y M con M > 1, N es divisible por M.
Alfabeto T = { A, B, 0, 1, 2 } Se almacenan en la cinta M y N codificados en base 1, separados
por el smbolo B y con el smbolo A marcando el fin del nmero. Estado inicial: q0 Estados posibles Q = {q0, q1 ,q2,qs, qn} Estados finales: qs, qn
-
Programa
Instrucciones
(q0, A,, q2 , A , + 1) (q1, A,, qn , * , *) (q2, A,, qs , * , *)(q0, B,, q0 , B , - 1) (q1, B,, q1 , B , + 1) (q2, B,, q2 , B , + 1)(q0, 0 , q0 , 0 , - 1) (q1, 0,, q1 , 0 , + 1) (q2, 0, q2 , 0 , + 1)(q0, 1 , q1 , 2 , + 1) (q1, 1 , q0 , 0 , - 1) (q2, 1 , q0 , 1 , -1)(q0, 2, q0 , 2 , -1) (q1, 2 , q1 , 2 , + 1) (q2, 2, q2 , 1 , + 1)
Cmo funciona esto?. Usar esta mquina para decidir si 5 es divisible por 3.
-
Cmo se calcula la complejidad de un algoritmo representado por una mquina de Turing?.
Formalmente un algoritmo es un objeto asociado a una mquina de Turing que resuelve un determinado problema. La complejidad del mismo debera ser calculada en funcin del mismo.
En la prctica sin embargo usaremos una nocin un poco menos formal de algoritmo y tambin para determinar la complejidad de un algoritmo, que se parece ms al modelo RAM.
Desde el punto de vista prctico ambos enfoques han mostrado ser equivalentes.
Determinaremos la complejidad contando la cantidad de operaciones bsicas de alto nivel que realiza el algoritmo, en funcin del tamao del problema.
Es correcto esto?. Puede ser peligroso?
-
Repasando notaciones
Dadas dos funciones f y g : N+ R decimos que:
f(n) = O (g(n)) si c> 0 y n0 N tal que f(n) c g(n) n > n0 . f(n) = (g(n)) si c> 0 y n0 N tal que f(n) > c g(n) n > n0 . f(n) = (g(n)) si c,c> 0 y n0 N tal que c g(n) f(n) c g(n) n > n0
Si f(n) = O (g(n)) se dice que f es de orden g(n).
-
Tamao de la entrada de un problema
Nmero de smbolos de un alfabeto finito necesarios para codificar todos los datos de un problema.
El tamao de la entrada de un problema depende de la base o alfabeto elegidos.
para almacenar un entero positivo N en base 2 se necesitan L =log2(N+1) dgitos binarios. en una base b cualquiera se necesitan L =logb(N+1) si a y b 1 entonces logb N = loga N / loga b
qu implica esto desde el punto de vista de la complejidad de un algoritmo?
-
Podemos considerar distintos modelos para determinar la complejidad en funcin del tamao de la entrada del problema.
Modelo uniforme: suponemos que los valores a almacenar estn acotados.
Modelo logartmico: consideramos la representacin binaria de los nmeros a almacenar, o sea medimos el tamao de la entrada en bits.
Qu consecuencias puede tener usar uno u otro modelo?
-
Cundo decimos que un algoritmo es bueno?
Armemos esta tabla..... supongamos que tenemos algoritmos con las siguientes complejidades y los corremos en la misma mquina(los tiempos estn dados en segundos )
10 20 30 40 50 60 n 0.00001 0.00002 0.00003 0.00004 0.00005 0.00006 n2 n3 n5 2n 3n
-
La tabla queda as..(los tiempos estn dados en segundos salvo cuando dice otra cosa)
10 20 30 40 50 60 n 0.00001 0.00002 0.00003 0.00004 0.00005 0.00006 n2 0.0001 0.0004 0.0009 0.0016 90.0025 0.0036 n3 0.001 0.008 0.027 0.064 0.125 0.216 n5 0.1 3.2 24.3 1.7 min 5.2 min 13.0 2n 0.001 1.0 17.9min 12.7das 35.6 aos 366 siglos 3n 0.59 58 min 6.5aos 3855siglos 2 E+8 siglos 1.3 E+13 siglos
-
Los datos de la tabla anterior corresponden a una mquina muy vieja (datos del libro de Garey y Johnson de 1979).
Qu pasa si tenemos una mquina 1000 veces ms rpida?. Un milln de veces ms rpida?. Cul sera el tamao del problema que podemos resolver en una hora comparado con el problema que podemos resolver ahora?.
actual computadora 1000 veces mas rpida n N1 1000 N1 n2 N2 31.6 N2 n3 N3 10 N3 n5 N4 3.98 N4 2n N5 N5 + 9.97 3n N6 N6 + 6.29
Qu pasara si tuviramos una computadora 1 milln de veces ms rpida?
-
Cundo diremos entonces que un algoritmo es bueno?.
Cundo un algoritmo es suficientemente eficiente para ser usado en la prctica?
=============================POLINOMIAL = buenoEXPONENCIAL = malo=============================
-
Qu pasa si tengo complejidades como las siguientes?:
n 80
1.001n
esto no ocurre en la prctica
-
Puede ocurrir que un algoritmo sea malo en el peor caso y bueno en la prctica?.
Hay muy pocos casos.
Ejemplo clsico: mtodo simplex para problemas de programacin lineal.En el peor caso es exponencial pero en la prctica el tiempo de ejecucin
es generalmente O(m3) donde m es el nmero de ecuaciones del problema de programacin lineal (es un mtodo MUY usado en la industria y los servicios para resolver problemas de optimizacindesde hace 50 aos)
-
Cundo decimos que un problema est computacionalmente bien resuelto?
Cundo hay un algoritmo polinomial para resolverlo.
Como veremos ms adelante hay problemas para los cuales no sabemos si existe o no un algoritmo polinomial para resolverlos. Saber si una gran familia de estos problemas tiene solucin polinomial o no es el problema abierto ms importante de teora de la computacin.......
continuar en el ltimo captulo del curso.......
-
Ejemplos de algunos algoritmos conocidos
Calculo de determinantes Sea una matriz M = (aij ) y sea Mij la submatriz de M que se
obtiene sacando de M la fila i y la columna j.
Frmula recursiva para calcular el determinante:(desarrollo por la primera fila)
det (M) = j (- 1) j+1 a ij det (M 1j)
-
Complejidad de este mtodo?.
Se puede calcular usando la frmula recursiva que se deduce de la versin recursiva que dimos del algoritmo:
t(n) = n t(n - 1) + O (n)
Complejidad O(n!)
Hay mtodos ms eficientes de calcular el determinante de una matriz?.
SI (triangular la matriz por el mtodo de Gauss y calcular el producto de la diagonal)
Est este problema bien resuelto computacionalmente?.
-
Bsqueda secuencial
Datos: n, b, (a1,a2,.............an)
Paso 1: para i = 1,n hacer if b = ai pararPaso 2 : parar
=========================
Complejidad?
-
Bsqueda Binaria
Function Bin (T,x)si n = 0 o x < T entonces returni 1j nmientras i < j hacer k (i+j+1)/2 si x < T (k) entonces j k-1 sino i kreturn i =========================Complejidad?
-
Algoritmos de ordenamiento
Algoritmo de burbujeoDatos: (a1,a2, ...................an)Paso 0: poner k = nPaso 1: mientras k 1 hacer Paso 2: poner i = 1 Paso 3: mientras i k hacer Paso 4 : si ai > ai+1 cambiar ai con ai+1 Paso 5: poner i = i + 1 Paso 6 : poner k = k -1Paso 7 : parar=========================Complejidad?
-
Heap sort
Heap: rbol binario casi completo, donde cada nodo tiene asignado un valor de forma que el valor de un nodo es mejor (mayor) que el de sus hijos.
Puede ser representado por un arreglo T en el cual los nodos del nivel k se guardan en las posiciones
T [2k], T [2k+1], ................T [2k+1-1]
-
ejemplo
T [1]
T [2] T [3]
T [4] T [5] T [6] T [7]
T [8] T [9] T [10]
-
Ordenar T = [1, 6, 9, 2, 7, 5, 2, 7, 4, 10] usando Heapsort.
1
6 9
2 7 5 2
7 104
-
Algoritmo Make-Heap
Dado un arreglo T los siguientes procedimientos nos permiten ordenarlo:
procedure sift-down(T [1..n], i)(baja el nodo i hasta que T [1..n] vuelve a ser un heap, suponiendo que
T sea suficientemente grande para ser un heap (caso base?)k irepetir mientras j k j k if 2j n y T [2j ] > T [k ] entonces k 2j if 2j < n y T [2j +1 ] > T [k ] entonces k 2j + 1 intercambiar T [j ] y T [k ] fin
-
procedure make-heap (T [1..n]) (arma el heap)para i = n /2 ....1 hacer sift-down (T,i) fin
procedure heapsort ((T [1..n]) (ordena T)make-heap (T)para i = n , 2 hacer intercambiar T [1] y T [i] sift-down(T [1..i-1], 1)fin
-
Complejidad de make-heap
Cmo calcular t(k), complejidad de armar un heap de altura k?
Podemos plantear la siguiente formula recursiva para la complejidad:
t(k) = 2 t (k-1) + O (k)entonces
t(k) = O (2k)
Cmo un heap de n elementos tiene altura log n entonces puede ser construido en en O(2 log n ) pasos o sea en tiempo lineal.
Cul es la complejidad de Heapsort?
-
Lmite inferior para la complejidad de un algoritmo
Cundo se puede obtener? Importancia
-
EJEMPLO: algoritmos de ordenamiento basados en comparaciones. Se pueden modelar por un rbol binario de decisin. Los estados finales del algoritmos estn representados en las hojas.
Entonces nro de hojas n! Como el rbol es binario, nro de hojas 2h (h altural del rbol) y 2h n! . Entonces
h log2 (n!) = log2 (n (n-1)....2. 1) > log2 (n (n-1)....n/2) > log2 n /2 (n/2) =
= n/2 (log2 n - 1) ) = (n log2 n )
Conclusin: HEAPSORT es ptimo dentro de este tipo de algoritmos.
-
Tcnicas de diseo de algoritmos
Algoritmos golosos Dividir y conquistar Recursividad Programacin dinmica Backtracking Algoritmos Probabilsticos
-
Algoritmos Golosos
Se usan principalmente para problemas de optimizacin.
Componentes:
Lista o conjunto de candidatos Conjunto de candidatos ya usados Funcin que verifica si un conjunto de candidatos da una solucin al
problema. Funcin que verifica si un conjunto de candidatos es hasta el momento
factible. Funcin de seleccin Funcin objetivo
-
---------------------------------------------------------------------------------Funcin GREEDY (C) {C es el conjunto de candidatos}S ------ Mientras NOT solucin(S) y C hacer x -------------------- elemento que maximice select (x) C
-
Minimizar el tiempo de espera en un sistema
Un servidor tiene n clientes para atender. Se sabe que el tiempo requerido para atender cada cliente i es ti. Se quiere minimizar
T = i (tiempo que i est en el sistema)
El algoritmo goloso que atiende al cliente que requiere el menor tiempo de atencin entre los que an estn en la cola resuelve el problema. (hay que demostrarlo)
-
Supongamos que I = ( i1,i2,......in) es una permutacin de los enteros {1,2....n}. Si los clientes son atendidos en el orden I entonces
T = ti1 + (ti1+ ti2) + (ti1 + ti2 + ti3) + ......
= k (n-k+1) tik
Usando esta expresin podemos probar que el algoritmo goloso es correcto..
-
Supongamos que en I hay dos enteros a y b con a < b y tal que tia > tib. O sea el cliente a es atendido antes que el b, a pesar de que el primero
requiere mas tiempo de servicio. Si intercambiamos cambiamos las posiciones de a y b tenemos un nuevo orden I para el cual
T (I) = (n-a + 1) tib +(n-b+1) tia + ka,b (n-k+1) tik
Entonces T(I) T ( I) = (n-a + 1) (tia - tib ) +(n-b+1) (tib - tia )=
= (b-a) (tia - tib ) > 0
Vemos que podemos seguir mejorando el valor de T intercambiando el orden de los clientes hasta obtener el orden ptimo dado por el algoritmo goloso.
==================================Cul es la complejidad de este algoritmo?
-
Planificacin de tareasHay n tareas que deben ser ejecutadas cada una de las cuales
requiere una unidad de tiempo. En cada momento se puede ejecutar una sola tarea.
Cada tarea i produce un beneficios gi y debe ser ejecutada antes del tiempo di.
Ejemplo con n = 4
1212di30151050gi4321i
-
Algoritmo goloso para este problema
En cada paso elegir para ejecutar la tarea an no realizada que produce el mayor beneficio, siempre y cuando el conjunto de tareas resultante sea factible.
Cmo se ve que un conjunto de tareas es factible?. Cuando hay un ordenamiento de esas tareas que permite
ejecutarlas a todas a tiempo.
-
Lema: sea J un conjunto de tareas y s = (s1, s2,, sk) una permutacin de dichas tareas tal que
ds1 ds2 dskJ es factible si y slo si s tambin lo es.
Dem: obvio. Si J es factible existe al menos una sucesin de los trabajos = (r1, r2,.rk) tal que dri i, para 1 i k. Si fuera s , sea a el menor ndice tal que sa ra y sea b el ndice tal que
rb = sa. Claramente b > a y dra dsa = drb.Entonces el trabajo ra podra ser ejecutado ms tarde en el lugar de rb y
este ltimo en el lugar de ra. Si los cambiamos en tenemos una sucesin factible que tiene un trabajo ms en coincidencia con s. Repitiendo este procedimiento podemos llegar a obtener s y ver entonces que es factible.
-
Lema: Este algoritmo goloso obtiene la solucin ptima para este problema de planificacin de tareas.
Dem: Supongamos que el conjunto I elegido por el algoritmo goloso es distinto de un conjunto J ptimo. Sean SI y Sj dos sucesiones factibles para estos conjuntos.
Hacemos intercambios de modo de obtener dos sucesiones factibles SI y Sj tal que los trabajos comunes en ambas secuencias sean ejecutados en el mismo momento (pueden quedar gaps en alguna de las planificaciones).
-
O sea si tenemos las secuencias
SI p y q x r - - - SJ r s t p u v q w
podemos reordenarlas de la siguiente forma
SI x y - p r - q -
SJ u s t p r v q w
(En SI y SJ se siguen respetando los tiempos de entrega di)
-
Como hemos supuesto que los conjuntos I y J son distintos, consideremos ahora un momento en el cual la tarea que est programada en SI es distinta de la programada en Sj :
Si una tarea a est programada en SI y en Sj hay un gap (la tarea no pertenece a J) entonces J {a} sera mejor que J, absurdo porque J es ptimo.
Si alguna tarea b est programada en Sj y en SI hay un gap entonces I {b} es factible y por lo tanto el algoritmo goloso tendra que haber includo a b y no lo hizo.
-
La ltima posibilidad es que haya una tarea a programada en SI y otra b en Sj. Esto implica que a no aparece en J y b no aparece en I :
- si fuera ga > gb se podra substituir a por b en J y mejorar a J (absurdo porque J era ptimo).
- si fuera fuera gb > ga el algoritmo goloso tendra que haber elegido a b antes de considerar a.
- entonces gb = ga
Por lo tanto SI y Sj tienen programadas en cada momento, o ninguna tarea, la misma tarea o distintas tareas que dan el mismo beneficio. Y entonces como J era ptimo I tambin lo es.
-
Algoritmo goloso(se supone que las tareas estn numeradas de modo que g1 g2 .. gn)-------------------------------------------------------------------Funcin sequence (d[0n])d[0], j[0] --------- 0k, j[1] ------1Para i= 1,n hacer r max ( d(i),r) hacer r = r-1 si d[j [r]] d[i] y d[i] > r entonces para l=k-1, r+1 hacer j[l+1] = j[l] j[r+1] ---------i k ---- k+1Return k, j[1,.k]------------------------------------------------------------------
-
El algoritmo se puede mejorar un poco, cambiando la forma de verificar cuando un conjunto de tareas es factible.
Podemos determinar un conjunto factible de tareas de una forma ms eficiente usando el siguiente lema:
Lema: Un conjunto de tareas es factible si y slo si podemos construir una secuencia factible que incluya todos los trabajos de la siguiente forma: para cada trabajo i J ejecutar i en el momento t, donde t es el mayor entero tal que
0 < t min (n,di) y en el momento t no se ha decidido que trabajo hacer.
Ejercicio: Demostrar este lema. Escribir un algoritmo ms eficiente que el anterior basado en este lema.
-
Problema de la mochila
Quiero decidir cules son los elementos que tengo que elegir para llevar en la mochila para maximizar mi beneficio respetando la restriccin de capacidad de la misma.
Max z =j cj xjsujeto a que
j aj xj bxj N+
b : capacidad de la mochila cj : beneficio de llevar una unidad del elemento jaj : peso del elemento j
b, cj , aj positivos
-
En esta primera versin del problema de la mochila vamos a suponer que podemos llevar a lo sumo un objeto de cada tipo o partes de los mismos, es decir que consideraremos que las variables xj son reales positivas, o sea queremos resolver el siguiente problema:
Max j cj xjsujeto a que
j aj xj b0 xj 1
-
Ejemplo: n = 5, b = 100 y los beneficios y pesos estn dados en la tabla
Posibles ideas para un algoritmo goloso para este problema:
Elegir los objetos en orden decreciente de su beneficio. Elegir los objetos en orden creciente de su peso..
Sirven estas ideas?. Dan el resultado correcto?
4060306620cj
4050203010aj
-
Que pasa si ordenamos los objetos por su relacin peso/beneficio? O sea en orden decreciente de los
cj /aj ?.
Lema: Si los objetos se eligen en el orden decreciente de los valores cj /aj entonces el algoritmo goloso encuentra la solucin ptima al problema de la mochila con variables continuas.
Dem: supongamos que tenemos los elementos ordenados en orden decreciente de su relacin cj /aj . Sea X = (x1,xn) la solucin encontrada por el algoritmo goloso. Si todos los xi son 1 la solucin es ptima. Sino sea j el menor ndice tal que sea xj < 1.
Es claro que xi = 1 para i < j y que xi = 0 para i > j y que ai xi = b
-
Sea V(X) = ci xi el valor de la solucin dada por el algoritmo goloso.
Sea Y = (y1yn) otra solucin cualquiera factible. Se puede ver que ( xi yi ) ai 0
Adems para todo ndice i se verifica que
( xi yi ) ci /ai ( xi yi ) cj /aj entonces
V (X) V ( Y ) = ( xi yi ) ci = ( xi yi ) aici /ai (cj / aj ) ( xi yi ) ai 0
O sea el valor de la solucin determinada por el algoritmo goloso es mejor o igual al valor de cualquier otra solucin.
-
Veamos que ocurre en el caso de que las variables xj tengan que tomar valores enteros (como ocurre en la prctica, es decir cuando no podemos llevar un pedazo de un objeto).
Algoritmo goloso para el problema de la mochila con variables enteras nonegativas:
----------------------------------------------- Ordenar los elementos de forma que cj / aj cj+1 / aj+1
Mientras b 0 hacer xj = b / aj b = b aj xj z = z + cj xj
Parar------------------------------------------------
-
Cuando las variables son enteras este algoritmo goloso no da siempre la solucin ptima para el problema de la mochila.
Ejemplo: tenemos una mochila de tamao 10 y 3 objetos, uno de peso 6 y valor 8, y dos de peso 5 y valor 5.
En el caso de variables enteras el algoritmo goloso que presentamos puede considerarse como una heurstica para resolver el problema.
-
Dividir y conquistarESQUEMA GENERAL:--------------------------------------------------------------------------------Funcin DQ (x) Si x es suficientemente chico o simple entonces return ADHOC(x) Sino, descomponer x en subinstancias x1.xk . Para i=1,k hacer yi = DQ (xi) Combinar las soluciones yi para construir una solucin y para xReturn y--------------------------------------------
Recursividad, Caso Base
-
Ejemplos:
Bsqueda binaria Merge Sort Quick Sort Algoritmo de multiplicacin de Strassen
Cmo calcular la complejidad de estos algoritmos?. Ecuaciones de recurrencia.
-
Algoritmo de multiplicacin de Strassen
Cmo calcular el producto de dos matrices de dos por dos usando menos multiplicaciones que con el mtodo tradicional.
Dadas dos matrices A = a11 a12 y B = b11 b12 a21 a22 b21 b22
podemos poner
-
m1 = (a21 + a 22 a 11 ) (b22 - b 12 + b 11 )m2 = a11 b11m3 = a12 b21m4 = (a 11 a 21 ) (b 22 b 12 ) m5 = (a21 + a 22 ) (b 12 b 11 ) m6 = (a12 - a 21 + a11 a 22 ) b22m7 = a22 ( b11 + b22 - b 12 b 21 )
Entonces el producto AB queda: m2 + m3 m1 + m2 + m5 + m6 m1 + m2 + m4 m7 m1 + m2 + m4 + m5
Este procedimiento requiere 7 multiplicaciones para cacular el producto de A y B (pero ms sumas que el mtodo tradicional!!).
-
Si reemplazamos cada elemento de A y B por una matriz de n x n, las frmulas anteriores nos dan una forma de multiplicar dos 2n X 2n matrices.
A partir de esto tenemos un mtodo recursivo para calcular el producto de matrices con n potencia de 2.
Cmo se calcula para n par, la complejidad t(n) de este algoritmo?.
t(n) = 7 t(n/2) + g(n) con g(n) O(n2)
Se puede demostrar que t(n) (n log 7) y por lo tanto t(n) O (n 2.81). (ejercicio)
Este mtodo se puede generalizar tambin a matrices cuyas dimensiones no sean de la forma 2 n.
-
Backtracking
Tcnica para recorrer sistemticamente todas las posibles configuraciones de un espacio. Puede pensarse tambin que es una tcnica para explorar implcitamente rboles dirigidos (o grafos dirigidos en general pero sin ciclos).
Procedure backtrack (v[1.k]) {v es un vector k-prometedor } si v es una solucin al problema entonces escribir v sino para cada vector k+1-prometedor w tal que w[1k] = v[1k] hacer backtrack (w[1k+1]) ===============================================No necesariamente exploramos todas las ramas del rbol : poda
-
Problema de las 8 reinas
Ubicar 8 reinas en el tablero de ajedrez sin que ninguna amenace a otra.
Cuntas operaciones tenemos que hacer si consideramos todas las combinaciones del tablero tomadas de a 8 y despus vemos cuales sirven?
64 = 442616536 8 Si mejoramos esto usando la representacin (i1, i2, i3 ,i4, i5 ,i6,i7 ,i8 ) donde ij indica que hay una reina en la
columna j y la fila ij y analizamos cuales son factibles o no. cuntas operaciones tendremos?.
8 8 = 16777216 (se encuentra una solucin despus de revisar slo 1299 852 posiciones)
-
Si vemos que dos reinas no pueden estar ni en la misma fila ni en la misma columna vemos que en realidad podemos representar el problema mediante las permutaciones de (1,2,3,4,5,6,7,8). Cuntas operaciones tenemos en este caso?.
8! = 40320 (implementando este algoritmo podemos ver que hay que
revisar 2830 posiciones hasta encontrar una primera solucin)
-
Algoritmo de bactracking
Decimos que un arreglo V de los enteros 1 a 8 es k-prometedor si ninguna de las reinas ubicadas en las posiciones (1, v(1)), (2,v(2)), (3,v(3)),..(k,v(k)), 1 k n amenaza a las otras.
O sea v es k-prometedor si para todo ij entre 1 y k, tenemos que v(i) v(j) {i-j,0,j-i}.
Un vector 8-prometedor es solucin del problema de las 8 reinas.
-
Algoritmo de bactracking
------------------------------------------------------------------------------------Procedimiento Queens (k, col, diag45, diag 135){Try[1,k] es k-prometedor, col = {try [i], 1 i k}diag45 = {try [i]-i +1, 1 i k}diag135 = {try [i] + i - 1, 1 i k}}Si k = 8 entonces {una 8-prometedora solucin es solucin}. Return trySino {explorar las k+1 extensiones de try} Para k=1,8 si j col y j-k diag45 y j+k diag135 entonces try[k+1] --j {try [1,.k+1] es k+1 prometedor} Queens (k+1, col U {j}, diag45 U {j}, diag135 U {j+k} -------------------------------------------------------------------------------------
-
Se puede ver computacionalmente que este rbol de bactracking tiene 2057 nodos y que es suficiente explorar 114 para encontrar la primera solucin. (Cmo se hace para calcular esto?).
Cul es la complejidad de este algoritmo de bactracking?
Ejercicio: Mostrar un valor de n 2 para el cual el problema de las n reinas no tiene solucin.
-
Otros ejemplos
Encontrar, usando backtracking todas las soluciones enteras de
x1+ x2 + x3 10
1 xi 4 i =1,2,3
-
Escribir algoritmos de backtracking (con poda cuando se pueda) para los siguiente problemas:
Encontrar una solucin para el siguiente puzzle: hay 4 cubos tales que cada una de las 24 caras de los mismos estn coloreadas de azul, rojo, verde y blanco. El juego consiste en ubicar los cubos en hilera de modo que cada color aparezca una vez arriba, otra abajo, otra en el frente y otra en la parte de atrs.
Un desarreglo de un conjunto de nmeros {1,n} es una permutacin p de dichos nmeros tal que ninguno de ellos queda en la posicin indicada por su valor, es decir, p(i) i
para todo 1 i n .
-
Programacin Dinmica Tcnica bottom- up
Principio de optimalidad : un problema de optimizacin satisface el principio de optimalidad si en una sucesin ptima de decisiones o elecciones, cada subsucesin es a su vez ptima. (es necesario que se cumpla para poder usar la tcnica de programacin dinmica, no todos los problemas lo cumplen)
Ejemplos: Coeficientes binomiales Producto de matrices Comparacin de secuencias de ADN Subsecuencia creciente mxima Arbol de bsqueda ptimo etc.
-
Clculo de coeficientes binomiales
Supongamos que queremos calcular los coeficientes binomiales usando la siguiente funcin (divide and conquer):
---------------------------Funcin C(n,k) si k = 0 or k = n entonces return 1 sino return C (n-1, k-1) + C (n-1, k)----------------------------Es eficiente calcular as?. No, los mismos valores de C(n,k) son calculados varias veces.
Cul es la complejidad de este algoritmo?. ( n )
k
-
Tringulo de Pascal
......n.....n-1.......1212
...111
......10
k k-1.3210
-
Cul es la complejidad de este algoritmo?. Cunta memoria requiere?. Hay que guardar en memoria toda la tabla?.
C (n,k)
C(n-1, k)C(n-1, k-1)
-
La frmula que usamos aqu es la misma que en el algoritmo divide and conquer, pero ac no calculamos varias veces lo mismo.
Tenemos entonces una complejidad de O(nk).
-
Problema de la multiplicacin de n matrices
Queremos ver la forma ptima de calcular
M= M1 M2 M3. Mn
Por la propiedad asociativa del producto de matrices esto puede hacerse de muchas formas. Queremos determinar la que minimiza el nmero de operaciones necesarias.
Vale el principio de optimalidad ac?
-
Ejemplo: supongamos que A es de 13 x5, B de 5 x 89 , C de 89 x 3 y D de 3 x 34.
((AB)C)D requiere 10582 multiplicaciones(AB)(CD) requiere 54201 multiplicaciones(A(BC))D requiere 2856 multiplicacionesA((BC)D) requiere 4055 multiplicacionesA(B(CD)) requiere 26418 multiplicaciones
-
Para ver cul es la forma ptima de multiplicar deberamos analizar todas las formas posibles de poner los parntesis y ver cual es la mejor.
Sea M =( M1 M2 M3. Mi)(Mi+1 M i+2. Mn)
Sea T(i) la cantidad de formas de poner los parntesis en el lado derecho y T(n-i) en el lado izquierdo. Entonces para cada i hay T(i)T(n-i) formas de poner los parntesis para toda la expresin y
T(n) = i T(i) T(n-i)
A partir de que T(1) =1 se puede calcular la expresin para cualquier n. (nmeros catalanes).
-
Encontrar de esta forma (algoritmo de fuerza bruta) la mejor manera de calcular la cantidad de multiplicaciones que requiere cada posibilidad es del orden (4n/n). 2n 2n-2 Dem: ejercicio, usar que n 4n / (2n+1) y T(n) = 1/n n -1 )
2674404862145211T(n)
151054321n
-
Cmo usar Programacin Dinmica para resolver este problema?
Construimos una tabla mij (1 i j n) donde mij es la cantidad mnima de multiplicaciones necesaria para calcular Mi M i+1 M i+2.Mj . La solucin al problema es entonces m1n.
Suponemos que las dimensiones de la matriz Mi estn dadas por un vector di , 0 i n, donde la matriz Mi tiene di-1 filas y di columnas y armamos la tabla diagonal por diagonal, para cada diagonal s, s = 0,., n-1
s=0 : mii = 0 para i=1,2,n s= 1 : mi i+1 = di-1didi+1 para i=1,2,n-1 1< s < n : mi i+s = mini k < i+s {mik + mk+1 i+s + di-1dkdi +s}
para i=1,2,n-s
-
En el ejemplo anterior d= ( 13,5,89,3,34) y entonces. Para s =1 m12 = 5785 , m23 = 1335, m34 = 9078 . Para s =2 m13 = 1530, m24 = 1845. Para s = 3 m12 = 2856
s=004
s=1907803
s=21845133502
s=32856153057850i=1432J=1
-
Cmo guardar la informacin para saber adems cul es la forma de hacer el producto tener este nmero de multiplicaciones?.
Complejidad : en cada diagonal s hay que calcular n-s elementos y para cada uno de ellos hay que elegir entre s posibilidades, entonces la cantidad de operaciones del algoritmo es
s (n-s)s = n s s - s s2 = n2 (n-1)/2 n (n-1) (2n-1)/6 = (n3 n )/6
o sea la complejidad del algoritmo es (n3).
-
Triangulacin de mnimo peso
Una triangulacin de un polgono convexo P = {v1, v2.... vn, v1} es un conjunto de diagonales que particiona el polgono en tringulos. El peso de la triangulacin es la suma de las longitudes de sus diagonales.
Ejemplo: dos triangulaciones de un mismo polgono.
Observar que cada eje del polgono original est en un solo tringulo.
-
Dado un segmento que une dos vrtices adyacentes, transformarlo en un tringulo implica determinar el tercer vrtice. Una vez identificado este vrtice al polgono le quedan dos polgonos menores que deben ser a su vez triangulados.
Sea T [i,j] el costo de triangular una de las parte del polgono que queda despus de trazar una diagonal desde el vrtice vi al vrtice vj,, sin tomar en cuenta la longitud dij de la cuerda que va de vi a vj (para no contarla dos veces).
-
k
i
j
T [i,j] = min jk = i {T [i,k] + T [k,j] + dik + dkj }
Caso base, cuando i y j son vecinos: T [i, i+1] = 0
-
Algoritmo para triangulacin del polgono
Triangulacin-mnima (P) para i = 1,n -1 hacer T[i,i+1] =0para gap = 1, n-1 para i = 1, n-gap hacer j= i+gap T [i,j] = minj k=i {T [i,k] + T [k+1,j] + dik + dkj }return T[1,n]
-
Complejidad : O(n3) Complejidad espacial: O(n2)
=========================================== Qu pasa si el polgono no es convexo?. Qu pasara si hubiera puntos en el interior del polgono?. El nmero de subregiones en cada paso ya no es 2 y crece
exponencialmente y entonces el algoritmo de programacin dinmica no es eficiente.
No se conocen algoritmos polinomiales para el problema de triangulacin en este caso.
-
Comparacin de secuencias de ADNSupongamos que tenemos dos secuencias de ADN GACGGATTAG y GATCGGAATAG
Queremos decidir si son parecidas o no.Para qu se usa esto?Alineamiento GA- CGGATTAG GATCGGAATAG
Objetivo: construir un algoritmo que determine la mejor alineacin global entre dos secuencias (que pueden tener distinta longitud).
Asignamos valores a las coincidencias, a las diferencias y a los gaps.
(Las transparencias que siguen sobre este tema, fueron preparadas por alumnos de la materia Biologa Computacional, ver pgina web).
-
match = +1mismatch = -1gap penalty = -2
Score(T, S) = 9 x 1 + 1 x (-1) + 1 x (-2) = 6
Ejemplo
T GACGGATTAGS GATCGGAATAG
Scores
-
Algoritmo de Programacin dinmicaNeedleman & Wunsch (1970)
Encuentra el mejor scoring para un alineamiento global de dos secuencias
A partir de all se determina un alineamiento que tiene ese score ptimo.
De acuerdo a los parmetros elegidos la alineacin ptima puede variar.
-
Se quiere alinear las secuencias S y T. Sea n el tamao de S y m el de T. Hay n+1 posibles prefijos de S y m+1 posibles
prefijos de T (incluyendo el string vaco). Se genera una matriz F de (n+1)x(m+1) elementos. El elemento F(i, j) tendr la mejor similitud entre las
subsecuencias S[1...i] y T[1...j].
-
Dadas las secuencias:
S = AAACT = AGC
A
A
A
C
A G C
-
Clculo de la similitud ptima
FF(i, j)= max(i, j)= maxF(i-1, j-1)+p(i,j)F(i-1, j-1)+p(i,j)F(i-1, j)-wF(i-1, j)-wF(i, j-1)-wF(i, j-1)-w
F(i-1,j-1) F(i,j-1)
F(i-1,j) F(i, j)
w=Penalizacin del Gap
-
Llenado de la Matriz
Se llena la matriz la primera fila y la primera columna con mltiplos de la penalidad por espacio.
Se llenan los elementos interioresF[i,j] = max F[i, j-1] + g
F[i-1, j-1] + p(i,j)F[i-1, j] + g
g = penalidad por espacio, p(i,j) = valor del matching entre S(i) y T(j)
Sigue cualquier orden que permita tener los valores F[i, j-1], F[i-1, j-1], F[i-1, j]. Como fila por fila ( de izquierda a derecha) o columna por columna (de arriba hacia abajo).
-
AlgoritmoAlgoritmo
n = long(S)m = long(t)Para i = 0 hasta n hacer
F[i, 0] = i gPara i = 0, m hacer
F[0, i] = i gPara i = 1, n hacer
Para j = 1, m hacerF[i, j] = max (F[i-1, j] + g, F[i-1, j-1]
+ p(i,j), F[i, j-1] + g)Return F
-
Inicio de la matriz:
A
A
A
C
A G C
0
A
-2
-
Inicio de la matriz:
A
A
A
C
A G C
0 -2 -4 -6
A G CA A A C
-
A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
-
A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1
1
1
1
-1
-1-1
-1 -1
-1-1
-1
-
A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1 -1
1
1
1
-1
-1-1
-1 -1
-1-1
??
?
F(i, j)=F(i, j)=F(i-1, j-1)+s(i,j)F(i-1, j-1)+s(i,j)F(i-1, j)-wF(i-1, j)-wF(i, j-1)-wF(i, j-1)-w
maxmax
-
A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1 -1
1
1
1
-1
-1-1
-1 -1
-1-1
1
F(i, j)=F(i, j)=F(i-1, j-1)+s(i,j)F(i-1, j-1)+s(i,j)F(i-1, j)-wF(i-1, j)-wF(i, j-1)-wF(i, j-1)-w
maxmax
AA
-
A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1 -1
1
1
1
-1
-1-1
-1 -1
-1-1
1
F(i, j)=F(i, j)=F(i-1, j-1)+s(i,j)F(i-1, j-1)+s(i,j)F(i-1, j)-wF(i-1, j)-wF(i, j-1)-wF(i, j-1)-w
maxmax
-1
A A G
-
1A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1 -1
1
1
1
-1
-1-1
-1 -1
-1-1
F(i, j)=F(i, j)=F(i-1, j-1)+s(i,j)F(i-1, j-1)+s(i,j)F(i-1, j)-wF(i-1, j)-wF(i, j-1)-wF(i, j-1)-w
maxmax
-1
0-1
-2-3
-4-5
-1
-1
-2
-3
score ptimo global
-
1A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1 -1
1
1
1
-1
-1-1
-1 -1
-1-1
-1
0-1
-2-3
-4-5
-1
-1
-2
-3
Tenemos el valorde la similitud entrelas secuencias.
Ahora necesitamos reconstruir el alineamiento
1 -1
0
-
Determinacin del alineamiento ptimo
Se comienza desde el valor de F[n,m] y se realiza el camino inverso hasta llegar al valor F[0,0].
Por cada valor F[i,j] se testea si provino de F[i-1, j-1] + p(i,j) o F[i-1, j] g o F[i, j-1] g.
-
Hay que tomar la ltima coincidencia del alineamiento y comenzar a Hay que tomar la ltima coincidencia del alineamiento y comenzar a buscar un camino hacia atrs que maximice la funcinbuscar un camino hacia atrs que maximice la funcin, es decir , es decir siguiendo los valores ms altos.siguiendo los valores ms altos.
Cuando los valores coinciden, cualquier camino que se tome Cuando los valores coinciden, cualquier camino que se tome conducir a la formacin de un alineamiento de igual score. Sin conducir a la formacin de un alineamiento de igual score. Sin embargo los algoritmos para resolverse deben dar preferencia a uno embargo los algoritmos para resolverse deben dar preferencia a uno de los valores, en nuestro caso se toma preferencia en el sentido de los valores, en nuestro caso se toma preferencia en el sentido horariohorario
Mxima preferencia
-
1A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1 -1
1
1
-1
-1-1
-1 -1
-1-1
-1
0-1
-2-3
-4-5
-1
1 -1
-2
-3
Mxima preferencia
-1-2
-1 0
A A CG C
-
1A
A
A
C
A G C
0 -2 -4 -60
-2
-4
-6
-8
1 -1
1
1
-1
-1-1
-1 -1
-1-1
-1
0-1
-2-3
-4-5
-1
1 -1
-2
-3
Mxima preferencia
-1-2
-1 0
111
A A A CA G C
-
Algoritmo de reconstruccinAlgoritmo de reconstruccin
Este algoritmo va a construir un alineamiento ptimo dadas la matriz F y las secuencias originales S y T.
La variable len contiene la longitud del alineamiento (que puede ser n+m)
Los vectores (secuencia de valores) aligS y aligT contienen los caracteres alineados.
-
INPUT: indices i,j, array F.Alinear(i, j)Si i=0 y j = 0 entonces
len = 0Sino Si i>0 y F[i,j] = F[i-1, j] + g entonces
Alinear(i-1, j, len)len = len + 1aligS[len] = s[i]aligT[len] = - //(espacio)
Sino Si i>0 y j>0 y F[i,j] = F[i-1, j-1] + p(i,j) entAlinear(i-1, j-1, len)len = len + 1aligS[len] = s[i]aligT[len] = t[j]
Sino // debe ser F[i,j] = F[i, j-1] + gAlinear(i, j-1, len)len = len + 1aligS[len] = - //(espacio)aligT[len] = t[j]
FinDevolver aligS, aligT y len.
+p(i,j)
+g
+g
j-1 j
i
i-1
-
+p(i,j)
+g
+gj-1 j
i
i-1
+p(i,j)
+g
+gj-1 j
i
i-1
+p(i,j)
+g
+gj-1 j
i
i-1
(0,0)
Recursin en el algoritmoRecursin en el algoritmo
-
ComplejidadComplejidadm = long(S)
n = long(t)
Para i, desde 0 hasta n hacer
F[i, 0] = i x g
Para i, desde 0 hasta m hacer
F[i, 0] = i x g
Para i, desde 1 hasta n hacer
Para j, desde 1 hasta m hacer
F[i, j] =mximo(F[i-1, j] + g, F[i-1, j-1] + p(i,j), F[i, j-1] + g).
Devolver F[n,m]
n veces
m veces
m veces
n veces
-
Complejidad
Complejidad Temporal: O(mn) en armar la matriz O(m + n) en buscar en la matriz (recorrer la
secuencia resultante, que a lo sumo tiene n+m elementos).
Complejidad Espacial: O (mn) por el espacio necesario para la matriz
-
Algoritmo de programacin dinmica para el problema de la mochila
Trabajaremos con la siguiente versin del problema de la mochila.
Problema P(n, k): dado un entero k y n items i de diferentes tamaos ki, encontrar un subconjunto de los items tal que sumen exactamente K o determinar que no existe tal conjunto
-
Algoritmo knapsack
Input: S un array con los tamaos de cada item y K.
Output: Un arreglo de dos dimensiones tal que P[i,k].exist = true si existe una solucin con los primeros i elementos para una mochila de tamao k y P[i,k].belong = true si el elemento i pertenece a esa solucin.
-
AlgoritmoEmpezar
P[0,0] exist = true para k = 1,K hacer P[0,k].exist = false para i =1,n hacer para k = 0,K hacer P[i,k]. exist = false if P[i-1,k]. exist then P[i,k]. exist = true P[i,k]. belong = false else if k-S[i] 0 if P[i-1,k-S[i]]. exist then P[i,k]. exist = true P[i,k]. belong = ture
end
-
Ejemplo: aplicar el algoritmo anterior a 4 items de tamao 2,3,5 y 6 tamaos de la mochila desde 2 a 16.
I-II-IOIOOIO-OO-6------I-II-O-OO-5
-----------I-IO-3--------------I-2
16151413121110987654321k
Referencias de la tabla:I : se encontr una solucin que contiene este itemO: se encontr una solucin sin este item- : no hay solucin hasta el momento (si este smbolo aparece en la ltima lnea
quiere decir que no hay solucin para este tamao de mochila)
-
Subsecuencia creciente ms larga
Determinar la subsecuencia creciente ms larga de una sucesin de nmeros.
Ejemplo:S = { 9,5,2,8,7,3,1,6,4)
Las subsecuencias ms largas son {2,3,4} o {2,3,6 }
Para construir un algoritmo de programacin dinmica definimos:li = longitud de la secuencia creciente ms larga que termina con el
nmero sipi = predecesor de si en la secuencia creciente ms larga que termina con
el nmero si
Vale el principio de optimalidad en este caso?. Cmo se expresara?.
-
Relacin de recurrencia:
l0 = 0li = maxj
-
Complejidad? O(n2) ( se podra implementar en O(nlogn))Cul es la complejidad espacial?.Cmo hacemos para tener tambin la sucesin y no slo la longitud.
33-222---predecesor
331222111longitud
461378259sucesin
-
Arboles de bsqueda ptimos
rbol binario de bsqueda: cada nodo contiene una clave, y el valor contenido en cada nodo interno es mayor o igual (numrica o lexicogrficamente) que el de su hoja izquierda y menor o igual que el de la derecha.
Cuntos rboles binarios de bsqueda distintos puede haber con un nmero dado n de palabras cdigo (o clave)?.
Cmo podemos determinar el rbol binario que minimiza el nmero promedio de comparaciones necesarias para encontrar una clave.
-
Supongamos que tenemos un conjunto c1 < c2 < ..< cn de claves con probabilidad pi de ser buscadas.
Si la clave ci est en el nivel di entonces hacen falta di + 1 comparaciones para encontrarla.
Suponemos pi = 1
Entonces para un rbol dado la cantidad de comparaciones que tenemos que hacer en media para buscar una clave es
C = i pi (di + 1)
-
Dado un conjunto de claves y sus probabilidades queremos construir un rbol que minimice esta funcin, usando programacin dinmica.
Se cumple el principio de optimalidad?.
en un rbol ptimo todos sus subrboles son ptimos para las claves que contienen
-
Relacin de recurrencia?
Sea: mij = jk= i pk (probabilidad de que una clave este en la sucesin ci,ci+1 ,cj )
Cij nmero de comparaciones promedio que se hacen en un subrbol ptimo que contiene las claves ci,ci+1 ,cj , cuando buscamos en el rbol completo.
C ij = 0 para j = i-1
C kij nmero de comparaciones promedio en un subrbol que contiene las claves ci,ci+1 ,cj , y tiene a la clave k en la raz. (siempre pensando que buscamos una clave en todo el rbol)
-
Si la clave k es la raz de ese subrbol podemos calcular:
Ckij = mij + Ci,k-1 + C k+1,j
o sea dado un subrbol con raz k: la probabilidad de que la clave buscada se una de las del subrbol o
sea alguna de las ci,ci+1 ,cj es mij una comparacin se hace con ck y el resto en el rbol derecho o en el
rbol izquierdo
Y si queremos que el subrbol sea optimo la raz tiene que ser elegida de modo a minimizar
Cij = mij + min ikj {Ci,k-1 + C k+1,j}
-
Ejemplo:
Calculamos la matriz de los mij
0.120.450.080.050.30pi
54321i
0.12
0.570.45
0.650.530.08
0.700.580.130.05
10.880.430.350.30
-
A partir de esto podemos calcular los Cij usando la frmula de recurrencia y obtener el mnimo nmero de comparaciones promedio necesarias del rbol ptimo.
Cmo hacemos para determinar el rbol ptimo?
0.1200.690.4500.850.610.0801.000.760.180.0501.731.490.610.400.30
-
La tcnica de Programacin Dinmica se aplica tambin a problemas con variables continuas
( los ejemplos que vimos ac fueron todos con variables discretas).
En el caso de variables continuas puede ser necesario resolver en el marco de las ecuaciones de recurrencia, problemas de maximizacin o minimizacin continuos, usando las herramientas habituales del clculo u otras.
-
Algoritmos probabilsticos
Cuando un algoritmo tiene que hacer una eleccin a veces es preferible elegir al azar en vez de gastar mucho tiempo tratando de ver cual es la mejor eleccin.
Pueden dar soluciones diferentes si se aplican dos veces a la misma
instancia. Los tiempos de ejecucin tambin pueden ser muy diferentes.
Tiempo promedio de un algoritmo determinstico: considera todas las instancias de un mismo tamao son similares. (ejemplo: quicksort)
Tiempo esperado promedio de un algoritmo probabilstico : es el tiempo medio de los tiempos de resolver la misma instancia del mismo problema muchas veces.
Peor tiempo esperado: tomando en cuenta el peor caso de todas las instancias de un cierto tamao.
-
Clasificacin de algoritmos probabilisticos
Algoritmos al azar para problemas numricos: la respuesta es siempre aproximada pero se espera que la solucin sea mejor cuando ms tiempo hay para ejecutar el algoritmo. (simulacin, integracin numrica).
Algoritmos de Monte Carlo: se quiere una respuesta exacta. Por ejemplo problemas de decisin. Un algoritmo Monte Carlo da siempre una respuesta pero la respuesta puede no ser correcta. La probabilidad de suceso, es decir de respuesta correcta crece con el tiempo disponible para correr ese algoritmo. La principal desventaja es que en general no se puede decidir eficientemente si la respuesta es correcta o no.(ejemplo: decidir si un arreglo T tiene un elemento mayoritario, o sea que aparece en T ms de n/2 veces)
-
Algoritmos Las Vegas: nunca dan una respuesta incorrecta pero pueden no dar ninguna respuesta. Tambin la probabilidad de suceso, es decir de tener respuesta correcta crece con el tiempo disponible para correr ese algoritmo. (ejemplo: en el problema de las 8 reinas poner las reinas al azar en las filas que an estn desocupadas, cuidando solamente que la solucin en construccin sea factible)
Algoritmos Sherwood : en este caso el algoritmo siempre da una respuesta y la respuesta es siempre correcta. Se usan cuando algn algoritmo determinstico para resolver un algoritmo es mucho ms rpido en promedio que en el peor caso. Al incorporar un factor de azar el algoritmo puede llegar a eliminar la diferencia entre buenas y malas instancias. (ejemplo: Quicksort)
-
En todos estos casos suponemos que tenemos disponible un generador de nmeros al azar de costo computacional unitario.
O sea dados reales a y b con a < b, uniform (a,b) devuelve un nmero x elegido al azar en el intervalo a x < b. La distribucin de x es uniforme en el intervalo y llamadas sucesivas del generados dan valores independientes de x.
Para generar enteros al azar uniform (ij) devuelve un entero k elegido al azar uniformemente en el intervalo
ik j
-
Ejemplo de algoritmo tipo Las Vegas: el problema de las 8 reinas.
Procedimiento Queens LV (var sol[18], sucess)array ok[18] (posiciones disponibles)col, diag45, diag135 Para k = 0,7 hacer(sol [1k] es k prometedor, hay que ubicar a la reina k+1) nb = 0 para j = 1, 8 hacer si j col y j-k diag45 y j+k diag135 entonces (la columna j esta
disponible) nb = nb +1 ok[nb] = j si nb = 0 entonces sucess =false j = ok[uniform (1.nb)] col = col U {j} diag45 = diag45 U {j} diag 135 = diag135 U {j+k} sol[k+1] = jreturn success = true
-
Ms ejemplos de algoritmos probabilsticos en el libro de Brassard y Bratley
-
Heursticas Dado un problema , un algoritmo heurstico es un
algoritmo que intenta obtener soluciones para el problema que intenta resolver pero no necesariamente lo hace en todos los casos.
Sea un problema de optimizacin, I una instancia del problema, x*(I) el valor ptimo de la funcin a optimizar en dicha instancia. Un algoritmo heurstico obtiene una solucin con un valor que se espera sea cercano a ese ptimo pero no necesariamente el ptimo.
Si H es un algoritmo heurstico para un problema de optimizacin llamamos xH(I) al valor que devuelve la heurstica.
-
Porqu usar algoritmos heursticos?. En que tipo de problemas?
Las heursticas que son de utilidad prctica son algoritmos polinomiales.
Cundo decimos que una heurstica es buena?Cmo hacemos para saber si una heurstica es buena?
-
Algoritmos aproximados
Decimos que H es un algoritmo - aproximado para el problema si para algn > 0
xH(I) - x*(I) | | x*(I) |
O equivalentemente un algoritmo es aproximado si existe > 0tal que para toda instancia I
xH(I) / x*(I) (problema de minimizacin)
Situacin ideal, pero poco frecuente
-
Ejemplo de algoritmo aproximado
Cuando las variables son enteras, el algoritmo goloso que vimos para el problema de la mochila es un algoritmo aproximado.
Se puede demostrar que para toda instancia I de dicho problema se verifica que:
xH(I) / x*(I) (c1b/a1 )/ (c1 (b /a1)) = = b/a1 / (b/a1) 0.5
(es un problema de maximizacin)
-
Cmo evaluamos una heurstica?
Comportamiento medio Anlisis probabilstico Comportamiento en peor caso (algoritmos aproximados): i) razn de perfomance en el peor caso : r = sup {xH(I) / x*(I) } r = inf {xH(I) / x*(I) } segn estemos minimizando o maximizando. ii) error relativo er = | xH(I) - x*(I) | /| x*(I)|
En la prctica no podemos calcular exactamente estos valores pero si a veces obtener cotas para ellos.
-
Metaheursticas
Ver presentacin aparte
-
GRAFOS
Qu es un modelo matemtico?
Problemas que pueden modelarse usando grafos.
La nocin de grafos fue planteada independientemente por varios cientficos de diferentes disciplinas.
-
Historia
Graph Theory: 1736-1936, Biggs,Lloyd, Wilson, Oxford University Press, 1976.
-
Euler (1736): Problema de los puentes de Konigsberg.
Modelo usando grafos
Primer teorema de teora de grafos: Hay un circuito que pasa por todas las lneas del grafo una y slo una vez si y slo si cada punto tiene un nmero par de lneas incidentes.
Euler plante el teorema, pero slo prob que la condicin es necesaria.
-
Wiener, 1873, Laberintos.
Vandermonde, 1771, Problema de los caballos en un tablero de ajedrez.
Kirkman, 1856, circuitos en poliedros, pionero en formular el problema del viajante de comercio.
-
Hamilton, 1858 : juego: dar la vuelta al mundo sin pasar dos veces por la misma ciudad.
Pasar por todos los vrtices de un dodecaedro una y slo una vez y volver a la ciudad de origen.
Generalizacin: circuitos hamiltonianos.
Problema del Viajante de Comercio
Problema computacionalmente no resuelto en el caso general.
-
Leyes de Kirschhoff (1847)
Introdujo el concepto de rboles para resolver el sistema de ecuaciones lineales que describen el flujo de la corriente elctrica en cada rama de cada circuito en una red elctrica.
Model la red compuesta de resistencias, condensadores, inductancias, etc, con un grafo.
No todas las ecuaciones son necesarias porque el sistema no es independiente. Solo es necesario un sistema fundamental de circuitos que se puede obtener a partir de un rbol generador.
-
Cayley, 1857: Ismeros Qumicos.
Cuntos compuestos qumicos diferentes pueden corresponder a una misma frmula?
Ejemplo : ismeros de CnH2n+2 (parafinas) Se pueden modelar como rboles con nodos de
grado 4 y nodos de grado 1 hay. Se quiere contar cuantos rboles distintos de ese
tipo hay.
-
Ejemplo: para n = 4 dos de los compuestos son:
Butano
Isobutano
-
Problema de los cuatro colores: se puede pintar cualquier mapa con cuatro colores sin que dos pases que tengan como frontera una lnea tengan el mismo color?.
Origen vago. Primer planteo conocido:De Morgan 1852. Antecedentes de 1840.
Primera supuesta demostracin, Kempe 1879 Error descubierto por Heawood, 1890, que demostr
el Teorema para 5 colores.
-
Problema abierto por ms de 100 aos
Avances de la teora de grafos alrededor de este problema.
Demostracin en 1976, Appel y Haken. Uso de la computadora en esta demostracin. Demostraciones posteriores.
-
Aplicaciones actuales
Redes de comunicaciones, diseo, ruteo. Problemas de distribucin y ruteo de vehculos. Planificacin de la produccin. Redes de trfico Demostracin de teoremas. Correctitud de programas VLSI Descifrado de Cdigos Ingeniera de Software Bases de datos Biologa Computacional etc..etc., etc.,etc,etc.,etc, etc., etc., etc., etc., etc...
-
Definiciones Un grafo G = (V,X) es un par de conjuntos, donde V
es un conjunto de puntos o nodos y X es un subconjunto del conjunto de pares no ordenados de elementos distintos de V .
Los elementos de X se llamas aristas o ejes o arcos.
Dados v, w V, si e = (v,w) X se dice que v y w son adyacentes y que e es incidente a v y a w.
Notacin: n= | V | m = | X |
-
El grado de un nodo es la cantidad de ejes incidentes a v.
Notacin: d(v) = grado de v.
Teorema: La suma de los grados de los nodos de un grafo es 2 veces el nmero de ejes, o sea:
i=1,n d (vi) = 2 m
-
Un grafo se dice completo si todos los nodos son adyacentes entre si.
Notacin: Kn grafo completo de n nodos.
Cuntos ejes tiene un grafo completo de n nodos?.
-
Un camino en un grafo es una sucesin de ejes e1 e2.......ek tal que un extremo de ei coincide con uno
de ei-1 y el otro con uno de ei+1.
Hay otras formas de describir un camino
Un camino simple es un camino que no pasa dos veces por el mismo nodo.
Un circuito es un camino que empieza y termina en el mismo nodo.
Un circuito simple es un circuito de 3 o ms nodos que no pasa dos veces por el mismo nodo.
-
La longitud de un camino es la cantidad de ejes que tiene ese camino.
La distancia d(v,w) entre dos nodos v y w de un grafo se define como la longitud del camino ms corto entre ambos.
Si no existe camino entre v y w decimos que d(v,w) =
-
Proposicin: la funcin distancia cumple las siguientes propiedades para todo v, u y w pertenecientes a V:
i) d(u,v) 0, d(u,v) = 0 si y slo si u= vii) d (u,v) = d(v, u)iii) d(u,w) d(u,v) + d(v,w)
-
Un grafo se dice conexo si existe un camino entre todo par de nodos.
Dado un grafo G = (V,X) un subgrafo de G es un grafo H = ( V, X) tal que
V V y X X ( Vx V)
Una componente conexa de un grafo G, es un subgrafo conexo maximal de G.
-
Un grafo orientado o digrafo G= (V,X) es un par de conjuntos V y X, donde V es un conjunto de puntos o nodos y X es un subconjunto del conjunto de pares ordenados de elementos distintos de V .
Un camino orientado en un grafo orientado es una sucesin de ejes e1 e2.......ek tal que el primer
elemento del par ei coincide con el segundo de ei-1 y el segundo elemento de ei con el primero de ei+1.
-
Un circuito orientado en un grafo orientado es un camino orientado que empieza y termina en el mismo nodo.
El grado de entrada din(v) de un nodo de un grafo orientado es la cantidad de ejes que llegan a v, es decir la cantidad de ejes que tienen a v como su segundo elemento.
El grado de salida dout(v) de un nodo de un grafo orientado es la cantidad de ejes que salen de v, es decir la cantidad de ejes que tienen a v como su primer elemento.
-
Multigrafo: grafo en el que puede haber varios ejes entre cada par de nodos distintos.
Seudografo: grafo en el cual puede haber varios ejes entre cada par de nodos y tambin puede haber ejes (loops) que unan a un nodo con si mismo.
(definiciones de acuerdo a la nomenclatura del libro de Harari)
-
Un grafo G = (V,X) es bipartito si existen dos subconjuntos V1 y V2 del conjunto de nodos V tal que:
V = V1 V2 , V1 V2 = , V1 V2 y tal que todos los ejes de G tienen un extremo en V1 y
otro en V2.
-
Teorema:Un grafo G es bipartito si y slo si todos sus
circuitos tienen longitud par
-
Dos grafos G = (V,X) y G= (V, X) se dicen isomorfos si existe una funcin biyectiva
f: V -------------> V
tal que para todo v, w V
(v,w) X si y slo si (f(v), f(w)) X
-
Proposicin:Si dos grafos G y G son isomorfos:
i) tienen el mismo nmero de nodosii) tienen el mismo nmero de ejesiii) para todo k, 0 k n-1 tienen el mismo nmero
de nodos de grado k.iv) tienen el mismo nmero de componentes conexas vi) para todo k, tienen el mismo nmero de caminos
simples de longitud k.
-
Es cierta la recproca de esta proposicin?
Hay condiciones necesarias y suficientes fcilmente verificables para ver si dos grafos son isomorfos?
-
Representacin de grafos en la computadora
Matrices Listas
-
Matriz de Adyacencia de un grafo G
A Rnxn , donde los elementos aij de A se definen como:
aij = 1 si G tiene un eje entre i y j 0 si no
-
Matriz de Incidencia de un grafo G
B Rmxn , donde los elementos bij de B se definen como:
bij = 1 si el eje i es incidente al nodo j 0 si no
-
Teorema: Si A es la matriz de adyacencia del grafo G, el elemento aijk de la matriz Ak , es igual a la cantidad de caminos de longitud k entre i y j.
Corolario: aii2 = d (vi)
-
Arboles
Def: Un rbol es un grafo conexo sin circuitos simples.
-
Teorema: dado un grafo G, son equivalentes:
d) G es un rbol.b) G es un grafo sin circuitos simples pero si se agrega
un eje a G, queda un grafo con circuitos simple. f) Todo par de nodos v y w en G est unido por un
nico camino simple.d) G es conexo pero si se quita un eje a G, queda un
nuevo grafo no conexo.
-
Def: una hoja es un nodo de grado 1.
Lema: Todo rbol no trivial tiene al menos una hoja.
Teorema: Dado un grafo G, son equivalentes:a) G es un rbol.b) G es un grafo sin circuitos y m = n-1 c) G es conexo y m = n-1
-
Def: Un rbol orientado es un grafo orientado tal que:
i) el grafo no orientado subyacente es un rbolii) En G hay un nodo r tal que existe un camino
orientado desde r a todos los dems.(cualquier nodo es alcanzable desde r por un camino
orientado)
En un rbol no orientado podemos definir un nodo cualquiera como raz.
-
Def: El nivel de un nodo de un rbol es la distancia de ese nodo a la raz.
Def: La altura h de un rbol es la longitud desde la raz al nodo ms lejano.
Def: Un rbol se dice (exactamente) m-ario si todos sus nodos,
salvo las hojas y la raz tienen grado (exactamente ) a lo sumo m+ 1 y la raz tiene grado m.
Def: Un rbol se dice balanceado si todas sus hojas estn a nivel h o h-1.
Def: Un rbol se dice balanceado completo si todas sus hojas estn a nivel h.
-
Los nodos internos de un rbol son aquellos que no son ni hojas ni la raz.
Cuntos nodos tiene en total un rbol exactamente m-ario que tiene i nodos internos?.
-
Teorema: Un rbol m-ario de altura h tiene (a lo sumo) mh
hojas.iii) Un rbol m-ario con l hojas tiene h logm l.iii) Si T es un rbol exactamente m-ario balanceado
entonces h = logm l.
-
Recorrido de rboles
BFS (Breadth-First Search)
DFS (Depth-First Search)
En qu casos conviene uno u otro mtodo de recorrido?.
-
Algoritmo Recorrer (para rboles no orientados)Empezar marcar nodo s pred(s) := 0 next :=1 order (s) := next LIST := {s} mientras LIST hacer empezar elegir un nodo i de LIST si i es incidente a un arco (i,j) tal que j LIST entonces empezar marcar j pred(j) := i next = next +1 order (next) := j LIST := LIST {j} fin else LIST := LIST \ { i} fin fin
-
Arboles generadores
Def: Dado un grafo G, un rbol generador de G es un es un subgrafo de G que es un rbol y tiene el mismo conjunto de nodos de G.
Def: Sea G= (V,X) un grafo y l : X -------------> Run funcin que asigna longitudes (o pesos) a los ejes de G. Definimos la longitud de un rbol T como l(T) = eT l(e)
Def: Dado un grafo G = (V,X) un rbol generador mnimo de G es un rbol T tal que l(T) es mnima.
-
Ejemplo
H
B C
I
AD
G
F E
1
68
4
12
8
3
6
5 3
4 13 9
10
-
Algoritmo de Prim
--------------------------------------------------------------------------Input: G = (V,X) grafo conexo con una funcin de longitudes
positivas asignadas a los ejes.Empezar Elegir un eje e X de longitud mnima. Poner T = {e}, i = 1 Mientras i < n-1 hacer Elegir e X tal que la longitud de e sea mnima entre los ejes que tienen un extremo en T y otro fuera de T. Poner T = T {e} Poner i = i+1 FinFin
-
Proposicin: Sea G un grafo conexo. El subgrafo T que el algoritmo de Prim construye es un rbol generador de G.
Proposicin: Sea G un grafo conexo. Sea Tk el rbol que el algoritmo de Prim determina en la iteracin k, para k n-1. Tk es un subrbol de un rbol generador mnimo de G.
Teorema: El algoritmo de PRIM es correcto, es decir dado un grafo G conexo determina un rbol generador mnimo de G.
Algoritmo goloso
-
Algoritmo de Kruskal
Input: G = (V,X) grafo conexo con una funcin de longitudes positivas asignadas a los ejes.Empezar Elegir un eje e X de longitud mnima. Poner T = {e}, i = 1. Mientras i < n-1 hacer Elegir e X tal que la longitud de e sea mnima entre los ejes que no forman circuito si los agregamos a T. Poner T = T {e}. Poner i = i+1. FinFin
-
Enumeracin
Cuntos grafos diferentes hay que tengan ciertas caractersticas?. (Ej: cuntos grafos conexos con 8 nodos y 2 circuitos)
Cuntos subgrafos de un cierto tipo de un grafo dado hay? (Ej: cuntos rboles generadores tiene un grafo, cuantos circuitos, cuntos grafos completos)
En general son problemas difciles
-
Ejemplos de algunas cosas que se pueden calcular:
Cuntos grafos rotulados distintos de n nodos y m ejes hay?.
Cuntos grafos rotulados distintos de n nodos hay?.
-
Teorema de Cayley (1875): El nmero de rboles rotulados distintos de n nodos es nn-2.
Dem: por induccin en n usando los algoritmos inversos de codificacin y decodificacin de Prufer que describiremos a continuacin para establecer una biyeccin entre el conjunto de rboles de n nodos y el conjunto de palabras de n-2 smbolos usando el alfabeto {1,...n} .
-
Algoritmo de codificacin de Prufer
Dado un rbol de n nodos rotulado con los nmeros de 1 a n, construye una palabra de longitud n-2 usando el alfabeto {1,,n}
----------------------------------------------------------------------------Input Un rbol T rotulado de n nodosEmpezar Para i =1,,n-2 Sea v la hoja de menor rtulo de T. Poner como si el rtulo del nodo adyacente a v. Poner T = T \ {v}. fin Return secuencia s1.sn-2fin
-
Proposicin: Si dk es el nmero de ocurrencias del nmero k en la secuencia que se obtiene despus de aplicar el algoritmo de codificacin de Prufer, entonces el grado del nodo k en el rbol T es dk + 1.
Dem: por induccin en n.
-
Algoritmo de decodificacin de PruferDada una palabra de longitud n-2 usando el alfabeto {1,,n} construye un
rbol de n nodos rotulado con los nmeros de 1 a n----------------------------------------------------------------------------Input Una palabra P = s1. sn-2Empezar Poner L = {1,n } Poner como T el conjunto de nodos aislados 1,.n. Para i =1,,n-2 Sea k el menor nmero de L que no est en P. Sea j el primer elemento de P. Agregar un eje en T uniendo los nodos k y j . Poner L = L \ {k}. Sacar la primera aparicin de j de la lista P. fin Agregar un eje entre los dos nodos cuyos nmeros quedaron en L. Return T fin
-
Proposicin: El algoritmo de decodificacinde Prufel define una funcin del conjunto de secuencias de longitud n-2 sobre el conjunto de rboles rotulados de n nodos.
Dem: El procedimiento construye grafos de n nodos. Hay que ver que el grafo resultante siempre es un rbol.(se puede demostrar por induccin en n, ejercicio)
Ejercicio: completar la demostracin del teorema de Cayley, probando por induccin que la funcin de decodificacin de Cayley es la inversa de la funcin de codificacin.
-
Algoritmos para determinar caminos mnimos en grafos
-
Def: Sea G= (V,X) un grafo y l:XR una funcin de longitud/peso para los ejes de G.
La longitud de un camino C entre 2 vrtices v y u es la suma de las longitudes de los ejes del camino o sea
l(C) = eC l(e)
Un camino mnimo C0 entre u y v es un camino de longitud l(C) tal que
l(C0) = mn {(l(C) / C es un camino entre u y v}
(puede haber varios caminos mnimos)
Cmo modificamos estas definiciones si G es un grafo orientado?
-
Problema: Dado G= (V,X) un grafo y l:XR una funcin que asigna a cada arco una cierta longitud y vV un vrtice del grafo, calcular los caminos mnimos de v al resto de los vrtices.
Distintas situaciones:
El grafo puede ser orientado o no. Todos los arcos tienen longitud no negativa. No hay un circuito orientado de longitud negativa. Hay un circuito orientado de longitud negativa. Cmo hacemos si queremos calcular los caminos mnimos entre todos
los pares de vrtices?
-
Algoritmo de Dijkstra (1959)
Suponemos que las longitudes de los ejes son todas positivas. El grafo puede ser orientado o no orientado.
-------------------------------------------------------------------Empezar S={v}, pi(v)=0, si vwX, pi(w)=l(vw), Mientras SV hacer Encontrar wV\S tal que pi(w)=min pi(u), uV\S. S=S{w}. uV\S / wuX,
si pi(u)>pi(w)+l(wu), pi(u)=pi(w)+l(wu),
FinFin------------------------------------------------------------------------ Cmo hacemos si adems de calcular las distancias queremos
determinar tambin un camino mnimo?
-
Algoritmo de Dijkstra (1959)
---------------------------------------------------------------------Empezar S={v}, pi(v)=0, padre(v)=0, si vwX, pi(w)=l(vw),
padre(w)=v, sino pi(w)=padre(w)=. Mientras SV hacer Encontrar wV\S tal que pi(w)=min pi(u), uV\S. S=S{w}. uV\S / wuX,
si pi(u)>pi(w)+l(wu), pi(u)=pi(w)+l(wu), padre(u)=w
FinFin----------------------------------------------------------------------------
-
111
2 3
6
54
43
1
43
3
7 1 1
-
111
2 3
6
54
43
1
43
3
7 1 1
0/ 0 3/ 1
/ 113/ 1/ 11
4/1
/11
7/1/11
/
/11//11
-
111
2 3
6
54
43
1
43
3
7 1 1
0/ 0 3/ 1
/ 113/ 1/ 11
4/1
/11
7/1/11
/
/116/4/11
-
111
2 3
6
54
43
1
43
3
7 1 1
0/ 0 3/ 1
/ 113/ 1/ 11
4/1
/11
7/1/11
/
/115/2/11
-
111
2 3
6
54
43
1
43
3
7 1 1
0/ 0 3/ 1
/ 113/ 1/ 11
4/1
/11
7/1/11
9/5/11
5/2/11
-
111
2 3
6
54
43
1
43
3
7 1 1
0/ 0 3/ 1
/ 113/ 1/ 11
4/1
/11
7/1/11
8/3/11
5/2/11
-
111
2 3
6
54
43
1
43
3
7 1 1
0/ 0 3/ 1
/ 113/ 1/ 11
4/1
/11
7/1/11
8/3/11
5/2/11
-
111
2 3
6
54
43
11
43
3
7-27
11
11-2
1
-
Algoritmo de Ford (1956)
En este caso suponemos G orientado y que no tenemos circuitos de longitud negativa
------------------------------------------------------------------------Empezar
pi(v)=0, wV\{v}, pi(w)=. Mientras hay cambio en pi hacer Para wV\{v} Hacer
pi(w)=min (pi(w), min uwX (pi(u)+l(uw))) Fin
FinFin-----------------
-
Teorema: Dado un grafo orientado G con longitudes positivas o negativas, pero sin circuitos de longitud negativa el algoritmo de Ford determina el camino mnimo entre el nodo 1 y todos los dems.
Cul es la complejidad del algoritmo de Ford? Qu pasa si aplicamos Ford a un grafo no orientado?. Cmo podemos modificar el algoritmo de Ford para
detectar si hay circuitos de longitud negativa?.
-
Algoritmo de Ford (1956)
Grafo orientado, detecta circuitos de longitud negativa
-----------------------------------------------------------Empezar
pi(v)=0, wV\{v}, pi(w)=, i=0. Mientras hay cambio en pi y i
-
Def: Sea G= ({1,...n},X) un digrafo y l:XR una funcin de longitud/peso para los ejes de G. Definimos las siguientes matrices:
L=(lij) definida por: lii=0 lij= l(ij) si ijX lij= si ijX
D=(dij) donde dij es la longitud del camino orientado mnimo de i a j , si camino entre i y j, y sino dij = .
D es llamada matriz de distancias de G.
Algoritmos matriciales
-
1 2 3 4
1 0 3 3
2 2 0 2 2
3 -2 0 1
4 4 4 0
L =
-
Algoritmo de Floyd (1962)G orientado, no hay circuitos de longitud negativa----------------------------------------------------------------------Empezar
L(0)=LPara k desde 1 hasta n hacer
Para i desde 1 hasta n hacerPara j desde 1 hasta n hacer
l(k)ij=min(l(k-1)ij,l(k-1)ik+ l(k-1)kj)Fin
FinFin
Fin
-
1 2 3 4
1 0 3 3
2 2 0 2 2
3 -2 0 1
4 4 4 0
L = L(0) =
1 2 3 4
1 0 3 3
2 2 0 2 2
3 -2 1 0 1
4 4 4 0
L(1) =
-
1 2 3 4
1 0 3 5 3
2 2 0 2 2
3 -2 1 0 1
4 6 4 4 0
L(2) =
1 2 3 4
1 0 3 3
2 2 0 2 2
3 -2 1 0 1
4 4 4 0
L(1) =
-
1 2 3 4
1 0 3 5 3
2 0 0 2 2
3 -2 1 0 1
4 2 4 4 0
L(3) =
1 2 3 4
1 0 3 5 3
2 2 0 2 2
3 -2 1 0 1
4 6 4 4 0
L(2) =
-
1 2 3 4
1 0 3 5 3
2 0 0 2 2
3 -2 1 0 1
4 2 4 4 0
D = L(4) =
1 2 3 4
1 0 3 5 3
2 0 0 2 2
3 -2 1 0 1
4 2 4 4 0
L(3) =
-
Lema: El algoritmo de Floyd determina los caminos mnimos entre todos los pares de nodos de un grafo orientado sin circuitos.
Cul es la complejidad de algoritmo de Floyd? Cunta memoria requiere?. Cmo podemos hacer si adems de las longitudes queremos
determinar los caminos mnimos? Cmo se puede adaptar para detectar si el grafo tiene
circuitos de longitud negativa?
-
Algoritmo de Floyd (1962)G orientado, detecta circuitos de longitud negativa----------------------------------------------------------------Empezar
L(0)=LPara k desde 1 hasta n hacer
Para i desde 1 hasta n hacerSi l(k-1)ik=, saltar al siguiente valor de i.Si l(k-1)ik+ l(k-1)ki
-
Algoritmo de Dantzig (1966)G orientado, detecta circuitos de longitud negativa-------------------------------------------------------------Empezar
Para k desde 1 hasta n-1 hacerPara i desde 1 hasta k hacer
li,k+1= minijk(li,j+ lj,k+1)lk+1,i= minijk(lk+1,j+ lj,i)
Fint= minijk(lk+1,i+ li,k+1)Si t
-
L =L =D =
1 2 3 4
1 0 3 5 3
2 2 0 2 2
3 -2 1 0 1
4 2 4 4 0
1 2 3 4
1 0 3 3
2 2 0 2 2
3 -2 0 1
4 4 4 0
1 2 3 4
1 0 3 3
2 2 0 2 2
3 -2 0 1
4 4 4 0
1 2 3 4
1 0 3 3
2 2 0 2 2
3 -2 0 1
4 4 4 0
1 2 3 4
1 0 3 5 3
2 2 0 2 2
3 -2 0 1
4 4 4 0
1 2 3 4
1 0 3 5 3
2 2 0 2 2
3 -2 1 0 1
4 4 4 0
1 2 3 4
1 0 3 5 3
2 2 0 2 2
3 -2 1 0 1
4 4 4 0
1 2 3 4
1 0 3 5 3
2 2 0 2 2
3 -2 1 0 1
4 2 4 4 0
-
Lema: El algoritmo de Dantzig determina los caminos mnimos entre todos los pares de nodos de un grafo orientado sin circuitos.
Cul es la complejidad del algoritmo de Dantzig?. Qu diferencia tiene con el algoritmo de Floyd?. Qu
ventajas o desventajas?.
-
Nota: El siguiente tema (prctico 7) fue dado en la terica, pero no est includo todava en esta presentacin:
PERT- CPM
-
Grafos Eulerianos
Def: Un circuito C en un grafo G se llama un circuito euleriano si C pasa pot todos los ejes de G una y slo una vez.
Def: Un grafo euleriano es un grafo que tiene un circuito euleriano.
Teorema (Euler 1736): Un grafo conexo es euleriano si y slo si todos sus nodos tienen grado par.
A partir de la demostracin del teorema de Euler se puede escribir un
algoritmo para construir un circuito euleriano para un grafo que tiene todos sus nodos de grado par.
Cul es la complejidad de este algoritmo?.
-
Def: Un camino euleriano en un grafo G es un camino que pasa por cada eje de G una y slo una vez.
Teorema: Un grafo conexo tiene un camino euleriano si y slo si tiene exactamente dos nodos de grado impar y el resto de los nodos tiene grado par.
Def: Un grafo orientado o digrafo, se dice euleriano si tiene un circuito orientado que pasa por cada eje de G una y slo una vez.
Teorema: Un digrafo conexo es euleriano si y slo si para todo nodo v de G se verfica que din (v) = dout (v)
-
Problema del cartero chino (Guan, 1962)
Dado un grafo G con longitudes asignadas a los ejes queremos encontrar un circuito de longitud mnima entre los que pasan por cada eje de G al menos una vez.
Si G es euleriano, un circuito euleriano es la solucin del problema del cartero chino.
Hay algoritmos polinomiales para el problema del cartero chino cuando G es orientado o no orientado, pero no se conocen algoritmos polinomiales o sea el problema no est computacionalmente resuelto si el grafo es mixto (algunos ejes orientados y otros no).
-
Grafos hamiltonianos
Def: Un grafo se dice hamiltoniano si tiene un circuito que pasa por cada nodo de G una y slo una vez.
No se conocen buenas caracterizaciones para grafos hamiltonianos.
Cmo intentar construir un circuito hamiltoniano?.
No se conocen algoritmos polinomiales para decidir si un grafo es hamiltoniano o no.
-
Teorema: Sea G un grafo conexo. Si existe W V tal que G \ W tiene c componentes conexas con c > | W| entonces G
no es hamiltoniano.
Es cierta la recproca de este teorema?
Teorema (Dirac): Sea G un grafo con n 3 y tal que para todo v V se verifica que d(v) n/2 entonces G es hamiltoniano.
Es cierta la recproca de este teorema?
-
Heurstica para decidir si un grafo es hamiltoniano (Posa)
----------------------------------------------------------------------------EmpezarPoner P = , k=1 , j =0 Mientras sea posible y |P | n hacer elegir j V tal que j sea vecino de k si j P poner P = P { (k,j)}, k = j sino buscar (j,m) X tal que P \ { (j,m)} { (k,j)} sea un camino simple. Poner P = P\ { (j,m)} { (k,j)} k = m Fin FinSi j = 1 return EXITOSino return FRACASOFin
-
Problema del viajante de comercio (TSP)
Dado un grafo G con longitudes asignadas a los ejes queremos determinar un circuito hamiltoniano de longitud mnima.
No se conocen algoritmos polinomiales para resolver el problema del viajante de comercio.
Tampoco