Diseño Y Analisis de Algoritmos - Ejercicios 1 - Complejidad Soluciones PDF

Preview

Summary

Ejercicios obligatorios resueltos sobre cálculo de la complejidad de algoritmos. Con todos los tipos de ejercicios....

Description

Pr´ actica 2: Complejidad de Algoritmos Dise˜no y An´alisis de Algoritmos atica Grado en Ingenier´ıa Inform´

Soluciones

Ejercicio 1. Demostrar: n ln n = O(n1+a), donde 0 < a < 1. Soluci´on: Podemos demostrar que n1+a (0 < a < 1) es cota superior de n ln n si se verifica: n ln n l´ım 1+a = 0 n→∞ n Procedemos a calcular el l´ımite: l´ım

n→∞

ln n n ln n ∞ = l´ım a = 1+a n→∞ ∞ n n

Aplicando L’Hopital (derivando numerador y denominador) se obtiene: l´ım

n→∞

1/n 1 = l´ım =0 ana−1 n→∞ ana

NOTA: se ha utilizado un logaritmo neperiano, pero el resultado es v´ alido independientemente de la base del logaritmo.

1

Ejercicio 2. Simplificar: O(3m3 + 2mn2 + n2 + 10m + m2 ) Soluci´on: Para simplificar la expresi´on, en primer lugar, podemos eliminar las constantes, quedando: O(m3 + mn2 + n2 + m + m2 )

En segundo lugar, resulta trivial ver que los t´ erminos m y m2 son de menor orden que m3 , por tanto tambi´en se pueden cancelar: O(m3 + mn2 + n2 ) Finalmente n2 tambi´en se puede eliminar dado que el t´ermino mn2 es de mayor orden. Esto puede comprobarse hallando los siguientes l´ımites: l´ım

n→∞

n2 =0 m→∞ mn 2

n2 1 6= ∞ = 2 m mn

l´ım

Como uno es igual a 0 y otro distinto de 0 se verifica que mn2 es de mayor orden n2 . Finalmente la expresi´ on no puede simplificarse m´as, quedando: O(m3 + mn2 ) NOTA: los dos u ´ ltimos t´erminos no se pueden eliminar. No se puede afirmar que m3 sea de mayor orden que mn2 ya que: mn2 =0 m→∞ m 3

mn2 =∞ n→∞ m 3 l´ım

l´ım

Es decir, un l´ımite es 0 y el otro infinito. An´alogamente, tampoco se puede afirmar que mn2 sea de mayor orden que m3 dado que: m3 =∞ m→∞ mn 2

m3 =0 n→∞ mn 2 l´ım

l´ım

2

Ejercicio 3. Demostrar utilizando la definici´on de θ: n2 /4 + 3n − 1 ∈ θ(n2 ) Soluci´on: Para hacer la demostraci´on debemos comprobar que n2 es tanto cota inferior como superior. Es decir, n2 /4 + 3n − 1 ∈ Ω(n2 ) y n2 /4 + 3n − 1 ∈ O(n2 ). Ω: Debemos encontrar un par de constantes positivas c1 y n1 tal que se cumpla: n2 /4 + 3n − 1 ≥ c1 n2 para todo n ≥ n1 . Por ejemplo, podemos elegir c1 = 1/4. En ese caso tenemos n2 /4 + 3n − 1 ≥ n2 /4 3n − 1 ≥ 0 Lo cual se cumple para todo n ≥ 1. Por tanto, simplemente escogemos n1 = 1. Finalmente, hemos visto que existen esas constantes y queda demostrado. O: Debemos encontrar un par de constantes positivas c2 y n2 tal que se cumpla: n2 /4 + 3n − 1 ≤ c2 n2 para todo n ≥ n2 . Por ejemplo, podemos elegir c2 = 1. En ese caso tenemos n2 /4 + 3n − 1 ≤ n2 3n − 1 ≤ 3n2 /4 El orden del termino cuadr´atico naturalmente es superior al lineal, con lo cual la desigualdad se va a cumplir a partir de un n dado. En ese caso, se cumple a partir de n ≥ 4, y podemos elegir n2 = 4. Una vez m´ as, hemos visto que existen esas constantes y queda demostrado. NOTA: pod´ıamos haber elegido otras constantes. Lo importante es que existan, no sus valores concretos.

3

Ejercicio 4. Consid´ erese el siguiente algoritmo, que determina si una matriz cuadrada A de tama˜ no N × N es sim´etrica (A = AT ): 1 2 3 4 5 6 7 8 9 10 11 12 13

es_traspuesta = TRUE; columna = 1; while (columnacolumna) AND es_traspuesta if A(fila,columna)!=A(columna,fila) es_traspuesta = FALSE; end fila = fila-1; end columna = columna+1; end return es_traspuesta;

Se pide hallar la complejidad θ asumiendo que se realiza una operaci´ on por cada l´ınea de c´ odigo (se valorar´ a el uso de sumatorios en la respuesta). Soluci´on: Analizamos la complejidad del algoritmo en el mejor y peor caso: Mejor caso: Si los dos primeros elementos comparados de la matriz son diferentes entonces el algoritmo devuelve el valor FALSE en un n´ umero constante de pasos, independientemente del tama˜ no del problema. Por tanto la complejidad en este caso es: θ(1) Peor caso: El peor caso ocurre cuando la matriz es sim´ etrica, y la variable es traspuesta siempre toma el valor verdadero. Para facilitar los c´ alculos dividimos el c´ odigo en los siguientes bloques:

4

es traspuesta = TRUE; columna = 1; while (columnacolumna) AND es traspuesta if A(fila,columna)!=A(columna,fila) es traspuesta = FALSE; end fila = fila-1; end columna = columna+1; end return es traspuesta; Considerando que se realiza una operaci´ on por cada l´ınea de c´odigo (sin contar los end, ni la instrucci´on en el cuerpo del if, ya que no se ejecuta en el peor caso), la f´ ormula para el tiempo de ejecuci´on suponiendo que la matriz es de tama˜ no N es:

T(N) = 1 + 1 +

N h X

1+1+

c=1

c+1 X

f=N

i (1 + 1 + 1) + 1 + 1 + 1 + 1

Simplificando y resolviendo los sumatorios se obtiene: T (N ) = 4 +

N h X c=1

N h c+1 i i X X 4 + 3(N − c) 4+ 3 = T (N ) = 4 + c=1

f =N

T (N ) = 4 + 4N + 3N 2 − 3 T (N ) =

N X c=1

c = 4 + 4N + 3N 2 − 3

3N 2 5N + +4 2 2

5

∈ θ(N 2 )

N (N + 1) 2

Ejercicio 5. Analizar la complejidad θ del problema de las Torres de Hanoi para n discos. Es decir, hallar la expresi´ on no recursiva del n´ umero de movimientos de discos Tn , para n discos, y describir su cota ajustada θ . (Ayuda: ver el enunciado del siguiente ejercicio). El pseudoc´ odigo del algoritmo es: 1 2 3 4 5

hanoi(int n, int destino, int origen, int auxiliar) if (n > 0) hanoi(n-1, auxiliar, origen, destino); > hanoi(n-1, destino, auxiliar, origen);

Soluci´on: La expresi´ on recursiva del algoritmo es la siguiente: Tn = 2Tn−1 + 1

T0 = 0

Para resolver la recurrencia y hallar una expresi´ on no recursiva de Tn se puede proceder de dos maneras: 1. Expansi´ on de recurrencias: Tn = 2Tn−1 + 1 = 2(2Tn−2 + 1) + 1 = 22 Tn−2 + 2 + 1 = 2(2(2Tn−3 + 1) + 1) + 1 = 23 Tn−3 + 4 + 2 + 1 = 2(2(2(2Tn−4 + 1) + 1) + 1) + 1 = 24 Tn−4 + 8 + 4 + 2 + 1 Se puede ver, por tanto, que la expresi´ on general es: i

Tn = 2 Tn−i +

i−1 X

2j

j=0

Se llega al caso base cuando el par´ ametro de la T es cero. Es decir, cuando n − i = 0. Despejando la i, se obtiene i = n. Sustituyendo en la expresi´on obtenemos: n−1 X n 2j Tn = 2 T0 + j=0

Viendo que T (0) = 0 y resolviendo la serie geom´ etrica queda finalmente: Tn = 2n − 1 ∈ θ(2n )

6

2. M´etodo general de resoluci´ on de recurrencias: La recurrencia se puede expresar como: Tn − 2Tn−1 = 1 · n0 · 1n La cual es una recurrencia no homog´enea, cuya ecuaci´ on caracter´ıstica es: (x − 2)(x − 1) = 0 Por tanto, la soluci´on final tiene la forma Tn = c1 2n + c2 1n = c1 2n + c2 Teniendo en cuenta dos casos base o condiciones iniciales podemos hallar el valor de las constantes resolviendo el siguiente sistema:  c 1 + c 2 = 0 = T0 2c1 + c2 = 1 = T1 De donde obtenemos c1 = 1 y c2 = −1. Finalmente, concluimos que la soluci´ on es: Tn = 2n − 1 ∈ θ(2n ) NOTA: No es necesario resolver el ejercicio usando los dos m´etodos. Uno es suficiente. Por otro lado, tambi´en se pod´ıa haber escogido el caso base T1 = 1 en el m´etodo de expansi´ on de recurrencias.

7

Ejercicio 6. En este ejercicio se pide analizar la complejidad θ del problema de las Torres de Hanoi C´ıclicas para n Torre X

Torre Z

Torre Y

Si a la funci´ on AntiClock la denominamos A, y Clock C, entonces tenemos las siguientes definiciones recursivas del n´ umero de operaciones (movimientos de discos), para n discos:  0 si n = 0 An = (1) 2An−1 + Cn−1 + 2 si n > 0  0 si n = 0 Cn = (2) 2An−1 + 1 si n > 0 Se pide demostrar: i √ √ 1 h An = √ (1 + 3)n+2 − (1 − 3)n+2 − 1 4 3 i √ √ 1 h Cn = √ (1 + 3)n+1 − (1 − 3)n+1 − 1 2 3 Soluci´on: En este ejercicio el primer paso consiste en eliminar la recursividad mutua, y expresar las funciones An y Cn en t´erminos de s´ı mismas. Dado que Cn = 2An−1 + 1, decrementando el ´ındice una unidad obtenemos Cn−1 = 2An−2 + 1. Sustituyendo en (1) logramos una definici´on recursiva que s´ olo depende de A, a la que a˜ nadimos los dos casos base necesarios:  si n = 0 0 2 si n = 1 An =  2A si n ≥ 2 n−1 + 2An−2 + 3

Se puede observar que A1 = C0 + 2 = 2. Adem´ as A2 = 7.

8

Tambi´en podemos hallar una expresi´on recursiva de C solamente en t´ erminos de s´ı misma. Por ejemplo, de (2) obtenemos las igualdades 2An−1 = Cn − 1, y An = (Cn+1 − 1)/2, que podemos sustituir en (1) para obtener: Cn+1 − 1 = Cn − 1 + Cn−1 + 2 2 Cn+1 = 2Cn + 2Cn−1 + 3 Finalmente, decrementando el ´ındice y a˜ nadiendo los casos base, se obtiene:  si n = 0 0 1 si n = 1 Cn =  2C si n ≥ 2 n−1 + 2Cn−2 + 3

Se puede observar que C1 = A0 + 1 = 1. Adem´ as C2 = 5. En primer lugar, desarrollamos la f´ormula no recursiva para A resolviendo la recurrencia no homog´enea: An − 2An−1 − 2An−2 = 3 La ecuaci´ on caracter´ıstica es: (x2 − 2x − 2)(x − 1) = 0 Las ra´ıces del primer polinomio son: √ √ 2± 4+8 x= = 1± 3 2 Por tanto, la ecuaci´ on caracter´ıstica es: √ √ (1 + 3)(1 − 3)(x − 1) = 0 Y la soluci´ on tiene la siguiente forma: √ √ An = c1 (1 + 3)n + c2 (1 − 3)n + c3 1n Para hallar los valores de las constantes resolvemos el siguiente sistema de ecuaciones, usando 3 casos base:  c + c + c = 0 = A 1 2 3 0  √ √ c1 (1 + 3) + c2 (1 − 3) + c3 = 2 = A1 √ √  c1 (1 + 3)2 + c2 (1 − 3)2 + c3 = 7 = A1 De la primera ecuaci´on obtenemos

c3 = −c1 − c2 9

(3)

que sustituimos en las dos restantes ecuaciones para obtener:  √ √ c1 (1 + + c2 (1 −√ 3) − c1 − c2 = 2 √ 3) c1 (1 + 3)2 + c2 (1 − 3)2 − c1 − c2 = 7 De la primera ecuaci´on se obtiene la expresi´ on: 2 c1 = √ + c2 3

(4)

que sustituyendo en la segunda se puede verificar que el valor de la constante c2 es: √ √ √ √ 3−2 (1 − 3)2 4−2 3 2− 3 √ c2 = √ = − √ = − √ =− 4 3 4 3 2 3 2 3 Sustituyendo el valor de c2 en (4) se obtiene: √ √ √ √ 4 + 2 3 (1 + 3)2 2+ 3 2 3−2 √ √ √ = = c1 = √ + √ = 4 3 4 3 2 3 2 3 3 Finalmente, sustituyendo c1 y c2 en (3) se obtiene c3 = −1, con lo cual la definici´ on de A resulta ser: i √ √ √   1 h (5) An = √ (1 + 3)n+2 − (1 − 3)n+2 − 1 ∈ θ (1 + 3)n 4 3 tal y como se hab´ıa pedido. La expresi´ on no recursiva de Cn se puede hallar de forma an´aloga, resolviendo un sistema de ecuaciones lineales. Sin embargo, dado que ya se ha calculado una expresi´ on no recursiva para An , podemos combinar (2) y (5) para hallar Cn :   √ n+1 √ n+1 i 1 h − (1 − 3) −1 +1 Cn = 2An−1 + 1 = 2 √ (1 + 3) 4 3 i √ √ 1 h Cn = √ (1 + 3)n+1 − (1 − 3)n+1 − 1 2 3

10

√   ∈ θ (1 + 3)n

Ejercicio 7. Demostrar que log(n!) ∈ Ω(n log n), de dos formas diferentes: a) Usando la aproximaci´ on de Stirling (0.1 puntos):  n n √ n! ∼ 2πn e para valores muy grandes de n. b) Utilizando la definici´on de Ω. Ayuda: usad la aproximaci´ on por integrales (0.2 puntos) Soluci´on:

a) Podemos demostrar que n log n es cota inferior de log(n!) si se verifica: log(n!) >0 n→∞ n log n l´ım

Procedemos a calcular el l´ımite: l´ım

n→∞

log(n!) ∞ = ∞ n log n

Aplicamos la aproximaci´ on de Stirling (ya que estamos calculando el l´ımite cuando n toma valores muy grandes): √ √  n  n √ log( 2πn ne ) log 2π + log n + log ne = = l´ım l´ım n→∞ n→∞ n log n n log n √ log 2π + 21 log n + n log ne = l´ım n→∞ n log n √ log 2π + 21 log n + n log n − n log e l´ım = n→∞ n log n 0+0+1+0= 1>0 En efecto, como el l´ımite es una constante, no solo log(n!) ∈ Ω(n log n), sino que adem´ as log(n!) ∈ Θ(n log n). b) Utilizando la definici´on de Ω tenemos que demostrar que existe una constante c > 0 y un n0 > 0 tal que log(n!) ≥ cn log n para tono n ≥ n0 . Comenzamos transformando la parte izquierda en un sumatorio: log(n!) =

n X

log i =

i=1

11

n X i=2

log i

El logaritmo es una funci´on mon´ otona creciente, por lo que se puede acotar utilizando la aproximaci´ on por integrales. En este caso nos interesa encontrar una cota inferior: Z n n X log x dx log i ≥ 1

i=2

Resolviendo la integral por partes: Z n h in log x dx = x log x − x = n log n − n − 0 + 1 1

1

Por tanto, combinando estos resultados: Z n n X log(n!) = log x dx = n log n − n + 1 ≥ cn log n log i ≥ 1

i=2

Lo cual implica que si podemos demostrar que n log n es cota inferior de n log n − n + 1, entonces necesariamente ser´a cota inferior de log(n!). De esta manera, solo queda encontrar las constantes c y n0 para: n log n − n + 1 ≥ cn log n Escojamos c = 1/2: 1 n log n − n + 1 ≥ n log n 2 n Lo cual es cierto para:

1 n log n − n + 1 ≥ 0 2

⇒

⇒

 1 log n − 1 + 1 ≥ 0 2

1 log n − 1 ≥ 0 2

⇒

log n ≥ 2

Finalmente, para cualquier base del logaritmo b, la desigualdad se cumple para todo n ≥ b2 , y podemos escoger un valore de n0 = b2 finito y positivo, terminando la demostraci´on.

12...