ANÁLISIS Y DISEÑO DE ALGORITMOS TALLER 3. RELACIONES DE RECURRENCIA

UNIVERSIDAD CATÓLICA DE COLOMBIA

FACULTAD DE INGENIERÍA

PROGRAMA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓN

ANÁLISIS Y DISEÑO DE ALGORITMOS

TALLER 3. RELACIONES DE RECURRENCIA

Problema

Considérese la recurrencia T(1) = 0; T(n) = aT(n/b) + an + bn2, donde n es una potencia de b, n ≥ 2. Aplique el método de la ecuación característica para encontrar la solución cuando a = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 (ver ejemplo).

Metodología

El taller consiste en resolver 10 recurrencias basadas en la recurrencia del problema, así. La primera recurrencia a resolver es, T(n) = 2T(n/b) + 2n + bn2, al hacer a = 2. La segunda recurrencia a resolver es, T(n) = 3T(n/b) + 3n + bn2, al hacer a = 3 y así sucesivamente hasta la décima recurrencia a resolver que es, T(n) = 11T(n/b) + 11n + bn2, al hacer a = 11. El valor de la constante b es el mismo para todas las recurrencias. Este valor es el asignado en la Tabla 1. Asignación de recurrencias.

Para que el taller sea corto y sencillo se requiere que el procedimiento de la solución de cada recurrencia se presente siguiendo el mismo formato descrito en el ejemplo. Para unificar el estilo utilizar letra Times New Roman, tamaño de fuente, interlineado sencillo.

Evaluación.

El taller tiene un valor de 10 puntos. Cada recurrencia tiene un valor de un punto.

Fecha de entrega: 11 de marzo de 2018

Bibliografía

Brassard, G y Bratley P. Fundamentos de algoritmia. Prentice Hall. Madrid. 1997

Ejemplo

Considérese la recurrencia T(0) = 0;  T(1) = 0; T(n) = 2T(n/2) + n – 1, n potencia de 2

Solución:

1. Sea n = 2i, entonces escribimos T(n) en términos de T(2i):        T(2i) – 2T(2i–1) = 2i – 1
2. Sea t(i) = T(2i), entonces escribimos T(2i) en términos de t(i):        t(i) – 2t(i – 1) = 2i – 1
3. Obtenemos la polinomio característico:                                (x – 2) (x – 2) (x – 1)
4. Obtenemos todas las soluciones de t(i):                                t(i) =  c11i + c22i + c3i2i
5. Sea T(n) = T(2i) = t(i). Escribimos t(i) en términos de T(n):        T(n) = T(2i) = t(i) = c11log n + c2n + c3n log n 
6. Hallamos T(0):                                                T(0) = 0 =  c11log 0 + c2 ⋅ 0 + c3 ⋅ 0 ⋅ log 0
7. Hallamos T(1):                                                T(1) = 0 =  c11log1  + c2 ⋅ 1 + c3 ⋅ 1 ⋅ log 1
8. Hallamos T(2):                                                T(2) = 1 =  c11log 2 + c2 ⋅ 2 + c3 ⋅ 2 ⋅ log 2
9. Obtenemos el valor de las constantes:                                 c1 = 0; c2 = 0; c3 = 1/2
10. Obtenemos la solución:                                        T(n) = ½ (n log n )

ASIGNACIÓN DE RELACIONES DE RECURRENCIA

Tabla 1. Asignación de relaciones de recurrencia

...