Matemáticas Discretas Taller 7 2015-01 Complejidad de algoritmos y relaciones de recurrencia 1. Sean f (x) y g (x) funciones con dominio los reales o los enteros positivos y conjunto de llegada los números reales. Escribimos f (x) = (g (x)) cuando hay constantes reales positivas C1 y C2 y un número entero positivo k tales que C1 jg (x)j jf (x)j C2 jg (x)j siempre que x > k: En otras palabras, f (x) = O (g (x)) y f (x) = (g (x)) : (a) Explique qué signi…ca que una función sea O (1) : (b) Demuestre que 2 + 4 + 6 + ::: + 2n = (n + 1) (n + 3) = n+2 (d) Demuestre que x + 21 = (x) (c) Demuestre que n2 (n) (e) Demuestre que (6n + 5) (1 + log2 n) = (n log2 n) 2 (f) Demuestre que n + log n = n 2. Seleccione una notación algoritmos: (n) para el número de veces que se ejecuta la instrucción x = x + 1 en los siguientes i=n while (i 1) f f or j = 1 : n b: x = x + 1 i i= 2 g i=1 while (i 2n) f a: x = x + 1 i=i+2 g 3. Considere el siguiente algoritmo recursivo de búsqueda binaria. La entrada es una lista ordenada de números distintos a1 ; a2 ; :::; an y un número x que puede estar o no estar en la lista. El objetivo es encontrar el índice k tal que ak = x: Si x no está en la lista, la salida es 0: Realice una prueba de escritorio para el algoritmo usando la siguiente información: Lista 4; 7; 8; 11; 14; 15; 17 y x = 4: buscabinaria (x; i; j) i+j m= 2 if x == am then lugar = m else if (x < am and i < m) then buscabinaria(x; i; m 1) else if (x > am and j > m) then buscabinaria(x; m + 1; j) else lugar = 0 4. Suponga que el número de bacterias de una colonia se triplica cada hora. (a) Establezca una relación de recurrencia para el número de bacterias al cabo de n horas. (b) Si hay 100 bacterias en el inicio de una nueva colonia, ¿cuántas bacterias habrá en la colonia al cabo de 10 horas? 5. Resuelva las siguientes relaciones de recurrencia: (a) an = an (b) an = 2an 1 + 6an 2; para n 2; a0 = 3; a1 = 6 an 2; para n 2; a0 = 4; a1 = 1 1 1 (c) an = an 2; (d) an+2 = 4an+1 + 5an ; para n (e) an + 3an (f) an 1 2an 1 (g) an + 4an (h) an an 1 1 para n 2; a0 = 5; a1 = n = 2 ; para n 2 = n ; para n + 4an = 2n 2 2 1 0; a0 = 2; a1 = 8 1; a0 = 0 1; a0 = 1 2 = n + n; para n n 1; para n 3; a1 = 1; a2 = 1 1; a0 = 4 6. Suponga que fn es el n esimo número de Fibonacci, es decir, pertenece a la sucesión de…nida asi: f1 = 1; f2 = 1; fn = fn 1 + fn 2 para n 3:. (a) Demuestre que f12 + f22 + ::: + fn2 = fn fn+1 siempre que n sea un entero positivo. (b) Demuestre que f1 + f3 + ::: + f2n 1 = f2n siempre que n sea un entero positivo. 7. La sucesión de Lucas L1 ; L2 ; ::: llamada asi en honor de Édouard Lucas, inventor del juego de las Torres de Hanoi, se de…ne por la relación de recurrencia Ln = Ln 1 + Ln 2; n 3; las condiciones iniciales L1 = 1; L2 = 3: (a) Encuentre L3 ; L4 y L5 : (b) Demuestre que Ln+2 = fn+1 + fn+3 ; n donde f1 ; f2 ; ::: denotan la sucesión de Fibonacci. 2 1;