INFB8071 - ANÁLISIS DE

ALGORITMOS
Departamento de Informática y Computación -
Universidad Tecnológica Metropolitana de Chile

Profesor: Luis Corral

2-2025
 Índice general

Índice general i

1 Introducción 1

2 Fundamentos 3
2.1. Notación asintótica . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Recurrencias en general . . . . . . . . . . . . . . . . . . . . . . 5
2.3. Recurrencias divide and conquer . . . . . . . . . . . . . . . . . 5
2.4. Recurrencias reduce and conquer . . . . . . . . . . . . . . . . 6
2.5. Método maestro para resolver recurrencias . . . . . . . . . . . 7
2.6. Modelo de computación WRAM . . . . . . . . . . . . . . . . . 8

3 Dividir y conquistar 9
3.1. Búsqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2. Merge sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3. El par de puntos más cercano . . . . . . . . . . . . . . . . . . 12
3.4. Algoritmo de Strassen . . . . . . . . . . . . . . . . . . . . . . . 14
3.5. Envoltura convexa . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Algoritmos codiciosos 19
4.1. Selección de actividades . . . . . . . . . . . . . . . . . . . . . 19
4.2. Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . 21
4.3. Códigos de Huffman . . . . . . . . . . . . . . . . . . . . . . . 24

5 Algoritmos de ordenamiento 28
5.1. Insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.2. Quick sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3. Heap sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.4. Cota inferior para el ordenamiento . . . . . . . . . . . . . . . 34
5.5. Counting sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.6. Radix sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

6 Programación dinámica 38
6.1. SRTBOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
6.2. Corte de una varilla . . . . . . . . . . . . . . . . . . . . . . . . 39
6.3. Bowling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

I
 Índice general

6.4. Parentización . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
6.5. Subsecuencia común más larga . . . . . . . . . . . . . . . . . . 46
6.6. Suma de subconjuntos . . . . . . . . . . . . . . . . . . . . . . 48

7 Algoritmos en grafos 50
7.1. Grafos direccionados y no direccionados . . . . . . . . . . . . . 50
7.2. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.3. Búsqueda en anchura . . . . . . . . . . . . . . . . . . . . . . . 51
7.4. Búsqueda en profundidad . . . . . . . . . . . . . . . . . . . . . 53
7.5. Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . 54
7.6. Algoritmo de Bellman-Ford . . . . . . . . . . . . . . . . . . . . 57

8 Las clases P, NP, NP-C, NP-H 59

8.1. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
8.2. La clase P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
8.3. La clase NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
8.4. La clase NP-H y NP-C . . . . . . . . . . . . . . . . . . . . . . 60
8.5. Reducciones y NP-Completitud . . . . . . . . . . . . . . . . . 60
8.6. El problema SAT y 3-SAT . . . . . . . . . . . . . . . . . . . . 61
8.7. 3-SAT y la suma de subconjuntos . . . . . . . . . . . . . . . . 62
8.8. 3-SAT y el problema clique . . . . . . . . . . . . . . . . . . . . 63
8.9. Clique y vertex cover . . . . . . . . . . . . . . . . . . . . . . . 65

9 Algoritmos para machine learning 66

9.1. K vecinos más cercanos . . . . . . . . . . . . . . . . . . . . . . 66
9.2. Gradiente descendiente . . . . . . . . . . . . . . . . . . . . . . 68
9.3. Backpropagation . . . . . . . . . . . . . . . . . . . . . . . . . 69

Bibliografía 72

II
 CAPÍTULO 1

Introducción

Este resumen está basado en el libro de Cormen et al. (2022) (abreviado

CLRS) para el curso INFB6061 Análisis de Algoritmos del Departamento de
Informática y Computación de la Universidad Tecnológica Metropolitana de
Chile. Este curso entrega una completa introducción al estudio de los algoritmos
computacionales y las técnicas más usadas para diseñarlos y analizar su tiempo
de ejecución. Se estudiarán en detalle múltiples algoritmos, principalmente a
partir de ejemplos. Para el desarrollo completo del curso, se consideran como
material visto en cursos anteriores los fundamentos del álgebra, cálculo integral,
diferencial y una introducción a la programación (en Python o C) incluyendo el
concepto de funciones recursivas.
Un algoritmo es un procedimiento computacional bien definido que toma
un valor o un conjunto de valores de entrada y los convierte en un valor o un
conjunto de valores de salida en un tiempo finito. El algoritmo es la serie de
pasos que transforma la entrada en la salida. Para un algoritmo definiremos
el tipo de valores de entrada, usualmente de rango y tamaño indefinido, y nos
aseguraremos que se obtengan las salidas correctas para todos los posibles casos
en el menor tiempo posible ignorando en gran parte el uso de memoria. Ya
que el curso no contempla todo el material de la bibliografía de referencia, es
recomendable realizar la lectura del presente documento antes de la cátedra y
luego recurrir a la referencia en caso de desear profundizar en el contenido.
El capítulo 2 incluye fundamentos matemáticos de la notación asintótica,
solución de recurrencias en general, divide and conquer, reduce and conquer y
el método maestro para resolver recurrencias, finalizando con la definición del
modelo de computación WRAM utilizado durante todo el curso. Las secciones
siguientes corresponden a estrategias de análisis y diseño de algoritmos. El
capítulo 3 dividir y conquistar, incluye el análisis de los algoritmos de búsqueda
binaria y merge sort, continuando con el estudio de los problemas del par de
puntos más cercano, la multiplicación de matrices a partir del algoritmo de
Strassen y la envoltura convexa de puntos en el plano. El capítulo 4 algoritmos
codiciosos, estudia el problema de selección de actividades, el algoritmo de
Kruskal y los códigos de Huffman. El capítulo 5 algoritmos de ordenamiento,
incluye el análisis de los algoritmos de insertion sort, quick sort, heap sort, la
cota inferior para el ordenamiento, counting sort y radix sort. El capítulo 6
programación dinámica, estudia la solución de distintos problemas utilizando
el paradigma SRTBOT aplicado al corte de una varilla, un juego de bowling,
el problema de parentización, la subsecuencia común más larga y la suma de
subconjuntos. El capítulo 7 algoritmos en grafos, estudia la solución al problema

1
de caminos más cortos desde un origen mediante la búsqueda en profundidad
y anchura, como también al problema de caminos de menor peso desde un
origen con valores positivos mediante el algoritmo de Dijkstra y con valores
negativos mediante el algoritmo de Bellman-Ford. El capítulo 8 las clases P,
NP, NP-C, NP-H, define las distintas clases de complejidad, la clasificación de
problemas NP-Hard y NP-Completo y distintas reducciones de problemas. El
capítulo 9 algoritmos para machine learning, se presenta el algoritmo de los K
vecinos más cercanos para el problema de clasificación, el algoritmo de gradiente
descendiente para la minimización de funciones convexas y el algoritmo de
backpropagation para el entrenamiento de redes neuronales.
Existen referencias adicionales en los pie de página a sitios web de interés
con material adicional.

2
 CAPÍTULO 2

Fundamentos

Para diseñar y analizar algoritmos, es necesario describir cómo se desarrollan

y también cómo operan. Para esto es necesario contar con un conjunto de
herramientas matemáticas para demostrar que un algoritmo se ejecuta de
manera correcta y que lo hace de manera eficiente. Las siguientes definiciones
matemáticas servirán para el análisis y para comprender las técnicas de diseño
que se estudiarán en futuras sesiones.

2.1. Notación asintótica

La notación asintótica nos permite medir de forma rápida el comportamiento
de una función T (n) a medida que n aumenta. En general utilizaremos el término
T (n) para referirnos al tiempo de ejecución de un algoritmo y n (n ∈ N) para
determinar el tamaño de un problema. Por ejemplo, diremos que “un algoritmo
crece a una razón significativamente más lenta o rápida que otro”. En lenguaje
más coloquial diremos que un algoritmo es más rápido (y mejor) que otro.
¿Por qué utilizar notación asintótica? El tiempo efectivo de cómputo (en
segundos) depende del hardware donde se ejecute el algoritmo. En notación
asintótica daremos un cota (generalmente superior) de crecimiento de un
algoritmo.

60 a
log(n)
n
n log(n)
40 n2
an

20

0
0 2 4 6 8
Figura 2.1: Crecimiento asintótico de distintas funciones.

3
 2.1. Notación asintótica

Notación big Oh
La notación O(g(n)) nos da un límite superior para la razón de crecimiento
de una función T (n). Para dos funciones no negativas T (n) y g(n), diremos que:

T (n) = O(g(n)) ó T (n) ≤ O(g(n)) (2.1)

si y sólo si:
T (n)
lı́m < ∞. (2.2)
n→∞ g(n)

Se define formalmente T (n) = O(g(n)) como: existen dos constantes c y n0

tal que 0 ≤ T (n) ≤ cg(n) para todo n ≥ n0 .

Notación big Omega

La notación Ω(g(n)) nos da un límite inferior para la razón de crecimiento
de una función T (n). Para dos funciones no negativas T (n) y g(n), diremos que:

T (n) = Ω(g(n)) ó T (n) ≥ Ω(g(n)) (2.3)

si y sólo si:
T (n)
lı́m > 0. (2.4)
n→∞ g(n)
Se define formalmente T (n) = Ω(g(n)) como: existen dos constantes c y n0
tal que 0 ≤ cg(n) ≤ T (n) para todo n ≥ n0 .

Notación big Theta

La notación Θ(g(n)) nos da un límite inferior y superior para la razón de
crecimiento de una función T (n). Para dos funciones no negativas T (n) y g(n),
diremos que:
T (n) = Θ(g(n)) (2.5)
si y sólo si:
T (n)
0 < lı́m < ∞.
n→∞ g(n)
Se define formalmente T (n) = Θ(g(n)) como: existen tres constantes c1 , c2
y n0 tal que 0 ≤ c1 g(n) ≤ T (n) ≤ c2 g(n) para todo n ≥ n0 .

T (n)
T (n) T (n)

T (n) T (n) T (n)

Figura 2.2: Notaciones O(n), Ω(n) y Θ(n) Cormen et al. (2022).

4
 2.2. Recurrencias en general

2.2. Recurrencias en general

Utilizaremos las recurrencias para analizar algoritmos que se implementan
mediante programas con funciones recursivas. Nos interesa obtener una solución
cerrada, de la forma O(g(n)), para una recurrencia algorítmica. Definiremos
una recurrencia algorítmica si para un umbral lo suficientemente grande n0 > 0
se cumplen las siguientes propiedades:

1. Para todo n < n0 se tiene T (n) = Θ(1) (tiempo constante).

2. Para todo n > n0 , cada camino de la recursión termina en un caso base
en un número finito de repeticiones.
Nos enfocaremos en las recurrencias del tipo divide and conquer
T (n) = aT (n/b) + f (n) y reduce and conquer T (n) = aT (n − b) + f (n), cada
una con distintos métodos para obtener soluciones de forma cerrada.

2.3. Recurrencias divide and conquer

Una recurrencia de la forma T (n) = aT (n/b) + f (n), representa un algoritmo
que en cada etapa de la recursión, realiza a trabajos donde el tamaño del
problema n se reduce en razón b más un factor f (n). Tomemos como ejemplo
la recurrencia T (n) = 2T (n/2) + n, que realiza dos trabajos de tamaño n/2
más un factor n en cada iteración. Para un tamaño del problema n = 8, la
tercera iteración reducirá el problema a un tamaño mínimo igual a uno, donde
el problema será resuelto como un caso base. Para obtener la solución de forma
cerrada T (n) = O(g(n)) podemos utilizar distintas metodologías.

Árbol de recursión
En un árbol de recursión, cada nodo representa el costo de cada subproblema
en el conjunto de llamadas recursivas. Cada nivel tiene a ramas por cada nodo,
con un total de logb (n) niveles. Se suman los costos en cada nivel y el costo final
T (n) corresponde a la suma de todos los costos por nivel. Así, para la recurrencia
T (n) = 2T (n/2) + n, cada nivel l divide el problema en 2l (bl ) trabajos de n/2l
(costo por nivel n) y cada nodo genera a = 2 ramas en el nivel siguiente.

n nivel l = 0

n n
2 2 costo n - nivel l = 1

n n n n ..
4 4 4 4 costo n .
.. .. .. .. .. .. .. .. costo n - nivel l = logb n
. . . . . . . .
Figura 2.3: Árbol de recursión.

Finalmente T (n) = O(n log(n)) corresponde al costo por nivel n multiplicado

por la altura del árbol log2 (n) (para cualquier base k, logk (n) = O(log(n))).

5
 2.4. Recurrencias reduce and conquer

Método de sustitución
El método de sustitución requiere obtener una solución (por ejemplo desde
un árbol de recursión) y comprobar la exactitud mediante inducción matemática,
lo cual permite obtener una solución más fiable. En general se obtiene la solución
en dos pasos:

1. Seleccionar la forma de la solución utilizando constantes simbólicas.

2. Utilizar inducción para mostrar que la solución funciona y encontrar las
restricciones.
A partir de la solución del árbol de recursión para la expresión
T (n) = 2T (n/2) + n podemos definir un predicado (una formulación que puede
ser verdadera o falsa) como P (n) := T (n) ≤ O(n log(n)) para una constante c.
El paso inductivo T (n) ≤ c(n log(n)) requiere la sustitución de la solución en la
recurrencia y luego verificar el resultado.

T (n) ≤ 2c((n/2) log(n/2)) + n

..
. ≤ cn log(n) − c log(2) + n (2.6)
..
. ≤ O(n log(n)).

Método de Akra-Bazzi
El método de Akra-Bazzi resuelve recurrencias de la forma (más complejas
que la forma general):
k
X
T (n) = f (n) + ai T (bi n). (2.7)
i=1

La solución se obtiene con:

! k
Z n
f (x) X
T (n) = O np + np dx , ai (bi )p = 1 (2.8)
1 xp+1 i=1

donde ai > 0, 0 < bi < 1 y |f ′ (n)| < xc (f (n) es polinomial). Para la recurrencia
T (n) = 2T (n/2) + n se obtiene k = 1, a1 = 2, b1 = 1/2, p = 1, |f ′ (n)| < xc
(f (n) = n es un polinomio), la integral reulta en log(n) (al sustituir x = n)
dando como resltado T (n) = O(n log(n)).

2.4. Recurrencias reduce and conquer

Antes de pasar a la forma general de recurrencias reduce and conquer
T (n) = aT (n − b) + f (n), podemos analizar una versión más general de
recurrencias lineales:
d
X
T (n) − ai T (n − i) = f (n) (2.9)
i=1

6
 2.5. Método maestro para resolver recurrencias

Solución mediante polinomios

Podemos obtener la solución T (n) = αn para una recurrencia lineal de orden
d expandida T (n) − a1 T (n − 1) − a2 T (n − 2) − . . . − ad T (n − d) = 0 en el caso
homogéneo f (n) = 0, como un polinomio αd − a1 αd−1 − a2 αd−2 − . . . − ad = 0.
Para resolver esta relación se utilizan las raíces αd y las constantes cd con la
forma:

T (n) = c1 α1n + c2 α2n + . . . + cn αdn (2.10)

Para la recurrencia T (n) = 2T (n − 1) + 1 el polinomio de grado d = 1
tiene como resultado α1 = 2, por lo que la solución homogénea corresponde a
T (n) = c1 2n . En general se obtendrá un sistema con d ecuaciones que requiere
de d condiciones de borde, las cuales se obtienen del análisis del algoritmo
desde donde se obtiene la recurrencia. Para el ejemplo T (n) = 2T (n − 1) + 1
con condición de borde T (1) = 1 se obtiene la solución c1 = 1 obteniendo como
resultado final T (n) = O(2n ).

2.5. Método maestro para resolver recurrencias

Además del método de Akra-Bazzi que permite obtener soluciones cerradas de
forma matemática y directa, existe el método maestro para resolver recurrencias
del tipo divide and conquer T (n) = aT (n/b) + f (n) y reduce and conquer
T (n) = aT (n − b) + f (n). Para las recurrencias del tipo divide and conquer
tenemos un método maestro general que permite obtener soluciones cerradas
con cotas inferiores y superiores T (n) = Θ(g(n)).


log (a)
Θ(n b )
 si f (n) = O(nlogb (a)−ϵ )
T (n) = Θ(nlogb (a) logk+1 (n)) si f (n) = Θ(nlogb (a) logk (n)) (2.11)

Θ(f (n)) si f (n) = Ω(nlogb (a)+ϵ )


para k ≥ 0 y ϵ > 0. Además, para el caso f (n) = Ω(nlogb (a)+ϵ ) se debe cumplir
con la condición de regularidad af (n/b) ≤ cf (n) para una constante c < 1 y
cualquier n lo suficientemente grande. Una versión simplificada permite obtener
soluciones cerradas con cotas superiores para las recurrencias del tipo divide
and conquer. Con a > 0 y b > 1, si f (n) está en O(nm ) para m ≥ 0:

m
O(n )
 si m > logb (a)
m
T (n) = O(n log(n)) si m = logb (a) (2.12)

O(nlogb (a) ) si m < logb (a)


De manera similar, existe una versión que permite obtener soluciones cerradas
con cotas superiores para las recurrencias del tipo reduce and conquer. Con
a > 0 y b > 0, si f (n) está en O(nm ) para m ≥ 0:

m
O(n )
 si a < 1
T (n) = O(nm+1 ) si a = 1 (2.13)
 m n/b
O(n a ) si a > 1


7
 2.6. Modelo de computación WRAM

2.6. Modelo de computación WRAM

Para poder analizar en detalle el costo temporal de un algoritmo, debemos
saber cuánto tiempo le toma a nuestro modelo computacional realizar
operaciones simples. Para esto, utilizaremos el modelo Word-RAM (WRAM)
de w-bits. El modelo consta de un arreglo de acceso aleatorio de direcciones de
memoria (adresses o words) con un procesador que puede operar sobre estos
valores. Una dirección de memoria es una secuencia de de w-bits que representa
el conjunto de {0, 1, . . . , 2w − 1} valores enteros. De la misma forma podemos
almacenar valores positivos, negativos, con y sin decimales pero dependiendo
del formato que utilicemos la cantidad será menor a 2w − 1. El modelo WRAM
puede realizar operaciones binarias básicas en dos direcciones de memoria
en tiempo constante O(1), incluyendo la suma, resta, multiplicación, división
entera, módulo, operaciones bit-a-bit y comparaciones binarias. Adicionalmente,
a partir de una dirección de memoria a, el modelo puede leer o escribir en la
dirección de memoria a en tiempo constante. Así, podemos definir el tamaño del
problema como una cantidad n de valores almacenados en distintas direcciones
de memoria, para lo cual es necesario un modelo de w > log2 (n) bits (para
computadores modernos en sistemas de 64-bits el tamaño del problema tiene
como máximo 1010 GB).

8
 CAPÍTULO 3

Dividir y conquistar

En la estrategia dividir y conquistar el problema es resuelto de manera

recursiva. Cuando el problema es lo suficientemente pequeño, su solución se
encuentra en el caso base. Se utiliza la recursión en tres pasos:
1. Dividir: se divide el problema en uno o más subproblemas de menor
tamaño pero que mantienen la forma del problema.
2. Conquistar: resolver los subproblemas de manera recursiva.
3. Combinar: las soluciones a los subproblemas se combinan para obtener
un resultado final.

3.1. Búsqueda binaria

Un algoritmo que tiene muchas aplicaciones es la búsqueda de un valor
en un arreglo de números. A partir de un arreglo A = [a0 , a2 , . . . , an−1 ] de n
elementos se desea obtener la posición de un valor x, es decir el índice i donde
x = A[i] o i = None si el elemento x no se encuentra en el arreglo A. La rutina
LINEAR-SEARCH soluciona el problema de manera exhaustiva.

1 LINEAR-SEARCH(A, n, x)
2 i = 0
3 while i < n and A[i] ̸= x
4 i = i + 1
5 if i > n - 1
6 return None
7 else
8 return i

Un análisis simple (para más detalles se recomienda la página 48 de CLRS

sobre “Loop invariants”) permite verificar que esta solución tiene tiempo de
ejecución T (n) = O(n). La justificación para la cota superior es que en el peor
caso, que el elemento x no se encuentre en el arreglo A o que este en la última
posición i = n − 1, se realizaran n iteraciones.
Para mejorar este tiempo de ejecución se debe ordenar los datos de mayor a
menor (luego se estudiarán los algoritmos de ordenamiento) y luego se aplica
la estrategia dividir y conquistar. La idea es escoger un valor pivote inicial

9
 3.1. Búsqueda binaria

correspondiente al índice ⌊(p + r)/2⌋, donde p y r son los índices del primer
y último elemento del arreglo, y luego verificar recursivamente si x es igual,
mayor o menor que el pivote. Si es mayor, se puede estar seguro (ya que el
arreglo está ordenado) que de encontrarse x en A debe estar entre los índices
⌊(p + r)/2⌋ + 1 y r. Por el contrario, si x es menor que el pivote, debe estar
entre los índices p y ⌊(p + r)/2⌋ − 1. En cada etapa de la recursión (donde la
nueva llamada a la función actualiza los valores de p y r), si x es igual al pivote
se retorna el índice del pivote (similar a un caso base) y en el caso de que el
valor no se encuentre en el arreglo el subproblema corresponde a un arreglo
vacío. La rutina BINARY-SEARCH implementa el algoritmo recursivo.

1 BINARY-SEARCH(A, x, p, r)
2 if p > r
3 return None
4 mid = floor((p + r) / 2)
5 if x == A[mid]
6 return mid
7 elseif x > A[mid]
8 return BINARY-SEARCH(A, x, mid + 1, r)
9 else
10 return BINARY-SEARCH(A, x, p, mid - 1)

El arreglo se divide en un problema de n/2 (la otra mitad del arreglo se

descarta) y la etapa de conquistar corresponde al cálculo y verificación de
manera recursiva del valor pivote que termina el algoritmo (si se encontró el
valor) o None (no se encontró el valor). En este caso no es necesario combinar el
resultado. El cálculo y verificación del valor pivote (parte no recursiva) se realiza
en tiempo constante (solo sumas, divisiones y comparaciones binarias << n).
De este análisis se puede obtener la recurrencia T (n) = T (n/2) + O(1) cuya
solución (mediante método maestro) corresponde a T (n) = O(log(n)). Este
resultado se puede comprobar mediante el árbol de recursión, donde se aprecia
un cálculo de tiempo constante realizado O(log(n)) veces (la altura del árbol).

n → O(1) - nivel l = 0

{} ⌊n/2⌋ → O(1) - nivel l = 1

{} {} {} ⌊n/4⌋ → O(1) - nivel l = 2

{} {} {} {} {} {} {} ⌊n/2l ⌋ → O(1) - nivel l = log2 (n)

Figura 3.1: Árbol de recursión de la búsqueda binaria.

En la Figura 3.2 se aprecia el árbol de recursión para el arreglo

A = [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18] y el valor x = 8. Notar que
para x = 9 la rutina BINARY-SEARCH retornara None.

10
 3.2. Merge sort

[1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18] O(1) - nivel 0

[1, 2, 3, 4, 5, 6, 7, 8] [] O(1) - nivel 1

[] [5, 6, 7, 8] [] [] O(1) - nivel 2

[] [] [] [7, 8] [] [] [] [] O(1) - nivel 3

[] [] [] [] [] [] [] [8] [] [] [] [] [] [] [] [] O(1) - nivel log2 n

Figura 3.2: Ejemplo de un árbol de recursión.

Si el arreglo no está ordenado, el tiempo de ordenamiento (tiempo lineal

O(n) en el mejor de los casos) debe sumarse al de la búsqueda binaria.

3.2. Merge sort

En un problema de ordenamiento, se desea obtener un arreglo de salida
donde los elementos se encuentran posicionados respecto a su índice de
manera monotónicamente incremental. Formalmente diremos que a partir
de un arreglo A = [a0 , a1 , . . . , an−1 ] de n elementos, se desea obtener una
permutación A′ = [a′0 , a′1 , . . . , a′n−1 ] donde a′0 ≤ a′1 ≤ · · · ≤ a′n−1 . El algoritmo
merge-sort divide el arreglo en dos subarreglos de tamaño n/2 mediante un
pivote igual al utilizado en la búsqueda binaria ⌊(p + r)/2⌋ y utilizando llamadas
recursivas para disminuir el tamaño del problema. En la etapa de conquistar
cada subarreglo es dividido en la mitad de elementos que la llamada anterior
hasta llegar al caso base de solo un elemento. La etapa de combinación, posiciona
los elementos de cada subproblema en el arreglo de manera ordenada. La Figura
3.3 muestra un ejemplo para el arreglo A = [3, 9, 10, 1, 8, 7, 5, 2].

n 3 9 10 1 8 7 5 2

n/2 3 9 10 1 8 7 5 2
Dividir

n/4 3 9 10 1 8 7 5 2

n/8 3 9 10 1 8 7 5 2

O(n) 3 9 1 10 7 8 2 5
Combinar

O(n) 1 3 9 10 2 5 7 8

O(n) 1 2 3 5 7 8 9 10

Figura 3.3: Ejemplo de cálculo para MERGE-SORT.

11
 3.3. El par de puntos más cercano

El algoritmo consta de dos rutinas. La rutina MERGE, toma como entrada el

arreglo A y los índices p y r para posicionar los elementos ordenados en cada
subproblema utilizando arreglos auxiliares. La rutina completa MERGE-SORT
realiza las llamadas recursivas, la llamada a la rutina MERGE y el caso base (p
= r). Las líneas 8 y 9 de la rutina MERGE concatena cada subproblema en los
arreglos L y R con un valor ∞.

1 MERGE-SORT(A, p, r):
2 if p < r
3 q = floor((p+r)/2)
4 MERGE-SORT(A, p, q)
5 MERGE-SORT(A, q+1, r)
6 MERGE(A, p, q, r)

7 MERGE(A, p, q, r)
8 L = CONCAT(A[p:q], ∞)
9 R = CONCAT(A[q+1:r], ∞)
10 i = j = 1
11 for k = p to r
12 if L[i] ≤ R[j]
13 A[k] = L[i]
14 i = i + 1
15 else
16 A[k] = R[j]
17 j = j + 1

La rutina MERGE itera sobre el largo del subproblema comparando los

elementos de los arreglos L y R. En cada paso de la iteración, el menor de
los elementos comparados se actualiza en el arreglo original A. Analizando el
pseudocódigo de la rutina MERGE, se aprecia que su tiempo de ejecución en
la primera llamada (con el arreglo completo) es T (n) = n/2 + 1 + n/2 + 1 + n
(crear los arreglos L y R más el ciclo for de n iteraciones). En cada etapa
se realizan dos llamadas nuevas de MERGE de tamaño n/2, resultando en un
tiempo no recursivo T (n) = O(n) para cada etapa. La parte recursiva realiza
dos llamadas de tamaño n/2. Así, la recurrencia del algoritmo corresponde
a T (n) = 2T (n/2) + n, que resulta (utilizando método maestro) en el tiempo
final para MERGE-SORT de T (n) = O(n log(n)).

3.3. El par de puntos más cercano

Dado un arreglo A = [a0 , a1 , . . . , an−1 ] de n números ¿Cómo se encuentran
el par de elementos con la menor distancia entre ellos? Este problema se
puede resolver exhaustivamente con la rutina CLOSEST_PAIR la cual compara
la distancia de cada uno de los n elementos contra el resto de los n − 1
elementos. Analizando el pseudocódigo CLOSEST_PAIR, se aprecia que el tiempo
de ejecución es T (n) = O(n2 ), dado que en el ciclo for anidado por cada
iteración de i, que se realiza n veces, se itera sobre el índice j realizando n
repeticiones. En cada paso, se calcula la distancia entre dos elementos de A,

12
 3.3. El par de puntos más cercano

descartando los índices iguales (distancia igual a 0), y al encontrar una distancia
menor a la anterior (que comienza en ∞) se actualiza el resultado.

1 CLOSEST_PAIR(A, n)
2 d_min = ∞
3 for i = 0 to n - 1
4 for j = 0 to n - 1
5 d = abs(A[j] - A[i])
6 if d < d_min and i ̸= j
7 d_min = d
8 return d_min

Utilizando un algoritmo de ordenamiento como MERGE-SORT, podemos

mejorar el tiempo de ejecución utilizando la estrategia dividir y conquistar.
Si el arreglo A esta ordenado, es decir a0 ≤ a1 ≤ . . . ≤ an−1 , es posible
identificar que ai+2 ≥ ai+1 ≥ ai y que |ai+2 − ai | > |ai+1 − ai | para cualquier
i = 0, 1, . . . , n − 2. La distancia mínima debe estar en algún par |ai+1 − ai |.

1 CLOSEST-PAIR-DC(A, p, r)
2 MERGE-SORT(A,p,r)
3 if p < r
4 q = floor((p+r)/2)
5 l_min = CLOSEST-PAIR-DC(A, p, q)
6 r_min = CLOSEST-PAIR-DC(A, q+1, r)
7 return min(l_min, r_min, abs(A[q+1] - A[q]))
8 else return ∞

La estrategia divide el arreglo en mitades, mientras que la etapa de conquistar

busca el mínimo entre elementos pares y entre los elementos continuos entre las
dos llamadas recursivas (elementos aq y aq+1 ). La parte no recursiva, el cálculo
del pivote y el mínimo entre cuatro valores, se realiza en tiempo constante. La
parte recursiva realiza dos llamadas de tamaño n/2, teniendo como resultado
la recurrencia T (n) = 2T (n/2) + 1. Esta recurrencia tiene como resultado
(utilizando teorema maestro) tiempo T (n) = O(n), que al sumar el tiempo
de ordenamiento de MERGE-SORT resulta en el tiempo final de ejecución para
CLOSEST-PAIR-DC en T (n) = O(n log(n)). Adicionalmente es posible evitar la
recursión iterando sobre los elementos de A manteniendo el tiempo de ejecución
sin ordenamiento T (n) = O(n) con un ciclo for de n iteraciones.

1 CLOSEST-PAIR-IT(A, p, r)
2 MERGE-SORT(A,p,r)
3 d_min = ∞
4 for i in 0 to (r - p) - 1
5 d = abs(A[i] - A[i+1])
6 if d < d_min
7 d_min = d

13
 3.4. Algoritmo de Strassen

3.4. Algoritmo de Strassen

El algoritmo de Strassen logra mejorar el tiempo del algoritmo general
para la multiplicación de matrices cuadradas utilizando la estrategia dividir y
conquistar. Para dos matrices cuadradas de tamaño n × n A[aij ] y B[bij ], el
resultado de su multiplicación C[cij ] = A · B es:
n
X
cij = aik bkj (3.1)
k=1
La rutina MATRIX-MULT implementa esta formula de manera exhaustiva.

1 MATRIX-MULT(A, B, C, n)
2 for i = 0 to n - 1
3 for j = 0 to n - 1
4 for k = 0 to n -1
5 c_{ij} = c_{ij} + a_{ik} b_{kj}

El análisis del pseudocódigo nos permite verificar el tiempo de ejecución

contando la cantidad de iteraciones anidadas de n repeticiones resultado en un
tiempo asintótico de T (n) = O(n3 ). Utilizando algebra de matrices se puede
expresar la Ecuación (3.1) como:

    
C11 C12 A11 A12 B11 B12
= (3.2a)
C21 C22 A21 A22 B21 B22
   
C11 C12 A11 · B11 + A12 · B21 A11 · B12 + A12 · B22
= (3.2b)
C21 C22 A21 · B11 + A22 · B21 A21 · B12 + A22 · B22
donde A[aij ], B[bij ] y C[cij ] son los cuadrantes de tamaño n/2 de las matrices
originales. La rutina MATRIX-MULT-DC resuelve el problema de manera recursiva.

1 MATRIX-MULT-DC(A, B, C, n)
2 if n == 1
3 c_11 = c_11 + a_11 * b_11
4 else
5 MATRIX-MULT-DC(A11, B11, C11, n/2)
6 MATRIX-MULT-DC(A11, B12, C12, n/2)
7 MATRIX-MULT-DC(A21, B11, C21, n/2)
8 MATRIX-MULT-DC(A21, B12, C22, n/2)
9 MATRIX-MULT-DC(A12, B21, C11, n/2)
10 MATRIX-MULT-DC(A12, B22, C12, n/2)
11 MATRIX-MULT-DC(A22, B21, C21, n/2)
12 MATRIX-MULT-DC(A22, B22, C22, n/2)

La Ecuación (3.3) muestra un ejemplo de cálculo para una matriz de 2 × 2

donde cada llamada recursiva ejecuta una multiplicación de un caso base n = 1.

    
14 19 1 2 2 5
= (3.3a)
6 7 0 1 6 7

14
 3.4. Algoritmo de Strassen

   
14 19 1·2+2·6 1·5+2·7
= (3.3b)
6 7 0·2+1·6 0·5+1·7

El análisis del algoritmo revela 8 llamadas recursivas de tamaño n/2 y

el trabajo no recursivo, una multiplicación y una suma, se realiza en tiempo
constante O(1). El resultado (mediante método maestro) revela el mismo tiempo
que el algoritmo iterativo T (n) = O(n3 ). Para mejorar el tiempo de ejecución
asintótico del algoritmo, se debe reducir la cantidad de llamadas recursivas
para reducir el factor logb (a). Mediante álgebra se puede reducir las operaciones
mediante matrices intermedias.

P1 = A11 · B12 − A11 · B22

P2 = A11 · B22 + A12 · B22
P3 = A21 · B11 + A22 · B11
P4 = A22 · B21 − A22 · B11
P5 = A11 · B11 + A11 · B22 + A22 · B11 + A22 · B22
P6 = A12 · B21 + A12 · B22 − A22 · B21 − A22 · B22 (3.4)
P7 = A11 · B11 + A11 · B12 − A21 · B11 − A21 · B12
C11 = C11 + P5 + P4 − P2 + P6
C12 = C12 + P1 + P2
C21 = C21 + P3 + P4
C22 = C22 + P5 + P1 − P3 − P7

Con esta reducción de operaciones se puede escribir la rutina STRASSEN que

resuelve el nuevo problema de manera recursiva.

1 STRASSEN(A, B, C, n)
2 if n == 1
3 c_11 = c_11 + a_11 * b_11
4 else
5 STRASSEN(A11, B12-B22, P1, n/2)
6 STRASSEN(A11+A12, B22, P2, n/2)
7 STRASSEN(A12+A22, B11, P3, n/2)
8 STRASSEN(A22, B21-B11, P4, n/2)
9 STRASSEN(A11+A22, B11+B22, P5, n/2)
10 STRASSEN(A12-A22, B21+B22, P6, n/2)
11 STRASSEN(A11-A21, B11+B12, P7, n/2)
12 C11 = C11 + P5 + P4 - P2 + P6
13 C12 = C12 + P1 + P2
14 C21 = C21 + P3 + P4
15 C22 = C22 + P5 + P1 - P3 - P7

El nuevo algoritmo realiza 7 llamadas recursivas de tamaño n/2 y el trabajo

no recursivo corresponde a la suma de 4 matrices que se realiza en O(n2 ). El
resultado (mediante método maestro) revela una mejora sobre el algoritmo
iterativo T (n) = O(n2,81 ).

15
 3.5. Envoltura convexa

3.5. Envoltura convexa

El problema de la envoltura convexa de puntos en el plano, consiste en una
secuencia que rodea y encierra todos los puntos existentes. Se definen ciertas
condiciones para un conjunto de puntos en el plano S = {ai } con i = 1, 2, . . . , n:

1. Se asume que no existen dos puntos con la misma coordenada x.

2. Se asume que no existen dos puntos con la misma coordenada y.
3. Se asume que no existen más de dos puntos en una línea recta.

La secuencia de puntos de la solución EC(S) se enumeran en sentido de las

manecillas del reloj (ver Fig. 3.4).

a2
a1
a7
a3
EC(S) = a1 a2 a3 a4 a5
a6
a5 a4

Figura 3.4: Ejemplo de solución EC(S).

El primer paso es determinar una forma de saber si un par de puntos ai y

aj están en la solución EC(S). A partir de una recta que une los puntos ai y
aj , estos serán parte de la solución si todos los puntos restantes se encuentran
al mismo lado de la recta.

a2 a2
a1 a1
a7 a7
a3 a3
a6 a6
a5 a4 a5 a4

Figura 3.5: Ejemplo de verificación de pares de puntos en la solución EC(S).

En la Figura 3.5 se aprecia un ejemplo de un par de puntos a1 ↔ a2 que

están en la solución EC(S) y un par de puntos a1 ↔ a3 que no están en la
solución EC(S). Para un problema de n puntos, existen O(n2 ) pares de puntos
ai ↔ aj . Para cada par, se debe verificar la posición de los n puntos restantes
respecto a la recta. Dado que el cálculo de la posición de un punto respecto
a la recta de referencia se puede realizar en tiempo constante O(1), la rutina
CONVEX-HULL soluciona el problema en tiempo T (n) = O(n3 ). La operación
CLOCKWISE verifica que los puntos en la secuencia de solución EC(S) estén en
orden de las manecillas del reloj.

16
 3.5. Envoltura convexa

1 CONVEX-HULL(S, n)
2 EC = {}
3 for i = 1 to n
4 for j = 1 to n
5 side_a = side_b = 0
6 for k = 1 to n
7 d=(S[k].x-S[i].x)(S[j].y-S[i].y)-
8 (S[k].y-S[i].y)(S[j].x-S[i].x)
9 if d < 0
10 side_a = side_a+1
11 else if d > 0
12 side_b = side_b+1
13 if (side_a == n - 2) or (side_b == n - 2)
14 EC ∪ {S[i], S[j]}
15 return CLOCKWISE(EC)

La estrategia dividir y conquistar separa el plano en subproblemas de n/2

recursivamente. El caso base se escoge como un conjunto de puntos k << n (por
ejemplo k = 3 puntos donde todos pertenecen a la envoltura convexa) que pueda
ser resuelto en tiempo constante O(1). El siguiente problema es combinar los
subproblemas, pares de envolturas convexas, en una solución final 1 . La rutina
TWO-FINGERS permite obtener la tangente superior (e inferior intercambiando
los signos “mayor que” por “menor que”) para combinar dos envolturas convexas
en la solución final EC(S) en tiempo T (n) = O(n).

1 TWO-FINGER(S, p, q)
2 i = j = 1
3 while (y(i, j+1) > y(i, j) or y(i-1, j) > y(i, j))
4 if (y(i, j+1) > y(i, j))
5 j = j+1 (mod q) % clockwise
6 else
7 i = i-1 (mod p) % anti-clockwise
8 return (a_i, b_j)

La solución recursiva divide el espacio en dos problemas de n/2 y el trabajo no

recursivo, el algoritmo TWO-FINGERS, se ejecuta en tiempo O(n). La recurrencia
es conocida T (n) = 2T (n/2) + n y su solución entrega el tiempo para encontar
la EC(S) en tiempo T (n) = O(n log(n)). La Figura 3.6 muestra la etapa de
combinación de dos envolturas convexas en la solución final EC(S).
Se enumeran las envolturas convexas comenzando desde la que se encuentra
más cercana a la línea divisora. Los índices i y j representan los p y q puntos
de cada envoltura convexa y la función y(i,j) corresponde al valor del eje y
del punto donde la recta ai ↔ aj cruza la línea divisora. Las funciones (mod p)
y (mod q) mantienen los valores de i y j en los rangos 1, 2, . . . , p y 1, 2, . . . , q
respectivamente.

1 [Link]

resources/lecture-2-notes/

17
 3.5. Envoltura convexa

b1
b0

a3
a2 b2

a0 b3

a1

b1
b0

a2 b2
a3

b3
a0
a1

b1
b0

a2 b2
a3

b3
a0
a1

Figura 3.6: Ejemplo de solución EC(S) dividir y conquistar.

18
 CAPÍTULO 4

Algoritmos codiciosos

Un algoritmo codicioso es capaz de obtener una solución óptima a un

problema seleccionando una secuencia de decisiones. En cada paso, el algoritmo
toma la solución que parece ser la mejor en el momento. Esta estrategia no
siempre encuentra la solución óptima.
La estrategia codiciosa consta de los siguientes pasos:

1. Transformar el problema en uno donde se realice una primera selección y

solo quede un subproblema para resolver.
2. Probar que la selección codiciosa siempre entregará una solución óptima.
3. Demostrar la subestructura óptima, probando que una vez realizada la
selección codiciosa, el problema restante es una combinación de la selección
codiciosa con la solución óptima del subproblema.

4.1. Selección de actividades

El problema de la selección de actividades comienza con un conjunto
S = {a1 , a2 , . . . , an } de n actividades que deben ser asignadas (por ejemplo
a una sala) y solo se puede realizar una a la vez. Cada actividad ai tiene un
tiempo de inicio si y un tiempo de término fi , donde 0 ≤ si < fi < ∞. Una
actividad seleccionada se realiza durante el intervalo semi-abierto [si , fi }. Las
actividades ai y aj son compatibles si los intervalos [si , fi } y [sj , fj } no se
superponen, es decir si si ≥ fj o sj ≥ fi (no existe pausa entre actividades).
Las actividades están ordenadas de menor a mayor tiempo de término
f1 ≤ f2 ≤ f3 ≤ . . . ≤ fn−1 ≤ fn . El objetivo es encontrar el subconjunto A ⊆ S
de mayor tamaño con actividades compatibles. El Cuadro 4.1 muestra un
ejemplo del problema, donde las actividades {a3 , a9 , a11 } son compatibles, ya
que s9 ≥ f3 y s11 ≥ f9 .

ai a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
si 1 3 0 5 3 5 6 8 8 2 12
fi 4 5 6 7 9 9 10 11 12 14 16
Cuadro 4.1: Ejemplo de la selección de actividades.

19
 4.1. Selección de actividades

Una primera idea de estrategia codiciosa para el problema de la selección

de actividades, es escoger primero la actividad que deje disponible la sala el
mayor tiempo posible, es decir, la actividad de S que tenga el menor tiempo
de término. Cómo están ordenadas de menor a mayor tiempo de término, la
selección codiciosa es a1 . El subproblema corresponde a encontrar todas las
actividades que comienzan luego que a1 finalice. No consideramos las actividades
que finalizan antes que a1 comience ya que no existen, debido a que s1 < f1 y
f1 ≤ f2 ≤ f3 ≤ . . . ≤ fn−1 ≤ fn . Todas las actividades compatibles con a1 deben
comenzar una vez que esta finalice. Considerar Sk = {ai ∈ S : si ≥ fk } como el
subconjunto de todas las actividades que comienzan una vez que ak finalizó. Pa-
ra la selección codiciosa a1 , las actividades compatibles S1 = {ai ∈ S : si ≥ f1 }
corresponden a S1 = {a4 , a6 , a7 , a8 , a9 , a11 }. El siguiente paso es probar si es
correcta la selección de a1 , es decir probar la subestructura óptima. Si a1
pertenece a la solución óptima, entonces la solución óptima incluye a1 y la
solución óptima de S1 . Se plantea el siguiente teorema y su comprobación.

Teorema: considerando cualquier subproblema Sk y am ∈ Sk correspondiente

a la actividad con el menor tiempo de término, am está incluida en alguno de
los subconjuntos de Sk de tamaño máximo con actividades compatibles. Es
decir, am siempre estará incluido en la solución al subproblema.

Comprobación: se define Ak como uno de los subconjuntos de Sk de tamaño

máximo con actividades compatibles, es decir, la solución al subproblema.
Considerando aj ∈ Ak correspondiente a la actividad con el menor tiempo de
término en la solución al subproblema, se deben verificar dos casos. El primero
y más simple aj = am , es decir, la solución al subproblema ya incluye am y se
verifica el teorema. En la segunda opción aj ̸= am , pero puede agregarse a una
nueva solución A′k = (Ak − {aj }) ∪ {am } donde sus actividades son compatibles
ya que fm ≤ fj . Finalmente |Ak | = |A′k |, entonces A′k es un subconjunto de Sk
de tamaño máximo con actividades compatibles donde am ∈ A′k ■

1 GREEDY-SA(s, f, n)
2 A = {a_1}
3 k = 1
4 for m = 2 to n
5 if s[m] ≥ f[k] % esta a_m en S_k?
6 A = A ∪ {a_m} % si, seleccionarlo
7 k = m % continuar desde m
8 return A

9 GREEDY-RECURSIVO-SA(s, f, k, n)
10 m = k + 1
11 while m ≤ n and s[m] < f[k] % primero en Sk en terminar
12 m = m + 1
13 if m ≤ n
14 return {a_m} ∪ GREEDY-RECURSIVO-SA(s, f, m, n)
15 else
16 return ∅

20
 4.2. Algoritmo de Kruskal

El teorema se cumple incluso para el conjunto completo, por ejemplo

la solución {a2 , a4 , a9 , a11 } no incluye la selección codiciosa a1 , pero esta se
puede agregar ya que f1 ≤ f2 . Las rutinas GREEDY-SA y GREEDY-RECURSIVO-SA
implementan la estrategia codiciosa para el problema de la selección de
actividades de manera iterativa y recursiva respectivamente. El tiempo de
ejecución T (n) = O(n) es fácil de verificar en la versión iterativa, ya que el ciclo
for se ejecuta siempre n veces. La versión recursiva tiene idéntico tiempo de
ejecución T (n) = O(n) ya que el ciclo while se ejecuta n veces pero actualizando
el valor de k en cada llamada recursiva. La solución al problema es un conjunto
de largo 4 A = {a1 , a4 , a8 , a1 1} y se puede obtener siguiendo la traza de las
rutinas GREEDY-SA o GREEDY-RECURSIVO-SA.

4.2. Algoritmo de Kruskal

El algoritmo de Kruskal opera sobre un grafo conexo no direccionado con
pesos G = (V, E), donde V es el conjunto de vértices {a, b, c . . . , |V |}, E es el
conjunto de |E| aristas posibles que conectan pares de nodos (ver Figura 4.1).
Para cada arista (u, v) ∈ E, una etiqueta o peso w(u, v) especifica el costo de
conectar u y v. El objetivo es encontrar un subconjunto acíclico T ⊆ E que
conecte todos los vértices con el costo mínimo
X
w(T ) = w(u, v) . (4.1)
(u,v)∈T

8 7
b c d

4 9
2

a 11 i 14 e
4
7 6
8 10

h g f
1 2

Figura 4.1: Ejemplo de un grafo conexo no direccionado con pesos.

La Figura 4.2 muestra la solución al problema T = {(a, b), (b, c), (c, d), (d, e),
(c, f ), (c, i), (f, g), (g, h)} con peso mínimo w(T ) = 37. Como T es acíclico
y conecta todos los nodos, debe formar un árbol, el cual se conoce co-
mo árbol recubridor mínimo (MST por las siglas minimum spanning tree).
Cabe destacar que el MST no es único, por ejemplo otra solución es
T = {(a, b), (a, h), (c, d), (d, e), (c, f ), (c, i), (f, g), (g, h)} intercambiando la aris-
ta (b, c) por (a, h).
Para encontrar la solución al problema se deben definir algunos conceptos. Un
corte (S, V − S) de un grafo G = (V, E) es una división de V en dos conjuntos
S y V − S. Una arista (u, v) ∈ E cruza el corte (S, V − S) si uno de sus nodos
pertenece a S y el otro pertenece a V − S. Un corte respeta un conjunto de
aristas si ninguna de ellas cruza el corte. Una arista es ligera al satisfacer una
propiedad si su peso es el mínimo de todas las aristas con la misma propiedad.

21
 4.2. Algoritmo de Kruskal

4
8 7
b c d b

8
4 9
c
2
2 4 7
a 11 i 14 e i f d
4
2 9
7 6
g e
8 10
1
h g f
1 2 h

Figura 4.2: Ejemplo de un MST.

La Figura 4.3 muestra un ejemplo de corte que genera los conjuntos

S = {a, b, d, e} y V − S = {c, f, g, h, i}, el conjunto de aristas cruzando el corte
{(a, h), (b, h), (b, c), (c, d), (d, f ), (f, e)}, el corte respeta el conjunto de aristas
{(a, b), (d, e), (c, i), (c, f ), (f, g), (g, h), (i, g), (i, h)} y la arista ligera al cruzar el
corte corresponde a (c, d).

8 7
b c d

4 9
2

S↑ a 11 i 14 e
4
7 6
8 10

V −S ↓ h g f
1 2

Figura 4.3: Ejemplo de corte en un grafo conexo no direccionado con pesos.

La estrategia codiciosa corresponde a comenzar con un conjunto vacío

A = {} y seleccionar la arista de peso mínimo, dejando como subproblema
todas aristas posibles de agregar a la solución que no generen un ciclo. Para
probar la subestructura óptima, se utiliza el siguiente teorema sobre la arista
segura y su comprobación.

Teorema: para un grafo conexo no direccionado y etiquetado G = (V, E), se

considera el subconjunto A ⊂ T donde T es cualquier MST de G. Para cualquier
corte (S, V − S) que respete A y una arista ligera al cruzar el corte (u, v), esta
se define como una arista segura para agregar a A.

Comprobación: como T es una solución al problema (un MST) que contiene

el subconjunto A ⊂ T , la arista ligera al cruzar el corte (u, v) genera dos casos.
En el primer caso, (u, v) ∈ T la arista es segura ya que está en la solución. Para
el segundo caso, como el corte definido respeta A y (u, v) ∈/ A entonces u y v no
están en el mismo subconjunto generado por el corte (S, V − S). Considerando
que T por definición conecta todos los vértices y es acíclico, el no contener

22
 4.2. Algoritmo de Kruskal

(u, v) hace posible llegar desde u a v recorriendo el MST, por lo que agregar
(u, v) a una nueva solución A ∪ (u, v) ∈ T ′ necesariamente genera un ciclo. Esto
indica que hay una arista (x, y) ∈ / A en el camino entre u y v que cruza el
corte. Quitar (x, y) de la solución T , la divide en dos árboles que se pueden
volver a unir agregando (u, v) a una nueva solución T ′ = (T − (x, y)) ∪ (u, v).
Como (u, v) es una arista ligera al cruzar el corte, remover (x, y) y agregar
(u, v) mantiene el peso mínimo w(T ′ ) ≤ w(T ) ■

La Figura 4.4 muestra una visualización de ejemplo del teorema de la arista

segura.

u
y

Figura 4.4: Ejemplo de una arista segura para agregar.

El teorema nos permite iterar sobre |E| agregando en cada ciclo la arista
de valor mínimo que no genere un ciclo en la rutina MST-KRUSKAL. El ciclo
for con la subrutina MAKE-SET genera |V | conjuntos disconexos (reemplazables
por estructuras de datos tipo heaps para el análisis) en tiempo O(|V |). La
subrutina FIND-SET(u) ̸= FIND-SET(u) realiza dos búsquedas en los conjuntos
disconexos (o heaps) en O(log(|V |)) para verificar que no existan ciclos, luego
lo agrega al conjunto de solución en tiempo O(1) y la subrutina UNION junta los
conjuntos disconexos (o heaps) en una estructura en O(log(|V |)). El tiempo final
del algoritmo es T (n) = |V | + |E| log(|V |) → T (n) = O(|E| log(|V |)). Cabe
destacar que la implementación del algoritmo de Kruskal mejora bastante
en la mayoría de los casos utilizando estructuras de datos avanzadas como
disjoint-sets.

1 MST-KRUSKAL(G, w)
2 A = ∅
3 for v in_s G.V
4 MAKE-SET(v)
5 edges = G.E
6 [Link](key = w)
7 for (u,v) in edges
8 ̸
if ( FIND-SET(u) =
9 FIND-SET(v) )
10 A = A ∪ {(u, v)}
11 UNION(u, v)
12 return A

23
 4.3. Códigos de Huffman

La Figura 4.5 muestra el detalle de las iteraciones y las selección de aristas

de la rutina MST-KRUSKAL.
8 7 8 7
b c d b c d

4 9 4 9
2 2

a 11 i 14 e a 11 i 14 e
4 4
7 6 7 6
8 10 8 10

h g f h g f
1 2 1 2

8 7 8 7
b c d b c d

4 9 4 9
2 2
a 11 i 14 e a 11 i 14 e
4 4
7 6 7 6
8 10 8 10

h g f h g f
1 2 1 2

8 7 8 7
b c d b c d

4 9 4 9
2 2
a 11 i 14 e a 11 i 14 e
4 4
7 6 7 6
8 10 8 10

h g f h g f
1 2 1 2

8 7 8 7
b c d b c d

4 9 4 9
2 2
a 11 i 14 e a 11 i 14 e
4 4
7 6 7 6
8 10 8 10

h g f h g f
1 2 1 2

Figura 4.5: Iteraciones del algoritmo de Kruskal.

4.3. Códigos de Huffman

Los códigos de Huffman comprimen datos de manera eficiente, las mejoras
típicas van del 20 % al 90 %. Los datos se reciben como una cadena de caracteres
y una tabla indicando la frecuencia de aparición de cada carácter para crear una
forma óptima de representar cada elemento como una cadena binaria. Como
ejemplo, supongamos que se recibe un archivo de datos de 100.000 caracteres
que se desea comprimir y se sabe que existen 6 elementos distintos con las
siguientes frecuencias:

Caracteres a b c d e f
Frecuencia (k) 45 13 12 16 9 5
Cuadro 4.2: Frecuencia de cada carácter en la secuencia.

Se necesitan ⌈log2 (n)⌉ bits para representar n ≥ 2 caracteres con códigos

de largo fijo. Para n = 6 se necesitan 3 bits, cada uno un código distinto con
un total de (100.000)*3 = 300.000 bits. Para mejorar, la idea es dar a los

24
 4.3. Códigos de Huffman

caracteres más frecuentes códigos cortos y a los menos frecuentes códigos largos.
El Cuadro 4.3 muestra la representación de largo fijo y utilizando códigos de
largo variable con un total de 45 × 1 + 13 × 3 + 12 × 3 + 16 × 3 + 9 × 4 + 5 × 4
= 224.000 bits.

Caracteres a b c d e f
Frecuencia (k) 45 13 12 16 9 5
Códigos de largo fijo 000 001 010 011 100 101
Códigos de largo variable 0 101 100 111 1101 1100
Cuadro 4.3: Representación en códigos de largo fijo y variable.

Se consideran solamente representaciones en las que ningún código es el

prefijo de otro código. Para codificar simplemente se debe concatenar cada
código correspondiente a cada carácter del archivo. Como ningún código es
prefijo de otro elimina las ambigüedades en la decodificación, por ejemplo,
la cadena 100011001101 tiene decodificación 100 · 0 · 1100 · 1101 = cafe.
Ambas representaciones, de largo fijo en la Figura 4.6 y de largo variable en la
Figura 4.7, tienen un árbol binario equivalente.

100

0 1
86 14

0 1 0
58 28 14

0 1 0 1 0 1
a : 45 b : 13 c : 12 d : 16 e:9 f :5

Figura 4.6: Árbol binario para representación de largo fijo.

100

0 1
a : 45 55

0 1
25 30

0 1 0 1
c : 12 b : 13 14 d : 16

0 1
f :5 e:9

Figura 4.7: Árbol binario para representación de largo variable.

25
 4.3. Códigos de Huffman

En el árbol binario, la dirección 0 significa “ir al nodo inferior izquierdo” y

1 significa “ir al nodo inferior derecho”. Para un alfabeto C de los caracteres
de entrada, el árbol tiene |C| nodos terminales y |C| − 1 nodos internos. Para
cada carácter c ∈ C, c.f req corresponde a su frecuencia y la función dT (c)
corresponde al nivel de c en el árbol que es equivalente a la cantidad de bits que
requiere codificar c. La rutina HUFFMAN implementa el árbol binario de largo
variable utilizando una estructura elemental de la Figura 4.8.

x y

Figura 4.8: Nodo elemental para los códigos de Huffman.

1 HUFFMAN(C)
2 n = |C|
3 Q = C
4 for i = 1 to n - 1
5 New z
6 x = EXTRACT-MIN(Q)
7 y = EXTRACT-MIN(Q)
8 [Link] = x
9 [Link] = y
10 [Link] = [Link] + [Link]
11 INSERT(Q, z)
12 return EXTRACT-MIN(Q)

14

0 1
f :5 e:9 c : 12 b : 13 d : 16 a : 45 c : 12 b : 13 f :5 e:9 d : 16 a : 45

30

0 1
14 25 25 14 d : 16

0 1 0 1 0 1 0 1
f :5 e:9 d : 16 c : 12 b : 13 a : 45 c : 12 b : 13 f :5 e:9 a : 45

100

55 0 1

0 1 a : 45 55

25 30
0 1
25 30
0 1 0 1
0 1 0 1
c : 12 b : 13 14 d : 16 c : 12 b : 13 14 d : 16
0 1 0 1
a : 45 f :5 e:9 f :5 e:9

Figura 4.9: Pasos de creación de los códigos de Huffman.

26
 4.3. Códigos de Huffman

La Figura 4.9 muestra el detalle de las iteraciones de la rutina HUFFMAN. La

estrategia codiciosa corresponde a representar cada carácter con su frecuencia
como un árbol de un solo nodo, y luego seleccionar los dos primeros árboles
con menor frecuencia para formar la primera estructura elemental. Esta
tiene como valor de frecuencia la suma de los nodos hijos. El subproblema
corresponde a buscar los siguientes dos árboles con menor frecuencia y repetir. La
implementación mediante heaps, permite realizar las subrutinas EXTRACT-MIN
e INSERT en tiempo O(log(n)), mientras que crear y asignar los valores a la
estructura elemental se realiza en tiempo constante O(1), resultando en un
tiempo final de ejecución T (n) = O(n log(n)).

27
 CAPÍTULO 5

Algoritmos de ordenamiento

Los algoritmos de ordenamiento tienen muchas aplicaciones, como facilitar

la búsqueda para aplicaciones de usuario de lista de contactos telefónicos,
ordenamiento por columnas o filas en hojas de cálculo o en sistemas de
archivos. Además, en los arreglos ordenados se puede realizar la búsqueda
en tiempo O(log(n)). En aplicaciones reales, muchos problemas se simplifican,
como encontrar la mediana, el mínimo o el máximo y en compresión de datos
donde los arreglos ordenados permiten contar y eliminar los duplicados.

5.1. Insertion sort

Recordando el problema de ordenamiento (ver Capítulo 2) de un arreglo
A = [a0 , a1 , . . . , an−1 ] de n elementos, el algoritmo de insertion sort permite
obtener la permutación comenzando un recorrido que utiliza un valor key con
valor inicial igual al segundo elemento y actualizando hasta el último. En cada
una de estas n iteraciones, se intercambian los i elementos menores al valor
key, lo que ordena el arreglo hasta la posición i de la iteración. La rutina
INSERTION-SORT implementa este algoritmo.

1 INSERTION-SORT(A, n)
2 for i = 2 to n
3 key = A[i]
4 j = i - 1
5 while j > 0 and A[j] > key
6 A[j + 1] = A[j]
7 j = j - 1
8 A[j + 1] = key

El análisis simple del tiempo de ejecución, permite ver que el ciclo for de
la línea 2, se ejecuta n − 1 veces ya que ninguna sentencia actualiza el valor
de i. En cada iteración se realizan tres actualizaciones de valores (líneas 3,
4 y 8) en tiempo constante O(1) y luego un ciclo while en la línea 5. Esta
iteración en el peor caso se ejecuta 1, 2, . . . , n − 1 veces en cada repetición del
ciclo for, realizando dos actualizaciones de valores (líneas 6 y 7) en tiempo
constante O(1). Esto permite calcular el tiempo de ejecución como la suma
Pn−1 2
i=1 i que da como resultado un tiempo asintótico T (n) = O(n ). Este peor

28
 5.2. Quick sort

caso corresponde al arreglo ordenado de mayor a menor. Este algoritmo permite

analizar el mejor caso, el arreglo ya ordenado. Aquí el ciclo while solo realiza
una comparación que al ser siempre falsa, A[j] nunca es mayor a key, reduce el
tiempo de ejecución a T (n) = O(n). Así, es un buen algoritmo para arreglos casi
ordenados, si la cantidad de elementos no ordenados es k << n (una constante)
el ciclo while se ejecuta k veces con tiempo O(kn) resultando en un tiempo de
ejecución lineal T (n) = O(n).

5.2. Quick sort

Recordando la rutina MERGE-SORT y en particular la subrutina MERGE, se
aprecia que esta utiliza memoria adicional en los arreglos L y R. Aunque hay
implementaciones de MERGE-SORT sin utilizar memoria adicional, el algoritmo de
QUICK-SORT es más fácil de analizar, no requiere memoria adicional y veremos
que su tiempo de ejecución es bastante similar a MERGE-SORT.

1 QUIC-KSORT(A, p, r)
2 if p < r
3 q = PARTITION(A, p, r)
4 QUICKSORT(A, p, q - 1)
5 QUICKSORT(A, q + 1, r)

6 PARTITION(A, p, r)
7 x = A[r]
8 i = p - 1
9 for j = p to r - 1
10 if A[j] ≤ x
11 i = i + 1
12 swap A[i] with A[j]
13 swap A[i + 1] with A[r]
14 return i + 1

Al igual que MERGE-SORT, la rutina QUICK-SORT selecciona un valor q que

llamaremos pivote para dividir el arreglo en dos llamadas recursivas. La Figura
5.1 muestra los intercambios o swap que realiza la subrutina PARTITION sobre
un ejemplo A = {5, 2, 4, 6, 1, 3}.

i ↓
a) A 5 2 4 6 1 3 b) A 2 5 4 6 1 3
j ↑

i ↓ i +1 ↓
c) A 2 1 4 6 5 3 d) A 2 1 3 6 5 4
j ↑ r ↑
Figura 5.1: Intercambios o swap de la rutina PARTITION con x = 3.

En términos generales, la subrutina PARTITION entrega el arreglo con el

pivote q en una posición intermedia, los valores menores al pivote desordenados

29
 5.2. Quick sort

a la izquierda y los valores mayores al pivote desordenados a la derecha. Así

la rutina QUICK-SORT omite la posición del pivote y ordena la parte izquierda
y derecha recursivamente. Un caso particular ocurre cuando el arreglo está
ordenado de mayor a menor. La Figura 5.2 muestra los pivotes q y las llamadas
recursivas de la rutina QUICK-SORT sobre un ejemplo A = {6, 5, 4, 3, 2, 1}.

q
a) b)
6 5 4 3 2 1 1 5 4 3 2 6

q q
c) d)
5 4 3 2 6 2 4 3 5

q q
e) f)
4 3 5 3 4
Figura 5.2: Pivote q de la rutina QUICK-SORT en el peor caso.

En este caso, se aprecia que en cada iteración sólo hay una llamada recursiva
(el pivote se omite, esta en la primera o la última posición y solo se utiliza la parte
izquierda o la derecha) y la parte no recursiva, la subrutina PARTITION, realiza
O(n) iteraciones. Esta recurrencia T (n) = T (n − 1) + n tiene como solución
T (n) = O(n2 ) que corresponde al tiempo de QUICK-SORT en el peor caso.
Para los casos donde el arreglo no está ordenado de mayor a menor,
se aprecia claramente que existen dos llamadas recursivas pero no es tan
claro en qué razón se dividió el arreglo en cada iteración, pero si se
aprecia que el trabajo no recursivo de la subrutina PARTITION se realiza en
tiempo O(n), ya que cada ciclo for recorre cada partición recursiva en su
totalidad. En el mejor caso el pivote siempre divide el arreglo en mitades,
resultando en una recurrencia T (n) = 2T (n/2) + n con tiempo de ejecución
T (n) = O(n log(n)). Incluso si la partición está desbalanceada en razón 9 es a 1,
la recurrencia T (n) = T (n/10) + T (9n/10) + n entrega un tiempo de ejecución
T (n) = O(n log(n)). Una forma simple de distribuir la partición de las llamadas
recursivas es escoger un pivote aleatorio. La rutina RANDOMIZED-QUICKSORT
intercambia el último elemento que corresponde al pivote en QUICK-SORT por
una posición aleatoria (sumando solo una operación de tiempo constante que
no afecta el tiempo de ejecución) lo que en la práctica se traduce en un tiempo
de ejecución de T (n) = O(n log(n)).

1 RANDOMIZED-QUICKSORT(A, p, r)
2 if p < r
3 q = RANDOMIZED-PARTITION(A, p, r)
4 RANDOMIZED-QUICKSORT(A, p, q - 1)
5 RANDOMIZED-QUICKSORT(A, q + 1, r)

6 RANDOMIZED-PARTITION(A, p, r)
7 i = RANDOM(p, r)
8 swap A[r] with A[i]
9 return PARTITION(A, p, r)

30
 5.3. Heap sort

5.3. Heap sort

El heap es una estructura de datos de cola de prioridad almacenada en
un arreglo A que representa un árbol binario casi completo, donde cada nodo
corresponde a un elemento del arreglo. El árbol está completo en todos los
niveles con excepción del más bajo, el cual se llena desde la izquierda. El
atributo heap-size, representa la cantidad de elementos en el heap y la raíz
del árbol es A[1], y dado un índice i que represente un nodo, los índices de
sus hijos izquierdo y derecho se obtienen con las rutinas LEFT(i) return 2i
y RIGHT(i) return 2i + 1 respectivamente. La Figura 5.3 muestra el heap
máximo A{16, 14, 10, 8, 7, 9, 3, 2, 4, 1}.

16
1
2 3

14 10

4 5 6 7

8 7 9 3

8 9 10
2 4 1

Figura 5.3: Árbol binario para el heap máximo almacenado en el arreglo A.

1 HEAP-SORT(A, n)
2 BUILD-MAX-HEAP(A, n)
3 for i = n downto 2
4 swap A[1] with A[i]
5 [Link]-size -= 1
6 MAX-HEAPIFY(A, 1)

7 BUILD-MAX-HEAP(A, n)
8 [Link]-size = n
9 for i = floor(n/2) down to 1
10 MAX-HEAPIFY(A, i)

11 MAX-HEAPIFY(A, i)
12 s = [Link]-size
13 l = LEFT(i)
14 r = RIGHT(i)
15 if l ≤ s and A[l] > A[i]
16 m = l
17 else m = i
18 if r ≤ s and A[r] > A[m]
19 m = r
20 if m ̸= i
21 swap A[i] with A[m]
22 MAX-HEAPIFY(A, m)

31
 5.3. Heap sort

La rutina HEAP-SORT comienza con una llamada de la rutina

BUILD-MAX-HEAP, la cual realiza una iteración desde ⌊n/2⌋ a 1 (desde ⌊n/2⌋ + 1
hasta n todos los elementos son nodos terminales) ejecutando la rutina
MAX-HEAPIFY. La Figura 5.4 muestra el árbol binario en cada iteración.

a)
4 4
1 1
2 3 2 3

1 3 1 3

4 5 6 7 4 5 6 7

2 16 9 10 2 16 9 10

8 9 8 9
10 10
14 8 7 14 8 7

b) c)
4 4
1 1
2 3 2 3

1 3 1 10

4 5 6 7 4 5 6 7

14 16 9 10 14 16 9 3

8 9 10 8 9 10
2 8 7 2 8 7

d) e)
4 16
1 1
2 3 2 3
16 10 14 10
4 5 6 7 4 5 6 7
14 7 9 3 8 7 9 3

8 9 10 8 9 10
2 8 1 2 4 1

Figura 5.4: Iteraciones de la rutina BUILD-MAX-HEAP (valor de i en gris).

Una forma simple de ver la traza de la rutina MAX-HEAPIFY es siguiendo el

valor de la variable m. Esta puede tomar los valores l, i o r (líneas 16, 17 o 19).
Se realiza una operación de intercambio o swap entre los índices m e i si es que
sus valores son distintos, por el valor más grande entre A[l] y A[r]. Luego se
repite la acción recursivamente en el nodo l o r que realizó el intercambio. Esto
permite que la condición del heap máximo se mantenga: para cada nodo i los
valores de sus nodos izquierdo y derecho deben ser menores o iguales al nodo

32
 5.3. Heap sort

padre. Así podemos ver que en la primera iteración a) no hay intercambio (el
valor máximo es m que es igual a i), en la segunda iteración b) hay intercambio
entre i y m que es igual a l y en la tercera iteración c) hay intercambio entre i
y m que es igual a r. En las dos últimas iteraciones donde hay intercambio de
valores, la llamada recursiva a MAX-HEAPIFY termina ya que los valores de l y
r para m son mayores al heap-size. En la cuarta iteración d) hay intercambio
entre i y m que es igual a r y recursivamente este ya cumple con la condición
del heap máximo. En la última iteración e) hay intercambio entre i y m que es
igual a l, recursivamente este se intercambia por su nodo l y este a su vez por
su nodo r. El tiempo de ejecución de la rutina BUILD-MAX-HEAP corresponde a
un ciclo for de ⌊n/2⌋ iteraciones (y tiempo O(\)) donde se ejecuta la rutina
MAX-HEAPIFY. Esta rutina en el peor caso recorre el árbol desde el nodo raíz
hasta el nivel inferior el cual tiene altura log2 (n), realizando comparaciones
y swap en tiempo constante O(1). Así, el tiempo de ejecución de la rutina
BUILD-MAX-HEAP corresponde a T (n) = O(n log(n)).

a)
16
14
1
2 3 1
2 3
14 10
8 10
4 5 6 7
4 5 6 7
8 7 9 3
4 7 9 3
8 9
8 9 10
2 4 1
2 1 16
10

b) c)
10 9
1 1
2 3 2 3

8 9 8 3

4 5 6 7 4 5 6 7

4 7 1 3 4 7 1 2

8 9 10 8 9 10
2 14 16 10 14 16

Figura 5.5: Iteraciones del algoritmo heap sort.

La rutina HEAP-SORT deja el elemento más grande al final del arreglo

para luego ejecutar la rutina MAX-HEAPIFY que mantiene la condición del
heap máximo para n − 1, n − 2, . . . , 2. El tiempo de ejecucion de HEAP-SORT
es el tiempo de la rutina BUILD-MAX-HEAP O(n log(n)) más un ciclo for de
n − 1 iteraciones donde se ejecuta la rutina MAX-HEAPIFY de tiempo O(log(n)).
Esto resulta en un tiempo final de ejecución del algoritmo heap sort de
T (n) = O(n log(n)).

33
 5.4. Cota inferior para el ordenamiento

d) e)
8 7
1 1
2 3 2 3

7 3 4 3

4 5 6 7 4 5 6 7

4 2 1 9 1 2 8 9

8 9 10 8 9 10
10 14 16 10 14 16

f) g)
4 3
1 1
2 3 2 3

2 3 2 1

4 5 6 7 4 5 6 7

1 7 8 9 4 7 8 9

8 9 10 8 9 10
10 14 16 10 14 16

h) i)
2 1
1 1
2 3 2 3

1 3 2 3

4 5 6 7 4 5 6 7

4 7 8 9 4 7 8 9

8 9 10 8 9 10
10 14 16 10 14 16

Figura 5.5 (continuación): Iteraciones del algoritmo heap sort.

5.4. Cota inferior para el ordenamiento

A partir de un modelo de arboles de desicion, se puede encontrar una
cota inferior para los algoritmos de ordenamiento de comparacion (todos los
algoritmos vistos hasta el momento son de comparacion). Los algoritmos de
ordenamiento de comparación para un arreglo A = {a1 , a2 , . . . , an } se pueden
modelar mediante un árbol de decisión, donde cada nodo indica la comparación
entre los elementos i : j. Esto genera dos nodos hijos ya que las únicas opciones
posibles son i ≤ j o i > j. Siguiendo las comparaciones se llega a un nodo
terminal, los que contienen todas las n! permutaciones posibles de A y al menos
una corresponde al arreglo ordenado. La Figura 5.6 muestra el árbol de decisión
para el algoritmo de insertion sort. En rojo se muestra la traza para un ejemplo

34
 5.5. Counting sort

A = {2, 5, 3}: comenzando desde el nodo raiz la comparacion 1:2 (indices 1:2 y
valores 2:3) resulta 2 ≤ 3 y se continúa al nodo hijo izquierdo, la comparación
2:3 resulta 5 > 3 (se intercambian los valores resultando en la permutación
[1,3,2]) y se continúa al nodo hijo derecho, finalmente la comparación 1:3 resulta
2 ≤ 5 y el algoritmo termina en la permutación [1,3,2] que corresponde al arreglo
ordenado A′ = {2, 3, 5}.

1:2

≤ >
2:3 1:3

≤ > ≤ >

[1,2,3] 1:3 [2,1,3] 2:3

≤ > ≤ >

[1,3,2] [3,1,2] [2,3,1] [3,2,1]

Figura 5.6: Árbol de decisión para insertion sort sobre el arreglo A = {2, 5, 3}.

Como la altura del árbol binario es log2 (n!), comenzando desde el nodo raíz
un algoritmo correcto debe llegar a alguna de las permutaciones que pueden
estar en el nivel más bajo. A partir de esto, la mínima cantidad de comparaciones
y por ende la cota inferior para los algoritmos de ordenamiento de comparación
es Ω(log(n!)) → Ω(n log(n)) correspondiente a la altura del árbol de decisión.
A partir de este resultado, los algoritmos merge sort y heap sort son algoritmos
de ordenamiento asintóticamente óptimos (quick sort entrega el mismo tiempo
pero en promedio debido a la selección aleatoria del pivote).

5.5. Counting sort

Counting sort es un algoritmo de ordenamiento que permite mejorar la
cota inferior de ordenamiento cuando el arreglo A = {a1 , a2 , . . . , an } contiene
elementos enteros positivos ai ∈ N.

1 COUNTING-SORT(A, n, k)
2 crear B[1 : n], C [0 : k]
3 for i = 0 to k
4 C[i] = 0
5 for j = 1 to n
6 C[A[j]] = C[A[j]] + 1
7 for i = 1 to k
8 C[i] = C[i] + C[i - 1]
9 for j = n downto 1
10 B[C[A[j]]] = A[j]
11 C[A[j]] = C[A[j]] - 1

35
 5.6. Radix sort

La rutina COUNTING-SORT utiliza dos arreglos auxiliares: B = {b1 , b2 , . . . , bn }

donde se copian los elementos ordenados de A y C = {c0 , c1 , . . . , ck } donde
k = máx(A). El primer ciclo for llena el arreglo C de ceros y el segundo
ciclo cuenta la cantidad de apariciones de cada elemento de A. Para el
arreglo de ejemplo A = {2, 5, 3, 0, 2, 3, 0, 3} con k = 5 el arreglo C resulta en
C = {2, 0, 2, 3, 0, 1}. El tercer ciclo genera un acumulado del arreglo C, para
el ejemplo C = {2, 2, 4, 7, 7, 8}. El último ciclo posiciona los elementos de A
ordenados en el arreglo B descontando los elementos de C. La Figura 5.7
muestra las iteraciones del algoritmo counting sort.

A[8] = 3 A[7] = 0
C[A[8]] = 7 C[A[7]] = 2
B = 3 B = 0 3
C = 2 2 4 6 7 8 C = 1 2 4 6 7 8

A[6] = 3 A[5] = 2
C[A[6]] = 6 C[A[5]] = 4
B = 0 3 3 B = 0 2 3 3
C = 1 2 4 5 7 8 C = 1 2 3 5 7 8

A[4] = 0 A[3] = 3
C[A[4]] = 1 C[A[3]] = 5
B = 0 0 2 3 3 B = 0 0 2 3 3 3
C = 0 2 3 5 7 8 C = 0 2 3 4 7 8

A[2] = 5 A[1] = 2
C[A[2]] = 8 C[A[1]] = 3
B = 0 0 2 3 3 3 5 B = 0 0 2 2 3 3 3 5
C = 0 2 3 4 7 7 C = 0 2 2 4 7 7

Figura 5.7: Iteraciones del último ciclo del algoritmo counting sort.

El tiempo de ejecución es simple de analizar ya que son dos ciclos for de

O(n) iteraciones y dos ciclos for de O(k) con un tiempo de ejecución total
T (n) = O(n + k). Cuando el valor máximo del arreglo es polinomialmente menor
a n, es decir k = O(n), el tiempo de ejecución del counting sort es T (n) = O(n).

5.6. Radix sort

Radix sort es un algoritmo que utiliza un algoritmo de ordenamiento
estable para números enteros positivos, como counting sort, para un arreglo
A = {a1 , a2 , . . . , an } ordenando cada uno de los dígitos comenzando desde
las unidades. La rutina RADIX-SORT implementa el algoritmo repitiendo d
veces, el número de dígitos del máximo del arreglo d = ⌊log10 (k)⌋ + 1 la rutina
COUNTING-SORT. La Figura 5.8 muestra la ejecución del algoritmo sobre el

36
 5.6. Radix sort

arreglo de ejemplo A = {329, 457, 657, 839, 436, 720, 355} con d = 3 y k = 839
obteniendo la versión ordenada A′ = {329, 355, 436, 457, 657, 720, 839}.

1 RADIX-SORT(A, n, d)
2 for i = 1 to d
3 COUNTING-SORT A en base al digito i

A d=1 d=2 d=3

3 2 9 7 2 0 7 2 0 3 2 9
4 5 7 3 5 5 3 2 9 3 5 5
6 5 7 4 3 6 4 3 6 4 3 6
8 3 9 → 4 5 7 → 8 3 9 → 4 5 7
4 3 6 6 5 7 3 5 5 6 5 7
7 2 0 3 2 9 4 5 7 7 2 0
3 5 5 8 3 9 6 5 7 8 3 9
Figura 5.8: Iteraciones del algoritmo radix sort.

El tiempo de ejecución del algoritmo radix sort es d veces el tiempo de

ejecución de la rutina COUNTING-SORT con un tiempo final T (n) = O(d(n + k)).
Para d constante y k = O(n), el tiempo de ejecución del algoritmo de radix sort
es T (n) = O(n).

37
 CAPÍTULO 6

Programación dinámica

La programación dinámica (PD), como la estrategia de dividir y conquistar,

soluciona un problema combinando una serie de subproblemas de manera
recursiva. “Programación” en este contexto se refiere a un método de tabulación
(que llamaremos memoización) y no a escribir pseudocódigo o código en algún
lenguaje de programación. La PD aplica cuando los subproblemas se superponen,
es decir los subproblemas comparten sub-subproblemas. La estrategia de dividir
y conquistar en este contexto realiza más del trabajo necesario calculando
soluciones repetidas, la PD resuelve cada subproblema solo una vez.
La memoizacion corresponde a recordar y reutilizar los subproblemas y
mantener la relación entre estos y sus soluciones. La función recursiva verifica si
el subproblema ya fue resuelto, si es así devuelve la solución desde la tabla y si
no ha sido resuelto llama la recursión. El tiempo de ejecución de un algoritmo
de PD es el tiempo de calcular cada subproblema multiplicado por la cantidad
de subproblemas. Así, si la cantidad de problemas sin contar los ya calculados
es polinomial y el tiempo de solución de cada subproblema es polinomial, se
obtendrá un tiempo de ejecución polinomial.

6.1. SRTBOT
La sigla SRTBOT se refiere al paradigma de diseño de algoritmos recursivos
usando programación dinámica y memoización. Sus elementos se definen como:

Definir los subproblemas a resolver.

Relacionar la solución a los subproblemas de manera recursiva.
Ordenar de manera Topológica los subproblemas para garantizar llamadas
recursivas acíclicas (incrementando o disminuyendo el valor de uno o más
índices).
Los casos Base de la relación recursiva.
El problema Original a resolver a partir de los subproblemas (llamada
original a la función).
Análisis Temporal del problema original.

38
 6.2. Corte de una varilla

A partir de la definición de SRTBOT para un problema en particular se

puede definir la solución recursiva e iterativa.

6.2. Corte de una varilla

El problema es el corte varilla en partes más pequeñas, las cuales tienen
un valor individual. El proceso de cortar una varilla no tiene costo y se desea
maximizar el valor de los cortes obtenidos. El problema corresponde a una
varilla de largo n y los valores p(i) de varillas de largo i ∈ {1, 2, . . . , n}, para
los cuales se desea obtener la partición de n de mayor valor. El Cuadro 6.1
muestra los valores de los cortes posibles, para una varilla de largo n = 7 el
óptimo corresponde a los cortes [3,2,2] que suman un valor total de 33.

i 1 2 3 4 5 6 7
p(i) 1 10 13 18 20 31 32
Cuadro 6.1: Largos de varillas y sus valores.

El algoritmo ingenuo para resolver el problema itera sobre los valores posibles
i con los que se puede cortar n y resuelve recursivamente sumando el valor y
reduciendo el problema en n − i con caso base n = 0 con costo 0. La rutina
CUT-ROD implementa esta solución y la Figura 6.1 muestra el árbol de recursión
del algoritmo.

1 CUT-ROD(p, n)
2 if n == 0
3 return 0
4 q = -∞
5 for i = 1 to n
6 q = max{q, p(i) + CUT-ROD(p, n - i)}
7 return q

(32) (31) (20) (18) (13) (10) (1)

0 1 2 3 4 5 6

1 10
3 2 13 1 0
18
1 1

2 10 1 0 1 0 0
13 10 1

1 1 0 0 0
10 1 1

1 0

Figura 6.1: Árbol de recursión del algoritmo ingenuo para el problema del corte
de una varilla.

39
 6.2. Corte de una varilla

Se aprecia que el algoritmo entrega la salida correcta. La llamada a la función

con n = 7 genera los valores de i en el rango 1, . . . , 7 y las llamadas recursivas
con n = 6, . . . , 0 a las cuales se les suma el valor de cada corte 1, 10, . . . , 32. En
esta primera llamada de la función para i = 3, se genera la llamada recursiva
con n = 4 y acumula el valor 13, luego se genera la llamada recursiva con n = 2
y acumula el valor 10 (23 en total) y finalmente se genera la ultima llamada
con n = 0 (el caso base) y acumula el valor 10 (33 en total). Ya que el árbol de
recursión representa el ciclo for y las llamadas recursivas, y considerando que
el resto de las operaciones son de tiempo constante, el tiempo de ejecución de la
rutina CUT-ROD corresponde a la cantidad de nodos del árbol de recursión. La
Figura 6.1 muestra el árbol completo para n = 4, donde cada nodo hijo genera
un
Pn−1arbol de tamaño 2n−i . Así, la cantidad de nodos corresponde a la sumatoria
i n
i=0 2 , resultando en un tiempo de ejecucion T (n) = O(2 ).
El planteamiento del problema, la identificación de los subproblemas, la
llamada recursiva, el caso base, el orden topológico y la llamada al problema
original son correctos. En PD utilizaremos el concepto de memoizacion que
mejorará el tiempo de ejecución del algoritmo. El SRTBOT para el problema
del corte de una varilla utilizando un entero n se define como:

Subproblemas: particiones de largo X(i) para i = 0, 1, . . . , n.

Relación Recursiva: X(i) = p(i) + X(n − i) para 1 ≤ i ≤ n.
Orden Topológico: incrementando i (for i = 1 to n).
Casos Base: X(0) = 0.
Problema Original: X(n).
Análisis Temporal: n subproblemas que demoran O(n) → T (n) = O(n2 ).

La rutina PD-CUT-ROD implementa la solución al problema mediante

programación dinámica. El pseudocódigo es muy similar pero se aprecia que
una vez calculado un valor de n este se guarda en el arreglo de memoizacion
r[n] y de esta forma no se repiten llamadas recursivas innecesarias.

1 PD-CUT-ROD(p, n, r) % r = [- ∞, - ∞, . . . ]
2 if r[n] ≥ 0
3 return r[n]
4 if n == 0
5 q = 0
6 else
7 q = -∞
8 for i = 1 to n
9 q = max{q, p(i) + PD-CUT-ROD(p, n - i, r)}
10 r[n] = q
11 return q

La Figura 6.2 muestra el árbol de recursión completo para n = 4 del algoritmo

de PD, donde la primera llamada recursiva n − 1, n − 2, . . . , 0 cae en el caso

40
 6.2. Corte de una varilla

base n = 0 que se guarda en el memo r[0] que da el resultado a n = 1 y a

r[1]. Estos dos valores dan el resultado a n = 2 y a r[2] y luego todas las
llamadas recursivas caen a valores guardados en la memoizacion r. Nuevamente
podemos calcular el tiempo de ejecución con la sumatoriaPde nodos del árbol
n
de recursión, que en este caso corresponde a la sumatoria i=0 i (cada nodo i
genera i nodos 1 vez), resultando en un tiempo de ejecución T (n) = O(n2 ).

(32) (31) (20) (18) (13) (10) (1)

0 1 2 3 4 5 6

1 10
3 2 13 1 0
18
1 1

2 10 1 0 1 0
13 10

1 0

Figura 6.2: Árbol de recursión del algoritmo PD para el problema del corte de
una varilla.

Otra forma de escribir los algoritmos de PD es de manera iterativa bottom-

up. En este tipo de algoritmos de PD es más simple implementar las soluciones
parciales del algoritmo. La rutina BUPD-CUT-ROD entrega los resultados parciales
para n = 0, . . . , n además del arreglo s que permite obtener los cortes del
resultado óptimo.

1 BUPD-CUT-ROD(p, n)
2 r[0 : n], s[1 : n]
3 r[0] = 0
4 for j = 1 to n
5 q = -∞
6 for i = 1 to j
7 if q < p[i] + r[j - i]
8 q = p[i] + r[j - i]
9 s[j] = i
10 r[j] = q
11 return r, s

n 0 1 2 3 4 5 6 7
p(n) 0 1 10 13 18 20 31 32
r(n) 0 1 10 13 20 23 30 33
s(n) 0 1 2 3 2 2 2 3
Cuadro 6.2: Soluciones parciales del problema del corte de una varilla.

Una forma de visualizar las soluciones parciales y los cortes de cada solución
óptima es a partir del grafo direccionado acíclico (DAG) que muestra el camino
desde los valores de n hasta el caso base y los valores óptimos. La lectura se

41
 6.3. Bowling

hace en base a los valores de s en el Cuadro 6.2 y el DAG en la Figura 6.3.

Para n = 4 el resultado óptimo es 20 (ver la fila r) y para obtener los cortes la
fila s indica que el primer valor es 2, por lo tanto se debe ir a la columna de
n = 2 (n = 4 − 2) la cual nuevamente indica que el corte es 2 y se debe ir a la
columna de n = 0 (n = 2 − 2).

32
31
20 20
18 18
13 13 13
10 10 10

7 1 6 1 5 1 4 1 3 1 2 1 1 1 0
10 10 10
13 13

18 18
20
31

Figura 6.3: DAG del algoritmo PD para el problema del corte de una varilla.

6.3. Bowling
El problema consiste en un juego creado por el Dr. Erik Demaine1 , en el
cual se tienen n pines 1, 2, . . . , n y cada pin i tiene valor vi . Solo se puede pasar
un pin, derribar un pin o dos pines en cada tiro, si se derriba el pin i se suman
vi puntos, si se derriban dos pines i e i + 1 se suman vi · vi+1 puntos y pasar
no suma puntos. El objetivo es obtener el mayor puntaje posible.

1 1 9 9 2 -5 -5

Figura 6.4: Ilustración del problema de bowling para n = 7.

i 1 2 3 4 5 6 7
v(i) 1 1 9 9 2 -5 -5
Cuadro 6.3: Valores de cada pin del problema de bowling para n = 7.
1 [Link]

006s20_lec15/

42
 6.3. Bowling

Para el ejemplo el puntaje máximo corresponde a 110, derribando los dos

primeros pines individualmente, los pines 3 y 4 juntos, el pin 5 individualmente
y los los pines 6 y 7 juntos. La solución recursiva se elabora a partir del
máximo valor obtenido entre las 3 opciones para cada pares de pines creando
dos subproblemas de i − 1 y uno de i − 1 utilizando sufijos. El SRTBOT para
el problema de bowling se define como:

Subproblemas: sufijos B(0 : i) → B(i) es el máximo puntaje posible con

0 ≤ i ≤ n pines.
Relación Recursiva: B(i) = máx{B(i − 1), B(i − 1) + vi , B(i − 2) +
vi · vi−1 } para i > 1 y B(i) = máx{B(i − 1), B(i − 1) + vi } para i = 1.
Orden Topológico: valor i decreciente.
Casos Base: B(0) = 0.
Problema Original: B(n).
Análisis Temporal: n subproblemas de tiempo O(1) → T (n) = O(n).
La rutina PD-BOWLING implementa la solución al problema de manera
recursiva utilizando memoizacion.

1 PD-BOWLING(v, n, r) % r = [- ∞, - ∞, . . . ]
2 if r[n] ≥ 0
3 return r[n]
4 if n == 0
5 q = 0
6 else
7 q = -∞
8 if i > 1
9 q = max{q, BOWLING(v, i-1, r),
10 BOWLING(v, i-1, r) + v(i),
11 BOWLING(v, i-2, r) + v(i)*v(i-1)}
12 else
13 q = max{q, BOWLING(v, i-1, r),
14 BOWLING(v, i-1, r) + v(i)}
15 r[n] = q
16 return q

La Figura 6.5 muestra el árbol de recursión, donde los nodos hijos derechos
corresponden a los subproblemas i − 2, los nodos hijos centrales corresponden
a los subproblemas i − 1 y los nodos hijos izquierdos corresponden a los
subproblemas i − 1 sin contar el valor (pasar). El tiempo de ejecución del
algoritmo se puede calcular como la cantidad de nodos del árbol de recursión, ya
que todo el trabajo no recursivo corresponde a operaciones de tiempo constante,
resultando en un tiempo de ejecución T (n) = 2 + 3n → T (n) = O(n). La rutina
BUPD-BOWLING implementa la versión iterativa con los cálculos de las soluciones
parciales, donde se aprecia más claramente el tiempo de ejecución T (n) = O(n)
por el ciclo for de n iteraciones con operaciones de tiempo constante.

43
 6.3. Bowling

7
0 25

6 6 -5 5
0

5 5 4 4 4 3 18
0 -5 -10 2

0 3 3 2 81
9

2 2 1 1 1 0
0 9 9 0 1 1

0 0 0 1

Figura 6.5: Árbol de recursión del algoritmo PD para el problema de bowling.

1 BUPD-BOWLING(v, n, r, s)
2 r[0 : n], s[1 : n]
3 r[0] = 0
4 q = -∞
5 for i = 1 to n
6 if i > 1
7 q = max{q, r[i-1], r[i-1] + v(i),
8 r[i-2] + v(i)*v(i-1)}
9 s[i] = argmax{r[i-1], r[i-1] + v(i),
10 r[i-2] + v(i)*v(i-1)}
11 else
12 q = max{q, r[i-1], r[i-1] + v(i)}
13 s[i] = argmax{r[i-1], r[i-1] + v(i)}
14 r[n] = q
15 return r, s

La Figura 6.6 muestra el DAG y el Cuadro 6.4 los valores de las soluciones
parciales del problema.

9 18 25

0 1 1 1 2 9 3 9 4 2 5 -5 6 -5 7
0 0 0 0 0 0 0
1 81 -10

Figura 6.6: DAG del algoritmo PD para el problema de bowling.

i 0 1 2 3 4 5 6 7
v(i) 0 1 1 9 9 2 -5 -5
r(i) 0 1 2 11 83 85 85 110
s(i) 0 1 1 1 2 1 1 2
Cuadro 6.4: Soluciones parciales del problema de bowling.

44
 6.4. Parentización

6.4. Parentización
El problema de parentización corresponde a encontrar la ubicación de
paréntesis (de manera consistente) para obtener el máximo valor de una fórmula
a0 ∗1 a1 ∗2 . . . ∗n−1 an−1 , donde ak ∈ N y ∗k ∈ {+, ×}. Ejemplo: 7 + 4 × 3 + 5
tiene como resultado máximo (7 + 4) × (3 + 5) = 88. Para resolver el problema,
los subproblemas deben ser desarrollados como substrings, ya que los elementos
ai y ai+2 no se relacionan (no hay operación + o × entre ellos). El SRTBOT
para el problema de bowling se define como:

Subproblemas: substrings X(i, j) = máximo para ai ∗i+i ai+1 . . . ∗j aj

con 0 ≤ i ≤ j < n.
Relación Recursiva: X(i, j) = máx{X(i, k) ∗k+1 X(k + 1, j)} para
i≤k<j
Orden Topológico: aumentando k.
Casos Base: X(i, i) = ai .
Problema Original: X(0, n − 1).
Análisis Temporal: n2 subproblemas de tiempo O(n) → T (n) = O(n3 ).
La rutina PD-PARENTHESIZATION implementa la solución con PD del
problema de parentización. La traza se debe realizar con cuidado ya que los
índices de los símbolos ∗k ∈ {+, ×} comienzan desde 1 a diferencia de los
números de la fórmula que comienzan en 0 (ver Cuadro 6.5).

1 PD-PARENTHESIZATION(a, s, i, j) % r = [- ∞, - ∞, . . ]
.
2 if r[i,j] ≥ 0
3 return r[i,j]
4 if i == j
5 q = a[i]
6 else
7 q = -∞
8 for k = i to j-1
9 q = max{q, PD-PARENTHESIZATION(a, s, i, k) s[k+1]
10 PD-PARENTHESIZATION(a, s, k+1, j) }
11 r[i,j] = q
12 return q

k 0 1 2 3
ak 7 4 3 5
∗k + × +
Cuadro 6.5: Arreglos del problema de parentización.

La Figura 6.7 muestra la tabla de memoizacion y el DAG sobre ella. La

rutina BUPD-PARENTHESIZATION implementa el algoritmo de manera bottom

45
 6.5. Subsecuencia común más larga

up iterativa, donde se pueden apreciar los ciclos anidados que caracterizan el

tiempo de ejecución T (n) = O(n3 ).

7 + 4 × 3 + 5

j\i 0 1 2 3
7 0 7 0 0 0
+
4 1 11 4 0 0
×
3 2 33 12 3 0
+
5 3 88 32 8 5

Figura 6.7: DAG y soluciones parciales del algoritmo PD para el problema de

parentización.

1 BUPD-PARENTHESIZATION(a, s, n):
2 r[0,0 : n,n]
3 for j = 0 to n - 1
4 for i = 0 to n - j - 1
5 q = -∞
6 if j == 0
7 q = a[i]
8 for k = 0 to j - 1
9 q = max{q, r[i][i + k] s[i + k + 1] +
10 r[i + k + 1][i + j] }
11 if q > r[i][i + j]:
12 r[i][i + j] = q
13 return r

6.5. Subsecuencia común más larga

El problema de dos cadenas de texto A y B requiere encontrar la subsecuencia
común más larga (LCS) de ambas secuencias, es decir, el subconjunto de
elementos comunes en orden de aparición desde la izquierda. Para las secuencias
A = T H E I R y B = H A B I T, la LCS(A, B) = H I resultante es de largo
2. La definición de los subproblemas para múltiples secuencias de entrada se
realiza a partir de dos índices y multiplicar el espacio de subproblemas.

n 0 1 2 3 4
A T H E I R
B H A B I T
Cuadro 6.6: Cadenas de texto del problema LCS.

El SRTBOT para el problema se define como:

46
 6.5. Subsecuencia común más larga

Subproblemas: prefijos L(i, j) en las subsecuencias A[i : |A|] y B[j : |B|]

para 0 ≤ i ≤ |A| y 0 ≤ j ≤ |B|.
Relación Recursiva:
(
1 + L(i + 1, j + 1) , si A[i] = B[j]
L(i, j) =
máx{L(i + 1, j), L(i, j + 1)} , si A[i] ̸= B[j]

Orden Topológico: aumentando i y j.

Casos Base: L(|A|, j) = L(i, |B|) = 0.
Problema Original: L(0, 0)
Análisis Temporal: (|A| + 1) · (|B| + 1) subproblemas de tiempo O(1)
→ T (n) = O(|A||B|).

La rutina PD-LCS implementa la solución con PD del problema LCS a partir

de los índices del Cuadro 6.6).

1 PD-LCS(a, b, i, j, r) % r = [- inf, - inf, . . . ]

2 if r [i,j] ≥ 0
3 return r[i,j]
4 if i == |a| or j == |b|
5 q = 0
6 else
7 q = -inf
8 if a[i] == b[j]
9 q = 1 + LCS(a, b, i+1, j+1, r)
10 else:
11 q = max(q, LCS(a, b, i+1, j, r),
12 LCS(a, b, i, j+1, r))
13 r[i,j] = q
14 return q

La Figura 6.8 muestra la tabla de memoización y el DAG sobre ella. La

rutina BUPD-LCS implementa el algoritmo de manera bottom up iterativa, donde
se pueden apreciar los ciclos anidados que caracterizan el tiempo de ejecución
T (n) = O(|A||B|).

1 BUPD-LCS(a, b):
2 r = r[0,0 : |A|,|B|]
3 for i = |A| - 1 to 0
4 for j = |B| - 1 to 0
5 if a[i] == b[j]:
6 r[i][j] = 1 + r[i+1][j+1]
7 else:
8 r[i][j] = max(r[i][j+1], r[i+1][j]])
9 return r

47
 6.6. Suma de subconjuntos

T H E I R

j\i 0 1 2 3 4 5
H 0 2 2 0 0 0 0

A 1 1 1 1 1 0 0

B 2 1 1 1 1 0 0

I 3 1 1 1 1 0 0

T 4 1 0 0 0 0 0

5 0 0 0 0 0 0

Figura 6.8: DAG y soluciones parciales del algoritmo PD para el problema LCS.

6.6. Suma de subconjuntos

La suma de subconjuntos es un problema de decisión (respuesta es True o
False) que dado un conjunto A = {a0 , a1 , . . . , an−1 } de n enteros y un valor t
donde ai , t ∈ N busca responder la pregunta: ¿Existe algún subconjunto S ⊆ A
donde la suma de sus valores ai sea igual a t? Como ejemplo para el arreglo
A = {3, 4, 3, 1} y t = 4 la respuesta es True ya que el subconjunto S = {3, 1}
cumple con la condición. El SRTBOT para el problema se define como:

Subproblemas: prefijos X(i, t) como el subconjunto de A que sume t

donde 0 ≤ i ≤ n y 0 ≤ t.
Relación Recursiva:
(
X(i + 1, t) , si A[i] > t
X(i, t) =
OR{X(i + 1, t), X(i + 1, t − A[i])} , si A[i] ≤ t

Orden Topológico: aumentando i y disminuyendo t.

Casos Base: X(i, 0) = 1 y X(n, t) = 0.
Problema Original: X(0, t).
Análisis Temporal: nt subproblemas de tiempo O(1) → T (n) = O(nt).

i 0 1 2 3
A 3 4 3 1
Cuadro 6.7: Conjunto de ejemplo del problema.

La rutina PD-SUBSET-SUM implementa la solución con PD para la suma de

subconjuntos.

48
 6.6. Suma de subconjuntos

1 PD-SUBSET-SUM(a, i, t, n, r) % r = [-1, -1, . . . ]

2 if r[i,t] ≥ 0
3 return r[i,t]
4 if t == 0
5 q = 1
6 else if i == n
7 q = 0
8 else
9 if a[i] > t
10 q = SUBSET-SUM(a, i+1, t, r)
11 else
12 q = OR{SUBSET-SUM(a, i+1, t, r),
13 SUBSET-SUM(a, i+1, t-a[i], r)}
14 r[i,t] = q
15 return q

La Figura 6.9 muestra la memoización, el DAG sobre ella y la rutina

BUPD-SUBSET-SUM implementa el algoritmo de manera bottom, donde se aprecia
los ciclos anidados que caracterizan el tiempo de ejecución T (n) = O(nt).

3 4 3 1

t\i 0 1 2 3 4
4 1 1 1 0 0

3 1 1 1 0 0

2 0 0 0 0 0

1 1 1 1 1 0

0 1 1 1 1 1

Figura 6.9: DAG y soluciones para el problema de la suma de subconjuntos.

1 BUPD-SUBSET-SUM(a, t, n)
2 r = [0,0 : (t + 1),(n + 1)]
3 for i = 0 to n
4 r[i][0] = 1
5 for i = n - 1 to 0
6 for j = t to 1:
7 if a[i] > j
8 r[i][j] = r[i+1][j]
9 else
10 r[i][j] = OR{r[i+1][j], r[i+1][j-a[i]]}
11 return r

49
 CAPÍTULO 7

Algoritmos en grafos

La representación de problemas mediante grafos, permite solucionar

problemas como caminos más cortos, árboles recubridores mínimos y generalizar
funciones como relaciones entre conjuntos. Para comenzar se definirán conceptos
generales para luego analizar algunas soluciones de problemas en grafos.

7.1. Grafos direccionados y no direccionados

Un grafo G = (V, E) se compone de un conjunto V que agrupa los vértices
{a, b, c . . .} y un conjunto E que agrupa las aristas que conectan pares de vértices.
Para cualquier arista {x, y} ∈ E con x, y ∈ V , un grafo con pesos incluye un
valor w(x, y) que corresponde al costo de conectar los vértices x e y. En un grafo
dirigido las aristas corresponden a flechas, por lo que su representación mediante
tuplas diferencia la arista (x, y) ∈ E de la arista (y, x) ∈ E que pueden tener
distinto peso w(x, y) ̸= w(y, x). En un grafo no dirigido la arista {x, y} ∈ E
se representa de la misma forma como {y, x} ∈ E y tienen el mismo peso
w(x, y) = w(y, x). En la Figura 7.1 muestra ejemplos de los grafos direccionados
y no direccionados.

11 11
a b a b

3 5 1 2 5

d c d c
3 3
a) b)
Figura 7.1: a) Grafo no direccionado y b) grafo direccionado.

Los algoritmos que se revisarán en esta sección requieren una definición

adicional conocida como grafos simples. En este tipo de grafos no se permiten
ciclos de un nodo (x, x) ∈
/ E con x ∈ V y todos las aristas son distintas, es decir
(x, y) se encuentra en E solo una vez. Con esta definición se puede dar una cota
superior al tamaño de un grafo con respecto a la cantidad de vértices. En un

50
 7.2. Definiciones

grafo no dirigido, la cantidad máxima de aristas corresponde a conectar todos

los pares de vértices entre sí, que resulta (por coeficiente binomial |V | choose 2)
en un tamaño |E| = O(|V |2 ). El mismo análisis en un grafo dirigido, conecta
todos los pares de vértices entre sí en ambas direcciones, resultando en el doble
de tamaño que asintóticamente comparten el mismo tamaño |E| = O(|V |2 ).

7.2. Definiciones
Un par de vértices son vecinos si existe una arista entre ellos. Para grafos diri-
gidos se define el conjunto de vértices de salida adj + (u) = {v ∈ V | (u, v) ∈ E} y
el conjunto de vértices de entrada adj − (u) = {v ∈ V | (v, u) ∈ E}. Para grafos no
dirigidos los vecinos de entrada y salida son iguales adj + (u) = adj − (u) = adj(u).
Un camino de largo k es una secuencia (no un conjunto) de vértices
P = (v1 , v2 , . . . , vk ) donde (vi , vi+1 ) ∈ E para i desde 1 a k, donde el largo
o distancia d(v1 , vk ) = k. Un conjunto de nivel k corresponde a todos los
vértices que se encuentran a distancia k, es decir los últimos vértices de todos
los caminos de largo k, de un vértice s de origen Lk = {v ∈ V | d(s, v) = k}.

7.3. Búsqueda en anchura

A partir de un grafo G = (V, E) (dirigido y no dirigido) y un vértice de
origen s, la búsqueda en anchura explora las aristas de G para encontrar los
vértices que forman los caminos más cortos a s, calculando su distancia y el
árbol de anchura. La rutina BFS implementa este algoritmo.

1 BFS(G, s)
2 L_{0} = {s}
3 d(s,s) = 0
4 P(s) = {}
5 i = 1
6 while L_{i-1} ̸= {}
7 for u in L_{i-1} and (v in adj+(u) - w in L_{0:i-1})
8 L_{i} = L_{i} ∪ v
9 d(s,v) = i
10 P(v) = u
11 i += 1

Al realizar la traza de la rutina BFS sobre el grafo de ejemplo en la Figura

7.2, se obtienen los conjuntos de datos de salida. Antes de comenzar el ciclo
while se calcula el conjunto de nivel L0 = {s}, la distancia del origen a sí mismo
d(s, s) = 0 y el predecesor del origen P (s) = {}. Ya que el índice i tiene valor
inicial 1 y L0 incluye el origen s, el ciclo while comienza y pasa a la iteración
del ciclo for. La línea 7 de la rutina BFS se debe leer como una iteración sobre
todos los vecinos v de todos los vértices u en el conjunto de nivel Li−1 que no
pertenezcan a ningún conjunto de nivel anterior L0:i−1 . En la primera iteración
(i = 1) el vértice v corresponde solo a a, el cual actualiza el conjunto de nivel
L1 = {a}, la distancia al origen d(s, a) = 1 y su predecesor P (a) = {s}. En la
iteración i = 2 el vértice v corresponde solo a b (s es vecino de a pero está en L0 ),

51
 7.3. Búsqueda en anchura

c d f

s a b g

Figura 7.2: Grafo no dirigido de ejemplo.

el cual actualiza el conjunto de nivel L2 = {b}, la distancia al origen d(s, b) = 2

y su predecesor P (b) = {a}. En la iteración i = 3 los vértices v corresponden
a c, d y e (a es vecino de b pero está en L1 ), los cuales actualizan el conjunto
de nivel L3 = {c, d, e}, las distancias al origen d(s, c) = d(s, d) = d(s, e) = 3 y
sus predecesores P (c) = P (d) = P (e) = {b}. En la iteración i = 4 los vértices v
corresponden a f y g (b es vecino de c, d y e pero está en L2 ), los cuales actualizan
el conjunto de nivel L4 = {f, g}, las distancias al origen d(s, f ) = d(s, g) = 4 y
sus predecesores P (f ) = P (g) = {d}. En la última iteración (i = 5) no existen
vértices v (d y e están en L3 ), lo cual deja vacío el conjunto de nivel L5 = {} y
detiene finalmente el ciclo while.

s L0

a L1

b L2

c d e L3

g f L4

Figura 7.3: Árbol de anchura para el grafo de ejemplo.

La Figura 7.3 muestra el resultado de los conjuntos de salida en el árbol

de anchura, notando que las distancias corresponden a los conjuntos de nivel
mostrando el camino más corto de todos los nodos al origen s y el camino
se obtiene mediante los predecesores P . Para analizar el tiempo de ejecución
de la rutina BFS, se utiliza una estructura de datos conocida como lista de
adyacencia (ver Figura 7.4). El algoritmo comienza desde el vértice fuente,
en el grafo de ejemplo s, y recorre sus vecinos que en la lista de adyacencia
corresponden a la columna del vértice correspondiente. En este recorrido se
agrega cada vértice vecino a su correspondiente conjunto de nivel, se calcula
la distancia y se almacena el predecesor, es decir, solo operaciones de tiempo

52
 7.4. Búsqueda en profundidad

V = s a b c d e f g
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
a s a b b b d d
↓ ↓ ↓ ↓ ↓
b c f g e
↓ ↓
d g
↓
e
Figura 7.4: Lista de adyacencia del grafo de ejemplo.

constante O(1). El proceso continúa recorriendo cada columna para cada vértice
solo una vez, ya que los vértices que ya pertenecen a un conjunto de nivel
son omitidos en la iteración. Como la lista de adyacencia para grafos dirigidos
tiene tamaño |V | + |E| y para grafos no dirigidos 2(|V | + |E|), su recorrido
realizando operaciones de tiempo constante resulta en un tiempo de ejecución
T (n) = O(|V | + |E|).

7.4. Búsqueda en profundidad

La búsqueda en profundidad realiza un proceso parecido a la rutina BFS,
recorriendo los vecinos de cada vértice de manera recursiva. En este recorrido
encuentra los vértices conexos por un camino pero no calcula las distancias al
origen. La rutina DFS implementa la búsqueda en profundidad.

1 DFS(G,s)
2 P(s) = {0}
3 visit(s)

4 visit(u)
5 for v in adj+(u)
6 if P(v) = {}
7 P(v) = u
8 visit(v)

La traza de la rutina DFS sobre el grafo de ejemplo en la Figura 7.2

permite obtener el conjunto de salida. Se comienza con el predecesor del origen
P (s) = {0} y una llamada a la subrutina visit(s) desde el origen. El vecino
de s es a lo que actualiza P (a) = {s} y llama a la subrutina visit(a). El
vecino de a es b (para el otro vecino s, P (s) ̸= {}) lo que actualiza P (b) = {a}
y llama a la subrutina visit(b). Los vecinos de b son c, d y e (para el otro
vecino a, P (a) ̸= {}) lo que actualiza P (c) = P (d) = P (e) = {b} y llama a las
subrutinas visit(c), visit(d) y visit(e). El vecino de c es b y P (b) ̸= {}.
Los vecinos de d son f y g (para el otro vecino b, P (b) ̸= {}) lo que actualiza
P (f ) = P (g) = {d} y llama a las subrutinas visit(f) y visit(g). El vecino
de f es d y P (d) ̸= {}. El vecino de g es e (para el otro vecino d, P (d) ̸= {}) lo
que actualiza P (g) = {e} y llama a la subrutina visit(e). Finalmente para las
dos llamadas de visit(e), los vecinos son b y g donde P (b) ̸= {} y P (g) ̸= {}.

53
 7.5. Algoritmo de Dijkstra

El resultado entrega el camino entre los vértices conexos pero no entrega las
distancias. La recursión busca en profundidad el camino desde el origen al nodo
más lejano y luego realiza un backtracking actualizando los predecesores de cada
uno de los vértices. A diferencia de la rutina BFS, la búsqueda en profundidad
verifica si el vértice tiene un predecesor y omite recorrer sus vecinos. Esto logra
que la rutina DFS recorra todas las |E| aristas actualizando en cada llamada
recursiva el predecesor correspondiente en tiempo constante O(1). El tiempo de
ejecución final es T (n) = O(|E|). Esta mejora en el tiempo de ejecución sobre
la búsqueda en anchura, permite generar una nueva versión que calcula los
vértices conexos considerando todos los vértices como origen. Esto tiene una
aplicación muy común que es buscar los predecesores para grafos no conexos.
La rutina FULL-DFS implementa esta versión modificada.

1 FULL-DFS(G)
2 for v in V
3 if P(v) = {}
4 DFS(G,v)

La traza de la rutina FULL-DFS sobre el grafo no conexo de la Figura

7.5 entrega el conjunto de salida. El ciclo for de la línea 2 comienza con el
vértice s que entrega los predecesores P (s) = {0}, P (a) = {s}, P (b) = {a} y
P (c) = {b}. Luego, el ciclo for omite los vértices a, b y c (P (a) ̸= {}, P (c) ̸= {}
y P (c) ̸= {}) y continua con el vértice d. Los siguientes predecesores son
P (d) = {0}, P (f ) = {d}, P (g) = {d} y P (e) = {g}.

c d f

s a b g

Figura 7.5: Grafo no conexo no dirigido de ejemplo.

El tiempo de ejecución de la rutina modificada FULL-DFS realiza una

verificación de cada vértice para buscar si ya se obtuvo su predecesor en tiempo
O(|V |) y el cálculo de los componentes conexos, la ejecucion de la rutina DFS,
en tiempo O(|E|), con un tiempo de ejecución final T (n) = O(|V | + |E|).

7.5. Algoritmo de Dijkstra

El algoritmo de Dijkstra resuelve el problema de los caminos más
cortos a todos los vértices desde un origen para grafos dirigidos con pesos
positivos w(x, y) ∈ N. Para el desarrollo del algoritmo se define el proceso de
inicialización, donde luego de seleccionar el vértice de origen se almacenan
los nodos en una estructura de datos Q que incluye un valor de prioridad cero

54
 7.5. Algoritmo de Dijkstra

para el nodo de origen u e ∞ para todos los otros nodos. Luego se define el
proceso de relajación para dos nodos u y v donde (u, v) ∈ E que corresponde a
actualizar el valor de prioridad del vértice v si su prioridad es mayor a la suma
valor de prioridad del vértice u con el peso w(u, v). Las rutinas INITIALIZE y
RELAX implementan los procesos de inicialización y relajación respectivamente.

1 INITIALIZE(G, s)
2 for v in V
3 v.d = ∞
4 Q = Q ∪ {v}
5 s.d = 0
5 Q = Q ∪ {s}
6 return Q, {}

8 RELAX(u, v, Q)
9 if v.d > u.d + w(u, v)
10 v.d = u.d + w(u, v)
11 P(v) = u

Con estos procedimientos, la rutina DIJKSTRA implementa el algoritmo para

encontrar los caminos más cortos a todos los vértices desde un origen s.

1 DIJKSTRA(G, s)
2 Q, S = INITIALIZE(G, s) % S = {}, Q = {{s,0}, {a, ∞ }, . . }
.
3 P(s) = {}
4 ̸ {}
while Q =
5 u = EXTRACT-MIN(Q)
6 S = S ∪ {u}
7 for v in adj+(u)
8 RELAX(u, v, Q)

La Figura 7.6 muestra un grafo de ejemplo luego del proceso de inicialización

y las iteraciones del algoritmo de Dijkstra. La estructura de datos Q incluye
los nodos con sus prioridades lo que permite el inicio del ciclo while. En la
primera iteración, el mínimo corresponde al origen s ya que es el único valor de
prioridad distinto a ∞ el cual se elimina de la estructura de datos Q y se agrega
al conjunto S. Los vecinos de salida de s corresponden a t e y lo que actualiza las
prioridades t = 10, y = 5 y los predecesores P (t) = P (y) = {s}. En la siguiente
iteración el mínimo corresponde a y, sus vecinos de salida corresponden a t,
x y z lo que actualiza las prioridades t = 8, x = 14, z = 7 y los predecesores
P (t) = P (x) = P (z) = {y}. En la siguiente iteración el mínimo corresponde a z,
sus vecinos de salida corresponden a x y s lo que actualiza la prioridad x = 13
y el predecesor P (x) = {z}. En la siguiente iteración el mínimo corresponde a
t, sus vecinos de salida corresponden a y y x lo que actualiza la prioridad x = 9
y los predecesores P (x) = {t}. En la última iteración el mínimo corresponde a
x, su vecino de salida corresponde a z lo que no realiza actualizaciones, se vacía
la estructura de datos Q y da fin a las iteraciones.
El camino más corto desde cualquier nodo al origen se obtiene con los
predecesores P y el costo de recorrer el camino corresponde a las prioridades

55
 7.5. Algoritmo de Dijkstra

a)
1 x, ∞ 1 x, ∞
t, ∞ t, 10
10 10
9 9
2 3 2 3
s, 0 5 4 6 s, 0 5 4 6
y, ∞ y, 5
2 2
z, ∞ z, ∞
7 7
b) c)
1 1
t, 8 x, 14 t, 8 x, 13
10 10
9 9
2 3 2 3
s, 0 5 4 6 s, 0 5 4 6
y, 5 y, 5
2 2
z, 7 z, 7
7 7
d) e)
1 1
t, 8 x, 9 t, 8 x, 9
10 10
9 9
2 3 2 3
s, 0 5 4 6 s, 0 5 4 6
y, 5 y, 5
2 2
z, 7 z, 7
7 7

Figura 7.6: Iteraciones del algoritmo de Dijkstra.

finales que se encuentran en S. Para analizar el tiempo de ejecución, se aprecia

que en cada iteración del ciclo while se elimina un vértice de la estructura
de datos Q, para el cual se recorre la columna correspondiente de la lista de
adyacencia. Esta operación no se repite ya que los vértices se eliminan de la
estructura de datos Q. Este proceso tiene un tiempo de ejecución O(|V | + |E|) ya
que la rutina RELAX y los procesos adicionales se realizan en tiempo constante
O(1) recorriendo la lista de adyacencia. El otro proceso corresponde a la
ejecución de la rutina EXTRACT-MIN en cada iteración del ciclo while que se
ejecuta O(|V |) veces. Dependiendo de la estructura de datos Q la extracción
del mínimo se puede realizar en tiempo O(|V |2 ) si se almacenan los vértices en
un arreglo o en tiempo O(|V | log(|V |)) si se almacenan los vértices en un heap.
Como los procesos de actualización de prioridades y extracción del mínimo se
realizan en la misma iteración, se suman resultando en un tiempo de ejecución
T (n) = O(|V |2 + |E|) en arreglos y T (n) = O(|V | log(|V |) + |E|) en heaps.

56
 7.6. Algoritmo de Bellman-Ford

7.6. Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford resuelve el problema de los caminos más
cortos a todos los vértices desde un origen para grafos dirigidos que puede
incluir pesos negativos siempre y cuando no existan ciclos negativos. La rutina
BELLMAN-FORD implementa el algoritmo para encontrar los caminos más cortos
a todos los vértices desde un origen s.

1 BELLMAN-FORD(G, s)
2 Q = INITIALIZE(G, s) %Q = {{s,0}, {a, ∞ }, . . }
.
3 for i = 1 to |V| - 1
4 for (u, v) in E
5 RELAX(u, v, Q)
6 for (u, v) in E
7 if v.d > u.d + w(u, v)
8 return FALSE
9 return TRUE

a) b)
5 5
t, 6 x, ∞ t, 6 x, 4
-2 -2
6 6
-3 -3
8 8
s, 0 7 -4 7 s, 0 7 -4 7
y, 7 y, 7
9 9
2 z, ∞ 2
z, 2

c) d)
5 5

t, 2 x, 4 t, 2 x, 4
-2 -2
6 6
-3 -3
8 8
s, 0 -4 s, 0 7 -4 7
7 7
y, 7 y, 7
9 9
2 2
z, 2 z, −2

Figura 7.7: Iteraciones del algoritmo de Bellman-Ford.

La Figura 7.7 muestra las iteraciones del algoritmo de Bellman-Ford sobre

un grafo de ejemplo. Las actualizaciones en cada iteración del ciclo for en la
línea 3 corresponden a: t = 6, y = 7 y a los predecesores P (t) = P (y) = {s}
en la primera, x = 4, z = 2 y a los predecesores P (x) = {y}, P (z) = {t} en la

57
 7.6. Algoritmo de Bellman-Ford

segunda, t = 2 y al predecesor P (t) = {x} en la tercera y z = −2 y al predecesor

P (z) = {t} en la última. El ciclo for de la línea 6 busca si queda algún proceso
de relajación posible ya que esto indica la presencia de un ciclo negativo. El
tiempo de ejecución del algoritmo de Bellman-Ford no se beneficia de una lista
de adyacencia, por lo que el primer ciclo for de |V | − 1 iteraciones realiza
|E| operaciones de relajación en tiempo constante O(1) y el segundo ciclo for
realiza |E| operaciones de tiempo constante O(1). Esto resulta en un tiempo de
ejecución final T (n) = O(|V ||E|).

58
 CAPÍTULO 8

Las clases P, NP, NP-C, NP-H

Todos los problemas estudiados hasta este capítulo tienen tiempos de

ejecución polinomial T (n) = O(nk ) para alguna constante k ≥ 1, con la
excepción del denominado tiempo pseudopolinomial, donde existe una constante
que multiplica el polinomio en la cota superior. De esta base podremos identificar
y reducir cuales son los problemas “difíciles” con una definición matemática
robusta para el término difícil.

8.1. Motivación
Un análisis simple nos permite concluir que la mayoría de los problemas
de decisión son en realidad indecidibles, es decir ∈ / R donde R es el conjunto
de problemas que se pueden resolver en tiempo finito. La noción es pensar en
un programa como una cadena de bits finita (por ejemplo transformándolo a
lenguaje de máquina) que a su vez es un número ∈ N (transformando la cadena
de bits finita a un decimal ∈ N). Por otro lado un problema de decisión es una
función que transforma una entrada, que corresponde cadena de bits infinita
ya que existen infinitas entradas para cada problema, en una salida ∈ {0, 1}.
Se puede pensar en un problema de decisión como una cadena de bits infinita
{b0 , b1 , . . . bi , . . .} donde bi ∈ {0, 1} es la salida y el índice i es la entrada. La
cantidad de programas es un conjunto infinito numerable, se puede contar de
uno en uno los números enteros de cero al infinito. Por otro lado, la cantidad
de problemas de decisión es un conjunto infinito no numerable, ya que cada
problema de decisión es en sí una cadena de bits infinita y no existe una noción
de conteo para múltiples infinitos. Este análisis se puede resumir en que la
cantidad de programas infinitos es mucho menor que la cantidad de problemas
de decisión.

8.2. La clase P
Definimos un algoritmo de la clase P si a partir de una entrada de tamaño
n se obtiene la solución en el peor caso en O(nk ) para alguna constante
k ≥ 1. Recordamos el caso especial denominado pseudopolinomial con el
problema de la suma de subconjuntos: problema de decisión, es decir que tiene
respuesta es True o False, que dado un conjunto A = {a0 , a1 , . . . , an−1 } de
n enteros y un valor t donde ai , t ∈ N busca responder la pregunta ¿Existe
algún subconjunto S ⊆ A donde la suma de sus valores ai sea igual a t?

59
 8.3. La clase NP

Como ejemplo para el arreglo A = {3, 4, 3, 1} y t = 4 la respuesta es True

ya que el subconjunto S = {3,P 1} cumple con la condición, lo cual se puede
verificar con la operación (s = ai ∈r ai ) == t ∧ ai ∈ A en O(n). El análisis
temporal indica nt subproblemas de tiempo O(1) → T (n) = O(nt). La condición
pseudopolinomial indica que el problema de la suma de subconjuntos no
pertenece a la clase P T (n) ̸= O(nk ) cuando t ̸= O(nk ), por ejemplo si t es
exponencialmente más grande t = O(an ) para cualquier valor a > 1. Por otro
lado el problema de la suma de subconjuntos pertenece a la clase P en tiempo
T (n) = O(nk ) cuando t = O(nk ) para k ≥ 1.

8.3. La clase NP
La clase NP es el conjunto de problemas de decisión donde una solución
se puede verificar en tiempo polinomial. Como ejemplo, para la suma de
subconjuntos A = {3, 4, 3, 1} y T = 4, verificar que cualquier solución (por
ejemplo r = {3,P1}) es correcta (resultado True) se puede realizar con la
operación (s = ai ∈r ai ) == t ∧ ai ∈ A en O(n). No nos dice nada sobre
cómo se obtuvo la solución, que ya sabemos que por ejemplo para la suma de
subconjuntos encontrar la solución podría no estar en P.

8.4. La clase NP-H y NP-C

La clase NP-H corresponde al conjunto de todos los problemas de decisión
que son tan difíciles como todos los problemas en NP, mientras que la clase
NP-C corresponde a los problemas que pertenecen a la clase en NP y a la clase
NP-H. El concepto “tan difíciles como” perderá su ambigüedad con el concepto
de reducciones. La Figura 8.1 muestra una representación lineal simple de las
distintas clases de problemas de decisión.

NP-H
NP

↑ Complejidad
NP-C
Figura 8.1: Clases de complejidad para algoritmos.

8.5. Reducciones y NP-Completitud

Una reducción desde un problema Y a un problema X corresponde a un
algoritmo de tiempo polinomial que convierte las entradas válidas de Y en
entradas equivalentes (misma respuesta True o False) de X. Entonces X es
tan difícil como Y . Esto nos permite elaborar un procedimiento para probar que
un problema X está en la clase NP-C. Primero se debe probar que X ∈ NP, es
decir verificar una solución en tiempo polinomial. Luego se debe reducir desde

60
 8.6. El problema SAT y 3-SAT

un problema Y ∈ NP-C a X. Un problema Y ∈ NP-C pertenece a NP-H, es

decir, es es tan difícil como todos los problemas en NP. La reducción desde Y a
X comprueba que X es tan difícil como Y , es decir, que pertenece a NP-H, una
definición robusta de un problema difícil. Como ya se comprobó que X ∈ NP y
X ∈ NP-H por definición X ∈ NP-C. El problema es ¿Cual es un problema Y ∈
NP-C? El teorema de Cook–Levin plantea que el problema de satisfacibilidad
booleana (SAT) pertenece a NP-C.
Adicionalmente, se define a partir del problema P vs NP: Considerando que
P ̸= NP, si X ∈ NP-C (X ∈ NP-H) entonces X ∈ / P. Esto quiere decir que
encontrar la solución al problema X no se podría realizar en tiempo polinomial
mientras P ̸= NP. A pesar que no se ha probado matemáticamente que P =
NP o que P ̸= NP, esta última opción es la más adoptada.

8.6. El problema SAT y 3-SAT

El primer problema NP-C es el problema SAT y su reducción a 3-SAT
permite realizar muchas otras reducciones. Corresponde a una fórmula booleana
en forma normal conjuntiva de literales Xi ∈ { True, False }. El problema
contiene cláusulas de dos o más literales relacionados con operadores or ∨ y
not ¬. Todas las cláusulas se relacionan con operadores and ∧.

(X1 ∨ X5 ∨ ¬X6 ) ∧(¬X3 ∨ X2 ∨ X4 ) ∧ (X6 ∨ ¬X2 ∨ ¬X4 ∨ ¬X1 ) ∧ (¬X1 ∨ ¬X2 )

| {z }
cláusula

Por ejemplo la fórmula (x1 ∨ ¬x2 ∨ ¬x3 ) ∧ (¬x2 ∨ ¬x3 ∨ x4 ∨ x1 ) ∧ (x1 )

tiene como solución x1 = True, , x2 =False, x3 = False y x4 = True. El
problema 3-SAT corresponde al problema SAT donde todas las cláusulas tienen
3 literales distintos. Para probar que 3-SAT ∈ NP-C primero se debe probar
que está en NP. Para un número de cláusulas n, se debe verificar a lo más 3
operaciones not ¬ y 2 operaciones or ∨ más n operaciones and ∧, resultando
en un tiempo de verificación polinomial O(n) dada una solución a los literales
Xi . Por lo tanto 3-SAT ∈ NP. Para reducir una instancia de SAT a 3-SAT se
siguen los siguientes pasos para cada clausula:

1. Si la cláusula tiene 1 literal x1 , se reemplaza por la cláusula (x1 ∨ x1 ∨ x1 ).

2. Si la cláusula tiene 2 literales x1 y x2 , se reemplaza por la cláusula
(x1 ∨ x2 ∨ x1 ).
3. Si la cláusula tiene 3 literales x1 y x1 y x1 , se sigue con la siguiente
cláusula.
4. Si la cláusula tiene k ≥ 4 literales x1 , x2 , . . ., xk , se crean los literales y1 , y2 ,
. . ., yk−3 y se reemplaza la cláusula por (x1 ∨ x2 ∨ y1 ) ∧ (¬y1 ∨ x3 ∨ y2 )∧
(¬y2 ∨ x4 ∨ y3 ) ∧ . . . ∧ (¬yk−4 ∨ xk−2 ∨ yk−3 ) ∧ (¬yk−3 ∨ xk−1 ∨ xk ) con
valores yi = True para 0 ≤ i ≤ j − 2 si xj = True o yi = True para
1 ≤ k si todos los xj = False para 1 ≤ j ≤ k.
Para verificar que la entrada SAT entrega la misma salida para la nueva ins-
tancia 3-SAT, basta con verificar que cada cláusula entregue el mismo resultado

61
 8.7. 3-SAT y la suma de subconjuntos

True o False. Las cláusulas de un literal no sufren cambio al repetir el literal

entre dos sentencias or ∨. Las cláusulas de 2 literales en donde al menos uno
de los valores es True, no cambia ya que basta solo uno de estos literales de
valor True para que la cláusula completa tenga como resultado True. Tampoco
cambia cuando ambos literales tienen valor False ya que al repetir un literal de
valor False se realizan comparaciones or ∨ entre tres literales de valor False.
La cláusula de 3 literales se mantiene igual, así que no hay cambios. Para cláu-
sulas de k ≥ 4 literales que tienen resultado False, el único caso que provoca
este resultado es cuando todos los literales xi tienen valor False. Todos los
literales yi aparecen en dos cláusulas con valor contrario (una operación not ¬)
lo que asegura que al menos una de las cláusulas nuevas contenga solo literales
con valor False provocando que toda la cadena tenga resultado False. Para
cláusulas de k ≥ 4 literales que tienen resultado True, todos los literales yi desde
1 ≤ i ≤ j − 2 aparecen en una cláusula con valor True hasta la cláusula donde
aparece el literal xj = True, todas con valor final True. En las cláusulas siguien-
tes aparece ¬yl = True para j − 1 ≤ l ≤ k lo que resulta en toda la cadena con
valor True. El tiempo de la reducción para una formula de n literales en el peor
caso, una formula que solo contiene cláusulas con k ≥ 4, cada una de ellas se va a
transformar en una nueva cláusula de largo O(3k) lo que extiende la fórmula de
manera lineal con tiempo polinomial de reducción O(n). Al finalizar la reducción
se puede concluir que 3-SAT es tan difícil como SAT es decir, que pertenece
a NP-H. Como 3-SAT ∈ NP y 3-SAT ∈ NP-H por definición 3-SAT ∈ NP-
C. La formula SAT (¬x1 ∨ ¬x4 ) ∧ (x1 ∨ ¬x2 ∨ ¬x3 ) ∧ (¬x2 ∨ ¬x3 ∨ x4 ∨ x1 )∧
(x1 ) de ejemplo tiene como reduccion a 3-SAT (¬x1 ∨ ¬x4 ∨ ¬x1 ) ∧ (x1 ∨ ¬x2 ∨
¬x3 ) ∧ (¬x2 ∨ ¬x3 ∨ y1 ) ∧ (¬y1 ∨ x4 ∨ x1 ) ∧ (x1 ∨ x1 ∨ x1 ) y ambas tienen co-
mo solucion x1 = True, , x2 = False, x3 = True, x4 = False e y1 = False.

8.7. 3-SAT y la suma de subconjuntos

A partir de una fórmula 3-SAT donde ninguna cláusula contiene un literal y
su negación, y todos los literales aparecen en al menos una cláusula, es posible
realizar una reducción de 3-SAT y la suma de subconjuntos. La reducción
crea 2 números vi y vi′ del conjunto S para cada literal xi y 2 números sj y
s′j del conjunto S para cada cláusula cj . El Cuadro 8.1 muestra los valores
de cada número vi , vi′ , sj , s′j y del valor t de la fórmula c1 ∧ c2 ∧ c3 ∧ c4
con c1 = (x1 ∨ ¬x2 ∨ ¬x3 ), c2 = (¬x1 ∨ ¬x2 ∨ ¬x3 ), c3 = (¬x1 ∨ ¬x2 ∨ x3 ) y
c4 = (x1 ∨ x2 ∨ x3 ).
La tabla comienza con valores cero, y luego se asignan los valores de cada
fila. Para cada número vi se asigna un 1 a la columna del literal correspondiente
xi y un 1 en la columna cj si aparece sin negación en la cláusula correspondiente.
Para cada número vi′ se asigna un 1 a la columna del literal correspondiente xi
y un 1 en la columna cj si aparece negado en la cláusula correspondiente. Para
cada número sj se asigna un 1 a la columna de la cláusula correspondiente cj y
para cada número s′j se asigna un 2 a la columna de la cláusula correspondiente
cj . La solución de la fórmula c1 ∧ c2 ∧ c3 ∧ c4 es x1 = False, , x2 =False, x3 =
True que indica los números del conjunto de solución S. Para cada literal xi se
selecciona si si su valor en la solución es True o s′i si su valor en la solución
es False. Adicionalmente se seleccionan los números sj y s′j necesarios para
formar el valor objetivo final t = 1114444 que consta de un valor 1 para cada

62
 8.8. 3-SAT y el problema clique

literal xi y un valor 4 para cada cláusula cj . El tiempo que toma realizar la

reducción corresponde al tiempo de llenar la tabla. Considerando la cantidad
total de cláusulas n, la fórmula contiene a lo más 3n literales. La tabla tiene a
lo más 8n filas y 4n columnas lo que resulta en un tamaño polinomial O(n2 )
que se recorre a lo más una vez para llenarla de ceros y una vez para asignar los
valores. Al finalizar la reducción se puede concluir que la suma de subconjuntos
es tan difícil como 3-SAT es decir, que pertenece a NP-H. Como la suma de
subconjuntos ∈ NP y la suma de subconjuntos ∈ NP-H por definición la suma
de subconjuntos ∈ NP-C.

- x1 x2 x3 c1 c2 c3 c4
v1 = 1 0 0 1 0 0 1
v1′ = 1 0 0 0 1 1 0
v2 = 0 1 0 0 0 0 1
v2′ = 0 1 0 1 1 1 0
v3 = 0 0 1 0 0 1 1
v3′ = 0 0 1 1 1 0 0
s1 = 0 0 0 1 0 0 0
s′1 = 0 0 0 2 0 0 0
s2 = 0 0 0 0 1 0 0
s′2 = 0 0 0 0 2 0 0
s3 = 0 0 0 0 0 1 0
s′3 = 0 0 0 0 0 2 0
s4 = 0 0 0 0 0 0 1
s′4 = 0 0 0 0 0 0 2
t= 1 1 1 4 4 4 4
Cuadro 8.1: Tabla de reducción de 3-SAT a la suma de subconjuntos.

8.8. 3-SAT y el problema clique

El problema clique para un grafo no direccionado G = (V, E) corresponde a
un subconjunto de vértices V ′ ⊆ V donde existe una arista {u, v} ∈ E para todo
par de vértices u, v ∈ V ′ . Un clique es un subgrafo completo de G, el problema
de decisión busca responder ¿Existe algún clique de tamaño n = |V ′ | para G?
Para probar que clique ∈ NP-C primero se debe probar que está en NP.

2 3 2 3

1 4 4

0 5 5

a) b)
Figura 8.2: a) Grafo no dirigido de ejemplo y b) un clique.

63
 8.8. 3-SAT y el problema clique

Un clique para el grafo de ejemplo de la Figura 8.2 es V ′ = {2, 3, 4, 5}. Para

verificar que esta solución es un clique en tiempo polinomial, en el peor de los
casos la solución incluye todos los vértices V ′ = V , para los que se deben revisar
O(V 2 ) pares de vértices en una operación de tiempo constante O(1) donde se
busca si la arista existe, por lo que el problema clique ∈ NP. Luego se define una
reducción desde el problema 3-SAT al problema clique. Se define una fórmula
c1 ∧ c2 ∧ . . . ∧ cn de n cláusulas, cada una con tres literales distintos x1 , x2 y x3 .
Se construye el grafo no direccionado G = (V, E) agregando a V tres vértices por
cada cláusula con las negaciones de dicha cláusula. Luego desde cada vértice se
agrega una arista a todos los vértices de cláusulas distintas exceptuando los casos
donde los literales iguales xi tengan valores de negación distintos. Como ejemplo,
para la fórmula c1 ∧ c2 ∧ c3 donde c1 = (x1 ∨ ¬x2 ∨ ¬x3 ), c2 = (¬x1 ∨ x2 ∨ x3 )
y c3 = (x1 ∨ x2 ∨ x3 ) se muestra el grafo G generado en la Figura 8.3.

c1 x1 ¬x2 ¬x3

c2 ¬x1 x1 c3

x2 x2

x3 x3

Figura 8.3: a) Grafo no dirigido de reducción y el clique.

El tiempo de la reducción corresponde al tiempo de generar el grafo G.

Considerando el número de cláusulas n, se deben agregar 3n = |V | vértices
y para cada uno de ellos, agregar aristas a las n − 1 cláusulas, resultando en
|E| = O(n2 ) aristas y una reducción en tiempo polinomial. Para comprobar la
equivalencia se parte desde una solución al problema 3-SAT que tenga resultado
True. Este debe tener al menos un literal con valor True por cláusula. Se
selecciona un vértice de cada cláusula que corresponda a un literal con valor
True para formar V ′ . Como se seleccionó una solución al problema 3-SAT con
resultado True, V ′ debería ser un clique. Como cada vértice de V ′ es de una
cláusula distinta y su correspondiente literal tiene valor True, si un par de
vértices corresponden al mismo xi literal tienen el mismo valor True y un vértice
existe entre ellos. Además, si un par de vértices corresponden a distintos literales
de distintas cláusulas un vértice existe entre ellos. Al finalizar la reducción se
puede concluir que el problema clique es tan difícil como 3-SAT es decir, que
pertenece a NP-H. Como el problema clique ∈ NP y el problema clique ∈ NP-H
por definición el problema clique ∈ NP-C.

64
 8.9. Clique y vertex cover

8.9. Clique y vertex cover

El vertex cover de un grafo no direccionado G = (V, E) es un subconjunto
V ′ ⊆ V donde para todo {u, v} ∈ E el vértice u ∈ V ′ , v ∈ V ′ o ambos. Es decir
un conjunto de vértices que cubren (o que están incluidas) todas las aristas (ver
Figura 8.4). El problema de decisión busca responder ¿Existe algún vertex cover
de tamaño n = |V ′ | para G? Para probar que vertex cover ∈ NP-C primero se
debe probar que está en NP.

u v u v

z w z w

y x y x

a) b)
Figura 8.4: a) Grafos no dirigido de ejemplo G y b) Ḡ.

Dada una solución V ′ al problema vertex cover, esta se puede verificar en

tiempo polinomial realizando O(|E|) comparaciones u ∈ V ′ , v ∈ V ′ o ambos en
tiempo O(|V ′ |), por lo que vertex cover ∈ NP. La reducción desde clique a vertex
cover se realiza generando el grafo complemento Ḡ = (V, Ē) de G = (V, E),
donde Ē = {(u, v) : u, v ∈ V, u ̸= v ∧ (u, v) ∈
/ E}. Este grafo tiene el mismo
conjunto de vértices V y todas las aristas posibles para todos los pares de
vértices que no están en E. La reducción se realiza en tiempo polinomial
O(|V |2 ) recorriendo todos los pares de vértices, verificando en tiempo O(|E|)
si (u, v) ∈
/ E para agregarlo a Ē. La reducción compara G = (V, E) que tiene
un clique V ′ con un vertex cover V − V ′ de Ḡ = (V, Ē). Para cualquier arista
(u, v) ∈ Ē se cumple (u, v) ∈/ E y se desprende que u o v no pertenecen a V ′ ,
ya que todos los pares de vértices en V ′ están conectados por una arista en
E. Por consecuencia u o v están cubiertas (pertenecen a) por V − V ′ . Esta
relación se cumple cualquier arista (u, v) ∈ Ē que está cubierta por V − V ′ de
tamaño |V − V ′ |. Al finalizar la reducción se puede concluir que el problema
vertex cover es tan difícil como clique es decir, que pertenece a NP-H. Como el
problema vertex cover ∈ NP y ∈ NP-H por definición el problema vertex cover
∈ NP-C.

65
 CAPÍTULO 9

Algoritmos para machine learning

Los algoritmos para machine learning buscan resolver problemas de

clasificación y predicción para ciencia de datos como también minimización de
funciones1 .

9.1. K vecinos más cercanos

El algoritmo de los K vecinos más cercanos se basa en una estrategia de
aprendizaje simple: recordar los valores del conjunto de datos. Depende de una
métrica de distancia d que cumpla con la desigualdad del triángulo. Para un
conjunto de n datos {xi , y i } el predictor ŷ más simple para un nuevo elemento
x̂ es ŷ = y i donde i = arg mini d(x, xi ). Un ejemplo de función simple para
calcular la distancia es la fórmula Euclidiana para p dimensiones:
v
u p
uX
d = t (xj − x̂j )2 (9.1)
j=1

La rutina SIMPLE-NN implementa el algoritmo para un conjunto de datos

calculando las distancias a todos los elementos y le asigna la etiqueta del valor
más cercano.

1 SIMPLE-NN(D,x) % D = {{x1, y1}, {x2, y2}, . . .

2 q =∞
3 for {xi, yi} in D
4 d = EUCLIDEAN(xi, x)
5 if d < q
6 q = d
7 v = yi
8 add {x, v} to D

El Cuadro 9.1 muestra un conjunto de datos de ejemplo, donde a partir

de dos mediciones xi = {x1 , x2 } cada elemento {xi , y i } pertenece a una clase
y i = {Virus, Bacteria}. Para un nuevo dato x con mediciones x1 = 60 y x2 = 60
el algoritmo le asigna la etiqueta Virus correspondiente al elemento de menor
1 [Link]

66
 9.1. K vecinos más cercanos

distancia. La Figura 9.1 muestra el conjunto de datos con el elemento nuevo

(triangulo negro) y su posterior clasificacion con la nueva etiqueta Virus.

x1 x2 Distancia Clase
40 36 20.4 Virus
30 30 31.6 Virus
32 45 28.4 Virus
37 55 27.5 Virus
40 47 21.2 Virus
52 40 8.0 Virus
48 59 22.5 Bacteria
60 67 27.0 Bacteria
68 50 12.8 Bacteria
40 65 32.0 Bacteria
55 55 15.8 Bacteria
58 68 28.1 Bacteria
Cuadro 9.1: Conjunto de datos de ejemplo.

Virus Virus
Bacteria Bacteria
60 60

40 40

40 60 40 60

Figura 9.1: Clasificación de ejemplo para el vecino más cercano.

Una extensión simple es seleccionar K elementos más cercanos para calcular

la distancia y asignarle la etiqueta más repetida entre los elementos. La rutina
SIMPLE-KNN implementa el algoritmo para un conjunto de datos calculando las
distancias a todos los elementos, selecciona las K más cercana y le asigna la
etiqueta del valor que más se repite. La Figura 9.2 muestra la clasificación con
la nueva etiqueta Bacteria con k = 3.

1 SIMPLE-KNN(D,x,n,k,C,p,r) % D = {{x1, y1}, . . }

. C = {0,0,. . }
.
2 d = [0]*n
3 for {xi, yi} in D
4 d[i] = {EUCLIDEAN(xi, x), yi}
5 d = QUICKSORT(d, p, r)
6 for i = 1 to k
7 C[d[i].yi] += 1
8 add {x, max(C).yi} to D

67
 9.2. Gradiente descendiente

Virus Virus
Bacteria Bacteria
60 60

40 40

40 60 40 60

Figura 9.2: Clasificación de ejemplo para k = 3 vecinos más cercanos.

9.2. Gradiente descendiente

El gradiente descendiente es un algoritmo iterativo de optimización para una
función f (x) basado en la razón de cambio a partir de derivadas. No garantiza
un óptimo global, pero sí un óptimo local. El teorema general plantea que si
f (x) es convexa, para cualquier exactitud e, existe un valor de n para el cual el
gradiente descendente converge a un valor de xmin ±e del óptimo.
1,2

0
1
↑
0,8 Mínimo
local
−0,5
f (x)

f (x)

0,6

0,4
−1
↑
0,2 Mínimo Mínimo
global global
↓
0 −1,5
−1 −0,5 0 0,5 1 −10 −5 0 5 10
x x

a) b)
Figura 9.3: Ejemplos de a) función convexas y b) no convexa.

La rutina 1DGD implementa el algoritmo para una función de ejemplo

f (x) = x2 su derivada f ′ (x) = 2x y los parámetros x = -1, e = 0.01 y
n = 0.4 se obtienen los mínimos xmin = -0.0079 y f (xmin ) = 0.

1 1DGD(x,f,f',e,n)
2 r_old = x
3 r_new = r_old - n*f'(r_old)
4 while |f(r_new) - f(r_old)| > e
5 r_old = r_new
6 r_new = r_old - n*f'(r_old)
7 return r_new

68
 9.3. Backpropagation

Para otro ejemplo se observa cómo se obtienen mínimos loca-

les y mínimos globales. La función f (x) = − sin(x)/x y su derivada
f ′ (x) = (sin(x) − x cos(x))/x2 con los parámetros x = -10, e = 0.0004 y
n = 10 se obtienen el mínimo local xmin = -7.75 y f (xmin ) = -0.128, mientras
que con los parámetros x = -2, e = 0.0004 y n = 5 se obtienen el mínimo
global xmin = 0.0345 y f (xmin ) = -0.9998.

0,2 0,2

0 0

−0,2 −0,2

−0,4 −0,4
f (x)

f (x)
−0,6 −0,6

−0,8 −0,8

−1 −1

−10 −5 0 5 10 −10 −5 0 5 10
x x

a) b)
Figura 9.4: Ejemplos de a) mínimo local y b) mínimo global.

9.3. Backpropagation
Backpropagation es una metodología para entrenar redes neuronales basada
en la actualización de parámetros utilizando la propagación del error de una
solución inicial mediante versión estocástica del gradiente descendiente. Podemos
definir de manera simple una red neuronal para predecir un valor único ŷ como
una secuencia de operaciones matemáticas bien definidas, donde cada capa
corresponde a una multiplicación de matrices y vectores

ŷ = f 1 (A0 · W1 ) · f 2 (A1 · W2 ) · . . . · f L (AL−1 · WL ) . (9.2)

| {z } | {z } | {z }
capa 1=A1 capa 2=A2 capa L=AL

La Figura 9.5 muestra una red neuronal para un esquema de dos

características x1 y x2 . Cuenta de dos capas, la primera con cuatro pesos
w1 , . . . , w4 y dos neuronas y la segunda con dos pesos w5 , w6 y una neurona.

x1 • w1 1
w5
w
2
3
w3
w6
x2 • w4 2

Figura 9.5: Ejemplos de una red neuronal.

69
 9.3. Backpropagation

Las operaciones necesarias para obtener ŷ corresponden a la siguiente

secuencia de multiplicaciones de matrices, vectores y aplicación de funciones
f 2 (f 1 (A0 · W1 ) · W2 ), con

    (
0
  1 w1 w2 2 w5 1 x si x > 0,
A = x1 x2 , W = , W = , f (x) =
w3 w4 w6 0 si x ≤ 0
y f 2 (x) = x.
(9.3)

La red neuronal se puede utilizar para predecir una función cuadrática de

dos características y = x21 + x2 . A partir de las características x1 = 1 y x2 = 0,
con resultado exacto y = 1, utilizando valores iniciales aleatorios para los pesos
w1 = 1, w2 = 0,5, w3 = 1, w4 = −0,5, w5 = 1 y w6 = 1 se obtiene un predictor
con error ŷ = 1,5. El procedimiento de aprendizaje consiste en actualizar los
pesos wi a partir del cálculo del gradiente descendiente de una función de
pérdida de un elemento i

∇W Loss(yˆi , y i ) (9.4)
la cual busca minimizar una función global
n
nX o
mı́n Loss(ŷ i , y i ) (9.5)
W
1

Una función de pérdida, o Loss(ŷ, y), simple es la resta de los valores

al cuadrado (ŷ − y)2 . Para el ejemplo, luego del cálculo de ŷ = 1,5 con los
pesos aleatorios la función de pérdida resulta en Loss(ŷ, y) = 0,25. Este cálculo
permite la actualización de los pesos w6 , . . . , w1 (en ese orden) mediante el
cálculo del gradiente descendiente con factor de aprendizaje η
∂Loss
wi = wi + η . (9.6)
∂wi
Así, se realizan distintas operaciones de actualización con distintas
dificultades. Por ejemplo para actualizar el peso w5 se requiere calcular

∂Loss ∂(A1 w5 + A2 w6 − y)2

= = 2A1 (A1 w5 + A2 w6 − y) (9.7)
∂w5 ∂w5
lo cual se calcula mediante la regla de la cadena para las derivadas parciales.
Por otro lado, actualizar el peso w1 se requiere calcular
∂Loss ∂Loss ∂A1
= (9.8)
∂w1 ∂A1 ∂w1
mediante la regla de la cadena, donde A1 depende de w1 . El valor
∂Loss
= 2w5 (A1 w5 + A2 w6 − y) (9.9)
∂A1
se obtiene mediante una relativamente simple regla de la cadena, mientras que
el valor

70
 9.3. Backpropagation

∂A1 ∂A1 ∂u
→ (9.10)
∂w1 ∂u ∂w1
para u = 1w1 + 0w3 aplica una nueva regla de la cadena. El valor
(
∂A1 1 si u > 0,
= (9.11)
∂u 0 si u ≤ 0

corresponde a la derivada de la función de activación f 1 por la derivada de

u = 1w1 + 0w3 . La rutina SGD-NEURAL-NET implementa un entrenamiento de
la red neuronal de una época (parámetro con distintas definiciones según
distintos autores) que corresponde a iterar sobre el largo del conjunto de datos
T. Este procedimiento de optimización de la función Loss(ŷ, y) se conoce como
el gradiente descendiente estocástico, ya que en cada iteración selecciona un
elemento aleatorio i del conjunto de datos.

1 SGD-NEURAL-NET(x, y, T, L, {f1, . . . , fL}, n)

2 Wl = rand()
3 for t = 1 to T
4 i = random remove from {1, . . . , n}
5 A_0 = x_i
6 for l = 1 to L
7 A_l = A_l-1 * f_l(A_l-1 * W_l)
8 loss = Loss(A_L, y_i)
9 for l = L to 1:
10 W_l = W_l - n * d(loss)/d W_l

Usualmente un procedimiento completo de entrenamiento requiere más de

una época, es decir, repetir más de una vez la rutina SGD-NEURAL-NET para
actualizar los pesos wi . Una vez terminado el entrenamiento es posible obtener
un predictor ŷ mediante la secuencia de multiplicaciones de matrices, vectores y
aplicación de funciones para un nuevo elemento de dos características x1 y x2 .
En general para obtener mejores resultados se aumenta la cantidad de capas y
neuronas por capa.

71
 Bibliografía

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction
to Algorithms, Fourth Edition, (4rd ed.). The MIT Press.

72