s1 = ‘C’, s2 = ‘G’, s3 = ‘J ’, s4 = ‘M’, s5 = ‘X’.
1. Muestre cómo se ejecuta el algoritmo 7.3.2 en el caso de clave = ‘G’.
7.3.2). Pruebe que an≤ an+1 para n ≥ 1.
de búsqueda binaria (algoritmo 7.3.2) en el peor caso para una sucesión
que contiene n elementos, entonces para todo entero positivo
n.
an = 2 + lg n
binaria:
búsqueda_binaria2(s, i, j, clave) {
if (i > j)
return 0
k = (i + j)/2
if (clave == sk)
return k
k1 = búsqueda_binaria2(s, i, k − 1, clave)
k2 = búsqueda_binaria2(s, k + 1, j, clave)
return k1 + k2
}
a) Demuestre que búsqueda_binaria2 es correcto; es decir, si clave
está presente, el algoritmo regresa su índice, pero si clave no
está presente, regresa 0.
b) Encuentre el tiempo de corrida en el peor caso de búsqueda_binaria2.
n artículos y que el algoritmo B requiere n2/4 comparaciones
para ordenar n artículos. ¿Para cuál n el algoritmo B es superior a A?
1, 9, 7, 3.
2, 3, 7, 2, 8, 9, 7, 5, 4.
11. Suponga que se tienen dos sucesiones, cada una de tamaño n, ordenadas
en orden no decreciente.
a) ¿En qué condiciones ocurre el máximo número de comparaciones
en el algoritmo 7.3.5?
b) ¿En qué condiciones ocurre el mínimo número de comparaciones
en el algoritmo 7.3.5?
una entrada para la que
an = a n/2 + a (n+1)/2 + n − 1.
13. ¿Cuál es el número mínimo de comparaciones requeridas por el
algoritmo 7.3.8 para ordenar una arreglo de tamaño 6?
algoritmo 7.3.8 para ordenar un arreglo de tamaño 6?
que an≤ an+1 para toda n ≥ 1.
en el peor caso. Demuestre que an≤ 3n lg n para n = 1, 2, 3, . . . .
comparaciones.
Los ejercicios 18 al 22 se refieren al algoritmo 7.3.11.
Algoritmo 7.3.11
Cálculo de una exponencial
Este algoritmo calcula an de manera recursiva, donde a es un número
real y n es un entero positivo
Entrada: a (número real), n (entero positivo)
Salida: an
1. exp1(a, n) {
2. if (n == 1)
3. return a
4. m = n/2
5. return exp1(a, m)*exp1(a, n − m)
6. }
Sea bn el número de multiplicaciones (línea 5) requeridas para calcular
an.
18. Explique la manera en que el algoritmo 7.3.11 calcula an.
19. Encuentre la relación de recurrencia y las condiciones iniciales para
la sucesión {bn}.
21. Resuelva la relación de recurrencia del ejercicio 19 para el caso en
el que n es una potencia de 2.
Los ejercicios 23 al 28 se refieren al algoritmo 7.3.12.
Algoritmo 7.3.12
Cálculo de una exponencial
Este algoritmo calcula an de forma recursiva, donde a es un número real
y n es un entero positivo.
Entrada: a (número real), n (entero positivo)
Salida: an
1. exp2(a, n) {
2. if (n == 1)
3. return a
4. m = n/2
5. potencia = exp2(a, m)
6. potencia = potencia * potencia
7. if (n es par)
8. return potencia
9. else
10. return potencia * a
11. }
Sea bn el número de multiplicaciones (líneas 6 y 10) requeridas para
calcular an.
23. Explique la forma en que el algoritmo 7.3.12 calcula an.
el que n es una potencia de 2.
Los ejercicios 29 al 34 se refieren al algoritmo 7.3.13.
Algoritmo 7.3.13
Encontrar los elementos más pequeño y más grande en una
sucesión
Este algoritmo recursivo encuentra los elementos menor y mayor en
una sucesión.
Entrada: si, . . . , sj, i y j
Salida: mayor (el elemento más grande en la sucesión), menor
(el elemento más pequeño en la sucesión)
1. mayor_menor (s, i, j, mayor, menor) {
2. if (i == j) {
3. mayor = si
4. menor = si
5. return
6. }
7. m = (i + j)/2
8. mayor_menor (s, i, m, mayor_izq, menor_izq)
9. mayor_menor (s, m + 1, j, mayor_der, menor_der)
10. if (mayor_izq > mayor_der)
11. mayor = mayor_izq
12. else
13. mayor = mayor_der
14. if (menor_izq > menor_der)
15. menor = menor_der
16. else
17. menor = menor_izq
18. }
Sea bn el número de comparaciones (líneas 10 y 14) requeridas para
una entrada de tamaño n.
29. Explique la forma en que el algoritmo 7.3.13 encuentra los elementos
mayor y menor.
30. Demuestre que b1= 0 y b2= 2.
32. Establezca la relación de recurrencia
bn = b n/2 + b (n+1)/2 + 2para n > 1.
33. Resuelva la relación de recurrencia (7.3.12) para el caso en el que
n es una potencia de 2, para obtener
bn = 2n − 2, n = 1, 2, 4, . . . .
34. Use inducción matemática para demostrar que
para todo entero positivo n.
Los ejercicios 35 al 38 se refieren al algoritmo 7.3.13, con los siguientes
renglones insertados después de la línea 6.
6a. if (j == i + l) {
6b. if (si > sj) {
6c. mayor = si
6d. menor = sj
6e. }
6f. else {
6g. menor = si
6h. mayor = sj
6i. }
6j. return
6k. }
Sea bn el número de comparaciones (líneas 6b, 10 y 14) para una entrada
de tamaño n.
n > 2.
38. Resuelva la relación de recurrencia (7.3.12) para el caso en el que
n es una potencia de 2 para obtener
bn = 3n/2 − 2, n = 2, 4, 8, . . . .
39. Modifique el algoritmo 7.3.13 insertando las líneas que preceden
al ejercicio 35 después de la línea 6 y sustituyendo la línea 7 con
lo siguiente:
7a. if (j − i es impar ∧ (1 + j − i)/2 es impar)
7b. m = (i + j)/2 - 1
7c. else
7d. m = (i + j)/2
Demuestre que en el peor caso, este algoritmo modificado requiere
cuando mucho (3n/2) − 2 comparaciones para encontrar los elementos
mayor y menor en una arreglo de tamaño n.
Algoritmo 7.3.14
Orden de inserción (versión recursiva)
Este algoritmo ordena la sucesión
s1, s2, . . . , sn
en orden no decreciente ordenando de manera recursiva los primeros n
− 1 elementos y después insertando sn en la posición correcta.
Entrada: s1, s2, . . . , sn y la longitud n de la sucesión
Salida: s1, s2, . . . ,sn arreglados en orden no decreciente
1. orden_inserción(s, n) {
2. if (n == 1)
3. return
4. orden_inserción(s, n − 1)
5. i = n − 1
6. temp = sn
7. while (i ≥ 1 ∧ si > temp) {
8. si+1= si
9. i = i − 1
10. }
11. si+l= temp
12. }
Sea bn el número de veces que se hace la comparación si > temp en la
línea 7 en el peor caso. Suponga que si i < 1, esa comparación no se
hace.
40. Explique cómo ordena la sucesión el algoritmo 7.3.14.
7.3.14?
Algoritmo 7.3.15
Entrada: s1, . . . , sn, n
Salida: s1, . . . , sn
algorl(s, n) {
i = n
while(i ≥ 1) {
si= si+ 1
i = i/2
}
n = n/2
if(n ≥ 1)
algorl(s, n)
}
Sea bn el número de veces que se ejecuta la instrucción si= si+ 1.
45. Encuentre una relación de recurrencia para la sucesión {bn} y calcule
b1, b2 y b3.
46. Resuelva la relación de recurrencia del ejercicio 45 para el caso en
el que n es una potencia de 2.
48. Encuentre una notación teta en términos de n para el número de
veces que se llama a algor2 cuando se invoca como algor2(1, n).
algor2(i, j) {
if (i == j)
return
k = (i + j)/2
algor2(i, k)
algor2(k + 1, j)
}
Los ejercicios 49 al 53 se refieren al algoritmo 7.3.16.
Algoritmo 7.3.16
Entrada: Una sucesión si, . . . , sj de ceros y unos
Salida: si, . . . , sj donde todos los ceros preceden a todos los unos
ordenar(s, i, j) {
if (i == j)
return
if (si== 1){
cambiar(si, sj)
ordenar(s, i, j − 1)
}
else
ordenar(s, i + 1, j)
}
49. Use inducción matemática sobre n, el número de artículos en la sucesión
de entrada, para probar que ordenar de hecho produce como
salida un versión rearreglada de la sucesión de entrada en la que todos
los ceros preceden a todos los unos. (El paso base es n = 1).
Sea bn el número de veces que se llama a ordenar cuando la sucesión
de entrada contiene n elementos.
50. Encuentre b1, b2 y b3.
51. Escriba una relación de recurrencia para bn.
52. Despeje bn de la relación de recurrencia del ejercicio 51.
53. En la notación teta, ¿cuál es el tiempo de corrida de ordenar como
una función de n, el número de elementos en la sucesión de entrada?
54. Resuelva la relación de recurrencia
an = 3a n/2 + n, n > 1,
para el caso en el que n es una potencia de 2. Suponga que a1= 1.
55. Demuestre que an= (nlg3), donde an se define como en el ejercicio 54.
Los ejercicios 56 al 63 se refieren a un algoritmo que acepta como entrada
la sucesión
si, . . . , sj.
Si j > i, los subproblemas
si , . . . , s (i+j )/2 s (i+j )/2+1 , . . . , s j
se resuelven de manera recursiva. Las soluciones a subproblemas de
tamaño m y k pueden combinarse en el tiempo cm,k para resolver el problema
original. Sea bn el tiempo requerido por el algoritmo para una
entrada de tamaño n.
56. Escriba una relación de recurrencia para bn suponiendo que cm,k= 3.
57. Escriba una relación de recurrencia para bn suponiendo que cm,k=m + k.
58. Resuelva la relación de recurrencia del ejercicio 56 para el caso en
el que n es una potencia de 2, suponiendo que b1= 0.
59. Resuelva la relación de recurrencia del ejercicio 56 para el caso en
el que n es una potencia de 2, suponiendo que b1= 1.
60. Resuelva la relación de recurrencia del ejercicio 57 para el caso en
el que n es una potencia de 2, suponiendo que b1= 0.
61. Resuelva la relación de recurrencia del ejercicio 57 para el caso en
el que n es una potencia de 2, suponiendo que b1= 1.
62. Suponga que si m1≥ m2 y k1≥ k2, entonces . Demuestre
que la sucesión b1, b2, . . . es no decreciente.
63. Suponiendo que cm,k= m + k y b1= 0, demuestre que bn≤ 4n lg n.
Los ejercicios 64 al 69 se refieren a la siguiente situación. Sea Pn un
problema específico de tamaño n. Si Pn se divide en subproblemas de
tamaños i y j, existe un algoritmo que combina las soluciones de estos
subproblemas en una solución de Pn en un tiempo de cuando mucho
2 + lg(ij). Suponga que ya se resolvió un problema de tamaño 1.
64. Escriba una relación de recurrencia para obtener Pn similar a la del
algoritmo 7.3.8.
65. Sea an el tiempo en el peor caso para obtener Pn con el algoritmo
del ejercicio 64. Demuestre que
an ≤ a n/2 + a (n+1)/2 + 2 lg n.
66. Sea bn la relación de recurrencia obtenida en el ejercicio 65 sustituyendo
“≤” por “=”. Suponga que b1= a1= 0. Demuestre que
si n es una potencia de 2,
bn = 4n − 2 lg n − 4.
67. Demuestre que an≤ bn para n = 1, 2, 3, . . . .
68. Demuestre que bn≤ bn+1 para n = 1, 2, 3, . . . .
70. Suponga que {an} es una sucesión no decreciente y que siempre
que m divide a n, an = an/m + d,
donde d es un número real positivo y m es un entero que satisface
m > 1. Demuestre que an= (lg n).
71. Suponga que {an} es una sucesión no decreciente y que siempre
que m divide a n,
an = can/m + d,
donde c y d son números reales que satisfacen c > 1 y d > 0, y m
es un entero que satisface m > 1. Demuestre que
72. [Proyecto] Investigue otros algoritmos para ordenar. Considere específicamente
la complejidad, los estudios empíricos y las características
especiales de los algoritmos (vea [Knuth, 1998b]).
