PDF de programación - 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 ∈Θ∈Θ∈Θ∈Θ(lgb n)).



3. Justifica si son ciertas o falsas las afirmaciones siguientes, siendo f(n) y h(n) funciones

Si a≠b, ¿es cierto 2lga n ∈∈∈∈ ΘΘΘΘ(2lgb n)?

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
begin

for I in 1..x loop

G

( x: in INTEGER) is

for J in 1..I loop

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) Escribe un 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, de tamañ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

(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 hora tenemos 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)?



8. Escribe un algoritmo que 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?

T(n) =

a


2T



n

4




n = 1
+ lgn n > 1



10. Calcula el orden temporal de los siguientes programas:

(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; Hallado: out boolean;

N:= A'Length;
M:= B'Length;

begin

Comienzo: out Indice) is

Encontrado:= false;
Limite:= n-m+1;

I, J : Indice;
Com:= A'First;

while not Encontrado

and

(Com ≤ Limite) loop

I:= Com; J:= B'First;
while J/= M+1 and then
I:= I+1; J:=J+1;

end loop;
Encontrado:= (J=M+1);
if

not Encontrado

then

(A(i)=B(j))

loop

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 se comprueba una vez que es cierta la condición J/= M+1.



12. Para ordenar el vector de n elementos <e1, e2, ...,en> se utiliza una estrategia análoga
al Mergesort pero dividiendo el vector en n/2 trozos de tamaño 2 y generalizando el
Merge a n/2 secuencias.

escríbase la función de eficiencia temporal justificando cada uno de los
sumandos de la misma, y

determínese el orden.



13. Dado el algoritmo siguiente, que determina si una cadena C es palíndromo:

•


•



función PAL (C, i, j) devuelve booleano

if i≥j then devuelve cierto
elsif C(i)≠C(j) then devuelve falso
else devuelve PAL(C, i+1, j-1)

Analiza la evaluación de PAL(C, 1, n) en el caso peor y en el caso medio, suponiendo
equiprobabilidad de todas las entradas y siendo {a, b} el alfabeto que forma las
cadenas.



14. Para resolver cierto problema se dispone de un algoritmo trivial cuyo tiempo de
ejecución t(n) -para problemas de tamaño n- es cuadrático (i.e. t(n)∈Θ(n2)). Se ha



3

encontrado una estrategia Divide y Vencerás para resolver el mismo problema; dicha
estrategia realiza D(n)= n log n operaciones para dividir el problema en dos
subproblemas de tamaño mitad y C(n)= n log n operaciones para componer una
solución del original con la solución de dichos subproblemas. ¿Es la estrategia Divide
y Vencerás más eficiente que la empleada en el algoritmo trivial?



15. Dado el siguiente algoritmo para calcular el máximo y el mínimo de un vector de
enteros, determínese el Nº DE COMPARACIONES entre componentes del vector que
se realizan en el caso peor.

MAX_MIN (T[i..j], Max, Min)

T[i] • T[j]

entonces Max:= T[j]; Min:= T[i];

Max:= T[i]; Min:= T[j];

i+1 j-1

entonces

MAX_MIN (T[i+1..j-1], Aux_Max, Aux_Min);
si
si Aux_Min < Min

Max < Aux_Max entonces
entonces

Max:= Aux_Max;
Min:= Aux_Min;

fin si;
fin si;

proc


-- i ≤ j
si
sino
fin si;
si

fin si;
fin proc;



16. Teniendo una secuencia de n claves distintas a ordenar, considérese la siguiente

variación del algoritmo de Ordenación por Inserción:



Para 2≤i≤n: insertar S(i) entre S(1)≤S(2)≤...≤S(i-1) empleando la
búsqueda dicotómica para determinar la posición correcta donde debe
ser insertado S(i).

Es decir, el algoritmo de inserción para determinar la posición donde debe insertarse
S(i) hará uso del siguiente algoritmo:

Alg BUSQ_DICOT_POSICION(Sec, Valor) devuelve Posición
-- Valor ∉ Hacer_Cjto(Sec)
Sec'Length=1

ent

si

Sec(Sec'First)<Valor
devolver Sec'First

si
else
si

sino

Sec((Sec'length)/2)<Valor

ent

ent

devolver

Sec'First+1

devolver BUSQ_DICOT_POSICION(Sec(((Sec'length)/2)+1)

..Sec'Last),

sino devolver BUSQ_DICOT_POSICION(Sec(Sec'First..

((Sec'length)/2)-1)), Valor)

Valor)

Ejemplos:



S
2
1



5
2

8
3

18
4

20
5

30
6

...
BUSQ_DICOT_POSICION(S(1..6), 1) → Posición: 1
BUSQ_DICOT_POSICION(S(1..6), 3) → Posición: 2
BUSQ_DICOT_POSICION(S(1..6), 9) → Posición: 4
BUSQ_DICOT_POSICION(S(1..6), 37) → Posición: 7

i

Valor ... S(n)

n

Analizar lo siguiente de esta variante del algoritmo de Ordenación por Inserción.



4

a) Comparaciones entre claves:



¿Cuál es un caso peor?
¿Cuál es el orden del número de comparaciones entre claves que se harán en
ese peor caso?


b) Movimientos de claves:
¿Cuál es el caso peor?


¿Cuántos movimientos de claves en total se harán en el peor caso?

c) ¿Cuál es el orden del tiempo de ejecución del algoritmo en el peor caso?



17. Hemos diseñado la siguiente versión del algoritmo Mergesort con intención de evitar

el uso de espacio extra de orden lineal.
Analice su eficiencia temporal.

procedure MERGESORT_SOBRE_VECTOR (V: in out VECTOR,

I,J: in INDICE) is

K: INDICE:= I+J/2;

ES_PEQUEÑO(I,J)

then

SIMPLE_SORT(V,I,J);

begin
if
else

MERGESORT_SOBRE_VECTOR(V,I,K);
MERGESORT_SOBRE_VECTOR(V,K+1,J);
MERGE_SOBRE_VECTOR(V,I,K,J);

end if;

end MERGESORT_SOBRE_VECTOR;



siendo MERGE_SOBRE_VECTOR(V,I,X,J) un procedimiento que ordena el
segmento V(I..J) del vector V cuando recibe dos segmentos ordenados que ocupan
posiciones consecutivas V(I..X) y V(X+1..J)

procedure MERGE_SOBRE_VECTOR (V: in out VECTOR, I,X,J: in INDICE) is

Izq: INDICE:=I; Der: INDICE:=X+1;
Aux: ELEM_VECTOR;

begin

while

Izq \= Der

loop
V(Izq)>V(Der)

if

then

end if;
Izq:= Izq+1;

end loop;

end MERGESORT_SOBRE_VECTOR;

Aux:= V(Izq);
V(Izq):=V(Der);
Insertar Aux en V(Der..J) dejándolo ordenado;



18. Suponga que vamos a utilizar el siguiente algoritmo para encontrar las k mayores

claves de una lista de n claves.

function

LAS_K_MAYORES_CLAVES (Vec: in VECTOR; K: in INTEGER)

return VECTOR is

M: VECTOR;
Claves: VECTOR(1..K);

begin
Crear montículo M con las n claves;

for

J

in 1 .. K

loop

5

Claves(J):= M(1);
M(1):= M(n-J+1);
HUNDIR_RAIZ(M(1..n-J));



end loop;
return Claves;

end LAS_K_MAYORES_CLAVES;

-- trasladar el último a la raíz

¿ De qué orden (en función de n) puede ser k para que este algoritmo sea de O(n)?



19. El siguiente algoritmo puede emplearse para buscar un nombre en un listín telefónico

(Obviamente el listado está ordenado alfabéticamente):

function

BUSCO

(Lis: in Listado; Apellido: in String;
Salto: in Positive) return Integer is

-- Se supone que Apellido está en Lis.
-- Devuelve el índice donde se encuentra Apellido en Lis.
begin

Indice:= Lis'First+Salto-1;
while

Lis'Last>Indice

Indice:= Indi