Algoritmos y Estructuras de Datos III

Primer cuatrimestre 2014

Algoritmos y Estructuras de Datos III
Primer cuatrimestre 2014

(bienvenidos!)
Programa

1. Algoritmos:
I Definición de algoritmo. Máquina RAM. Complejidad.
Algoritmos de tiempo polinomial y no polinomial. Lı́mite
inferior.
I Técnicas de diseño de algoritmos: divide and conquer,
backtracking, algoritmos golosos, programación dinámica.
I Algoritmos aproximados y algoritmos heurı́sticos.
Programa

2. Grafos:
I Definiciones básicas. Adyacencia, grado de un nodo,
isomorfismos, caminos, conexión, etc.
I Grafos eulerianos y hamiltonianos.
I Grafos bipartitos.
I Árboles: caracterización, árboles orientados, árbol generador.
I Planaridad. Coloreo. Número cromático.
I Matching, conjunto independiente, recubrimiento.
Recubrimiento de aristas y vértices.
Programa
3. Algoritmos en grafos y aplicaciones:
I Representación de un grafo en la computadora: matrices de
incidencia y adyacencia, listas.
I Algoritmos de búsqueda en grafos: BFS, DFS, A*.
I Mı́nimo árbol generador, algoritmos de Prim y Kruskal.
I Algoritmos para encontrar el camino mı́nimo en un grafo:
Dijkstra, Ford, Floyd, Dantzig.
I Planificación de procesos: PERT/CPM.
I Algoritmos para determinar si un grafo es planar. Algoritmos
para coloreo de grafos.
I Algoritmos para encontrar el flujo máximo en una red: Ford y
Fulkerson.
I Matching: algoritmos para correspondencias máximas en
grafos bipartitos. Otras aplicaciones.
Programa

4. Complejidad computacional:
I Problemas tratables e intratables. Problemas de decisión. P y
NP. Máquinas de Türing no determinı́sticas. Problemas
NP-completos. Relación entre P y NP.
I Problemas de grafos NP-completos: coloreo de grafos, grafos
hamiltonianos, recubrimiento mı́nimo de las aristas, corte
máximo, etc.
Bibliografı́a

1. G. Brassard and P. Bratley, Fundamental of Algorithmics,

Prentice-Hall, 1996.
2. F. Harary, Graph theory, Addison-Wesley, 1969.
3. J. Gross and J. Yellen, Graph theory and its applications, CRC
Press, 1999.
4. R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory,
Algorithms, and Applications, Prentice-Hall, 1993.
5. M. Garey and D. Johnson, Computers and intractability: a
guide to the theory of NP- Completeness, W. Freeman and
Co., 1979.
Algoritmos

I ¿Qué es un algoritmo?
I ¿Qué es un buen algoritmo?
I Dados dos algoritmos para resolver un mismo problema, ¿cuál
es mejor?
I ¿Cuándo un problema está bien resuelto?
Complejidad computacional

Definición informal: La complejidad de un algoritmo es una

función que representa el tiempo de ejecución en función del
tamaño de la entrada del algoritmo.
I Complejidad en el peor caso.
I Complejidad en el caso promedio
Complejidad computacional

Definición informal: La complejidad de un algoritmo es una

función que representa el tiempo de ejecución en función del
tamaño de la entrada del algoritmo.
I Complejidad en el peor caso.
I Complejidad en el caso promedio (dijo “promedio”?).
Complejidad computacional

Definición informal: La complejidad de un algoritmo es una

función que representa el tiempo de ejecución en función del
tamaño de la entrada del algoritmo.
I Complejidad en el peor caso.
I Complejidad en el caso promedio (dijo “promedio”?).

Definición formal?
Máquina RAM (modelo de cómputo)

Definición: Máquina de registros + registro acumulador +

direccionamiento indirecto.

Motivación: Modelar computadoras en las que la memoria es

suficiente y donde los enteros involucrados en los cálculos entran
en una palabra.
Máquina RAM (modelo de cómputo)

Definición: Máquina de registros + registro acumulador +

direccionamiento indirecto.

Motivación: Modelar computadoras en las que la memoria es

suficiente y donde los enteros involucrados en los cálculos entran
en una palabra.

I Unidad de entrada: Sucesión de celdas numeradas, cada una

con un entero de tamaño arbitrario.
I Memoria: Sucesión de celdas numeradas, cada una puede
almacenar un entero de tamaño arbitrario.
I Programa no almacenado en memoria (aún ası́ es una
máquina programable!).
Máquina RAM - Instrucciones

I LOAD operando - Carga un valor en el acumulador

I STORE operando - Carga el acumulador en un registro
I ADD operando - Suma el operando al acumulador
I SUB operando - Resta el operando al acumulador
I MULT operando - Multiplica el operando por el acumulador
I DIV operando - Divide el acumulador por el operando
I READ operando - Lee un nuevo dato de entrada → operando
I WRITE operando - Escribe el operando a la salida
I JUMP label - Salto incondicional
I JGTZ label - Salta si el acumulador es positivo
I JZERO label - Salta si el acumulador es cero
I HALT - Termina el programa
Máquina RAM - Operandos

I LOAD = a: Carga en el acumulador el entero a.

I LOAD i: Carga en el acumulador el contenido del registro i.

I LOAD ∗i: Carga en el acumulador el contenido del registro

indexado por el valor del registro i.
Complejidad en la Máquina RAM

I Asumimos que cada instrucción tiene un tiempo de ejecución

asociado.

I Tiempo de ejecución de un algoritmo A:

TA (I ) = suma de los tiempos de ejecución de las instrucciones
realizadas por el algoritmo con la instancia I .

I Complejidad de un algoritmo A:
fA (n) = máxI :|I |=n TA (I )
Complejidad en la Máquina RAM

I Asumimos que cada instrucción tiene un tiempo de ejecución

asociado.

I Tiempo de ejecución de un algoritmo A:

TA (I ) = suma de los tiempos de ejecución de las instrucciones
realizadas por el algoritmo con la instancia I .

I Complejidad de un algoritmo A:
fA (n) = máxI :|I |=n TA (I ) (pero debemos definir |I |!).
Tamaño de una instancia

Definición (incompleta): Dada una instancia I , se define |I |

como el número de sı́mbolos de un alfabeto finito necesarios para
codificar I .

I Depende del alfabeto y de la base!

I Para almacenar n ∈ N, se necesitan dlog2 (n + 1)e dı́gitos
binarios.
I en una base b cualquiera, se necesitan dlogb (n + 1)e dı́gitos.
loga N 1
I Si a y b 6= 1 entonces logb N = loga b = loga b × loga N.
Tamaño de una instancia

I Modelo uniforme: Asumimos que los valores numéricos

dentro de la instancia están acotados de antemano.

I Modelo logarı́tmico: Medimos el tamaño en bits de cada

entero por separado, y no se asume una cota superior de
antemano.
Notación O

Dadas dos funciones f , g : N → R, decimos que:

I f (n) = O(g (n)) si existen c ∈ R+ y n0 ∈ N tales que

f (n) ≤ c g (n) para todo n ≥ n0 .

I f (n) = Ω(g (n)) si existen c ∈ R+ y n0 ∈ N tales que

f (n) ≥ c g (n) para todo n ≥ n0 .

I f (n) = Θ(g (n)) si f = O(g (n)) y f = Ω(g (n)).

Ejemplos

I Búsqueda secuencial: O(n).

I Búsqueda binaria: O(log(n)).
Ejemplos

I Búsqueda secuencial: O(n).

I Búsqueda binaria: O(log(n)).

I Ordenar un arreglo (bubblesort): O(n2 ).

I Ordenar un arreglo (quicksort): O(n2 ) en el peor caso (!).
I Ordenar un arreglo (heapsort): O(n log(n)).
Ejemplos

I Búsqueda secuencial: O(n).

I Búsqueda binaria: O(log(n)).

I Ordenar un arreglo (bubblesort): O(n2 ).

I Ordenar un arreglo (quicksort): O(n2 ) en el peor caso (!).
I Ordenar un arreglo (heapsort): O(n log(n)).

Es interesante notar que O(n log(n)) es la complejidad óptima

para algoritmos de ordenamiento basados en comparaciones (cómo
se demuestra?).
Ejemplo dramático: Cálculo del determinante de una matriz

Recordemos: Si A ∈ Rn×n , se define su determinante por

n
X
det(A) = (−1)j+1 aij det(Aij ),
j=1

donde i ∈ {1, . . . , n} y Aij es la submatriz de A obtenida al

eliminar la fila i y la columna j.
Ejemplo dramático: Cálculo del determinante de una matriz

Recordemos: Si A ∈ Rn×n , se define su determinante por

n
X
det(A) = (−1)j+1 aij det(Aij ),
j=1

donde i ∈ {1, . . . , n} y Aij es la submatriz de A obtenida al

eliminar la fila i y la columna j.

n f (n − 1) + O(n) si n > 1
Complejidad: f (n) =
O(1) si n = 1
Ejemplo dramático: Cálculo del determinante de una matriz

Recordemos: Si A ∈ Rn×n , se define su determinante por

n
X
det(A) = (−1)j+1 aij det(Aij ),
j=1

donde i ∈ {1, . . . , n} y Aij es la submatriz de A obtenida al

eliminar la fila i y la columna j.

n f (n − 1) + O(n) si n > 1
Complejidad: f (n) =
O(1) si n = 1
Complejidad: f (n) = O(n!) (oops!).
Ejemplo dramático: Cálculo del determinante de una matriz

Algoritmo alternativo: Obtener la descomposición LU,

escribiendo PA = LU. Entonces,

det(A) = det(P −1 ) det(L) det(U),

y todos los determinantes del lado derecho son sencillos de calcular.

Ejemplo dramático: Cálculo del determinante de una matriz

Algoritmo alternativo: Obtener la descomposición LU,

escribiendo PA = LU. Entonces,

det(A) = det(P −1 ) det(L) det(U),

y todos los determinantes del lado derecho son sencillos de calcular.

Complejidad: f (n) = O(n3 ) + 3O(n) = O(n3 ) (ta-daaa!).

Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.
Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.

n = 10 n = 20 n = 30 n = 40 n = 50
Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.

n = 10 n = 20 n = 30 n = 40 n = 50
O(n) 0.01 ms 0.02 ms 0.03 ms 0.04 ms 0.05 ms
Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.

n = 10 n = 20 n = 30 n = 40 n = 50
O(n) 0.01 ms 0.02 ms 0.03 ms 0.04 ms 0.05 ms
O(n2 ) 0.10 ms 0.40 ms 0.90 ms 0.16 ms 0.25 ms
Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.

n = 10 n = 20 n = 30 n = 40 n = 50
O(n) 0.01 ms 0.02 ms 0.03 ms 0.04 ms 0.05 ms
O(n2 ) 0.10 ms 0.40 ms 0.90 ms 0.16 ms 0.25 ms
O(n3 ) 1.00 ms 8.00 ms 2.70 ms 6.40 ms 0.12 sg
Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.

n = 10 n = 20 n = 30 n = 40 n = 50
O(n) 0.01 ms 0.02 ms 0.03 ms 0.04 ms 0.05 ms
O(n2 ) 0.10 ms 0.40 ms 0.90 ms 0.16 ms 0.25 ms
O(n3 ) 1.00 ms 8.00 ms 2.70 ms 6.40 ms 0.12 sg
O(n5 ) 0.10 sg 3.20 sg 24.30 sg 1.70 min 5.20 min
Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.

n = 10 n = 20 n = 30 n = 40 n = 50
O(n) 0.01 ms 0.02 ms 0.03 ms 0.04 ms 0.05 ms
O(n2 ) 0.10 ms 0.40 ms 0.90 ms 0.16 ms 0.25 ms
O(n3 ) 1.00 ms 8.00 ms 2.70 ms 6.40 ms 0.12 sg
O(n5 ) 0.10 sg 3.20 sg 24.30 sg 1.70 min 5.20 min
O(2n ) 1.00 ms 1.00 sg 17.90 min 12 dı́as 35 años
Problemas bien resueltos

Definición: Decimos que un problema está bien resuelto si existe

un algoritmo de complejidad polinomial para el problema.

n = 10 n = 20 n = 30 n = 40 n = 50
O(n) 0.01 ms 0.02 ms 0.03 ms 0.04 ms 0.05 ms
O(n2 ) 0.10 ms 0.40 ms 0.90 ms 0.16 ms 0.25 ms
O(n3 ) 1.00 ms 8.00 ms 2.70 ms 6.40 ms 0.12 sg
O(n5 ) 0.10 sg 3.20 sg 24.30 sg 1.70 min 5.20 min
O(2n ) 1.00 ms 1.00 sg 17.90 min 12 dı́as 35 años
O(3n ) 0.59 sg 58 min 6 años 3855 siglos 2 × 108 siglos!
Problemas bien resueltos

Conclusión: Los algoritmos polinomiales se consideran

satisfactorios (cuanto menor sea el grado, mejor), y los algoritmos
supra-polinomiales se consideran no satisfactorios.
Problemas bien resueltos

Conclusión: Los algoritmos polinomiales se consideran

satisfactorios (cuanto menor sea el grado, mejor), y los algoritmos
supra-polinomiales se consideran no satisfactorios.
I Si los tamaños de instancia son pequeños, ¿es tan malo un
algoritmo exponencial?
I ¿Cómo se comparan O(n85 ) con O(1,001n )?
I ¿Puede pasar que un algoritmo de peor caso exponencial sea
eficiente en la práctica? ¿Puede pasar que en la práctica sea el
mejor?
I ¿Qué pasa si no encuentro un algoritmo polinomial?
Técnicas de diseño de algoritmos

I Algoritmos golosos
I Divide and conquer (dividir y conquistar)
I Recursividad
I Programación dinámica
I Backtracking (búsqueda con retroceso)
I Algoritmos probabilı́sticos
Algoritmos golosos

Idea: Construir una solución seleccionando en cada paso la mejor

alternativa, sin considerar (o haciéndolo débilmente) las
implicancias de esta selección.
Algoritmos golosos

Idea: Construir una solución seleccionando en cada paso la mejor

alternativa, sin considerar (o haciéndolo débilmente) las
implicancias de esta selección.

I Habitualmente, proporcionan heurı́sticas sencillas para

problemas de optimización.
I En general permiten construir soluciones razonables, pero
sub-óptimas.
I Sin embargo, en ocasiones nos pueden dar interesantes
sorpresas!
Ejemplo: El problema de la mochila

Datos de entrada:
I Capacidad C ∈ R+ de la mochila (peso máximo).
I Cantidad n ∈ N de objetos.
I Peso pi ∈ R+ del objeto i, para i = 1, . . . , n.
I Beneficio bi ∈ R+ del objeto i, para i = 1, . . . , n.

Problema: Determinar qué objetos debemos incluir en la mochila

sin excedernos del peso máximo C , de modo tal de maximizar el
beneficio total entre los objetos seleccionados.
Ejemplo: El problema de la mochila

Algoritmo(s) goloso(s): Mientras no se haya excedido el peso de

la mochila, agregar a la mochila el objeto i que ...
I ... tenga mayor beneficio bi .
I ... tenga menor peso pi .
I ... maximice bi /pi .
Ejemplo: El problema de la mochila

Algoritmo(s) goloso(s): Mientras no se haya excedido el peso de

la mochila, agregar a la mochila el objeto i que ...
I ... tenga mayor beneficio bi .
I ... tenga menor peso pi .
I ... maximice bi /pi .

¿Qué podemos decir en cuanto a la calidad de las soluciones

obtenidas por estos algoritmos? ¿Qué podemos decir en cuanto a
su complejidad?
Ejemplo: Tiempo de espera total en un sistema

Problema: Un servidor tiene n clientes para atender, y los puede

atender en cualquier orden. Para i = 1, . . . , n, el tiempo necesario
para atender al cliente i es ti ∈ R+ . El objetivo es determinar en
qué orden se deben atender los clientes para minimizar la suma de
los tiempos de espera de los clientes.
Ejemplo: Tiempo de espera total en un sistema

Problema: Un servidor tiene n clientes para atender, y los puede

atender en cualquier orden. Para i = 1, . . . , n, el tiempo necesario
para atender al cliente i es ti ∈ R+ . El objetivo es determinar en
qué orden se deben atender los clientes para minimizar la suma de
los tiempos de espera de los clientes.

Si I = (i1 , i2 , . . . , in ) es una permutación de los clientes que

representa el orden de atención, entonces la suma de los tiempos
de espera es

T = ti1 + (ti1 + ti2 ) + (ti1 + ti2 + ti3 ) + . . .

X n
= (n − k + 1)tik .
k=1
Ejemplo: Tiempo de espera total en un sistema

Algoritmo goloso: En cada paso, atender al cliente pendiente que

tenga menor tiempo de atención.

I Retorna una permutación IGOL = (i1 , . . . , in ) tal que

tij ≤ tij+1 para j = 1, . . . , n − 1.
I ¿Cuál es la complejidad de este algoritmo?
Ejemplo: Tiempo de espera total en un sistema

Algoritmo goloso: En cada paso, atender al cliente pendiente que

tenga menor tiempo de atención.

I Retorna una permutación IGOL = (i1 , . . . , in ) tal que

tij ≤ tij+1 para j = 1, . . . , n − 1.
I ¿Cuál es la complejidad de este algoritmo?
I Este algoritmo proporciona la solución óptima! (cómo se
demuestra?)
Divide and conquer

I Si la instancia I de entrada es pequeña, entonces utilizar un

algoritmo ad hoc para el problema.
I En caso contrario:
I Dividir I en sub-instancias I1 , I2 , . . . , Ik más pequeñas.
I Resolver recursivamente las k sub-instancias.
I Combinar las soluciones para las k sub-instancias para obtener
una solución para la instancia original I .
Ejemplo: Mergesort

Algoritmo divide and conquer para ordenar un arreglo A de n

elementos (von Neumann, 1945).

I Si n es pequeño, ordenar por cualquier método sencillo.

I Si n es grande:
I A1 := primera mitad de A.
I A2 := segunda mitad de A.
I Ordenar recursivamente A1 y A2 por separado.
I Combinar A1 y A2 para obtener los elementos de A ordenados
(apareo de arreglos).
Ejemplo: Mergesort

Algoritmo divide and conquer para ordenar un arreglo A de n

elementos (von Neumann, 1945).

I Si n es pequeño, ordenar por cualquier método sencillo.

I Si n es grande:
I A1 := primera mitad de A.
I A2 := segunda mitad de A.
I Ordenar recursivamente A1 y A2 por separado.
I Combinar A1 y A2 para obtener los elementos de A ordenados
(apareo de arreglos).

Este algoritmo contiene todos los elementos tı́picos de la técnica

divide and conquer.
Ejemplo: Mergesort

Algoritmo divide and conquer para ordenar un arreglo A de n

elementos (von Neumann, 1945).

I Si n es pequeño, ordenar por cualquier método sencillo.

I Si n es grande:
I A1 := primera mitad de A.
I A2 := segunda mitad de A.
I Ordenar recursivamente A1 y A2 por separado.
I Combinar A1 y A2 para obtener los elementos de A ordenados
(apareo de arreglos).

Este algoritmo contiene todos los elementos tı́picos de la técnica

divide and conquer.
Ejemplo: Multiplicación de Strassen

I Sean A, B ∈ Rn×n . El algoritmo estándar para calcular AB

tiene una complejidad de Θ(n3 ).
I Durante muchos años se pensaba que esta complejidad era
óptima.
Ejemplo: Multiplicación de Strassen

I Sean A, B ∈ Rn×n . El algoritmo estándar para calcular AB

tiene una complejidad de Θ(n3 ).
I Durante muchos años se pensaba que esta complejidad era
óptima.

I Sin embargo, Strassen (1969) pateó el tablero. Particionamos:

   
A11 A12 B11 B12
A= , B= .
A21 A22 B21 B22
Ejemplo: Multiplicación de Strassen

Definimos:

M1 = (A21 + A22 − A11 ) (B22 − B12 + B11 )

M2 = A11 B11
M3 = A12 B21
M4 = (A11 − A21 ) (B22 − B12 )
M5 = (A21 + A22 ) (B12 − B11 )
M6 = (A12 − A21 + A11 − A22 ) B22
M7 = A22 (B11 + B22 − B12 − B21 ).
Ejemplo: Multiplicación de Strassen

Definimos:

M1 = (A21 + A22 − A11 ) (B22 − B12 + B11 )

M2 = A11 B11
M3 = A12 B21
M4 = (A11 − A21 ) (B22 − B12 )
M5 = (A21 + A22 ) (B12 − B11 )
M6 = (A12 − A21 + A11 − A22 ) B22
M7 = A22 (B11 + B22 − B12 − B21 ).

Entonces,
 
M2 + M3 M1 + M2 + M5 + M6
AB = .
M1 + M2 + M4 − M7 M1 + M2 + M4 + M5
Ejemplo: Multiplicación de Strassen

I Este algoritmo permite calcular el producto AB en tiempo

O(nlog2 (7) ) = O(n2,81 ) (!).
I Requiere 7 multiplicaciones de matrices de tamaño n/2 × n/2,
en comparación con las 8 multiplicaciones del algoritmo
estándar.
I La cantidad de sumas (y restas) de matrices es mucho mayor.
Ejemplo: Multiplicación de Strassen

I Este algoritmo permite calcular el producto AB en tiempo

O(nlog2 (7) ) = O(n2,81 ) (!).
I Requiere 7 multiplicaciones de matrices de tamaño n/2 × n/2,
en comparación con las 8 multiplicaciones del algoritmo
estándar.
I La cantidad de sumas (y restas) de matrices es mucho mayor.

I El algoritmo asintóticamente más eficiente conocido a la fecha

tiene una complejidad de O(n2,376 ) (Coppersmith y Winograd,
1987).
Backtracking

Idea: Técnica para recorrer sistemáticamente todas las posibles

configuraciones de un espacio asociado a soluciones candidatos de
un problema computacional. Se puede pensar este espacio tiene
forma de árboles dirigidos (o grafos dirigidos en general pero sin
ciclos).
Backtracking

Idea: Técnica para recorrer sistemáticamente todas las posibles

configuraciones de un espacio asociado a soluciones candidatos de
un problema computacional. Se puede pensar este espacio tiene
forma de árboles dirigidos (o grafos dirigidos en general pero sin
ciclos).

I Habitualmente, utiliza un vector a = (a1 , a2 , . . . , ak ) para

representar una solución candidata, cada ai pertenece un
dominio/conjunto ordenado y finito Si .
I Se extienden las soluciones candidatas agregando un elemento
más al final del vector a, las nuevas soluciones candidatas son
sucesores de la anterior.
Backtracking: Esquema General
BT(a, k)

1. Si a es solución
2. entonces solución:=a
3. debe finalizar?:=verdadero
4. sino para cada a0 ∈ Sucesores(a, k)
5. BT(a0 , k + 1)
6. Si debe finalizar?
7. entonces retornar solucion
Backtracking: Esquema General
BT(a, k)

1. Si a es solución
2. entonces solución:=a
3. debe finalizar?:=verdadero
4. sino para cada a0 ∈ Sucesores(a, k)
5. BT(a0 , k + 1)
6. Si debe finalizar?
7. entonces retornar solucion

I solución es una variable global que guarda la solución final.

I debe finalizar? es una variable booleana global que indica que
se encontró o no la solución final, inicialmente tiene valor
falso.
Ejemplo: Problema de las 8 reinas

Ubicar 8 reinas en el tablero de ajedrez (8 × 8) sin que ninguna

”amenace” a otra.
Ejemplo: Problema de las 8 reinas

Ubicar 8 reinas en el tablero de ajedrez (8 × 8) sin que ninguna

”amenace” a otra.
I ¿Cuántas combinaciones del tablero hay que considerar?
Ejemplo: Problema de las 8 reinas

Ubicar 8 reinas en el tablero de ajedrez (8 × 8) sin que ninguna

”amenace” a otra.
I ¿Cuántas combinaciones del tablero hay que considerar?
 
64
8 = 442616536

I Sabemos que cada fila debe tener exactamente una reina.

Entonces ai es la posición (columna que está la reina de la fila
i) o sea podemos usar el vector a = (a1 , . . . , a8 ) representa
una solución candidata.
Ejemplo: Problema de las 8 reinas

Ubicar 8 reinas en el tablero de ajedrez (8 × 8) sin que ninguna

”amenace” a otra.
I ¿Cuántas combinaciones del tablero hay que considerar?
 
64
8 = 442616536

I Sabemos que cada fila debe tener exactamente una reina.

Entonces ai es la posición (columna que está la reina de la fila
i) o sea podemos usar el vector a = (a1 , . . . , a8 ) representa
una solución candidata.

Tenemos ahora 88 = 16777216 combinaciones.

Ejemplo: Problema de las 8 reinas

I Es más, una misma columna debe tener exactamente una

reina!
Ejemplo: Problema de las 8 reinas

I Es más, una misma columna debe tener exactamente una

reina!

Se reduce a 8! = 40320 combinaciones.

Ejemplo: Problema de las 8 reinas

I Es más, una misma columna debe tener exactamente una

reina!

Se reduce a 8! = 40320 combinaciones.

I ¿Cómo chequear un vector a es una solución?

Ejemplo: Problema de las 8 reinas

I Es más, una misma columna debe tener exactamente una

reina!

Se reduce a 8! = 40320 combinaciones.

I ¿Cómo chequear un vector a es una solución?

ai − aj 6∈ {i − j, 0, j − i}, ∀i, j ∈ {1, . . . , 8} e i 6= j.

Ejemplo: Problema de las 8 reinas

I Es más, una misma columna debe tener exactamente una

reina!

Se reduce a 8! = 40320 combinaciones.

I ¿Cómo chequear un vector a es una solución?

ai − aj 6∈ {i − j, 0, j − i}, ∀i, j ∈ {1, . . . , 8} e i 6= j.

I Ahora estamos en condición de implementar un algoritmo

para resolver el problema!
Ejemplo: Problema de las 8 reinas

I Es más, una misma columna debe tener exactamente una

reina!

Se reduce a 8! = 40320 combinaciones.

I ¿Cómo chequear un vector a es una solución?

ai − aj 6∈ {i − j, 0, j − i}, ∀i, j ∈ {1, . . . , 8} e i 6= j.

I Ahora estamos en condición de implementar un algoritmo

para resolver el problema!
I ¿Cómo generalizar para el problema de n reinas?
Programación Dinámica

I Es aplicada tı́picamente a problemas de optimización, donde

puede haber muchas soluciones, cada una tiene un valor
asociado y prentendemos obtener la solución con valor
óptimo. Al igual que ”dividir y conquistar”, el problema es
dividida en subproblemas de tamanõs menores que son más
fácil de resolver, una vez resuletos esto subproblemas, se
combinan las soluciones obtenidas para generar la solución del
problema original.
Programación Dinámica

I Es aplicada tı́picamente a problemas de optimización, donde

puede haber muchas soluciones, cada una tiene un valor
asociado y prentendemos obtener la solución con valor
óptimo. Al igual que ”dividir y conquistar”, el problema es
dividida en subproblemas de tamanõs menores que son más
fácil de resolver, una vez resuletos esto subproblemas, se
combinan las soluciones obtenidas para generar la solución del
problema original.
I Es bottom up y no es recursivo.
Programación Dinámica

I Es aplicada tı́picamente a problemas de optimización, donde

puede haber muchas soluciones, cada una tiene un valor
asociado y prentendemos obtener la solución con valor
óptimo. Al igual que ”dividir y conquistar”, el problema es
dividida en subproblemas de tamanõs menores que son más
fácil de resolver, una vez resuletos esto subproblemas, se
combinan las soluciones obtenidas para generar la solución del
problema original.
I Es bottom up y no es recursivo.
I Principio de optimalidad: un problema de optimización
satisface el principio de optimalidad de Bellman si en una
sucesión óptima de decisiones o elecciones, cada subsucesión
es a su vez óptima. (es condición necesaria para poder usar la
técnica de programación dinámica).
Programación Dinámica: ejemplos

n


I Coeficientes binomiales k
I Producto de matrices
I Subsecuencia creciente máxima
I Comparación de secuencias de ADN
I Arbol de búsqueda óptimo
I etc.
Coeficientes binomiales

   
n n−1 n−1


k = k−1 + k
Coeficientes binomiales

   
n n−1 n−1


k = k−1 + k

I Triángulo de Pascal
Coeficientes binomiales

   
n n−1 n−1


k = k−1 + k

I Triángulo de Pascal
I Función recursiva (”dividir y conquistar”)
Coeficientes binomiales

   
n n−1 n−1


k = k−1 + k

I Triángulo de Pascal
n


I Función recursiva (”dividir y conquistar”) complejidad Ω( k )
Coeficientes binomiales

   
n n−1 n−1


k = k−1 + k

I Triángulo de Pascal
n


I Función recursiva (”dividir y conquistar”) complejidad Ω( k )
I Programación dinámica
Coeficientes binomiales

   
n n−1 n−1


k = k−1 + k

I Triángulo de Pascal
n


I Función recursiva (”dividir y conquistar”) complejidad Ω( k )
I Programación dinámica complejidad O(nk)
Multiplicación de n matrices

M = M1 × M2 × . . . Mn
Multiplicación de n matrices

M = M1 × M2 × . . . Mn

Por la propiedad asociativa del producto de matrices esto puede

hacerse de muchas formas. Queremos determinar la que minimiza
el número de operaciones necesarias. Por ejemplo: las dimensiones
de A es de 13 × 5, B de 5 × 89, C de 89 × 3 y D de 3 × 34.
Tenemos
I ((AB)C )D requiere 10582 multiplicaciones.
I (AB)(CD) requiere 54201 multiplicaciones.
I (A(BC ))D requiere 2856 multiplicaciones.
I A((BC )D) requiere 4055 multiplicaciones.
I A(B(CD)) requiere 26418 multiplicaciones.
Subsecuencia creciente más larga

Determinar la subsecuencia creciente más larga de una sucesión de

números.
I Ejemplo: S = {9, 5, 2, 8, 7, 3, 1, 6, 4}
I Las subsecuencias más largas son {2, 3, 4} o {2, 3, 6}
Comparación de secuencias de ADN

Una secuencia de ADN se representa con una cadena de

caracteres, por ejemplo: GACGGATTAG.
Comparación de secuencias de ADN

Una secuencia de ADN se representa con una cadena de

caracteres, por ejemplo: GACGGATTAG.
I ¿Cuándo 2 secuencias (cadenas de caracteres) son parecidas?
I Por ejemplo GACGGATTAG y GATCGGAATAG
Comparación de secuencias de ADN

Una secuencia de ADN se representa con una cadena de

caracteres, por ejemplo: GACGGATTAG.
I ¿Cuándo 2 secuencias (cadenas de caracteres) son parecidas?
I Por ejemplo GACGGATTAG y GATCGGAATAG
I Alineamiento: asignar valor de coincidencias, diferencias y
gaps.
I Por ejemplo:
GA–CGGATTAG
GATCGGAATAG

coincidencia = +1
diferencia = −1 Puntaje= 9 × 1 + 1×(−1)+1×(−2)= 6
gap = −2
Algoritmos probabilı́sticos

I Cuando un algoritmo tiene que hacer una elección a veces es

preferible elegir al azar en vez de gastar mucho tiempo
tratando de ver cual es la mejor elección.
I Algoritmos al azar para problemas numéricos: siempre da una
respuesta aproximada. + tiempo proceso ⇒ + precisión (por
ejemplo cálculo de integral)
I Algoritmos de Monte Carlo: siempre da una respuesta exacta
no garantizada. + tiempo proceso ⇒ + probabilidad de
acertar (por ejemplo determinar la existencia de un elemento
mayor en un arreglo).
Algoritmos probabilı́sticos

I Algoritmos Las Vegas: la respuesta siempre es correcta pero

puede no darla. + tiempo proceso ⇒ + probabilidad de
obtener la respuesta (por ejemplo problema de 8 reinas)
I Algoritmos Sherwood : randomiza un algoritmo determinı́stico
donde hay una gran diferencia entre el peor caso y caso
promedio. Elimina la diferencia entre buenas y malas
instancias (quicksort).
Heurı́sticas

I Dado un problema Π , un algoritmo heurı́stico es un algoritmo

que intenta obtener soluciones para el problema que intenta
resolver pero no necesariamente lo hace en todos los casos.
I Sea Π un problema de optimización, I una instancia del
problema, x ∗ (I ) el valor óptimo de la función a optimizar en
dicha instancia. Un algoritmo heurı́stico obtiene una solución
con un valor que se espera sea cercano a ese óptimo pero no
necesariamente el óptimo.
I Si H es un algoritmo heurı́stico para un problema de
optimización llamamos x H (I ) al valor que devuelve la
heurı́stica.
Algoritmos aproximados

Decimos que H es un algoritmo  – aproximado para el problema Π

si para algún  > 0

|x H (I ) − x ∗ (I )| ≤ |x ∗ (I )|
Algoritmos con certificados

I ¿Cómo podemos saber si la respuesta o el resultado de un

algoritmo es correcto o no?
I Algoritmos que ordenan un arreglo
I Algoritmos que multiplican matrices
I Algoritmos que determinan un número natural es o no
compuesto
Algoritmos con certificados

I ¿Cómo podemos saber si la respuesta o el resultado de un

algoritmo es correcto o no?
I Algoritmos que ordenan un arreglo
I Algoritmos que multiplican matrices
I Algoritmos que determinan un número natural es o no
compuesto
I Certificados y algoritmos de verificación o autenticación