Download Recurrencias - Ciencias Computacionales

Análisis y Diseño de Algoritmos
Recurrencias
DR. JESÚS A. GONZÁLEZ BERNAL
CIENCIAS COMPUTACIONALES
INAOE
Introducción
2
—  Cuando un algoritmo se llama a sí mismo
¡  Su tiempo de ejecución se puede describir con una recurrencia
—  Recurrencia
¡  Ecuación o desigualdad que describe una función en términos
de su valor para entradas más pequeñas
—  Ejemplo de MergeSort
⎧Θ(1)
T (n) = ⎨
⎩2T (n / 2) + Θ(n)
¡ 
Cuya solución se dijo que es:
T (n) = Θ(n lg n)
if n = 1,
if n > 1,
Introducción
3
—  Métodos para resolver recurrencias
¡  Substitución
÷  Adivinar
¡ 
una cota, prueba con inducción matemática
Método de Iteración
÷  Expande,
itera sobre la recurrencia y la expresa como sumatoria en
términos dependientes de n y las condiciones iniciales
¡ 
Árboles de recursión
÷  Convierte
la recurrencia en un árbol cuyos nodos representan los
costos de los dif. niveles de la recursión
¡ 
Método maestro
÷  Provee
÷ 
fronteras (bounds) para recurrencias de la forma
T (n) = aT (n / b) + f (n), donde a ≥ 1, b ≥ 1, f (n) es una función dada
÷  Requiere
memorizar tres casos
Método de Substitución
4
—  Consta de 2 pasos
¡  Adivinar la forma de la solución
¡  Utilizar inducción matemática para encontrar las constantes y
mostrar que la solución funciona
—  Método poderoso
—  Solo se aplica a casos en que es fácil adivinar la
forma de la respuesta
—  Para establecer fronteras superiores o inferiores en
una recurrencia
Método de Substitución
5
—  Ejemplo:
—  Adivinamos:
—  Probamos que:
para una constante c >0
—  Entonces:
—  Substituimos en la recurrencia:
—  El último paso es cierto si c ≥ 1
Asumimos que la
cota es cierta
para n/2
Método de Substitución
6
—  El método de inducción requiere probar que la solución es cierta para
las condiciones frontera
¡ 
¡ 
¡ 
¡ 
Elegir c suficientemente grande para que
funcione para las
condiciones de frontera
Para notación asintótica requerimos probar que
nosotros
elegimos n0
Evitamos condición frontera difícil para T(1) = 1 para la prueba de inducción
% (
Aplicamos en la recurrencia T (n) = 2T '!!" n ##$* + n
& 2 )
T (1) = 1
; La recurrencia no funciona para T(1) al probar en la notación asintótica
; pero sí para T(2) y T(3)
T (2) = 2T (2) + 2 = 2 *1+ 2 = 4
T (3) = 2T (3) + 3 = 2 *1+ 3 = 5
Ahora, en la prueba de notación Asintótica:
T (2) ≤ c2 lg 2 = 2c, c ≥ 2
T (3) ≤ c3lg3 = 4.75c, c ≥ 2
Método de Substitución
7
—  Adivinando una buena primera aproximación
¡  No hay una buena manera general de adivinar soluciones
correctas a recurrencias
¡  Requiere experiencia y creatividad
¡  Algunas heurísticas
÷  Usar
árboles de recursión para generar buenos valores iniciales
÷  Si la recurrencia es similar a otra, usar una solución similar
Método de Iteración
8
—  No requiere adivinar la respuesta
—  Puede requerir más álgebra que el de substitución
—  Expande (itera) la recurrencia y la expresa como
sumatoria de términos dependientes de n y las
condiciones iniciales
—  Después usa técnicas para evaluar sumatorias para
dar cotas a la solución
—  Puede ser difícil resolver recurrencias con este
método
¡ 
A veces al iterar la recurrencia, adivinamos una solución y
seguimos con el método de substitución
Método de Iteración
9
—  Ejemplo, dada la recurrencia:
Método de Iteración
10
—  ¿Qué tanto iteramos para llegar a la condición de frontera?
¡  El i’ésimo término en la serie es 3i ⎣n/4i⎦
¡  La iteración llega a n = 1 cuando ⎣n/4i⎦ =1 ó equivalentemente,
cuando i excede log4n, que corresponde a los niveles del árbol
¡  Llevando la iteración a este punto y usando la frontera:
÷ 
⎣n/4i⎦ ≤ n/4i , descubrimos que la sumatoria contiene una serie
geométrica decreciente:
Método de Árbol de Recursión
11
—  Visualizar la iteración de una recurrencia
¡  Dibujar un árbol de recursión y obtener una buena solución
inicial
¡  Utilizamos método de sustitución para comprobar
—  Árbol de recursión
¡  Cada nodo representa el costo de un subproblema en el
conjunto de llamadas a funciones recursivas
¡  Sumamos costos por nivel y determinamos el costo total de
todos los niveles de recursión
¡  Útiles cuando la recurrencia describe tiempo de ejecución de
un algoritmo divide-y-conquista
Método de Árbol de Recursión
12
—  Para resolver la recurrencia
T (n) = 3T ( ⎣n / 4⎦) + Θ(n 2 )
—  Creamos árbol de recursión para T (n) = 3T (n / 4) + cn 2
¡  Incluímos el coeficiente c > 0
¡  Asumimos que n es una potencia exacta de 4
Método de Árbol de Recursión
13
Método de Árbol de Recursión
14
Método de Árbol de Recursión
15
—  El tamaño del problema decrece con la profundidad
del árbol
¡ 
Eventualmente alcanzamos condición frontera
—  ¿Qué tan lejos de la raíz llegamos?
¡  El tamaño del subproblema para un nodo en profundidad i es
n/4i
¡  El tamaño llega a n = 1 cuando n/4i = 1, o i = log4n
¡  Entonces el árbol tiene log4n+1 niveles (0, 1, 2, …, log4n)
Método de Árbol de Recursión
16
—  Después determinamos el costo en cada nivel del
árbol
Cada nivel tiene tres veces más nodos que el nivel anterior
¡  El número de nodos a profundidad i es 3i
¡  Cada nodo a profundidad i para i = 0, 1, 2, …, log4n-1 tiene costo
de c(n/4i)2
¡  Multiplicando, vemos que el costo de todos los nodos al nivel i
para i = 0, 1, 2, …, log4n-1 es 3ic(n/4i)2 = (3/16)icn2
¡  El último nivel a profundidad log4n tiene 3log4n = nlog4 3 nodos,
cada uno con costo T(1), con costo total nlog4 3 T(1) con Θ(nlog 3 )
¡ 
4
Método de Árbol de Recursión
17
—  Sumamos los costos de todos los niveles para obtener
el costo de todo el árbol
Método de Árbol de Recursión
18
— 
Podemos usar una serie geométrica infinita
decreciente como cota superior, ecuación A.6
Método Maestro
19
—  Receta para recurrencias del tipo:
¡  a ≥ 1 y b > 1 son constantes y f(n) es una función
asintóticamente positiva
—  La recurrencia describe el tiempo de ejecución de un
algoritmo que:
Divide un problema de tamaño n en a subproblemas
¡  Cada subproblema de tamaño n/b
¡  a y b son constantes positivas
¡  Los a subproblemas se resuelven recursivamente
¡ 
÷  En
¡ 
tiempo T(n/b)
Costo de dividir el problema y combinar los resultados esta
dado por f(n)
Método Maestro
20
—  Teorema maestro
¡ 
Sean a ≥ 1 y b > 1 constantes
¡ 
Sea f(n) una función
¡ 
Sea T(n) definida por los enteros no-negativos por la recurrencia
¡ 
¡ 
n/b puede ser ⎣n/b⎦ ó ⎡n/b⎤, entonces T(n) se puede acotar
asintóticamente como sigue:
Método Maestro
21
—  En todos los casos compara f(n) con nlogba
¡  La solución a la recurrencia la domina la mayor de las 2
funciones
¡  Caso 1: nlogba es la mayor, la solución es T(n) = Θ(nlogba)
¡  Caso 3: f(n) es mayor, la solución es T(n) = Θ(f(n))
¡  Caso 2: las dos funciones son del mismo tamaño,
multiplicamos por un factor logarítmico, T(n) = Θ(nlog algn) =
Θ(f(n)lgn)
b
Método Maestro
22
—  Algunos aspectos técnicos…
¡  En el caso 1:
÷  f(n)
debe ser polinómicamente más pequeña que nlog a
Asintóticamente más pequeña que nlog a por un factor de n∈ para
una constante ∈ > 0.
b
b
¡ 
En el caso 3:
÷  f(n)
debe ser polinómicamente mayor a nlog a
÷  También debe satisfacer la condición de regularidad de af(n/b) ≤
cf(n)
¢  Esta condición se satisface por la mayoría de las funciones
polinómicamente acotadas que podemos encontrar.
¡ 
b
Esto quiere decir que los 3 casos no cubren todas las
posibilidades de f(n).
Polinomios
23
Exponentes
24
Método Maestro
25
—  Ejemplo 1:
Método Maestro
26
—  Ejemplo 2:
Método Maestro
27
—  Ejemplo 3:
Método Maestro
28
—  Ejemplo 4:
Tarea
29
—  Ejercicios:
¡  4.2-1
¡  4.2-3
—  Problemas
¡  4-1: a, b
¡  4-4: a, b, c