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