Guia Nalisis Y Diseño De Algoritmos

Dise˜o de algoritmos
n
Jes´s Berm´dez de Andr´s. UPV-EHU
u
u
e
Ejercicios: An´lisis de algoritmos
a
Curso 2008-09
o
1. Con un algoritmo de funci´n de coste temporal f (n) = n3 resolvemos problemas de tama˜o K en una hora. ¿Hasta qu´ tama˜o podremos resolver, en el
n
e
n
mismo tiempo, con una m´quina 1000 veces m´s r´pida? ¿Y si la funci´n de
a
aa
o
n?
coste fuese f (n) = 2
2.Disponemos de dos algoritmos A y B para resolver el mismo problema, con
implementaciones que realizan 8n2 y 64n lg n operaciones elementales, para
entradas de tama˜o n, respectivamente. Determine para qu´ tama˜os de la
n
e
n
entrada, el algoritmo A es m´s r´pido que B .
aa
e
n
a
aa
3. Determine para qu´ tama˜os de entrada, en la misma m´quina, es m´s r´pido
un algoritmo con funci´n decoste 100n2 que otro con funci´n de coste 2n .
o
o
4. Analice el siguiente algoritmo, definiendo la funci´n de coste pertinente y eso
pecificando claramente qu´ es lo que se est´ considerando como tama˜o de la
e
a
n
entrada.
func Es Equilibrado (V , inicio, fin ) return integer
for i in inicio .. fin loop
izq ← 0;
for k in inicio .. i − 1 loop izq ← izq+V (k ); end loop;
der ← 0;
for kin i .. fin loop der ← der+V (k ); end loop;
if izq = der then return i;
end loop;
return 0;

o
5. El siguiente algoritmo busca la primera aparici´n de un string B (1..k ) en
el string A(1..n); devuelve true y el ´
ındice de A donde comienza B , si lo
encuentra; y false en caso contrario. El valor n − k + 1 es la posici´n m´s a la
o
a
derecha en A donde podr´ comenzar B .
ıa
funcStringSearch (A, B : String) return (boolean, natural)
N ← A.length; K ← B.length; Inicio ← A.f irstIndex;

1

UPV-EHU. Dise˜o de algoritmos
n

2

Encontrado ← f alse;
Limite ← N-K+1;
while not Encontrado and Inicio ≤ Limite loop
I ← Inicio;
J ← B.f irstIndex;
while J = K+1 and then (A(i) = B (j )) loop
I ← I+1; J ← J+1;
end loop ;
Encontrado ← (J=K+1);
if not Encontrado thenInicio ← Inicio+1;
end loop ;
return (Encontrado, Inicio)
¿Cu´ntas veces se ejecuta la comparaci´n A(i) = B (j ) en el peor caso? ¿Qu´ ena
o
e
tradas dan lugar al peor caso? Obs´rvese que el operador booleano and then
e
hace que la comprobaci´n s´lo se realice cuando sea verdadera la condici´n J
oo
o
= K+1.
6. El siguiente algoritmo realiza una b´squeda secuencial de un n´mero X en
u
uuna tabla T(I..F). Determine cu´ntas comparaciones, del n´mero X con un
a
u
elemento de la tabla T , se realizan en el caso peor y en el caso medio.
func Busqueda Secuencial (T : Tabla; I, F : integer; X : integer)
return boolean
Actual ← I
while Actual ≤ F and then T (Actual) = X loop
Actual ← Actual+1
end loop
if Actual > F then return false
else return true
u
o
7. Un n´mero naturaln ≥ 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
u
y 15 = 1 + 2 + 3 + 4 + 5.
a ) Escriba un algoritmo que, dado un entero positivo n ≥ 1, decida si ´ste
e
es un n´mero triangular.
u
b ) Analice su algoritmo.
o
8. Calculela funci´n de coste temporal de los siguientes algoritmos:
a ) func Serie (n, m: natural) return natural
if n ≤ 1 then return m
else return m + Serie(n − 1, 2 × m)

UPV-EHU. Dise˜o de algoritmos
n

3

b ) func Total (n: natural) return natural
if n ≤ 1 then return 1
else return Total(n − 1) + 2 × Parcial(n − 1)
siendo
func Parcial (k : natural) return natural
if k ≤ 1 then return1
else return 2 × Parcial(k − 1)
9. Dado el algoritmo siguiente, que determina si una cadena C es pal´
ındromo:
func Pal (C, i, j ) return booleano
if i ≥ j then return verdadero
elsif C (i) = C (j ) then return falso
else return Pal(C, i + 1, j − 1)
Analice la evaluaci´n de Pal(C, 1, n) en el caso peor y en el caso medio,
o
suponiendo equiprobabilidad de todas las entradas y siendo...