Solución a Ecuaciones de
Recurrencia
Dr. Rogelio Dávila Pérez
División de Posgrado
Universidad Autónoma de Guadalajara
[email protected]
Complejidad de programas
Evalúe el orden del siguiente algoritmo:
for i=1 to n
for j=1 to i
for k=1 to j
x = x +1
endfor
endfor
endfor
Complejidad de programas
Evalúe el orden del siguiente algoritmo:
Exp2(a,n) {
if( n == 1)
return(a) ;
m = n/2
power = exp2(a, m)
power = power * power
if (n es par)
return(power)
else
return(power * a)
}
Relaciones de recurrencia
Def. Una relación de recurrencia es una fórmula que nos
permite calcular los elementos de una secuencia, uno
después de otro iniciando con uno o más valores.
Suponga por ejemplo que deseamos generar una secuencia
de números x0 , x1 , x2 ,… por medio de:
xn+1 = 3xn
(x0=1)
Que nos genera la secuencia:
1, 3, 9, 27, 81, …
1 En 1202, regresando de Oriente, Fibonacci escribió su famoso trabajo. Liber Abaci, en el que introduce
su famosa secuencia originada a partir de un problema relacionado con la reproducción de conejos.
Relaciones de recurrencia
Ejemplo 2:
Secuencia de Fibonacci1
La secuencia de Fibonacci f1 , f2 , … se define por la ecuación de
recurrencia:
fn = fn-1 + fn-2,
y las condiciones iniciales:
n≥3
f1 = f2 = 1
La secuencia se genera como: 1, 1, 2, 3, 5, 8, 13, 21, 33, …
1 En 1202, regresando de Oriente, Fibonacci escribió su famoso trabajo. Liber Abaci, en el que introduce
su famosa secuencia originada a partir de un problema relacionado con la reproducción de conejos.
Relaciones de recurrencia
Problemas ejemplo:
Resuelva la siguientes ecuaciones de recurrencia:
(a) xn+1 = cxn (c≥0; x0=1)
(b) xn+1 = bn+1 xn (x0 given)
(c) xn+1 = bn+1 xn + cn+1 (x0 given)
Relaciones de recurrencia
Problema
1.
Sea cn el término que denota el número de veces que
la instrucción x=x+1, es ejecutada en el algoritmo:
calcula(n) {
if (n==1) return ;
for i=1 to n
x = x+1;
calcula(n/2)
}
Relaciones de recurrencia
Solución
Tenemos la condición inicial:
c1 = 0
ya que si n=0 el algoritmo calcula simplemente hace return.
Cuando n>1, la instrucción x=x+1 es ejecutada n veces y llama a
calcula(n/2). Lo que ocasiona que x=x+1 sea ejecutado
adicionalmente c[n/2] veces. Así obtenemos la siguiente
ecuación de recurrencia:
cn = n + c[n/2]
Resolviendo relaciones de recurrencia

El problema es que para calcular el valor de la ecuación para
cada número k, a partir de esta definición, tenemos que
realizar k+c[k/2] pasos para computar ck.

Es más conveniente manejar una expresión más explicita y
fácil de calcular para cn. A este proceso se le denomina:
“resolver la relación de recurrencia”.

Resolver la relación de recurrencia para la secuencia {cn}
consiste en dar una fórmula para cn que no contenga a ci
para ningún elemento i.

El problema es similar al de resolver una ecuación algebraica
(ej. una ecuación cuadrática). La diferencia es que en una
ecuación algebraica la solución es un número y en una
relación de recurrencia, la solución es una secuencia.
Resolviendo relaciones de recurrencia
La ecuación de recurrencia:
xn+1 = cxn
(c≥0, x0=1)
Es una ecuación de primer orden ya que el valor
nuevo xn+1 , de la secuencia depende tan solo
del elemento xn.
La definición de la ecuación consta de dos partes:
(i) el inicio: x0=1
(ii) valores de n a los que se aplica la ecuación,
n≥0.
Resolviendo relaciones de recurrencia
Una técnica llamada iteración o sustitución, es
utilizada para resolver una relación de
recurrencia en la cual el elemento n esta dado
solamente en términos del elemento que
inmediatamente le precede, el n-1.
Ejemplo:
Resuelva la siguiente ecuación de recurrencia:
cn = n + cn-1, n≥1
Resolviendo relaciones de recurrencia
Solución
Desarrollemos la ecuación:
cn = n + cn-1
= n + [(n-1) + cn-2]
= n + [(n-1) + [(n-2) + cn-3]]
…
= n + (n-1) + (n-2) + … + 2 + 1 + 0
Lo que nos lleva a la solución:
cn 
n(n  1)
2
Resolviendo relaciones de recurrencia
Ejercicio
La ecuación de recurrencia:
cn = n + c[n/2] ,
n≥ 1
es típica de las ecuaciones de recurrencia que describen el
tiempo requerido para los algoritmos del tipo divide-yvencerás. Resolver la ecuación.
Ejercicios
1.
2.
a.
b.
Utilice iteración para resolver las siguientes relaciones recurrentes:
an = an-1+ 3, n > 1 ; a1 = 2
an = 2nan-1 , n > 0 ; a0 = 1
Dado el siguiente algoritmo, evalúa el valor de an. El número de
multiplicaciones requerido para evaluar an, es denotado como cn:
exp1(a,n) {
if( n == 1)
return(a) ;
m = n/2
return(exp1(a,m)*exp1(a, n-m))
}
a. Explique como el algoritmo mostrado calcula an .
b. Encuentre la ecuación de recurrencia y las condiciones iniciales
para la secuencia {cn}.
c. Evalúe c2, c3 y c4.
d. Resuelva la relación de recurrencia encontrada en el inciso b, para el
caso en que n sea una potencia de 2.
Descargar

Relaciones de Recurrencia. - Página oficial del Doctor Rogelio