66 Problemas resueltos de análisis y diseño de algoritmos

66 problemas resueltos de Análisis y Diseño de Algoritmos
Rosa Arruabarrena Jesús Bermúdez

Informe interno: UPV/EHU /LSI / TR 8-99 REVISADO

15 de Octubre del 2000

PARTE I: Problemas
1. Supuesto que ∀n≥n0 f(n)≥g(n)≥0 y que f(n),g(n) ∈ Θ(h(n)), ¿qué puedes decir del orden de f(n)-g(n)?

2.

Demuestra que ∀a,b (a,b>1 ⇒ lga n ∈Θ b n)). ∈Θ(lg Si a≠b, ¿es cierto 2lga n ∈ Θ(2lgb n)?3.

Justifica si son ciertas o falsas las afirmaciones siguientes, siendo f(n) y h(n) funciones de coste resultantes de analizar algoritmos: (a) O(f(n)) = O(h(n)) ⇒ O(lgf(n)) = O(lgh(n)) (b) O(lgf(n)) = O(lgh(n)) ⇒ O(f(n)) = O(h(n))

4.

Sea t(n) el número de líneas generadas por una realización del procedimiento G(n).
procedure G ( x: in INTEGER) is begin for I in 1..x loop for J in 1..Iloop PUT_LINE(I,J,x); end loop; end loop; if x>0 then for I in 1..4 loop G(x div 2); end loop; end if; end G;

Calcula el orden exacto de la función t(n).

5.

Un natural n≥1 es triangular si es la suma de una sucesión ascendente no nula de naturales consecutivos que comienza en 1. (Por tanto, los cinco primeros números triangulares son 1, 3=1+2, 6=1+2+3, 10=1+2+3+4, 15=1+2+3+4+5.) (a) Escribeun programa que, dado un entero positivo n≥1, decida si éste es un número triangular con eficiencia incluida en O(n) y empleando un espacio extra de memoria constante. (b) Analiza tu programa.

1

6.

Supongamos que cada noche disponemos de una hora de CPU para ejecutar cierto programa y que con esa hora tenemos suficiente tiempo para ejecutar un programa con una entrada, a lo sumo, detamaño n= 1 000 000. Pero el centro de cálculo tras una reasignación de tiempos decide asignarnos 3 horas diarias de CPU. Ahora, ¿cuál es el mayor tamaño de entrada que podrá gestionar nuestro programa, si su complejidad T(n) fuera (para alguna constante ki)? (a) k1 n (b) k2 n2 (c) k3 10n

7.

Supongamos que cada noche disponemos de una hora de CPU para ejecutar cierto programa y que con esa horatenemos suficiente tiempo para ejecutar un programa con una entrada, a lo sumo, de tamaño n= 1 000 000. En esta situación nuestro jefe compra una máquina 100 veces más rápida que la vieja. Ahora ¿cuál es el mayor tamaño de entrada que podrá gestionar nuestro programa en una hora, si su complejidad T(n) fuera (para alguna constante ki)? (a) k1 n (b) k2 n2 (c) k3 10n

8.

Escribe un algoritmoque calcule los valores máximo y mínimo de un vector con n valores realizando para ello menos de (3n/2)comparaciones entre dichos valores. Demuéstrese que la solución propuesta realiza menos comparaciones que las mencionadas.

9.

Resuélvase la siguiente ecuación de recurrencia. ¿De qué orden es? n =1 a T(n) = 2T  n  + lgn n > 1   4

10. Calcula el orden temporal de los siguientesprogramas:
(a) function total(n:positivo) if n=1 then 1 else total(n-1) + 2 ∗ parcial(n-1) siendo function parcial (m:positivo) if m=1 then 1 else 2 ∗ parcial(m-1) (b) function total(n,m:positivo) if n=1 then m else m + total (n-1, 2 ∗ m)

2

11. El siguiente algoritmo es utilizado por muchos editores de texto. Busca la primera aparición de un string (esto es, de un array de caracteres B(1..m)en el string A(1..n) ), devolviendo el índice de A donde comienza B, si procede. El valor Limite=n-m+1 es la posición más a la derecha en A donde podría comenzar B.
procedure StringSearch (A,B: in String; Comienzo: out Encontrado:= false; Limite:= n-m+1; Hallado: out boolean; Indice) is I, J : Indice; Com:= A'First;

N:= A'Length; M:= B'Length; begin while not Encontrado and (Com ≤ Limite) loopI:= Com; J:= B'First; while J/= M+1 and then (A(i)=B(j)) loop I:= I+1; J:=J+1; end loop; Encontrado:= (J=M+1); if not Encontrado then Com:= Com+1; end if; end loop; Hallado:= Encontrado; Comienzo:= Com; end StringSearch;

¿Cuántas veces se ejecuta la comparación A(i)=B(j) en el peor caso? ¿Qué entradas dan lugar al peor caso? Obsérvese que, usando el lenguaje de programación Ada, el test sólo...