Notas

Apuntes de Estructuras de Datos
Facultad de Ingeniera Electrica

Jose Ortiz Bejar
[email protected]
Garibaldi Pineda Garca
[email protected]
2
Indice general
1. Modelo de datos, Iteracion y Recursi on 13
1.1. Programaci on Iterativa . . . . . . . . . . . . . . . . . . . . . . 13
1.1.1. Iteracion mediante FOR . . . . . . . . . . . . . . . . . 13
1.1.2. Iteracion WHILE . . . . . . . . . . . . . . . . . . . . . 14
1.1.3. Iteracion DO WHILE . . . . . . . . . . . . . . . . . . . 15
1.1.4. Como elegir que estructura de iteraci on utilizar . . . . 15
1.2. Pruebas inductivas . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1. Ejemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.2. Ejemplo 2: Suma geometrica . . . . . . . . . . . . . . . 20
1.2.3. Ejemplo 3 . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3. Deniciones y funciones Recursivas . . . . . . . . . . . . . . . 21
1.3.1. El factorial . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.2. M aximo com un divisor . . . . . . . . . . . . . . . . . . 24
1.3.3. Caminata Rob otica . . . . . . . . . . . . . . . . . . . . 25
1.3.4. Torres de Hanoi . . . . . . . . . . . . . . . . . . . . . . 27
1.4. Algoritmos de ordenamiento . . . . . . . . . . . . . . . . . . . 31
1.4.1. conceptos preliminares . . . . . . . . . . . . . . . . . . 31
1.4.2. Ordenamiento de Burbuja (BubbleSort) . . . . . . . . 32
1.4.3. Ordenamiento de por mezcla (MergeSort) . . . . . . . 34
1.4.4. Ordenamiento rapido (QuickSort) . . . . . . . . . . . . 36
1.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2. El modelo de datos de listas 43
2.1. Introducci on . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2. Implementacion del modelo de Listas ligadas . . . . . . . . . . 43
2.3. Operaciones basicas con Listas . . . . . . . . . . . . . . . . . . 45
2.3.1. Insercion de nodos . . . . . . . . . . . . . . . . . . . . 45
2.3.2. Borrado de nodos . . . . . . . . . . . . . . . . . . . . . 48
3
4

INDICE GENERAL
2.3.3. B usqueda e Impresion . . . . . . . . . . . . . . . . . . 50
2.3.4. Algoritmos de Ordenamiento utilizando listas . . . . . 51
2.4. Implementacion del modelo de Pilas . . . . . . . . . . . . . . . 54
2.4.1. Conversi on de notaci on inja a posja . . . . . . . . . 55
2.5. Implementacion del modelo de Colas . . . . . . . . . . . . . . 56
2.5.1. Programacion Din amica . . . . . . . . . . . . . . . . . 57
2.5.2. top-down . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3. El modelo de conjunto de datos 67
3.1. Deniciones B asicas y Principales Operaciones con Conjuntos 67
3.1.1. Deniciones B asicas . . . . . . . . . . . . . . . . . . . . 67
3.1.2. Operaciones con Conjuntos . . . . . . . . . . . . . . . 69
3.1.3. Implementaci on de Conjuntos Utilizando Listas . . . . 71
3.1.4. Relaciones y Funciones . . . . . . . . . . . . . . . . . . 76
3.2. Proyecto de Programaci on . . . . . . . . . . . . . . . . . . . . 78
3.2.1.

Indices invertidos . . . . . . . . . . . . . . . . . . . . . 78
3.2.2. Trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4. El modelo de datos de arboles 81
4.1. Terminologa B asica . . . . . . . . . . . . . . . . . . . . . . . 81
4.1.1. Denicion Recursiva . . . . . . . . . . . . . . . . . . . 82
4.1.2. Rutas, Antecesores y Descendientes . . . . . . . . . . . 82
4.1.3. Sub-arboles . . . . . . . . . . . . . . . . . . . . . . . . 83
4.1.4. Altura y Profundidad . . . . . . . . . . . . . . . . . . . 83
4.1.5.

Arboler Ordenados . . . . . . . . . . . . . . . . . . . . 83
4.1.6.

Arboles Etiquetados . . . . . . . . . . . . . . . . . . . 83
4.1.7.

Arboles de Expresiones . . . . . . . . . . . . . . . . . . 84
4.2. Estructuras de Datos para

Arboles . . . . . . . . . . . . . . . 85
4.2.1. Representaci on m as a la izquierda-hermano a la derecha 85
4.2.2. Apuntador hacia el Padre . . . . . . . . . . . . . . . . 85
4.3. Recursi on en

Arboles . . . . . . . . . . . . . . . . . . . . . . . 86
4.4.

Arboles Binarios . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.4.1. Estructuras de Datos para

Arboles Binarios . . . . . . 90
4.4.2. Recursion sobre

Arboles Binarios . . . . . . . . . . . . 91
4.4.3. Recurridos en Orden . . . . . . . . . . . . . . . . . . . 91
4.5.

Arboles de B usqueda Binarios . . . . . . . . . . . . . . . . . . 91
4.5.1. Implementaci on de

Arboles de B usqueda Binarios . . . 92
INDICE GENERAL 5
4.6. Colas de Prioridad y

Arboles Parcialmente Ordenados . . . . . 94
4.6.1. Colas de Prioridad . . . . . . . . . . . . . . . . . . . . 94
4.6.2.

Arboles Parcialmente Ordenados (POT) . . . . . . . . 94
4.6.3. POTs Balanceados y Montculos (Heaps) . . . . . . . . 95
4.7. Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.8. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5. Teora y algoritmos de grafos 99
6

INDICE GENERAL
Indice de cuadros
1.1. Descomposici on del problema del factorial . . . . . . . . . . . 22
1.2. Combinacion de los subproblemas del problema del factorial . 23
1.3. Simulaci on para las Torres de Hanoi con N = 3 . . . . . . . . 30
2.1. LLenado de el arreglo L . . . . . . . . . . . . . . . . . . . . . 63
3.1. Equivalencia Operaciones Vectores Caractersticos . . . . . . . 74
4.1. Evaluacion en Preorden . . . . . . . . . . . . . . . . . . . . . . 89
4.2. Evaluacion en postorden . . . . . . . . . . . . . . . . . . . . . 89
7
8

INDICE DE CUADROS
Indice de guras
1.1. Cubos numerados sobre una mesa . . . . . . . . . . . . . . . 16
1.2. Secuencia de movimientos parar 3 discos . . . . . . . . . . . . 28
1.3. Descomposici on del algoritmo de ordenamiento por mezcla . . 35
1.4. Parte de mezclado del algoritmo de ordenamiento por mezcla 35
2.1. Variable de referencia a un objeto . . . . . . . . . . . . . . . . 44
2.2. Representaci on de una lista ligada . . . . . . . . . . . . . . . . 44
2.3. Inserci on al principio de una lista . . . . . . . . . . . . . . . . 46
2.4. Inserci on al nal de una lista . . . . . . . . . . . . . . . . . . . 47
2.5. Borrar al principiol de una lista . . . . . . . . . . . . . . . . . 48
2.6. Borrar al nal de una lista . . . . . . . . . . . . . . . . . . . . 49
2.7. Proceso de divisi on de una lista . . . . . . . . . . . . . . . . . 52
2.8. Subsecunecia com un m as larga . . . . . . . . . . . . . . . . . . 59
3.1. Operaciones con conjuntos . . . . . . . . . . . . . . . . . . . 69
3.2. Diagrama de Venn . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3. Tabla Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.1.

Arbol B asico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.2. Relaci on a la izquierda . . . . . . . . . . . . . . . . . . . . . . 83
4.3. (E
1
+ E
2
) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.

Arbol ejemplo para funciones recursivas . . . . . . . . . . . . . 86
4.5.

Arbol ejemplo evaluacion preorden y postorden - a+(b-c)*d . 88
4.6. Heap Basico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.7. Heapsort Basico . . . . . . . . . . . . . . . . . . . . . . . . . . 96
9
10

INDICE DE FIGURAS
Lista de algoritmos
1. Calculo de n factorial . . . . . . . . . . . . . . . . . . . . . . 23
2. Calculo recursivo del maximo com un divisor . . . . . . . . . . 25
3. Caminata de un robot . . . . . . . . . . . . . . . . . . . . . . 26
4. Secuencia de movimientos para el juego de Torres de Hanoi . 30
5. Ordenamiento de burbuja . . . . . . . . . . . . . . . . . . . . 34
6. Ordenamiento de mezcla . . . . . . . . . . . . . . . . . . . . . 36
7. Funci on de mezcla de sublistas . . . . . . . . . . . . . . . . . . 37
8. Ordenamiento rapido . . . . . . . . . . . . . . . . . . . . . . 38
9. Funci on que encuentra el elemento de particion . . . . . . . . 39
10. Funcion para saber si un patr on en una subsecuencia de un
texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
11. Uni on con Listas Desordenadas . . . . . . . . . . . . . . . . . 71
12. Funcion auxiliar ensambla . . . . . . . . . . . . . . . . . . . . 71
13. Uni on Listas Ordenadas . . . . . . . . . . . . . . . . . . . . . 72
14. Intersecci on Listas Ordenadas . . . . . . . . . . . . . . . . . . 73
15. Diferencia Listas Ordenadas . . . . . . . . . . . . . . . . . . . 74
16. Funcion Hash Letra Inicial . . . . . . . . . . . . . . . . . . . . 75
17. Funcion Inserta en Tabla Hash . . . . . . . . . . . . . . . . . . 76
18. Funcion Eliminar de Tabla Hash . . . . . . . . . . . . . . . . . 76
19. Funcion Buscar en Tabla Hash . . . . . . . . . . . . . . . . . . 76
20. Estructura de Celda Lista Ligada para Funciones . . . . . . . 77
21. Inserta en Tabla Hash para Funciones . . . . . . . . . . . . . 78
22. Estructura - solo padre . . . . . . . . . . . . . . . . . . . . . . 85
23. Estructura - solo hijos . . . . . . . . . . . . . . . . . . . . . . 85
24. Estructura - mas a la izquierda-hermano a la derecha . . . . . 86
25. Estructura - apuntador al padre . . . . . . . . . . . . . . . . . 86
26. Recursividad en arboles - F(n) . . . . . . . . . . . . . . . . . . 87
27. Evaluacion en Preorden - F(n) . . . . . . . . . . . . . . . . . . 88
11
28. Evaluacion en Postorden - F(n) . . . . . . . . . . . . . . . . . 89
29. Estructura Nodo

Arbol Binario . . . . . . . . . . . . . . . . . 90
30. Recursi on

Arbol Binario . . . . . . . . . . . . . . . . . . . . . 91
31. Evaluacion en Orden - F(n) . . . . . . . . . . . . . . . . . . . 91
32. Inserta en arbol binario . . . . . . . . . . . . . . . . . . . . . . 92
33. Buscar en arbol binario . . . . . . . . . . . . . . . . . . . . . . 93
34. Eliminar en arbol binario . . . . . . . . . . . . . . . . . . . . . 93
35. Inserta en heap . . . . . . . . . . . . . . . . . . . . . . . . . . 95
36. Eliminar de heap . . . . . . . . . . . . . . . . . . . . . . . . . 96
37. Fase 2 de heapsort . . . . . . . . . . . . . . . . . . . . . . . . 96
38. Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Captulo 1
Modelo de datos, Iteracion y
Recursi on
1.1. Programaci on Iterativa
Los ciclos o bucles son estructuras iterativas que proveen los lenguajes
de programaci on para ejecutar un conjunto de instrucciones un n umero de
veces determinado por una expresi on. Las instrucciones en ciclos resuelven
el problema de repetir un conjunto de instrucciones m as de una vez.A cada
repetici on del conjunto de acciones se denomina iteracion
1.1.1. Iteraci on mediante FOR
Es una estructura iterativa que es controlada mediante un ndice o va-
riable de control, la cual se incrementa o decrementa hasta llegar a un valor
lmite o valor nal que representa la condicion de paro. L a condici on de paro
no es una expresi on l ogica sino un valor que indica el nal de ciclo.
Por su parte, en Java la condici on de paro si es una expresion logica
por consiguiente se puede ejecutar tanto un n umero predenido de veces
como hasta que se cumpla una determinada condicion.En su forma simple la
inicializaci on es una instrucci on de asignaci on que indica el valor de inicio de
la variable ndice.
La expresi on condicional eval ua la variable ndice con valor nal o de pa-
rada que determina cuando termina el ciclo.El incremento/decremento dene
la forma en que la variable de control del ciclo debe cambiar cada vez que se
realiza una iteracion.
13
14 CAP
ITULO 1. MODELO DE DATOS, ITERACI
ON Y RECURSI
ON
En java
for (< inicializaci on >; < expresi on condicional >; < inc/dec >) {
< inst 1 >; s
.
.
< inst n >;
}
En seudocodigo
Para < inicializaci on > hasta < valor2 > en
< inc/dec > hacer
< inst 1 >;
.
.
< inst n >;
FPara;
1.1.2. Iteraci on WHILE
Es una estructura iterativa que permite la ejecuci on de un bloque de
instrucciones, siempre que una condici on dada se cumpla, es decir cuando la
condici on evaluada es verdadera.
El while repite las instrucciones del ciclo cero (0) o mas veces, ya que
la condicion de entrada se verica al inicio de cada iteraci on y podra no
cumplirse la primera vez.
En java
while (< expresi on >) {
< inst 1 >;
.
.
< inst n >;
}
En seudocodigo
Mientras (< expresi on >) Hacer
< inst 1 >;
.
1.1. PROGRAMACI
ON ITERATIVA 15
.
< inst n >;
FMientras
1.1.3. Iteraci on DO WHILE
Un do while al igual que un while ejecuta un bloque de instrucciones
hasta que se cumpla la condicion de paro, es decir, hasta que la evaluacion
de la condicion de paro sea verdadera. Este bloque de instrucciones se realiza
al menos una (1) vez, ya que la condicion se verica al nal lo cual permite
ejecutar el ciclo al menos la primera vez.
El comportamiento de do while en seudocodigo y en lenguaje Java no es el
mismo. La diferencia principal radica en que en el seudoc odigo l el conjunto
de instrucciones se realiza hasta que la condici on sea verdadera, en cambio
en el lenguaje Java se realizan mientras la condici on sea verdadera.
En java
do {
< inst 1 >
.
.
< instn >} while (< expresi on >);
En seudocodigo
Repetir
< inst1 >;
.
.
< instn >;
Hasta (< expresi on >);
1.1.4. Como elegir que estructura de iteracion utilizar
Pueden considerarse los siguientes puntos en la elecci on del tipo de sen-
tencia de iteraci on :
Si se conoce la cantidad exacta de veces que se va a ejecutar el ciclo o
si se puede calcular de alguna manera, entonces usar Para (for).
16 CAP
ON Y RECURSI
ON
Si se desconoce la cantidad de veces en que se deben repetir las instruc-
ciones o se deben utilizar uno o varios criterios de paro para detener
el ciclo, y las condiciones deben vericarse al inicio del ciclo, entonces
utilizar while.
Si se desconoce la cantidad de veces en que se repetir an las instrucciones
o se deben utilizar uno o varios criterios de parada para detener el ciclo,
pero las instrucciones deben realizarse al menos la una vez, entonces
utilizar do - while.
1.2. Pruebas inductivas
Supongamos que una serie de cubos numerados 1, 2, 3 ... est an sobre una
mesa (innitamente) larga y que algunos cubos est an marcados con una X
(ver Figura1.1). Supongamos que :
Proposicion 1 El primero de los cubos esta marcado
Proposicion 2 Si todos los cubos anteriores al cubo (n+1) estan marcados,
entonces el cubo (n + 1) tambien lo esta.
! ! ! ! !
"""
# $ % & '
Figura 1.1: Cubos numerados sobre una mesa
Mostraremos que 1 y 2 implican que cada cubo est a marcado, examinando
los cubos uno por uno.
La armacion de 1 establece de manera explcita que el cubo 1 esta mar-
cado. Consideremos el cubo 2. Todos los cubos anteriores al cubo 2, a saber,
el cubo 1, esta marcado, as de acuerdo al 2, el cubo 2 tambien esta marcado.
Consideremos el cubo 3, los cubos 1 y 2 est an marcados; as de acuerdo con 2
1.2. PRUEBAS INDUCTIVAS 17
el cubo 3 tambien esta marcado. De esta forma, podemos mostrar que cada
cubo est a marcado. Por ejemplo supongamos que se ha vericado que los
cubos de 1 al 5 est an marcados, como muestra la Figura 1.1. Para mostrar
que el cubo 6 que no aparece en la Figura, est a marcado, observemos que
todos los cubos anteriores al cubo 6 estan marcados, de modo que por 2 el
cubo 6 tambien esta marcado.
El ejemplo anterior ilustra el principio de induccion matematica.
Para mostrar c omo se puede utilizar la induccion matematica de manera
mas profunda, sea S
n
la suma de los primeros n enteros positivos
S
n
= 1 + 2 + 3 + . . . + n (1.1)
Supongamos que alguien arma que
S
n
=
n(n+1)
2
, para n = 1, 2, 3, . . . , n (1.2)
En realidad se establece la siguiente serie de armaciones
S
n
=
1(2)
2
S
n
=
2(3)
2
.
.
.
S
n
=
n(n + 1)
2
Supongamos que cada ecuacion verdadera tiene una Xjunto a ella. Co-
mo la primera ecuaci on es verdadera, esta marcada. Ahora, supongamos que
podemos mostrar que si todas la ecuaciones anteriores a una ecuaci on par-
ticular, digamos la ecuaci on (n + 1), est an marcadas, entonces la ecuacion
(n+1) tambien esta marcada. Entonces, como en el ejemplo los cubos, todas
las ecuaciones estan marcadas; es decir todas las ecuaciones son verdaderas
y se verica la ecuaci on 1.2.
Debemos mostrar que si todas la ecuaciones anteriores a la ecuacion (n+1)
son verdaderas, entonces la ecuaci on (n + 1) tambien lo es. Suponiendo que
todas la ecuaciones anteriores a la ecuaci on (n+1) son verdaderas, entonces,
en particular la ecuaci on n es verdadera.
S
n
= n
n(n + 1)
2
(1.3)
18 CAP
ON Y RECURSI
ON
Debemos mostrar que la ecuacion (n + 1)
S
n
= n
(n + 1)(n + 2)
2
es verdadera. De acuerdo a la ecuaci on 1.1
S
n+1
= 1 + 2 + 3 + . . . + n + (n + 1)
Observamos que S
n
est a contenida dentro de S
n+1
, en el sentido de que
S
n+1
= 1 + 2 + 3 + . . . + n + (n + 1) = S
n
+ (n + 1) (1.4)
Debido a 1.3 y 1.4, tenemos
S
n+1
= S
n
+(n+1) =
n(n + 1)
2
+n+1 =
n(n + 1) + 2(n + 1)
2
=
(n + 2)(n + 1)
2
La demostraci on por induccion consto de dos pasos. En primer lugar,
vericamos que la armacion correspondiente a n = 1 era verdadera. En
segundo lugar, se supuso que las armaciones 1, 2, 3 . . . n eran verdaderas
y se demostr o que la armaci on (n + 1) tambien lo era. Al demostrar la
armaci on (n+1), podamos utilizar las armaciones 1, 2, 3 . . . n; de hecho, la
tecnica para construir una demostraci on por inducci on matem atica consiste
en relacionar las armaciones 1, 2, 3 . . . n con la armaci on (n + 1).
A continuacion enunciamos de manera formal el principio de induccion
matem atica.
Principio de induccion matematica Supongamos que para cada entero
positivo n tenemos una armacion S(n) que es verdadera o falsa. Suponga-
mos que.
Proposicion 3 S(1) es verdadera;
Proposicion 4 si S(i) es verdadera, para toda i < n +1, entonces S(n +1)
es verdadera
La condici on 3 se llama paso base Entonces S(n) es verdadera para cada
entero positivo n y la condici on 4 se le llama paso inductivo.
1.2. PRUEBAS INDUCTIVAS 19
1.2.1. Ejemplo 1
Ahora se ilustra la induccion matem atica mediante otro ejemplo.
Utilizar induccion matem atica para mostrar que
n! 2
n1
(1.5)
Paso Base (Condici on 3 ) Debemos mostrar que 1.5 es verdadera si n = 1.
Esto es f acil de vericar 1! = 1 1 = 2
11
.
Paso Inductivo (Condici on 4) Debemos mostrar que si i! 2
i1
para i =
1, 2, 3, . . . , n entonces
(n + 1) 2
n
(1.6)
Supongamos que i 2
i1
para i = 1, 2, 3, . . . , n. Entonces en particular,
para i = n, tenemos
n 2
n1
(1.7)
Podemos relacionar 1.6 y 1.7 observando que
(n + 1)! = (n + 1)(n!).
Ahora,
(n + 1)! = (n + 1)(n!)
(n + 1)2
n1
por 1.7
2 2
n1
pues n + 1 2
= 2
n
Por tanto, 1.5 es verdadera. Se ha concluido el paso inductivo.
Como se ha vericado el paso base y el paso inductivo, el principio de
inducci on matem atica nos dice que 1.5 es verdadera para cada entero positivo
n.
Para vericar el paso inductivo 4 suponemos que si S(i) es verdadera
para toda i < n + 1 y luego demostramos que S(n + 1) es verdadera. Es-
ta formulacion de la inducci on matematica se le llama la forma fuerte de
20 CAP
ON Y RECURSI
ON
la induccion matematica. Con frecuencia, como en le caso de los ejem-
plos anteriores, podemos deducir S(n + 1) suponiendo solamente S(n). En
realidad, con frecuencia ser enuncia el paso inductivo de la manera siguiente:
Si S(n) es verdadera, entonces S(n + 1) es verdadera.
En estas dos formulaciones, el paso base no se modica. Puede mostrarse
que las dos formas de inducci on matematica son equivalentes.
Si queremos vericar que las armaciones
S(n
0
), S(n
0
+ 1), . . . ,
donde n
0
= 1, son verdaderas, debemos cambiar el paso base a
S(n
0
) es verdadera.
El paso inductivo no se modica.
1.2.2. Ejemplo 2: Suma geometrica
Utilizar induccion para mostrar que si r = 1,
a + ar
1
+ ar
2
+ + ar
n
=
a(r
n+1
1)
r 1
(1.8)
para n = 0, 1, . . .
La suma de la izquierda se llama suma geometrica. En una suma geometri-
ca, la raz on entre los terminos consecutivos (ar
i+1
/ar
i
= r es constante.
Paso Base . El paso base, que en este caso se obtiene haciendo n = 0, es
a =
a(r
1
1)
r 1
lo cual es verdadero.
Paso Inductivo . Supongamos que la armaci on 1.8 es verdadera para n.
Ahora
a + ar
1
+ ar
2
+ + ar
n
+ ar
n+1
=
a(r
n+1
1)
r1
+ ar
n+1
=
a(r
n+1
1)
r1
+
ar
n+1
(r1)
r1
=
a(r
n+2
1)
r1
Como se ha vericado el paso base modicado y el paso inductivo, el
principio de inducci on matem atica nos dice que 1.8 es verdadera para n =
0, 1, . . .
1.3. DEFINICIONES Y FUNCIONES RECURSIVAS 21
1.2.3. Ejemplo 3
Utilizar induccion para mostrar que 5
n
1 es divisible entre 4 para n =
1, 2, . . .
Paso Base . Si n = 1, 5
n
1 = 5
1
1 = 4, que es divisible entre 4.
Paso Inductivo . Supongamos que 5
n
1 es divisible entre 4. Debemos
mostrar que 5
n1
1 es divisible entre 4. Para relacionar el caso (n+1)
con el caso n, escribimos
5
n+1
1 = 5 5
n
1 = (4 + 1) 5
n
1 = 4 5
n
+ (5
n
1)
Por hip otesis 5
n
1 es divisible entre 4, y como 4 5
n
es divisible entre
4, la suma
4 5
n
+ (5
n
1)
es divisible entre 4. Como se ha vericado el paso base y el paso induc-
tivo, el principio de inducci on matematica dice que 5
n
1 es divisible
entre 4 para n = 1, 2, . . ..
1.3. Deniciones y funciones Recursivas
Un procedimiento recursivo es aquel que se llama a s mismo. La recursion
es poderosa, elegante y natural de resolver una gran variedad de problemas.
Un problema puede resolverse mediante una tecnica divide y venceras en la
cual el problema se descompone en problemas del mismo tipo que el origi-
nal. Cada subproblema, a su vez, se descompone de nuevo y as hasta que
se obtienen subproblemas los cuales pueden resolverse de manera directa.
Por ultimo, las soluciones de los subproblemas se combinan para obtener la
soluci on del problema original.
1.3.1. El factorial
El factorial de n o n factorial se dene como
n! =
1 si n = 0
n(n 1)(n 2) 2 1 si n 1
Observe que n factorial puede escribirse en terminos de si mismo pues si
quitamos n, el producto restante es s olo (n 1)!; es decir,
22 CAP
ON Y RECURSI
ON
n! = n(n 1)(n 2) 2 1 = n(n 1)!
Por ejemplo
5! = 5 4 3 2 1 = 5 4!
La ecuacion n(n 1)!, muestra la forma de descomponer el problema
original (calcular n!) en subproblemas cada vez m as sencillos [calcular (n1),
calcular (n2)! ...] hasta que el proceso llegue a un problema m as simple, el
calculo de 0!. En ese momento las soluciones de estos subproblemas pueden
combinarse (multiplicando) para resolver el problema original.
Por ejemplo, el problema de calcular 5! se reduce a calcular 4!; el problema
de calcular 4! se reduce a calcular 3! ; y as sucesivamente. La tabla 1.1 resume
el proceso.
Cuadro 1.1: Descomposici on del problema del factorial
Problema Problema simplicado
5! 5 4!
4! 4 3!
3! 3 2!
2! 2 1!
1! 1 0!
0! Ninguno
Una vez que el problema de calcular 5! se ha reducido a resolver subpro-
blemas, la solucion del problema m as sencillo puede utilizarse para resolver
el siguiente subproblema, y as sucesivamente, hasta resolver el problema ori-
ginal. La tabla 1.2 muestra como se combinan los subproblemas para resolver
el problema original
A continuacion escribimos un algoritmo recursivo que calcula factoriales.
El algoritmo es una traduccion directa de la ecuaci on n(n 1)!
Ahora mostraremos la forma en que el Algoritmo 1 calcula n! para diversos
valores de n. Si n = 0, el procedimiento regresa, en la lnea 3, el valor correcto
1.
Si n = 1, como n = 0 pasamos a la lnea 4. Utilizamos este procedimiento
para calcular 0!. Ya hemos observado que el procedimiento calcula 0!. En la
lnea 4 el procedimiento calcula de forma correcta el valor de 1!.
Cuadro 1.2: Combinacion de los subproblemas del problema del factorial
Problema Soluci on
0! 1
1! 1 0! = 1
2! 2 1! = 2
3! 3 2! = 3 2 = 6
4! 4 3! = 4 6 = 24
5! 5 4! = 5 24 = 120
Algoritmo 1 C alculo de n factorial
Entrada: n, un entero mayor o igual con 0
Salida: n!
1: factorial(n)
2: si n = 0 entonces
3: devolver 1
4: n si
5: devolver n factorial (n 1)
(n 1)! n = 0! 1 = 1 1 = 1
para calcular 1!. Ya hemos observado que el procedimiento calcula 1 como el
valor de 1!. En la lnea 4 el procedimiento calcula de forma correcta el valor
de 2!.
(n 1)! n = 1! 2 = 1 2 = 1
para calcular 2!. Ya hemos observado que el procedimiento calcula 2 como el
valor de 2!. En la lnea 4 el procedimiento calcula de forma correcta el valor
de 3!.
(n 1)! n = 2! 3 = 2 3 = 6
Los argumentos anteriores pueden generalizarse mediante inducci on ma-
tem atica para demostrar que el algoritmo 1 tiene como salida correcta el
valor de n! para cualquier entero no negativo n.
24 CAP
ON Y RECURSI
ON
TEOREMA 1 El algoritmo 1 produce como salida el valor de n!, n 0
Paso Base. (n = 0). Ya hemos observado que si n = 0, el algoritmo produce
correctamente como salida el valor de 1 0!.
Paso Inductivo . Supongamos que el Algoritmo 1 produce correctamente
como salida el valor de (n 1)! para n > 0. Ahora supongamos que n
es la entrada del Algoritmo 1. Como n es mayor que 0, al ejecutar el
procedimiento en el Algoritmo pasamos a la lnea 4. Por la hipotesis de
induccion, el procedimiento calcula correctamente el valor de (n 1)!.
En la lnea 4, el procedimiento calcula correctamente el valor (n1)!
n = n!. Por tanto el Algoritmo 1 produce correctamente como salida el
valor de n! para cada entero n 0.
Deben existir casos en los que un procedimiento recursivo no se llame
a si mismo: en caso contrario, se llamara a s mismo por siempre. En el
Algoritmo 1, si n = 0, el procedimiento no se llama a s mismo. Los valores
para los cuales un procedimiento recursivo no se llama a s mismo, son los
casos bases. Para resumir, cada procedimiento recursivo debe tener al menos
un caso base.
Se ha mostrado que la inducci on matematica puede utilizarse para de-
mostrar que un algoritmo recursivo calcula el valor que arma calcular. El
vnculo entre la induccion matem atica y los algoritmos es mucho mas pro-
fundo. Con frecuencia, una demostracion por inducci on matem atica puede
considerarse como algoritmo para calcular un valor o realizar una construc-
ci on particular. El paso base de una demostracion por inducci on matem atica
corresponde al caso base de un procedimiento recursivo y el paso inductivo
de una demostraci on corresponde a la parte de un procedimiento recursivo
donde se llama a si mismo.
1.3.2. Maximo com un divisor
El Teorema ?? establece que si a es un entero no negativo, b es un entero
positivo y a = bq + r, 0 r < b, entonces
mcd(a, b) = mcd(b, r) (1.9)
mcd(x, y) denota el m aximo com un divisor de x, y. De manera inherente
la ecuaci on 1.9 es recursiva; reduce el problema de calcular el maximo com un
divisor a y b a un problema menor, el de calcular el m aximo com un divisor
de b y r. El algoritmo recursivo 2, que calcula el maximo com un diviso, se
basa en la ecuaci on 1.9.
Algoritmo 2 C alculo recursivo del m aximo com un divisor
Entrada: q y b enteros positivos mayores o igual con 0
Salida: M aximo com un divisor de a y b
1: mcd(a, b)
2: //se hace que a sea el n umero mayor de a, b
3: si a < b entonces
4: intercambiar(a, b)
5: n si
6: si b = 0 entonces
7: devolver a
8: n si
9: dividir a entre b para obtener a = bq + r, 0 r < b
10: devolver mcd(b, r)
1.3.3. Caminata Rob otica
Un robot puede dar pasos de 1 y 2 metros. Escribir un algoritmo para el
c alculo del n umero de formas en que el robot puede recorrer n metros. Por
ejemplo:
Distancia Serie de pasos N umero de formas de recorrerlos
1 1 1
2 1,1 o 2 2
3 1,1,1 o 1,2 o 2,1 3
4 1,1,1,1 o 1,1,2 5
1,2,1 o 2,1,1 o 2,2
Sea walk(n) el n umero de formas en el que el robot puede recorrer n
metros. Puede observarse que
walk(1) = 1 walk(2) = 2
26 CAP
ON Y RECURSI
ON
Suponiendo que n > 2. El robot pude comenzar dando un paso de 1 metro
o un paso de 2 metros. Si el robot comienza dando un paso de 1 metro, resta
una distancia de n 1 metros, pero por denici on, el resto de la caminata
puede completarse en walk(n 1) formas. De manera an aloga, si el robot
comienza dando un paso de 2 metros, resta una distancia de n 2 metros y,
en este caso el resto de la caminata puede concluirse en walk(n 2) formas.
Como la caminata debe comenzar con un paso de 1 o de 2 metros, se han
abarcado todas las formas de recorrer n metros. Se obtiene la formula
walk(n) = walk(n 1) + walk(n 2)
Por ejemplo,
walk(4) = walk(3) + walk(2) = 3 + 2 = 5
Podemos escribir un algoritmo recursivo para calcular walk(n) traducien-
do la ecuaci on walk(n) = walk(n 1) + walk(n 2) directamente en un
algoritmo. Los caso bases son n = 1 y n = 2.
El algoritmo calcula la funci on denida como
walk(n) =
1 si n = 1
2 si n = 2
walk(n 1) + walk(n 2) si n > 2
Algoritmo 3 Caminata de un robot
Entrada: n,
Salida: walk(n)
1: robot walkl(n)
2: si n = 1 o n = 2 entonces
3: devolver n
4: n si
5: devolver robot walkl(n 1) + robot walkl(n 2)
La sucesi on walk(1), walk(2), walk(1), ..., cuyos valores comienzan con
1, 2, 3, 5, 8, 13, ..., es llamada sucesi on de Fibonacci en honor a Leonardo
Fibonacci (hacia 1170-1250), comerciante y matematico italiano. En lo su-
cesivo denotaremos la sucesi on de Fibonacci como f
1
, f
2
, . Esta sucesion
queda denida mediante la ecuaciones
f
1
= 1
f
2
= 2
f
n
= f
n1
+ f
n2
, n > 2
1.3.4. Torres de Hanoi
Las torres de Hanoi son un juego inventado en la decada de los 80s por
Edouard Lucas, un matem atico frances. La soluci on a este juego constituye
una ilustracion de la utilidad de la recursion.
El juego consta de 3 varillas verticales (que representan las torres) y
un conjunto de discos agujerados en su parte central, lo que les permite
deslizarse por las varillas. Cada uno de los discos tiene un di ametro distinto.
Inicialmente, todos los discos est an apilados en una de las varillas por orden
de tama no, de modo que el disco de mayor diametro se encuentra en la parte
inferior, como se muestra en la Figura ??.
El objetivo del juego consiste en mover todos los discos desde la varilla
original (la primera ) hasta la varilla destino (la tercera). Se puede utilizar
la varilla adicional como lugar para colocar temporalmente los discos, pero
es necesario seguir las siguiente tres reglas :
1. Solo es posible mover un disco cada vez
2. No puede ponerse un disco sobre otro de menor tama no.
3. Todos los discos deben encontrarse en todo momento en una de las
varillas, salvo el disco que estemos moviendo de una varilla a otra.
Estas reglas implican que debemos tratar de quitar de en medio los discos
mas peque nos para poder mover un disco de mayor tama no de una varilla a
otra. La gura 1.2 muestra la solucion paso a paso para el caso de tres discos
de la primera varilla a la tercera, primero tenemos que alcanzar un punto
en que los dos discos mas peque nos hayan sido apartados, colocandolos en
la segunda varilla, para poder as mover el disco de mayor tama no desde la
primera varilla a la tercera.
Los primeros tres movimientos mostrados en la Figura 1.2 pueden consi-
derarse como los movimientos necesarios para apartar del camino los discos
de menor di ametro. El cuarto movimiento coloca el disco de mayor tama no en
su destino nal, los ultimos tres movimientos colocan los discos m as peque nos
en su destino nal, sobre el disco de mayor diametro.
28 CAP
ON Y RECURSI
ON
Solucin para 3 discos

Segn la leyenda, los monjes de un templo tenan que mover una pila de 64
discos sagrados de un sitio a otro. Slo podan mover un disco al da y, en el
templo, slo haba otro sitio en el que podan dejarlos, siempre ordenados de
forma que los mayores quedasen en la base.

El da en que los monjes realizasen el ltimo movimiento,
el final del mundo habra llegado
Figura 1.2: Secuencia de movimientos parar 3 discos
La idea anterior se utiliza para construir una estrategia general. Para
mover una pila de N discos desde la varilla original a la varilla destino:
Hay que mover los N 1 discos situados en la parte superior desde la
varilla original hasta la varilla temporal, utilizando la varilla destino
como temporal
Hay que mover el disco de mayor tama no desde la varilla original a la
varilla destino
Hay que mover los N 1 discos de la varilla temporal hasta la varilla
destino, utilizando la varilla original como temporal.
Esta estrategia se presenta de forma obvia en la implementaci on de una
soluci on recursiva. El paso consiste en mover los N1 discos para apartarlos
del camino es el mismo problema, conceptualmente hablando, que se tiene
en el instante de partida: desplazar la pila de discos. Sin embargo, para
esta tarea tenemos un disco menos, y la varilla de destino es utilizada como
varilla temporal. Una situacion analoga se produce despues de haber movido
el disco de mayor tama no, ya que tenemos que volver a mover los N 1
discos originales.
El caso base para este problema se produce cuando se quiere desplazar
una pila constituida por un solo disco. Dicho paso pude llevarse a cabo di-
rectamente y sin necesidad de recursion.
El Algoritmo 4 considera primero el caso base (una pila de un disco).
Cuando se produce este caso, ejecuta la lnea 3, que imprime una unica lnea
que describe el movimiento. Si la pila contiene mas de un disco, se invoca
de nuevo moveTower (en la lnea 5) para apartar los N 1 discos, luego se
mueve el disco de mayor tama no (lnea 6) y despues los N 1 discos hasta
su destino nal con otra llamada a moveTower (lnea 7).
Observe que los parametros que se pasan a moveTower para describir las
varillas se intercambian seg un es necesario para desplazar las pilas parciales
de discos. El Algoritmo 4 se ajusta a la estrategia general y utiliza moveTower
para desplazar todas las pilas parciales de discos.
La simulaci on para N = 3 est a dada por la Tabla 1.3.
En las Torres de Hanoi, el tama no del juego est a dado por el n umero de
discos, y las operaciones de procesamiento relevantes es le paso que consiste
en mover un disco de una varilla a otra. Cada llamada en el algoritmo 4
hace que se mueva un disco, Desafortunadamente, salvo en el caso base, cada
30 CAP
ON Y RECURSI
ON
Algoritmo 4 Secuencia de movimientos para el juego de Torres de Hanoi
Entrada: n, n umero de discos a mover, la funci on de cada varilla origen,
destino y temporal ,
Salida: Imprime la secuencia de movimientos para mover n discos de la
varilla origen hasta la destino
1: moveTower(n, origen, destino, temporal )
3: Imprimir mover un disco de origen a destino
4: si no
5: moveTower(n 1, origen, temporal , destino)
6: Imprimir mover un disco de origen a destino
7: moveTower(n 1, temporal , destino, inicio)
8: n si
Cuadro 1.3: Simulacion para las Torres de Hanoi con N = 3
mT(1, o, d, t) Mover disco de Origen a Destino
mT(2, o, t, d) Mover disco de Origen a Temporal
mT(1, d, t, o) Mover disco de Destino a Temporal
mT(1, t, o, d) Mover disco de Temporal a Origen
mT(2, t, d, o) Mover disco de Temporal a Destino
llamada recursiva hace que el metodo se invoque a si mismo el doble de veces,
y cada llamada opera sobre una pila de discos que s olo tiene un disco menos
que el problema que se pasa como par ametro. Por tanto si ejecutamos el
procedimiento moveTower para 1 disco, se producira el desplazamiento de
un disco; si ejecutamos moveTower para 2, se producira el desplazamiento
de 3 discos; si ejecutamos moveTower para 3, se producira el desplazamiento
de 7 discos; si invocamos moveTower para 4 se producir a el desplazamiento
de 15 discos, etc. Dicho de otro modo, si f(n) representa el crecimiento del
problema, entonces:
f(n) = 1 cuando n = 1
para n > 1, f(n) = 2 (f(n 1) + 1)
= 2
n
1
En contraste con su implementacion breve y elegante, la soluci on es muy
1.4. ALGORITMOS DE ORDENAMIENTO 31
ineciente, ya que para resolver un juego con una pila de N discos, se tienen
que realizar 2
n
1 movimientos de discos individuales.
1.4. Algoritmos de ordenamiento
El ordenamiento es una tarea com un que realizamos continuamente. Or-
denar es algo tan com un que no nos detenemos a pensar en ello. Ordenar es
simplemente colocar informacion de una manera especial bas andonos en un
criterio de ordenamiento.
En la computacion el ordenamiento de datos tiene una funcion muy im-
portante, ya sea como un n en s o como parte de otros procedimientos mas
complejos. Se han desarrollado muchas tecnicas en este ambito, cada una
con caractersticas especcas, y con ventajas y desventajas sobre las dem as.
En esta seccion se revisaran algunos de los algoritmos de ordenamiento mas
comunes.
1.4.1. conceptos preliminares
Clave : La parte de un registro por la cual se ordena la lista. Por ejemplo,
una lista de registros con campos nombre, direcci on y telefono se puede
ordenar alfabeticamente de acuerdo a la clave nombre. En este caso los
campos direcci on y telefono no se toman en cuenta en el ordenamiento.
Criterio de ordenamiento (o de comparaci on): El criterio que se utiliza
para asignar valores a los registros con base en una o mas claves. De
esta manera decidimos si un registro es mayor o menor que otro.
Registro : Un grupo de datos que forman la lista. Pueden ser datos at omicos
(enteros, caracteres, reales, etc.) o grupos de ellos, que en Java equivalen
a objetos y en C a estructuras.
En el an alisis de algoritmos de todo tipo, no s olo de ordenamiento, se
debe tener una forma de evaluarlos antes de programarlos, que se base en
aspectos independientes de la plataforma y el lenguaje. De esta manera es
posible decidir cu al se adapta mejor a los requerimientos del sistema. Los
siguientes aspectos son los mas comunes:
Estabilidad : Como se comporta con registros que tienen claves iguales. A
los algoritmos que mantienen el orden relativo entre estos se les llama
32 CAP
ON Y RECURSI
ON
estables y no estables a los que no lo mantienen. Por un ejemplo. Si se
tiene la siguiente lista de datos (letra, n umero): [(J,19), (A,5), (B,9),
(C,4), (B,8), (Z,4), (J,0)] se ordena alfabeticamente por la letra con un
algoritmo estable quedara as: [(A,5), (B,9), (B,8), (C,4), (J,19), (J,0),
(Z,4)]. Un algoritmo no estable podra dejar a (B, 8) antes de (B,9) o
(J,0) antes que (J,19).
Tiempo de ejecucion : La complejidad del algoritmo, la cual tiene que ver
con rendimiento. Es una funci on independiente de la implementacion.
En este caso se tiene que identicar una operaci on fundamental que
realice el algoritmo, en el caso del ordenamiento comparaciones. Se
cuenta las veces el algoritmo necesita comparar. Si en una lista de
n terminos se realizan n comparaciones la complejidad es O(n). (En
realidad m as complicado que eso, pero en este curso se considera as, un
an alisis m as profundo es parte de un curso de An alisis de Algoritmos).
Algunos ejemplos de complejidades comunes son:
O(1): Complejidad constante.
O(n): Complejidad cuadratica.
O(nlog(n)): Complejidad logartmica.
On
2
: Complejidad cuadratica
Es posible decir que un algoritmo de complejidad O(n) es mas rapido
que uno de complejidad O(n
2
). Otro aspecto a considerar es la dife-
rencia entre el peor y el mejor caso. Cada algoritmo se comporta de
modo diferente de acuerdo a c omo se le entregue la informacion; por
eso es conveniente estudiar su comportamiento en casos extremos, como
cuando los datos est an pr acticamente ordenados o muy desordenados.
Requerimientos de memoria : El algoritmo puede necesitar memoria adi-
cional para realizar su labor. En general es preferible que no sea as,
pero es com un en la programacion tener que sacricar memoria por
rendimiento.
1.4.2. Ordenamiento de Burbuja (BubbleSort)
Este es probablemente el algoritmo m as sencillo. Consiste en iterar repe-
tidamente la lista, comparando elementos los adyacentes de dos en dos. Si un
elemento es mayor que el que esta en la siguiente posici on se intercambian.
La estrategia general del metodo es la siguiente: explorar la lista com-
parando los elementos adyacentes e intercambi andolos sino est an en orden
relativo. Esto tiene el efecto de que el elemento de mayor valor se desplace
como una Burbuja hasta la ultima posici on de la lista, que es la posici on
que le corresponde dentro de la lista nal ordenada. A continuaci on se repite
la operacion, haciendo que se desplace el segundo valor mas grande. Este
proceso continua hasta que se hayan desplazado todos los elementos a sus
posiciones correctas.
Cada pasada el algoritmo de la burbuja hace que se desplace el valor
m as grande a si posici on nal. A lo largo de una iteraci on, tambien pueden
reposicionarse otros elementos. Por ejemplo, si comenzaramos con la lista:
9 6 8 12 3 1 7
primero se compararan el 9 y el 6 y, como no est an en el orden correcto,
se intercambian con lo que quedara:
6 9 8 12 3 1 7
Despues se compara el 9 con el 8 y, de nuevo al ver que no est an en orden,
se intercambian obteniendose:
6 8 9 12 3 1 7
Luego se compara el 9 con el 12. Puesto que ya est an en orden correcto,
no se intercambian. En lugar de ello, se toma la siguiente pareja de valores
para compararlos, es decir, se compara el 12 con el 3. Puesto que no estan
en el orden correcto, se intercambian obteniendo:
6 8 9 3 12 1 7
A continuaci on se compara el 12 con el 1 y se intercambian, quedando:
6 8 9 3 1 12 7
Despues comparamos el 12 con el 7 y se intercambian nuevamente, con
lo que se obtiene:
6 8 9 3 1 7 12
Esto completa una iteracion a traves de los datos que hay que ordenar.
Despues de esta primera iteraci on el valor de mayor de la lista se encuentra
en la posicion correcta, pero no es posible asegurar lo mismo de los n umeros
restantes. Cada iteraci on subsiguiente garantiza que se ponga en la posici on
correcta otro elemento mas. Por tanto tendremos que hacer n1 iteraciones,
por que cuando se tienen n1 elementos en la posici on correcta el elemento
n tambien estara en la posici on correcta.
El algoritmo 5 implementa el ordenamiento mediante el metodo de bur-
buja. Del algoritmo 5 puede observarse en la lnea 4 que el debemos iterar
n veces los datos para poder asegurar que los n elementos terminan en su
34 CAP
ON Y RECURSI
ON
posicion correcta. En la lnea 5 observamos que solo es necesario comparar
hasta lo posicion n i (el 1 es debido a que solo podemos compara hasta
el elemento n1 con es n) ya que despues de la i-esima iteraci on los ultimos
i elementos ya estar an ordenados.
Algoritmo 5 Ordenamiento de burbuja
Entrada: A, un arreglo desordenado y n n umero de elementos en A
Salida: ordena A
1: bubbleSort(A, n)
2: para i = 0 hasta n hacer
3: para j = 0 hasta n 1 i hacer
4: si A[j]A[j + 1] entonces
5: aux = A[j]
6: A[j]=A[j + 1]
7: A[j + 1]= aux
8: n si
9: n para
10: n para
Analizando el algoritmo 5 la complejidad esta dada por los dos ciclos
presentes. Cuando i = 0 debemos realizar n 1 operaciones, cuando i = 1,
n2 y as sucesivamente. De lo anterior es posible observar que la complejidad
(n umero de operaciones necesarias) esta dada por (n 1) + (n 2) + (n
3) + + 1 como ya se demostro en la secci on 1.2 es sumatoria est a dada
por la funci on (n 1)(n 2)/2 = n
2
n + 2 lo cual es O(n
2
), por tanto el
algoritmo de burbuja es de orden cuadr atico.
1.4.3. Ordenamiento de por mezcla (MergeSort)
El algoritmo de ordenamiento por mezcla, es un algoritmo recursivo, el
cual ordena una lista dividiendo recursivamente la lista en dos mitades hasta
que cada sublista tiene un elemento, y luego combina las sublistas en orden.
La estrategia general del algoritmo por mezcla es la siguiente: se comienza
dividiendo la lista en dos partes aproximadamente iguales y luego se invoca
recursivamente el mismo algoritmo de ordenamiento para cada una de esa
lista, Esta descomposici on recursiva de la lista continua hasta alcanzar el
caso base de la recursion, que es el caso en que se tienen listas de longitud
uno, que estar an por denici on ordenadas. A continuaci on, a medida que
se devuelve el control hacia arriba a traves de la estructura recursiva de
llamadas, el algoritmo va mezclando es una unica lista ordenada las dos
sublistas ordenadas resultantes de las dos llamadas recursivas.
Por ejemplo, si se hubiera comenzado con la lista inicial [9.6,7,30,12,11,8],
la parte de descomposici on recursiva del algoritmo nos dara los resultado que
se muestran en la Figura 1.3.
! " # $%&'&&(
Figura 1.3: Descomposici on del algoritmo de ordenamiento por mezcla
La parte de la mezcla del algoritmo recombinara a continuaci on la lista
como se muestra en la Figura 1.4
! " # $ %%%& '(
Figura 1.4: Parte de mezclado del algoritmo de ordenamiento por mezcla
Para realizar un analisis de complejidad (simple), suponemos que n es una
potencia de 2, por tanto n puede expresarse como n = 2
x
y de la denicion del
logaritmo tenemos que log
b
(n) = x n = b
x
, con lo anterior podemos
deducir que el n umero maximo de sublista es x = log
2
(n) y cada una de
36 CAP
ON Y RECURSI
ON
las log
2
(n) se tienen que realizar n operaciones de mezcla, de lo anterior es
posible deducir que se tienen que mezclar log
2
(n) los n elemento de la lista,
por lo que la complejidad esta dada por nlog
2
(n) es decir es O(log
2
(n)).
El algoritmo de ordenamiento, en este caso lo describimos como dos fun-
ciones, una que representa el ordenamiento y otra para el mezclado de las
sublistas. La funcion de ordenamiento est a dada por el Algoritmo 6 y la de
mezclado por Algoritmo 7.
Algoritmo 6 Ordenamiento de mezcla
Entrada: A[], un arreglo desordenado y min ndice donde inicia la sublista
y max ndice donde termina la sublista
Salida: A
o
[] lista ordenada
1: mergeSort(A)
2: n = longitud(n)
4: devolver A
5: n si
6: L
1
=A[1],A[2], , A[n/2]
7: L
2
=A[n/2 + 1],A[n/2 + 2], , A[n]
8: mergesort(L
1
)
9: mergesort(L
2
)
10: devolver merge(L
1
, L
2
)
1.4.4. Ordenamiento rapido (QuickSort)
El Algoritmo QuickSort ordena una lista dividiendo una lista mediante
un elemento de particion elegido arbitrariamente y luego ordenando recursi-
vamente las sublistas situadas a ambos lados del elemento de partici on. La
estrategia general del algoritmo es la siguiente: en primer lugar, se seleccio-
na un elemento de la lista para que act ue como elemento de particion; a
continuacion, se parte la lista en de forma que todos los elementos menores
que el elemento de partici on se encuentren a la izquierda de dicho elemento,
mientras que los mayores se ubiquen a la derecha; nalmente, se aplica esta
estrategia (recursivamente) a ambas particiones.
La seleccion del elemento de partici on es arbitraria, as que para este ca-
so se utiliza el primer elemento de la lista. Por razones de eciencia, sera
Algoritmo 7 Funcion de mezcla de sublistas
Entrada: A y B arreglos ordenados
Salida: C mezcla de A y B
1: merge(A, B)
2: i = 0
3: j = 0
4: n = longitud(A)
5: m = longitud(B)
6: mientras i < n && j < m hacer
7: si A[i]> B[j] entonces
8: C[i + j]=B[j]
9: j = j + 1
10: si no
11: C[i + j]=A[i]
12: i = i + 1
13: n si
14: n mientras
15: mientras i < n hacer
16: C[i + j]=A[i]
17: i = i + 1
18: n mientras
19: mientras j < m hacer
20: C[i + j]=B[j]
21: j = j + 1
22: n mientras
23: devolver C
38 CAP
ON Y RECURSI
ON
conveniente que el elemento de partici on dividiera la lista aproximadamen-
te en dos mitades, pero el algoritmo funciona igual independientemente de
que elemento se seleccione para realizar la particion.
Examinemos un ejemplo. Si comenz aramos con la siguiente lista:
9 6 7 30 12 11 8
se elegira 9 como el elemento de particion. Despues se reordena la lista,
intercambiando los elementos que sean menores de 9 para situarlos del lado
izquierdo y situando los mayores del lado derecho, con lo que resulta:
8 6 7 9 12 11 30
Despues se aplica el algoritmo de ordenamiento por separado a ambas
particiones. Este proceso continua hasta que una particion solo contenga
un elemento, que estar a inherentemente ordenado. As despues de aplicar el
algoritmo recursivamente en ambos lados, la lista entera estar a ordenada.
Una vez determinado y colocado el elemento de particion inicial, no se le
vuelve a tener en cuenta ni a desplazar.
El Algoritmo 8. Recibe como par ametros un arreglo y los valores de los
ndices m aximo (min) y mnimo (max) de los elementos del arreglo por or-
denar. Al inicio del algoritmo, los valores min y max abarcan todo el arreglo
de elementos.
Algoritmo 8 Ordenamiento r apido
Salida: No regresa nada, ordena A en sitio.
1: quickSort(A, min, max)
2: si max min > 0 entonces
3: pivote = findPartition(A, min, max)
4: quickSort(A, min, pivote 1)
5: quickSort(A, pivote + 1, max)
6: n si
El Algoritmo ?? se basa en el metodo ndPartition, al que llama para di-
vidir el arreglo en dos particiones. El metodo ndPartition devuelve el ndice
(pivote) del valor de la partici on. Entonces, entonces quickSort se llama dos
veces (recursivamente) para ordenar las dos particiones resultantes. El caso
base de la recursion, representado por la instruccion IF del metodo quickSort,
es cuando se tiene una lista de un elemento o menos, que estara inherente-
mente ordenada. El Algoritmo que determina el ndice pivote se muestra a
continuacion (ver Algoritmo 9):
Algoritmo 9 Funcion que encuentra el elemento de partici on
Salida: rigth ndice de la partici on
1: ndPartition(A, min, max)
2: left = min
3: right = max
4: partitionElement = A[min]
5: mientras left < right hacer
6: mientras A[left]< partitionElement hacer
7: left = left + 1
8: n mientras
9: mientras A[rigth]> partitionElement hacer
10: rigth = right 1
11: n mientras
12: si left < right entonces
13: temp = A[left]
14: A[left]= A[right]
15: A[right]= temp
16: n si
17: n mientras
18: temp = A[min]
19: A[min]= A[right]
20: A[right]= temp
21: devolver right
Los dos ciclos WHILE internos del metodo ndPartition se utilizan para
encontrar los elementos que se encuentran en las particiones incorrectas e
intercambiarlos. El primero de los ciclos explora de izquierda a derecha bus-
cando un elemento que sea mayor que el elemento de partici on. El segundo
ciclo explora de derecha a izquierda buscando un elemento que sea menor
el elemento de particion. Una vez encontrados los dos elementos, se inter-
cambian. Este proceso continua hasta que los ndices derecho e izquierdo se
encuentran en el medio de la lista. La ubicacion en la que se encuentran
tambien indica d onde debe situarse elemento de partici on (que no se mueve
de su posici on hasta el nal).
40 CAP
ON Y RECURSI
ON
1.5. Ejercicios
1. En los siguiente ejercicios utilice inducci on para vericar que cada ecua-
ci on es verdadera
a) 1 + 2 + 5 + . . . + 2(n 1) = n
2
b) 1 2 + 2 3 + 3 4 + . . . + n(n + 1) =
n(n+1)(n+2)
3
c) 1
2
2
2
+ 3
2
+ . . . + n
2
=
n(n+1)(2n+1)
6
2. En los siguiente ejercicios utilice induccion para vericar la desigualdad
a) 2n + 1 2
n
, n = 3, 4, . . .
b) 2
n
n
2
, n = 4, 5, . . .
c) (1 + x)
n
1 + nx, para x 1 y n = 1, 2, . . .
3. En los siguiente ejercicios utilice induccion para demostrar cada ar-
maci on
a) 7
n
1 es divisible entre 6, para n = 1, 2, . . .
b) 3
n
+ 7
n
2 es divisible entre 8, para n = 1, 2, . . .
c) Mostrar que cualquier tarifa postal de 5 centavos o m as puede
cobrarse utilizando solo estampillas de 2 y 5 centavos.
d) Mostrar que cualquier tarifa postal de 24 centavos o mas puede
cobrarse utilizando solo estampillas de 5 y 7 centavos.
4. Proporcione un algoritmo que invierta un n umero decimal(sin conver-
tirlo a cadena) solo utilizando operaciones aritmeticas.
5. Proporciones versiones iterativas y recursivas de algoritmos que solu-
ciones los siguientes problemas.
6. Escriba una denicion recursiva para la multiplicacion entera n*m para
n > 0. Dena la multiplicaci on en terminos de la suma de enteros. Por
ejemplo 3*4 es igual a sumar 3 el 4.
7. De un algoritmo recursivo para la division entera n/m para m > 0.
Dena la divisi on en terminos de la resta de enteros.
1.5. EJERCICIOS 41
8. Escriba un algoritmo recursivo que calcule el resto de la divisi on n%m
para m > 0 (ej. si n = 5 y m = 3 5 %3 = 2).
a) Se ha depositado en una instituci on bancaria un monto de capital
m por el cual se recibe un X % de interes anual. El problema
consiste en determinar el capital que se tendr a al cabo de n meses.
Recuerde que para el algoritmo recursivo debe establecer los casos
base y recursivo del problema.
b) Dados como datos dos n umeros enteros positivo A y B, escriba
un programa calcule A
B
.
c) Escriba un programa que, dado como dato un n umero entero po-
sitivo regrese 1 si todos los dgitos de dicho numero son pares y 0
en otro caso.
d) Dado un arreglo de enteros, dise nar algoritmos que calculen :
El mayor elemento del arreglo.
La suma de los elementos del arreglo.
La media de los elementos del arreglo.
e) Escriba un programa que invierta el orden de los elementos de
un arreglo de n n umeros enteros. Es decir que el elemento den
la posicion n se intercambie con el de la posici on n, el 2 con la
posici on n-2 y as sucesivamente.
f ) Proporcione un algoritmo que busque el valor X en un arreglo de
enteros ordenado de forma decreciente.
g) Escriba un programa que dado un arreglo de n elementos(n debe
ser par) , determine si las sumas de las dos mitades ( del elemento
0 a (n 1)/2 y del elemento (n 1)/2 + 1an 1) son iguales.
h) Escriba un metodo que dado un vector contar el n umero de veces
que aparece un termino X.
i ) Dise ne un algoritmo que dado un entero n determine si es pri-
mo (recuerde que los n umeros primos son aquellos que solo son
divisibles entre ellos mismos y la unidad).
9. Denir el/los caso(s) base y recursivo para determinar si una cadena es
o no un palndromo. Los palndromos son palabras, n umeros o frases
que se lee igual hacia adelante que hacia atras(ana, 00100, 0110, etc).
42 CAP
ON Y RECURSI
ON
10. Dado el siguiente programa analizarlo y decir que imprime para los
siguientes valores de x: x = 38, x = 51, x = 24
public P1(int x){
if (x>100)
System.out.println(x-8);
else{
System.out.println(x+9);
P1(x+9);
}
}
11. Dada la siguiente lista: [90 8 7 56 13 23 9]. Muestre la ejecucion para
los siguientes algoritmos:
a) ordenamiento de la burbuja
b) ordenamiento por mezcla
c) ordenamiento rapido
12. Diga cuantas comparaciones realizar an para el arreglo [1,2,3,4,5,6] los
siguientes algoritmos de ordenamiento: mergesort, quick sort utilizando
como pivote al primer elemento, quick sort utilizando pivote el ultimo
elemento y el oredenamiento de burbuja. Explique sus respuestas.
13. Modique los algoritmos de ordenamiento presentados en el captulo
(burbuja, mezcla y r apido) a nadiendo c odigo a cada uno de los metodos
con el n de contar el n umero total de comparaciones y del tiempo
total de ejecuci on de cada algoritmo. Ejecute los diversos algoritmos de
ejecuci on con los mismos datos de entrada, registrando el n umero total
de comparaciones y el tiempo de ejecuci on. Repita la prueba n veces
(n = 100) para listas de 10,100,200, 300 hasta 1000, es decir aplicar
el proceso de ordenamiento 100 veces sobre una lista de 10, luego 100
veces sobre una lista de 100 y as sucesivamente, obtener el promedio
de las n ejecuciones y gracar el promedio contra el la longitud de la
lista.
Nota: Cada lista se debe generarse de manera aleatoria, es decir 100
listas generadas aleatoriamente para cada caso (e.j 100 listas de 10 ...).
Captulo 2
El modelo de datos de listas
2.1. Introduccion
Frecuentemente utilizamos el concepto de lista. Es muy com un hacer lis-
tas de compras, lista de tareas pendientes o listas de invitados a una esta.
Las listas suelen estar enumeradas y ordenadas de acuerdo a alg un crite-
rio. En esta secci on analizaremos el modelo de datos de listas, as como la
impelentaci on de las operaciones b asicas.
2.2. Implementaci on del modelo de Listas li-
gadas
Las estructura de datos se implementa mediante el uso de referencias
para crear enlaces entre objetos. Est a solucion tiene ventajas y desventajas
respecto a soluciones equivalentes haciendo uso de arreglos.
Las listas ligadas implementadas utilizan variables de referencia a objetos
con el n de crear enlaces entre objetos. Recuerde que con una variable de
referencia a objeto almacena la direcci on del objeto, que indica donde esta ese
objeto almacenado en memoria.
Usualmente, una variable de referencia a objeto es solo importante para
poder accede a un objeto, pero generalmente no tiene ninguna importancia
que ubicaci on especca en memoria ocupe el objeto. Por tanto, en vez de
mostrar direcciones normalmente se muestran las variables de referencia como
nombres que apuntan a un objeto(ver Figura 2.1).
43
44 CAP
ITULO 2. EL MODELO DE DATOS DE LISTAS

referencia
Figura 2.1: Variable de referencia a un objeto
Si se dene una clase que tiene como dato una referencia a otro objeto
de la misma clase. Por ejemplo considere el codigo del listado 2.1.
Listing 2.1: Denicion de nodo
public class Nodo{
Object o;
Nodo siguiente;
}
Utilizando la clase anterior es posible crear una estructura enlazada. Cada
objeto Nodo contendr a un enlace a un segundo objeto Nodo. El segundo
objeto tambien contendr a una referencia a un objeto Nodo, que a su vez
contendr a otra, etc.
Este tipo de relacion es la base para crear una lista ligada, que es una
estructura enlazada en la que cada objeto hace referencia al siguiente, creando
as un orden lineal de los objetos de la lista. En la Figura 2.2 se muestra la
representaci on para una lista ligada.
primero
...
Figura 2.2: Representacion de una lista ligada
De la Figura 2.2 puede observarse que se necesita una variable de referen-
cia separada para indicar le primer nodo de la lista. La lista se terminar a en
nudo cuya referencia siguiente (porque apunta al siguiente objeto) sea nulo
2.3. OPERACIONES B
ASICAS CON LISTAS 45

(representado por el smbolo de tierra). El c odigo para la representaci on de
una lista ligada se muestra en el listado 2.2
Listing 2.2: Denicion de nodo
public class Lista{
Nodo primero;
public Lista (){
primero=null;
}
}
A diferencia de los arreglos que tienen un tama no jo, las lista no tienen
un lmite superior en lo que respecta a su capacidad, salvo las limitaciones de
memoria de la propia computadora. Una lista es considerada una estructura
de datos din amica, porque su tama no crece y disminuye seg un sea necesario.
2.3. Operaciones basicas con Listas
Sin importar el tipo de datos que se almacenen en una lista enlazada,
debe implementarse un algunas operaciones b asicas para gestionar los datos
que se guarden en ella. Especcamente es necesario poder agregar nodos,
eliminar nodos, buscar e imprimir (algunas otras operaciones se dejan como
ejercicio al alumno).
2.3.1. Inserci on de nodos
En una lista es posible insertar un nodo en cualquier ubicacion de la
misma: al inicio, al nal o incluso entre dos nodos interiores. Si agregamos un
nodo al inicio de la lista, es necesario reinicializar la referencia que apunta al
primer nodo de la lista, como se muestra en la Figura 2.3. Primero se apunta
la referencia siguiente del nodo nuevo al nodo que est a como primero de la
lista. En segundo lugar se reinicializa la referencia primero para que apunte
al nodo recien agregado.
Observe que podra haber dicultades si se invirtiera el orden le los pa-
sos de la inserci on . Si se reinicializara la referencia primero se perdera la
unica referencia a la lista y ya no podra recuperarse. El c odigo java para la
operaci on insertar al principio(insertaP) se muestra en el listado 2.3 .
46 CAP

primero
...
nuevo
X
1
2
Figura 2.3: Inserci on al principio de una lista
Listing 2.3: Inserci on de un nodo al principio de una lista
1: public void insertaP(Nodo nuevo ){
2: if(primero !=null)
3: nuevo.siguiente=primero;
4: primero=nuevo;
5:}
En el Listado 2.3 se contemplan dos casos. Cuando la lista esta vaca solo
se ejecuta la lnea 4 haciendo el unico nodo igual al primero de la lista. En
el caso donde la lista contiene al menos un elemento se ejecutan las lneas 3
y 4, realizando el proceso descrito en la Figura 2.3 .
La insercion de un al nal (en la que solo se tiene referencia la primero)
de una lista requiere de cierto procesamiento adicional. Primero se tiene
que encontrar el nodo que debe preceder al nodo nuevo. A diferencia de un
arreglo, en el que es posible acceder los elementos utilizando ndices, las listas
requieren que utilicemos una referencia separada para iterar a traves de los
nodos de la lista, hasta encontrar el nodo deseado (en este caso el ultimo de
la lista). En este caso a dicha referencia se le denominar a actual (indica el
nodo actual que se esta procesando).
En el proceso de insertar al nal es necesario hacer que la referencia actual
apunte al nodo al nal de la lista, y una ves encontrado poner el nuevo nodo
como el siguiente de actual (ver Figura 2.4). Es posible encontrar el ultimo
elemento en una lista mediante dos aproximaciones: utilizando inicializando
2.3. OPERACIONES B

actual como el primero de la lista e iterarlo mientras el siguiente no sea
nulo(est a aproximaci on es iterativa y se deja como ejercicio al alumno). La
segunda opci on es mediante recursi on, en este caso tenemos que enumerar
el/los caso(s) base y el/los caso(s) recursivos.
caso base 1 : Lista vaca, si la lista hacemos que primero apunte al nuevo
caso base 2 : actual es el ultimo de la lista, entonces hacemos que siguiente
de actual apunte a nuevo.
caso recursivo : Si actual no es el ultimo de la lista, entonces insertamos
al nal utilizando como actual al siguiente de actual.
El Listado 2.4 muestra el c odigo java para insertaF. Las lneas 2 y 3 son
el caso donde la lista est a vaca. Las lineas 6 y 7 el caso donde actual ha
alcanzado el nal de la lista, en 7 se hace la referencia de siguiente a nuevo.
Las lneas 4 y 5 son el caso recursivo, se prueba que actual no es el ultimo
en la lnea 4, sino se procede a hacer la llamada recursiva con el siguiente de
actual.
primero
...
nuevo
X
actual
Figura 2.4: Inserci on al nal de una lista
Listing 2.4: Inserci on de un nodo al nal de una lista
1: public void insertaF(Nodo actual ,Nodo nuevo){
2: if(actual ==null)
48 CAP

3: primero=nuevo;
4: else if(actual.siguiente !=null)
5: insertaF(actual.siguiente ,nuevo);
6: else if(actual.siguiente ==null){
7: actual.siguiente=nuevo;
8: }
9:}
2.3.2. Borrado de nodos
Es posible eliminar cualquier nodo de la lista, pero es necesario mantener
la integridad de la lista. As como en el proceso de insersi on de un nodo, es
posible borrar ya sea el primer o el utlimo elemento de la lista.
Para borrar el primer elemento se hace que el segundo elemento de la
lista ocupe el lugar del primero. Este proceso se muestra en la Figura 2.5. .
primero
...
X
Figura 2.5: Borrar al principiol de una lista
El c odigo en java para insertar un elemento al inicio de una lista se mues-
tra en el listado 2.5. En la lnea 2 se guarda una referencia al nodo que se va
a eliminar. La lnea 3 verica si la lista esta vacia, si no esta vacia se apunta
primeroa a primero.siguiente. En la lnea 5 se regresa el valor que se acaba
de borrar.
Listing 2.5: Borrado de un nodo al principio de una lista
1: public Nodo borraP (){
2: Nodo aux=primero;
3: if(primero !=null)
4: primero=primero.siguiente
5: return primero;
2.3. OPERACIONES B

6:}
Para borrar el ultimo nodo de una lista, primero debe encontrarse el nodo
anterior al elemeto del nal. Esto requiere utilizar dos referencias una que
apunte el nodo del nal y otra que apunte al nodo precedente. Esas referecias
se denominan actual y previo como se observa en la Figura 2.5.
primero
...
X
actual
previo
Figura 2.6: Borrar al nal de una lista
En el listado 2.6 muestra el codigo en java que implementa el algoritmo
recursivo para borrar al nal de una lista ligada.
Listing 2.6: Borrado de un nodo al nal de una lista
1: public Nodo borraF(Nodo previo , Nodo actual ){
3: return null;
4: else if(actual.siguiente ==null&& actual == primero ){
5: primero=null;
6: return actual;
7: }
8: else if(actual.siguiente ==null){
9: previo.siguiente=null;
10: return actual;
11: }
12: return borraF(actual ,actual.siguiente );
13:}
En el metodo las referencias a los nodos actual y previo deben iniciar
ambas en el nodo primero. Del listado podemos enumerar dos casos base el
primero consideado en la lnea 4, que es cuando se borra de una lista con un
solo elemento. En tal caso se vacia la lista haciendo que el apuntador primero
50 CAP

apunte al nal de la lista, esto es necesario , ya que previo y actual apuntan
al mismo elemento. El segundo caso base (lnea 4) es cuando; actual est a al
nal de la lista, en esta situacion se realiza la operaci on indicada en la lnea 9
y se regresa el valor de nodo que se acaba de borrar. El caso recursivo ocurre
cuando actual todava tiene un nodo siguiente lo cual quiere decir que no es
el ultimo elemento de la lista. En este caso se llama recursivamente a borraF
haciendo previo el nodo actual y recorriendo actual a actual.siguiente. El caso
de la lnea 1 es cuando se quiere borrar un elemento de una lista vacia, aunque
tambien podra manejarse como una excepcion aqu se considera como una
un caso especial, para simplicar el c odigo.
Tambien es posible borrar un elemeto intermedio de una lista, pero esto
se deja como ejercicio al alumno, as como las implementaciones iterativas de
los metodos de borrado.
2.3.3. B usqueda e Impresion
Al realizar una b usqueda en una lista ligada, nos interesa saber si un
elemento x es o no un elemento de esta. A diferencia de los arreglos en
los cuales es posibles responder a una b usqueda en O(log(n)) si el arreglo
est a ordenado, para realizar una b usqueda en una lista es necesario en el
peor caso recorrer la lista entera, por lo que tendremos una complejidad de
O(n).
Para realizar una b usqueda iterativa es necesario recorrer la lista desde el
inicio e iterar cada nodo; hasta encontrar el elemento x o bien llegar al nal
de la lista. El algoritmo iterativo para realizar una b usqueda se queda como
ejercicio al alumno. El algoritmo recursivo se basa en la idea de comenzar
revisando un nodo de la (se comienza con el primero) de la lista, si el nodo
contiene a x se termina el algoritmo y se tiene una b usqueda exitosa. Si el
primero no contiene a x entonces se hace una llamada recursiva al metodo
de b usqueda con el nodo siguiente . Una vez que se alcanza el nal de la lista
(es decir el nodo actual es nulo) se puede armar que x no es parte de la
lista. Para el algoritmo podemos enumerar los siguientes casos:
caso base 1 : El nodo actual es nulo, si esto sucede x no se encuentra en la
lista.
caso base 2 : El nodo actual contiene a x entonces el elemento si se encuen-
tra en la lista.
2.3. OPERACIONES B

caso recursivo : Si actual no es nulo y no contiene a x, entonces se hace
una llamada recursiva a b usqueda con el siguiente del nodo actual .
El listado 2.7 muestra el c odigo en java que implemta el algoritmo de
b usqueda en una lista ligada.
Listing 2.7: Buscar un elemento x en una lista
1: public boolean busca(Nodo actual , Nodo x){
3: return false;
4: else if(actual.compareTo(x)==0)
5: return true;
6: else
7: return busca(actual.siguiente ,x);
8: }
La lnea dos es el caso cuando se ha alcanzado el nal de la lista, este caso
s olo ocurre cuando x no es parte de la misma y en consecuencia se regresa
un falso. En la lnea 4 se prueba que el nodo actual contiene a x, si es as se
regresa verdadero ya que x si forma parte de la lista. La lnea 6 es el caso
recursivo si e x no se encuentra en el nodo actual se revisa el resto de la lista.
En el caso de impresion de una lista la idea es muy similar; se procesa el
primer nodo de la lista sino es nulo se imprime el contenido y se hace una
llamada recursiva al metodo de impresi on con el nodo siguiente del actual.
Los caso para este metodo son:
caso base 1 : El nodo actual es nulo, si esto sucede ya e termino de imprimir
la lista
caso recursivo : Si el nodo actual no es nulo, imprimir el contenido y hacer
una llamada recursiva al metodo que imprime la lista.
2.3.4. Algoritmos de Ordenamiento utilizando listas
Los algoritmos de ordenamiento previamente vistos pueden ser imple-
mentados para ordenar listas ligadas. En este apartado revisaremos como
implementar el mergeSort utilizando listas ligadas.
Como se muestra en el algoritmo 7, el algoritmo consiste en dividir la
lista en dos mitades, ordenar las mitades resultantes con el mismo algoritmo
52 CAP

para nalmente ordenar las mitades resultantes. En esencia el algoritmo para
ordenar listas es el mismos que el ya visto, la principal diferencia son procesos
de divisi on y mezcla que nos permiten en este caso implementar el algoritmo
sin necesidad de utilizar memoria adicional.
Divisi on
El proceso de division podra ser tan simple como contar los elementos de
la lista y despues borrar la mitad de los elementos e insertarlos en una nueva
lista. Con la idea anterior se realizan un total de n operaciones para contar los
elementos en la lista y n/2 operaciones para borrar e insertar los elementos
en la nueva lista, con lo cual realizamos aproximadamente 3/2n operaciones
en la division. Es posible optimizar un poco el n umero de operaciones a n/2.
La idea consiste en crear una nueva lista en la que el primer nodo de la misma
apunte al segundo nodo de la lista original y hacer que el siguiente de la lista
original apunte al tercer nodo de ella. La idea se ilustra en la gura 2.7. De
manera formal podemos denir el algoritmo que divide la lista como sigue:
prmero
prmero
sta nueva
nodo de
regreso
Lamada
recursva a spt
Figura 2.7: Proceso de division de una lista
caso base : Si la lista est a vaca o contiene un solo elemento, la segunda
lista es una lista vaca.
caso recursivo : Si la lista tiene mas de un elemento se borra el segundo
de la lista original y se pone en la lista nueva. Se repite el proceso para
2.3. OPERACIONES B

el siguiente elemento de la lista original y se asigna el resultado como
el siguiente de la lista nueva.
El listado se muestra en 2.8
Listing 2.8: Dividir una lista en dos
1: public Nodo split(Nodo fl){
2: Nodo sl=new Nodo ();
3: if(fl==null || fl.siguiente ==null)
4: return null;
5: else{
6: sl=fl.siguiente;
7: fl.siguiente=sl.siguiente;
8: sl.siguiente=split(sl.siguiente );
9: return sl;
10: }
11:}
El primer caso se considera en las lneas 3 y 4, el segundo de la lnea 6 a
9.
Mezcla
El proceso de mezcla no requiere memoria adicional ya que podemos
enlazar las dos listas sin necesidad de crear una nueva lista. La denici on
recursiva del algoritmo queda como sigue:
caso base : Si una de las dos listas esta vaca, se regresa la otra lista.
caso recursivo : Si el nodo actual de la lista
1
es el mayor que el nodo
actual de la lista
2
entonces seleccionar el nodo de la lista
2
y asignar al
siguiente de este la mezcla de la lista
1
con el resto de los nodos de la
lista
2
. En contrario caso tomar el nodo siguiente de la lista
1
y asignar
a su siguiente el resultado de la mezcla de la lista
2
con el resto de los
nodos en la lista
1
El codigo java para el algoritmo de mezcla se muestra se muestra en 2.9
54 CAP

Listing 2.9: Mezclar dos listas ordenadas
1: public Nodo merge(Nodo lp , Nodo rp){
2: if(lp==null)
3: return rp;
4: else if(rp==null)
5: return lp;
6: else if(rp.compareTo(lp)>0){
7: lp.siguiente=merge(lp.siguiente ,rp);
8: return lp;
9: }
10: else{
11: rp.siguiente=merge(lp ,rp.siguiente );
12: return rp;
13: }
14:}
Las lneas 2 a 5 contemplan el caso base. El caso recursivo se implementa
de la lnea 6 a 13.
Una vez implementados los metodos de division y mezclado el algoritmo
de ordenamiento es pr acticamente el mismo que se implemento en la versi on
con arreglos.
2.4. Implementaci on del modelo de Pilas
Una Pila o Stack es un tipo especial de lista en el que las inserciones y
borrados ser realizan en el mismo extremo de la lista(al inicio o al nal),
a el extremo seleccionado se le denomina tope. A las pilas se les denomina
LIFO (Last In First Out) o listas ultimo en entrar, primero en salir . Una
pila puede ser visto como un grupo de libros amontonado sobre el piso, o de
platos en una estantera, situaciones en la que es conveniente quitar o agregar
un objeto en el extremo superior de la pila (tope). Una pila debe incluir las
siguiente operaciones:
push Agrega un elemento al tope de la pila. Se realiza la operacion mediante
la funcion insertaP
pop Elimina lo que hay en el tope de la pila. Se implementa utilizando el
metodo borraP de una lista
2.4. IMPLEMENTACI
ON DEL MODELO DE PILAS 55

seek Devuelve el valor que se encuentra en el tope de la pila. Se puede
implementar regresando el valor que contiene el nodo primero de la
lista.
empty Verica si la pila est a vacia. Regresa verdadero si primero apunta a
nulo.
Como puede observarse para implementar una pila es posible utilizar la
implementaci on de listas ligadas. S olo es necesario insertar y borrar por el
mismo extremo, ya sea al inicio o nal de la lista. Se utilizan las funciones
que insertan/borran al principio por cuestiones de eciencia.
2.4.1. Conversi on de notacion inja a posja
Una pila puede ser utilizada para convertir una expresi on inja a nota-
ci on posja. La notaci on inja es la utilizamos cotidianamente para escribir
expresiones aritmeticas por ejemplo 3 2 + 5. La notaci on inja necesita re-
glas de precedencia, por ejemplo en la expresi on anterior hacemos primero
la operaci on 3 2 y despues la suma con 5, esto porque el operador tiene
mayor precedencia que el operador +. si se quisiera hacer primero la suma
de 2 + 5 se tendra que expresarlo median el uso de parentesis reescribiendo
la expresi on como 3 (2 + 5). La notacion posja es m as sencilla de proce-
sar para una computadora ya que no necesita precedencia y por tanto no es
necesario el uso de parentesis. En una expresi on posja el operador siempre
est a a la derecha de sus dos operandos, por ejemplo la notaci on posja de
3 + 2 se reescribe como 32+.
Es posible convertir cualquier expresi on inja a posjo mediante el uso
del siguiente procedimiento.
Si el car acter actual es un dgito poner en posjo
Si el car acter es un parentesis izquierdo poner en la pila
Si el car acter actual es un operador
Sacar los operadores (si los hay) de la parte superior de la pila,
mientras tengan mayor o igual precedencia que el operador actual,
e insertarlos en posjo
Meter en la pila el car acter actual
56 CAP

Si el car acter actual en injo es un parentesis derecho
Sacar los operadores de la parte superior de la pila e insertarlos
en posjo, hasta encontrar un parentesis izquierdo en la pila
Sacar y descartar el parentesis izquierdo
2.5. Implementaci on del modelo de Colas
Una cola es otro tipo especial de lista en la que los elementos se insertan
por un extremo (posterior) y se eliminan (frente) en el otro. Las colas son
conocidas tambien como FIFO (del ingles rst-in rst-out) o listas primero
en entrar primero en salir. Las operaciones de una cola son an alogas a las de
las pilas; las diferencias sustanciales consisten en que una de las dos opera-
ciones de inserci on y borrado se hace por un extremo diferente(por ejemplo
insertamos al inicio y borramos al nal o viceversa). En el caso de una cola
deben implementarse las siguientes operaciones:
enqueue Agrega un elemento en la parte posterior de la cola. Se realiza la
operaci on mediante la funci on insertaP
queue Elimina lo que hay en el frente de la cola. Se puede ejecutar esta
operaci on utilizando el metodo borraP de una lista
front Devuelve el valor que se encuentra en al frente de la cola. Se puede
implementar regresando el valor que contiene el nodo que este en el
extremo que es frente de la lista
empty Verica si la cola esta vacia. Regresa verdadero si primero apunta a
nulo.
En esta instancia sera relativamente sencillo implementar un modelo de
colas utilizando el modelo de listas ya visto, por lo que se deja como ejercicio
al lector.
2.5. IMPLEMENTACI
ON DEL MODELO DE COLAS 57

2.5.1. Programaci on Dinamica
Subsecuencia Com un mas Larga (Longest Common Subsequence
LCS)
El problema de Longest Common Subsequence es un excelente ejemplo
para mostrar el uso de la Programac on Din amica. La programaci on dinami-
ca se basa en la siguiente idea: primero se obtiene un algoritmo recursivo,
el cual puede ser ineciente debido a que se ejecuta repetidamente en los
mismos subproblemas. La tecnica consiste en almacenar la soluci on a cada
subproblema la primera vez que se computa, para despues recuperarla en lu-
gar de volverla a computar. El incremento en la eciencia de un algoritmo de
programaci on din amica con respecto de su soluci on recursiva es proporcional
a n umero de subproblemas repetidos que resuelve la soluci on recursiva.
Existen dos formas de programaci on din amica, top-down y bottom-up.
El metodo Top-down es muy parecido al algoritmo de la soluci on recursiva,
por tanto mas f acil de entender, pero el metodo bottom-up es usualmente
m as eciente.
subsecuencia
Antes de denir el problema de la subsecuencia com un mas larga, se re-
solver a un problema m as simple. Suponiendo que se proporciona una cadena
peque na (patron) y una cadena muy larga(texto), como en el problema de
b usqueda de un patr on en un documento. Pero en este caso no importa si
el patron aparece de forma continua en el texto, si el patr on ocurre decimos
que una subsecuencia del texto.
Como ejemplo gata.
es
una subsecuencia de ingeniera en computaci on.
La forma m as sencilla de visualizarlo es capitalizando la subsecuencia inGe-
nierA en compuTAci on. Es posible vericar si un patron es subsecuencia
de un texto con el algoritmo 10
Subsecuencia com un mas larga
Este problema consiste en encontrar la secuencia que ocurre tanto en
el patr on como en el texto, en este caso el texto y el patron pueden ser de
longitudes muy similares por lo tanto; nos referiremos a ellos como las cadenas
A y B. Una soluci on para LCS es de utilidad en m ultiples aplicaciones:
58 CAP

Algoritmo 10 Funcion para saber si un patron en una subsecuencia de un
texto
Entrada: p y T el patron y el texto
Salida: Verdadero si p ocurre en T falso de cualquier otra forma
1: n =longitud de T
2: m =longitud de p
3: mientras i < n && j < m hacer
4: si T[i] == p[j] && j == m1 entonces
5: devolver cierto
6: n si
7: si T[i] == p[j] entonces
8: j = j + 1
9: n si
10: i = i + 1
11: n mientras
12: devolver falso
En biologa molecular. Las secuencias de ADN pueden ser representa-
das por cuatro letras ACGT, correspondientes a las cuatro submolecu-
las que conforman el ADN. Cuando los bi ologos encuentran una nueva
secuencia, tpicamente se quiere saber a que otras subsecuencias se pa-
rece m as. Una forma de computar que tan similares son dos secuencias
es encontrando la longitud de la LCS.
Comparaci on de archivos. El programas di de Unix es utilizado para
comparar dos versiones del mismo archivo, para determinar que cam-
bios han sido realizados. Este funciona encontrando la LCS de las lineas
de los dos archivos; cualquier linea en la subsecuencia no ha sido cam-
biada, entonces despliega el conjunto de lneas restantes que son las
que fueron modicadas.
Solucion recursiva
Para obtener la solucion de programacion din amica para LCS , primero
es necesario obtener la soluci on recursiva. Programaci on dinamica no nos
proporciona una soluci on al problema, solo nos ayuda a hacer la solucion
m as eciente una vez que ya se ha obtenido.
2.5. IMPLEMENTACI

Se puede observar que el problema lo podemos resolver alineando la le-
tras que coinciden de ambas cadenas, por ejemplo para hola mundo y
landaquedara como en la gura 2.8
h o a m u n d o
a n d a
Figura 2.8: Subsecunecia com un mas larga
Si se dibujan lineas conectando las letras de la primera cadena que coin-
ciden con la segunda, sin que haya lneas que se crucen. En consecuencia
cualquier conjunto de lneas que se dibujen y las cuales no se crucen repre-
sentan una subsecuencia.
De lo anterior se puede observar el siguiente hecho: si dos cadenas co-
mienzan con la misma letra, siempre es posible elegir esa letra como el inicio
de una subsecuencia. Esto es debido a que, si se existe alguna otra subse-
cuencia, representado como en el gura 2.8, puede moverse la linea de mas a
la izquierda al inicio de las dos cadenas, sin causar ning un cruce, y conseguir
una representaci on de la misma longitud que la que comienza de la misma
forma.
Por otro lado, suponiendo que, como en el ejemplo, las dos primeras
letras son diferentes. Entonces es posible para ambas formar parte de una
subsecuencia com un o una o ambas podran ser eliminadas de la subsecuencia
.
Finalmente se puede observar que una vez decidido que hacer con el pri-
mer caracter de las cadenas, el problema restante es nuevamente el problema
de LCS, con dos cadenas mas cortas. Por tanto se puede resolver recursiva-
mente.
En lugar de encontrar la subsecuencia, es m as eciente encontrar la longi-
tud de la misma. Entonces en el caso donde el primer caracter diere, puede
determinarse cual subproblema proporciona la soluci on correcta mediante la
resoluci on de ambos y tomando la longitud maxima de las resultantes. Una
vez que se obtiene la soluci on con programaci on din amica es posible obtener
la subsecuencia misma.
A partir de las observaciones mencionadas es posible derivar el siguiente
60 CAP

algoritmo.
caso base : Si una de las cadenas est a vaca, entonces la longitud de la LCS
es 0.
caso recursivo 1 : Si la primera letra de ambas cadenas es igual, la longitud
de la LCS es al menos de 1 m as la longitud de la LCS de las cadenas
eliminado el primer caracter en ambas.
caso recursivo 2 : Si la primera letra es diferente, entonces la longitud es
el m aximo de resolver LCS para la subcadena resultante de remover la
primer letra de A mientras B se mantine completa y el de resolver para
B sin el primer caracter y A completa.
El listado 2.10 se muestra el c odigo java para lo soluci on recursiva a LCS.
El caso base se implementa en las lineas 2 y 3, el caso recursivo en las lneas
4 a 6, en este caso se resuelve el problema de LCS utilizando los sujos de A
y B. El caso recursivo 2 es la lnea 7.
Listing 2.10: Solucion recursiva para LCS
1: public static int lcs(String A, String B){
2: if(A.length ()==0 || B.length ()==0)
3: return 0;
4: else if(A.charAt (0)==B.charAt (0)){
5: return 1+lcs(A.substring (1),B.substring (1));
6: }
7: return Math.max(lcs(A,B.substring (1)),lcs(A.substring (1),B));
8:}
Esta es una solucion correcta pero muy ineciente. Por ejemplo, si dos
cadenas no contienen ning un caracter en com un, entonces siempre ocurre el
caso recursivo 2, y si las longitudes de ambas cadenas son n se obtiene una
complejidad de 2
n
.
2.5.2. top-down
El problema con la solucion recursiva es que el mismo subproblema es
resuelto muchas veces. Un subproblema consiste en todas las llamadas re-
cursivas a LCS, con los sujos de A y B, entonces existen exactamente
2.5. IMPLEMENTACI

(n+1)(m+1) posible subproblemas. Los subproblemas que deben ser recor-
dados es la combinacion de los n + 1 sujos de A(aunque la longitud de A
es n tambien la cadena vaca es un sujo de A y de ah el +1) y los m + 1
sujos de B, por tanto necesitamos resolver (n + 1) (m + 1) posibles so-
luciones. Si hay cerca de 2
n
llamadas recursivas, eso implica que algunos de
eso subproblemas son resueltos varias veces.
La soluci on mediante programacion din amica consiste en vericar si cada
subproblema ya ha sido resuelto. Si ya fue resuelto s olo se recupera en lugar
de volver a computarlo. La implementacion de la soluci on de programaci on
din amica consiste en modicar el algoritmo recursivo para que almacene los
subproblemas y puedan reutilizarse las soluciones, a esto a lo que se le llama
top down.
En el problema LCS, los subproblemas consisten en un par de sujos de las
cadenas de entrada. Para hacer facilitar almacenar y recuperar las soluciones
parciales, se utilizar an la posiciones en las que comienzan los sujos.
LSC recursivo con indixes
Con en objeto de facilitar la deduccion de la solucion utilizando progra-
maci on din amica, primero se modica la soluci on recursiva, para que, utilice
ndices. La soluci on queda como en el listado 2.11
Listing 2.11: Soluci on recursiva para LCS utilizando ndices
1: public static int lcs_index(String A, String B,int i, int j){
2: if(A.length ()==i || B.length ()==i)
3: return 0;
4: else if(A.charAt(i)==B.charAt(j)){
5: return 1+ lcs_index(A,B,i+1,j+1);
6: }
7: return Math.max(lcs(A,B,i,j+1), lcs_index(A,B,i+1,j));
8:}
Puede observarse que los casos son los mismos, pero en el listado 2.10
se elimina el primer caracter de la cadena con lo que sujo a procesar en
cada subproblema comienza siempre en la posici on 0. En el listado 2.11 se
introducen las variables i y j para recordar donde comienza el sujo que
se esta procesando.
Ahora ya es posible convertir la solucion recursiva en un algoritmo de
programaci on din amica, solo se necesita usar un arreglo para almacenar el
62 CAP

resultado de cada subproblema. Cuando se quiere la soluci on de un sub-
problema dado, primero se verica en el arreglo si ya se ha computado la
soluci on. Si es as se regrese el resultado; en caso contrario se calcula y se
almacena el resultado en el arreglo.
En LCS, no existen resultados negativos, por lo que es posible utilizar 1
para indicar al algoritmo que la soluci on a un subproblema a un no ha sido
computado.
Listing 2.12: Soluci on top-down
1: public static int lcs_array(String A, String B){
2: int n=A.length ()+1;
3: int m=B.length ()+1;
4: int L[][]= new int[n][m];
5: for(int i=0;i<n;i++){
6: for(int j=0;j<m;j++)
7: L[i][j]=-1;
8: }
9: return subproblema(A,B,L,0 ,0);
10:}
Listing 2.13: Subproblema LCS
1: public static int subproblema(String A, String B, int L[][], int i, int j){
2: if(L[i][j]<0){
3: if(A.length ()==i || B.length ()==j)
4: L[i][j]=0;
6: L[i][j]=1+ subproblema(A,B,L,i+1,j+1);
7: }
8: else{
9: L[i][j]=Math.max(subproblema(A,B,L,i+1,j),subproblema(A,B,L,i,j+1));;
10: }
11: }
12: return L[i][j];
13:}
La recursion en el listado 2.13 es quien determina el llenado de la matriz
L. En tabla 2.1 se muestra como llena la matriz L. En la tabla se etiquetan
las las con los caracteres en A y las columnas con los caracteres en B, como
2.5. IMPLEMENTACI

puede observarse la posicioni, j representa las soluci on para las cadenas donde
el sujo comienza en esa posicion. Por ejemplo el caso 0, 0 es el problema para
las cadena A y B completas y por tanto la solucion de problema original.
Mientras en la posici on n + 1, m + 1 es el subproblema donde los sujos
de ambos son la cadena vaca y la soluci on es 0 y ocurre lo mismo para
todos los casos i, m + 1 y n + 1, j. Para comprender como se llena la matriz
podemos observar de la tabla 2.1 que no se computaron todos los valores, esto
debido a que para computar L[0][0] (como h = l) debemos computar L[0][1] y
L[1][0], a su vez L[0][1] requiere el calculo de L[0][2] yL[1][1]; mientras L[1][0]
depende de L[1][1] y L[2][1] y as sucecivamente hasta que se encuentre un
caso que no dependa de una llamada recursiva. Puede observarse que L[1][1]
ser a resuelto solamente una vez a un cuando lo requieren L[1][0] y L[0][1],
ya que si lo calcula y almacena la llamada desde L[1][0]; cuando lo requiera
L[0][1] solo tendr a que recuperarse. El algorimto termina cuando ha resuleto
todos los subproblemas necesarios para calcular L[0][0] y es por ellos que fue
necesario calcular todos los subproblemas.
Cuadro 2.1: LLenado de el arreglo L
h o l a m u n d o
l 4 4 4 -1 -1 -1 -1 -1 -1 -1
a 3 3 3 3 -1 -1 -1 -1 -1 -1
n 2 2 2 2 2 2 2 -1 -1 -1
d 1 1 1 1 1 1 1 1 -1 -1
a 1 1 1 1 0 0 0 0 0 0
0 0 0 -1 0 0 0 0 0 -1
De los listados 2.12 y 2.13 podemos observar que cada subproblema con-
sume tiempo constante. Se hace una sola llamada a la rutina principal (2.12),
y a lo mas dos llamadas por cada vez que se resuelve un subproblema. Son
tiempo constante: el caso donde ya se computo la entrada solo se revisa el
arreglo (lnea 12), cuando ya se proceso al menos una de las cadenas com-
pleta L[i][j] = 0 (lneas 3 y 4) y se resuelven dos llamadas recursivas cuando
A[i] = B[j](lneas 8-10) y una en caso de que A[i] = B[j] (lneas 5-7). De
lo anterior se puede deducir que a lo m as se haran dos ejecuciones cada que
se computa un elemento del arreglo L. Como hay (m + 1)(n + 1) elementos,
entonces el n umero total de ejecuciones sera de a lo mas 2(m+1)(n +1) +1
lo que resulta en una complejidad de O(mn). Como es usual, este es el peor
64 CAP

caso. Por lo que el n umero de operaciones necesarias puede ser menor en
algunas ocasiones, cuando no sea necesario computar todas las entradas del
arreglo. Por ejemplo si las dos cadenas son iguales es solo necesario calcular
la diagonal de L y el algoritmo ser a m as rapido.
Bottom up
El codigo de los listados 2.12 y 2.13 puede ser visto como una forma m as
inteligente de escribir el algoritmo recursivo original, que ahorra tiempo al no
repetir trabajo. Pero tambien es posible pensar que es una forma de llenar
las entradas en L. El algoritmo recursivo controla el orden que el arreglo
es llenado, pero se obtendran los mismos resultados si se llenara utilizando
alguna otra estrategia. Por ejemplo podra utilizarse un ciclo que compute las
entradas de forma mas sistem atica. El unico problema sera decidir cuando es
el momento para computar un L[i, j] dado, del algoritmo recursivo podemos
observar que cada subproblema depende ya sea de L[i + 1][j + 1] o de los
L[i][j +1] y L[i +1][j]. Por est a razon es necesario iterar el arreglo en forma
inversa (ya que el solucion i depende del solucion i + 1), desde la ultima
la hasta la primera y de la ultima columna hacia la primera. El algoritmo
resultante es un algoritmo iterativo o bottom up(debido a que en este caso
se comienza con los subproblemas m as simples para resolver los subproblema
m as complicados).
Implementado la idea anterior obtenemos la solucion iterativa para LCS
( ver 2.14).
Listing 2.14: Solucion de LCS Bottom up
1: public static int lcs_it(String A, String B){
2: int n=A.length ();
3: int m=B.length ();
4: int L[][]= new int[n+1][m+1];
5: String subs="";
6: for(int i=n;i>=0;i--){
7: for(int j=m;j>=0;j--){
8: if(n==i || m==j)
9: L[i][j]=0;
11: L[i][j]=1+L[i+1][j+1];
12: }
2.6. EJERCICIOS 65
13: else
14: L[i][j]=Math.max(L[i+1][j],L[i][j+1]);
15: }
16: }
17: return L[0][0];
18:}
Las ventajas del metodo en el listado 2.14 incluyen en hecho de que la
iteraci on es normalmente m as rapida que la recursion, no es necesario ini-
cializar todos los valores de la matriz en -1 y que cuando se quiere calcular
L[i][j] no es necesario probar si L[i][j + 1], L[i + 1][j] y L[i + 1][j + 1] ya
que han sido computados en las iteraciones previas. Una desventaja sobre la
estrategia top-down es que ser requiere calcular todos los valores en el arreglo
a un cuando el problema podra resolverse computando solo una fracci on de
las celdas del arreglo.
2.6. Ejercicios
1. Dada una lista de enteros ordenada y un valor entero, especicar un
algoritmo que inserte el valor en el lugar apropiado y sin repeticion, es
decir si el valor ya esta en la lista no se realiza la inserci on.
2. Dada una lista y un valor , especicar un algoritmo recursivo que borre
todas las apariciones de ese elemento de la lista.
3. Proponga un algoritmo que procese una lista y la imprima de forma
inversa.
4. Escriba algoritmos recursivo e iterativo que sume dos listas elemento a
elemento y regrese una tercera lista que contenga los elementos de la
sumas. Por ejemplo si la entrada son 1-2-3 y 4-1-0 la lista resultante
debera contener 5-3-3 (considere que las listas siempre tiene el mismo
n umero de elementos).
5. Proponga una estructuras basada en listas para representar polinomios.
6. Basado en su representacion(del ejercicio anterior) implemente un al-
goritmo que calcule la derivada de un polinomio
66 CAP

7. Escriba los estados de una pila en el proceso de conversi on a posjo de
la siguiente expresion (3 + 4) (5 3)/2
8. Implementar un evaluador de expresiones en posjo.
9. Describa como podra implementar una cola con dos pilas.
10. Describa como podra implementar una pila con dos colas.
11. Proporcione un algoritmo que dadas dos listas A y B ordenadas de
forma ascendente, obtenga una lista C que sea la mezcla de las lista A
y B pero ordenada en forma descendente.
12. Propocioen una implementacion del algoritmo de ordenamiento de bur-
buja utilizando listas ligadas.
13. Proporcione una versi on modicada del algoritmo visto en clase para
obtener la longitud el patr on LCS, el cual debe regresar la cadena
que representa la LCS (e.g. si se tienen las cadenas Hola mundo y
landa el algoritmo deber a regresa land en lugar del 4 que regresaba
el algoritmo visto en clase)
14. Implemete una solucion de programaci on lineal para el problema de los
coeciente binomiales.
15. Dados los siguiente pares de cadenas:
A B
abracadabra abracadabra
abracadabra barba
di-
ga cual es la matriz resultante L de aplicar la soluci on de programacion
din amica top-down para el problema de LCS, a cada uno de los pares.
Captulo 3
El modelo de conjunto de datos
3.1. Deniciones Basicas y Principales Ope-
raciones con Conjuntos
3.1.1. Deniciones Basicas
Generalmente un conjunto no se dene explcitamente, m as bien se de-
ne por las propiedades que este guarda. Una de estas propiedades es la de
pertenencia, es decir, dado un conjunto S y un elemento x se puede realizar
la pregunta pertenece el elemento x al conjunto S? As, un conjunto S con-
siste de todos los elementos x para los que el predicado x pertenece a S es
verdadero. La notacion estandar para conjuntos se muestra a continuaci on
1. La expresi on x S signica que x pertenece al conjunto S.
2. Si x
1
, x
2
, . . . , x
n
son elementos del conjunto S, entonces se puede escri-
bir:
S = {x
1
, x
2
, . . . , x
n
}
N otese que cada x es distinta y el orden en que se presentan los ele-
mentos es irrelevante.
3. El conjunto vaco (denotado por ) es el conjunto que no contiene
elementos. Por lo que x ser a siempre falso para toda x.
67
68 CAP
ITULO 3. EL MODELO DE CONJUNTO DE DATOS
Atomos
De manera formal, en la teora de conjuntos solo existen conjuntos, sin
embargo, en estructuras de datos o algoritmos es conveniente tener elementos
( atomos) que no sean conjuntos. Un atomo puede ser miembro de un con-
junto, pero no contener elementos. En ocasiones es necesario que los atomos
sean informacion compleja, por lo que un atomo puede ser una estructura o
un arreglo.
Denici on de Conjuntos por Comprensi on
Anteriormente se propuso que un conjunto debe ser denido enlistando
a todos sus miembros (denici on por extensi on), lo que puede llegar a ser
inconveniente. Para realizar una denicion por comprensi on de un conjunto
A se requiere de un conjunto S y, al menos, una regla o proposicion P, es
decir, todos los elementos del conjunto A deben pertenecer a S y cumplir
con P. Esto es
A = {x S P (x)}
o bien,
{A | x S P (x)}
Igualdad de Conjuntos
Un conjunto es igual a otro si ambos contienen exactamente a los mismos
elementos. Es decir, un conjunto A es igual a un conjunto B (escrito A = B)
si y solo si todos los elementos de A lo son de B y todos los elementos de B
son miembros de A. Por ejemplo,
{1, 2} = {x | x {1, 2, 3, } x < 3} = {2, 1}
Conjuntos Innitos
Algunos conjuntos tienen un n umero nito de elementos, por lo que se
puede establecer su cardinalidad con un n umero entero. Existen conjuntos
cuya cardinalidad es innita, que tienen un n umero innito de elementos, por
ejemplo los n umeros Naturales (N), Enteros (Z), Reales (R) y Complejos
(C).
3.1. DEFINICIONES B
ASICAS YPRINCIPALES OPERACIONES CONCONJUNTOS69

3.1.2. Operaciones con Conjuntos
En este apartado se revisan las operaciones con conjuntos y se discuten
sus implementaciones.
Union, Interseccion, Diferencia
Se entiende por uni on de dos conjuntos S y T al conjunto que contiene
todos los elementos de S y todos los de T, y se denota por S T.
Dados dos conjuntos S y T, el conjunto que contiene los elementos de S
que adem as son miembros de T es conocido como la intersecci on de S y T,
matem aticamente, S T.
La resta o diferencia de dos conjuntos S y T (S T) es el subconjunto
que contiene los elementos que est an en S y no est an en T.
Gr acamente:
Unin
Interseccin
Resta
Figura 3.1: Operaciones con conjuntos
Diagramas de Venn
Los diagramas de Venn son una herramienta graca para ver las distintas
operaciones realizadas a dos o m as conjuntos, la Figura 3.1 muestra una
versi on primitiva de un diagrama de Venn.
70 CAP

Figura 3.2: Diagrama de Venn
En la Figura 3.2
Regi on 1 Elementos que no est an en S ni pertenecen a T
Regi on 2 Elementos que son miembros de S y no se encuentran en T (S T)
Regi on 3 Elementos que pertenecen tanto a S como a T (S T)
Regi on 4 Elementos que son miembros de T y no se encuentran en S (T S)
Regiones 2,3,4 La combinacion de las regiones 2, 3 y 4 representa la union de los
conjuntos S y T (S T)
Algebra de Conjuntos
En lo sucesivo S, T, y R son conjuntos no vacos y la equivalencia entre
expresiones se denota por .
Conmutatividad de la union. (S T) (T S),
Asociatividad de la union. (S (T R)) ((S T) R)
Conmutatividad de la interseccion. (S T) (T S)
Asociatividad de la interseccion. (S (T R)) ((S T) R)
Distributividad de la interseccion sobre la union. (S (T R)) ((S T) (S R))
Distributividad de la union sobre la interseccion. (S (T R)) ((S T) (S R))
Asociatividad de la union y la diferencia. (S (T R)) ((S T) R)
Distributividad de la diferencia sobre la union. ((S T) R) ((S R) (T R))
Identidad de la union.(S )
Idempotencia de la union. (S S) S
Idempotencia de la interseccion. (S S) S
Otras leyes del conjunto vaco. (S S) , ( S) , ( S)
3.1. DEFINICIONES B

3.1.3. Implementaci on de Conjuntos Utilizando Listas
Se recomienda utilizar listas ligadas ordenadas, de lo contrario se tendra
que comparar cada elemento de cada conjunto para realizar las operaciones
b asicas de conjuntos. Por ejemplo el algoritmo para la uni on de dos conjuntos
S y T, (U = S T):
Algoritmo 11 Uni on con Listas Desordenadas
Entrada: lista
1
,lista
2
1: copiar lista
1
a lista
nueva
2: para todo elemento en lista
2
hacer
3: si elemento no es miembro de lista
1
entonces
4: agregar elemento a lista
nueva
5: n si
6: n para
7: devolver lista
nueva
cada uno de los m elementos de T se compara con los n elementos de S,
por lo que su tiempo de ejecucion ser a O(nm).
Operaciones Basicas con Listas Ligadas Ordenadas
Union. Realizar las operaciones b asicas de conjuntos con listas previamen-
te ordenadas resulta m as econ omico que con listas en desorden. Nuevamente
se toma el caso de la uni on entre los conjuntos S y T. La principal ventaja de
utilizar es la de reducir el n umero de comparaciones pues estas se realizan en-
tre cabeceras de los conjuntos, el procedimiento es similar a un ordenamiento
por mezcla (merge sort).
Algoritmo 12 Funcion auxiliar ensambla
Entrada: elemento,lista
1
,lista
2
1: lista
nueva
= nueva (lista)
2: lista
nueva
elemento = elemento
3: lista
nueva
siguiente = union(lista
1
, lista
2
)
4: devolver lista
nueva
El Algoritmo 13 depende de una funci on auxiliar (Algoritmo 12) que va
creando y ligando los elementos de la lista que representa a la uni on de
72 CAP

Algoritmo 13 Uni on Listas Ordenadas
Entrada: lista
1
,lista
2
1: si lista
1
== null y lista
2
== null entonces
2: devolver null
3: si no, si lista
1
== null entonces
4: devolver ensambla(lista
2
element, null , lista
2
siguiente)
5: si no, si lista
2
== null entonces
1
element, lista
1
siguiente , null )
7: si no, si lista
1
elemento == lista
2
elemento entonces
1
element, lista
1
siguiente, lista
2
siguiente)
9: si no, si lista
1
elemento < lista
2
elemento entonces
1
element, lista
1
siguiente, lista
2
)
11: si no
2
element, lista
1
, lista
2
siguiente)
13: n si
los conjuntos, ademas las funciones son mutuamente recursivas (porque una
llama a la otra). En el Algoritmo 13 se presentan las siguientes condiciones:
1. Cuando las listas est an vacas (lneas 1 y 2) se terminan las llamadas
recursivas porque no hay mas elementos a procesar.
2. Si una lista est a vaca y la otra no (lneas 3, 4, 5 y 6) se contin ua
copiando la lista con elementos
3. Cuando el elemento inicial en ambas listas es igual (8 y 9), se copia al
conjunto nuevo y se siguen procesando los elementos restantes.
4. Los ultimos casos son similares, cuando el elemento inicial de una lista
es menor al de la otra, se agrega el elemento al nuevo conjunto y se
procesando los siguientes elementos de su lista.
Con esto se aprovecha el hecho de que las listas esten ordenadas pues
se comparan las cabeceras y no cada elemento. El tiempo de ejecuci on es
O(n + m) porque la cabecera de cada conjunto se compara contra los ele-
mentos del otro.
Interseccion. El Algoritmo 14 denota el proceso de interseccion entre dos
listas ordenadas, utiliza la funcion ensambla (modicada) para crear la nueva
3.1. DEFINICIONES B

lista. En este caso solamente se realiza la inserci on en la nueva lista cuando se
presenta el caso donde el valor de la cabecera en ambas listas es igual (lneas
3 y 4).
Algoritmo 14 Intersecci on Listas Ordenadas
Entrada: lista
1
,lista
2
1: si lista
1
== null o lista
2
== null entonces
2: devolver null
3: si no, si lista
1
elemento == lista
2
elemento entonces
1
element, lista
1
siguiente, lista
2
siguiente)
5: si no, si lista
1
elemento < lista
2
elemento entonces
6: devolver interseccion(lista
1
siguiente, lista
2
)
7: si no
8: devolver interseccion(lista
1
, lista
2
siguiente)
9: n si
Diferencia. En el caso de la diferencia el Algoritmo 15 tiene las siguientes
consideraciones:
Cuando la primer lista (minuendo) est a vaca se termina la recursivi-
dad, pues todos los elementos posibles para el nuevo conjunto se han
examinado ya.
Cuando la segunda lista (sustraendo) ya se ha vaciado no queda mas
que insertar los elementos del minuendo al nuevo conjunto
Si la cabecera de la primer lista es igual a la cabecera de la segunda,
entonces se descarta el elemento.
Si la cabecera de la primer lista es menor a la de la segunda se inserta
el elemento del minuendo al nuevo conjunto y se avanza al siguiente
miembro de ese conjunto.
Cuando la cabecera del segundo conjunto es menor a la del primero, se
inserta el elemento del primer conjunto y se avanzan ambas listas.
74 CAP

Algoritmo 15 Diferencia Listas Ordenadas
Entrada: lista
1
,lista
2
1: si lista
1
== null entonces
2: devolver null
3: si no, si lista
2
== null entonces
1
elemento, lista
1
siguiente, lista
2
)
5: si no, si lista
1
elemento == lista
2
elemento entonces
6: devolver diferencia(lista
1
siguiente, lista
2
siguiente)
7: si no, si lista
1
elemento < lista
2
elemento entonces
1
elemento, lista
1
siguiente, lista
2
)
9: si no
1
elemento, lista
1
siguiente, lista
2
siguiente)
11: n si
Operaciones Basicas con Vectores Caractersticos
Cuando los conjuntos con los que se har an operaciones son todos subcon-
juntos de un conjunto nito y de cardinalidad peque na se puede hacer uso
de vectores de n umeros binarios.
Cuadro 3.1: Equivalencia Operaciones Vectores Caractersticos
Operaci on Equivalencia Ejemplo
Uni on OR 001100 OR 111001 = 111101
Intersecci on AND 001100 AND 111001 = 001000
Resta AND y NOT 001100 AND NOT(111001) = 000100
N otese que la representaci on de cada subconjunto tiene todos los elemen-
tos del conjunto universo y los elementos que pertenecen al subconjunto
est an encendidos (valor 1 o verdadero) y los que no son miembros estaran
apagados (valor 0 o falso). Esta es una forma eciente de representar con-
juntos en cuanto a velocidad, sin embargo, el tama no puede llegar a ser un
problema. El conjunto universo se representara en una estructura de datos
separada.
3.1. DEFINICIONES B

Representaci on con Tablas Hash
Una tabla hash es una estructura de datos que relaciona llaves y datos.
En la Figura 3.3 muestra la forma general de dicha estructura, existe una
funci on h (hash) que toma un elemento x y lo convierte en un valor entero
entre 0 y B 1; donde B es el n umero de llaves o cubetas que contiene la
tabla hash.
. . .
. . .
. . .
Llaves
0
1
h(x) x
h
B - 1
a
1
a
2
a
n
Figura 3.3: Tabla Hash
La funcion h indica a que llave corresponde el elemento evaluado, por
ejemplo, si se quieren asociar palabras por su letra inicial, entonces la funci on
h ser a:
Algoritmo 16 Funcion Hash Letra Inicial
Entrada: palabra
1: devolver numero( letraInicial(palabra) )
La funci on hash es, quiz a, la parte m as importante de la implementacion
de esta estructura de datos, por lo que se debe tener cuidado al dise narla. Lo
m as deseable es que cada llave tenga aproximadamente el mismo n umero de
elementos asociados a ella.
76 CAP

Insertar, Eliminar y Buscar Los Algoritmos 17, 18 y 19 esbozan las fun-
ciones insertar, eliminar y buscar para una tabla hash. En general se
obtiene la llave que corresponde a la entrada y posteriormente se realiza
la operacion como si la lista seleccionada fuese el conjunto completo.
Algoritmo 17 Funcion Inserta en Tabla Hash
Entrada: palabra
1: h = hash(palabra)
2: tabla[h]inserta(palabra)
Algoritmo 18 Funcion Eliminar de Tabla Hash
Entrada: palabra
2: devolver tabla[h]eliminar(palabra)
Algoritmo 19 Funcion Buscar en Tabla Hash
Entrada: palabra
2: devolver tabla[h]buscar(palabra)
3.1.4. Relaciones y Funciones
Hasta ahora se han utilizado elementos at omicos (indivisibles) como miem-
bros de los conjuntos, sin embargo, no siempre es una condici on ideal. Se
conocen como tuplas a las listas utilizadas como elementos de un conjunto
y al n umero de elementos por tupla se llama grado o aridad. Los conjuntos
que contienen tuplas de un mismo grado se denotan Relaciones, de acuerdo
al grado que tengan se llamaran unaria para grado uno, binaria para grado
dos, etc.
Producto Cartesiano El producto cartesiano de dos conjuntos se dene
como el conjunto de parejas donde el primer elemento se obtiene del
primer conjunto y el segundo elemento del segundo conjunto, es decir,
A B = {(a, b) | a A b B}
3.1. DEFINICIONES B

Relaciones Binarias
Una relacion binaria R es un subconjunto del producto cartesiano entre
dos conjuntos A y B. S R es un subconjunto de A B se dice que R es de
A a B. Se llama dominio de R al conjunto A y rango de R al conjunto B.
As pues
R = {(a, b) | a A b B P (a, b)}
donde el predicado P debe ser cierto para todos los elementos de la rela-
ci on R, notese que el tama no del conjunto R no es necesariamente el mismo
del producto cartesiano de A y B.
Funciones
Se conoce como funci on parcial a la relacion de A a B donde los elementos
del dominio se relacionan a lo mas con un elemento del rango. Una funcion
(total) f es la relacion entre el dominio A y el rango B cuando a cada elemento
de A le corresponde exactamente un elemento de B, y generalmente se denota
por f : A B o f(a) = b.
Representaci on de Funciones con Listas Ligadas
Dado que una funcion es un conjunto de pares, esta se puede representar
como una lista ligada. En general se denir an con tres valores: uno para el
valor del dominio, otro para el valor del rango y otro para apuntar al siguiente
elemento. Habr a que tener especial atenci on al insertar pues cada valor del
dominio estara relacionado exactamente con un valor del rango.
Algoritmo 20 Estructura de Celda Lista Ligada para Funciones
1: valorDominio
2: valorRango
3: siguiente
Representaci on de Funciones con Tablas Hash
Al igual que en las listas ligadas se pueden representar funciones con
tablas hash, lo importante ser a aplicar la funci on hash al valor del dominio y
78 CAP

se guarde en la lista ligada correspondiente tanto el valor del dominio como
el del rango.
Algoritmo 21 Inserta en Tabla Hash para Funciones
Entrada: elemento
1: h = hash(elemento valorDominio)
2: tabla[h]inserta(elemento)
3.2. Proyecto de Programacion
3.2.1.

Indices invertidos
Un ndice invertido (tambien conocido como listas de posteo) es una es-
tructura de datos que representa un ndice ordenado que mapea un archivo
por su contenido, como palabras, n umeros a una posici on en una base de da-
tos, o en un documento o conjunto de documentos. El proposito de un ndice
invertido es permitir la b usqueda en texto completo, esto agregando el costo
de procesamiento del (los) documentos para agregarlos a la base de datos. El
ndice invertido puede ser la misma base de datos. Los ndices invertidos son
ampliamente utilizados en sistemas de recuperacion de documentos.
Ejemplo
Dado el conjunto de textos A = {T
0
, T
1
, T
2
} donde T
0
=compro paco po-
cas copas T
1
=y como pocas copas compro, T
2
=pocas copas paco pago,
se obtiene el siguiente ndice invertido:
Palabra ocurrencias
compro 0,1
paco 0,2
pocas 0,1,2
copas 0,1,2
y 1
como 1
pago 2
3.2. PROYECTO DE PROGRAMACI
ON 79
La b usqueda de las palabra paco, pocas y pago regresara la los conjuntos
0,2 ,0,1,2 y 2. Si buscamos la frase pocas copas paco , puede observarse que
la frase aparece en los textos T
0
y T
2
, pero solo aparece en le orden el mismo
orden en T
2
.
3.2.2. Trabajo
.
Programaci on
Implementar una estructura de datos basada en tablas hash, la cu al debe
cumplir los siguientes requisitos.
1. Cada elemento de la tabla debe ser una tupla constituida por la palabra
y una lista de los ndices de los textos en los que ocurre la palabra.
2. Proponer un conjunto de documentos (noticias, poemas, manuales,
rese nas de pelculas, etc) y crear su archivo de ndice invertido (En
est a parte tendran que procesar los documentos para generar los ndi-
ces).
3. Implementar b usqueda utilizando intersecci on de conjuntos
4. Proporcionar una interfaz para hacer consultas
Reporte tecnico
Presentar un reporte tecnico de su trabajo el cu al debera incluir los si-
guientes apartados.
1. Portada
2. Introduccion. Descripci on breve de los ndices invertidos y del conjunto
de documentos.
3. Desarrollo. Describir la estructura de datos a utilizar, el procesamiento
de los documentos y la implementacion de la b usqueda.
4. Conclusiones. Utilidad de lo que se hizo. Como se puede mejorar?
80 CAP

Captulo 4
El modelo de datos de arboles
En muchas ocasiones la informacion tiene una estructura jerarquica o
anidada, como los arboles familiares o diagramas organizacionales. La es-
tructura que modela este tipo de informaci on se llama arbol y es uno de los
tipos m as utilizados en las ciencias computacionales.
4.1. Terminologa Basica
Los arboles son un conjunto de puntos y lneas, llamados nodos y ejes
respectivamente. Para formar un arbol se deben unir los nodos mediante
los ejes, un nodo padre puede conectarse con varios nodos hijos, la relaci on
inversa no est a permitida, es decir, un hijo no podra tener varios padres. Los
hijos de un mismo padre se conocen como hermanos.
R
N
1
N
2
N
3
N
4
N
5
Figura 4.1:

Arbol B asico
81
82 CAP
ITULO 4. EL MODELO DE DATOS DE

ARBOLES
Existe un nodo especial que no tiene padre alguno, a este nodo se le
conoce como nodo raz, se denota R en la Figura 4.1. Los nodos N
3
, N
4
y N
5
son conocidos como hojas ya que no tienen hijos. La estructura que guarda
el arbol permite que desde cualquier nodo se puede llegar a la raz.
4.1.1. Denici on Recursiva
Es posible determinar un arbol mediante una denici on inductiva que
construye arboles grandes a partir de peque nos.
Base Sea n la raz de un arbol con un unico nodo.
Induccion Sea r un nodo nuevo y T
1
, T
2
, . . . , T
n
arboles con races c
1
, c
2
, . . . , c
n
respectivamente. Se requiere que ning un nodo se repita en los arboles
T
i
, dado que r es un nodo nuevo, tampoco estara en alguno de los
arboles existentes. Se formara un nuevo arbol de la siguiente manera:
a) Sea r la raz del arbol T.
b) Agregar ejes que conecten cada uno de los nodos c
1
, c
2
, . . . , c
n
a r,
con lo que se hace a r la raz de cada T
i
.
4.1.2. Rutas, Antecesores y Descendientes
Las relaciones antecesor y descendiente son una extensi on de la relaci on
padre-hijo, los antecesores de un nodo pueden encontrarse siguiendo la re-
laci on de un nodo a su padre, y este a su padre, y este ultimo a su padre y
as sucesivamente. La relaci on descendiente es la inversa de la de antecesor.
Supongase que m
1
, m
2
, . . . , m
k
son una secuencia de nodos donde el nodo
m
i
es padre del nodo m
i+1
, se conoce a esta secuencia como la ruta de m
1
a
m
k
y tiene una longitud de k 1.
Si m
1
, m
2
, . . . , m
k
es una ruta de un arbol, entonces m
1
es un antecesor
propio de m
k
, similarmente m
k
es un descendiente propio de m
1
. Cuando la
longitud de la ruta es cero, el nodo es antecesor y descendiente de s mismo,
m as no un descendiente o antecesor propio. La raz es el antecesor de todos
los nodos en el arbol y cada uno de estos nodos ser a su descendiente.
4.1. TERMINOLOG
IA B
ASICA 83
4.1.3. Sub-arboles
En un arbol T un nodo n con todos sus descendientes propios, si es que
existen, se llama un sub-arbol de T.
4.1.4. Altura y Profundidad
En un arbol, la altura de un nodo n es la longitud del camino m as largo
desde el nodo n hasta una hoja; la altura del arbol es la altura del nodo raz.
La profundidad de un nodo n es la distancia entre la raz hasta n.
4.1.5.

Arboler Ordenados
Los nodos de un arbol pueden estar ordenados. Si m y n son hermanos
y m est a a la izquierda de n, entonces todos los descendientes de m estar an
a la izquierda de los descendientes de n. Para encontrar la relaci on de a la
izquierda entre cualesquiera nodos x y y, se debe seguir la ruta hasta un
antecesor com un y de ah conocer el orden.
z
m
n
x
y
Figura 4.2: Relaci on a la izquierda
4.1.6.

Arboles Etiquetados
Un arbol etiquetado es aquel que asocia una etiqueta o valor a cada uno
de sus nodos, puede ser algo simple como un n umero o caracter, o complejo
84 CAP

ARBOLES
como el texto completo de un documento. La etiqueta de un nodo puede ser
modicada, no as su nombre. Si el nombre de un nodo no es importante, el
nodo puede ser representado por su etiqueta; sin embargo, es posible repetir
etiquetas, en estos casos es conveniente representar cada nodo tanto por su
etiqueta como por su nombre.
4.1.7.

Arboles de Expresiones
Las expresiones aritmeticas pueden ser representadas mediante arboles
etiquetados, de hecho, un arbol de expresion especica la asociaci on entre
operadores y operandos en una forma consistente. Se puede denir un arbol
de expresiones como sigue:
Base Un operando atomico es una expresi on y el arbol que la representa
es un nodo cuya etiqueta es el mismo operando.
Inducci on Sean E
1
y E
2
expresiones representadas por los arboles T
1
y T
2
,
respectivamente. Entonces la expresion (E
1
+ E
2
) se representara con
un arbol cuya raz ser a un nodo con etiqueta + con hijos T
1
y T
2
,
como se ve en la gura 4.3. De forma similar las expresiones (E
1
+ E
2
),
(E
1
+ E
2
) y (E
1
+ E
2
), es decir, se denir an por un arbol cuya raz es
un nodo con el respectivo operador como etiqueta. Cuando se trata del
operador unario se procede de forma similar creando un nuevo arbol
con un nodo etiquetado con el operador como raz y conectado a la raz
del arbol que representa al operando.
+
T
1
T
2
Figura 4.3: (E
1
+ E
2
)
4.2. ESTRUCTURAS DE DATOS PARA

ARBOLES 85
4.2. Estructuras de Datos para

Arboles
Existen distintas formas de representar arboles en una estructura de da-
tos, esto dependera, mayormente, de las necesidades del programa. Por ejem-
plo, si solo se requiere conocer el padre del nodo (recorrer hacia arriba):
Algoritmo 22 Estructura - solo padre
Entrada: padre, etiqueta
1: nodo etiqueta = etiqueta
2: nodo padre = padre
3: devolver nodo
Si lo que se necesita es conocer a los hijos (recorrer hacia abajo), la ventaja
de la estructura 23 es acceder a los hijos en un tiempo constante O(1) pero el
costo de memoria es elevado cuando algunos nodos tienen pocos hijos, pues
la mayora de los espacios para hijos tienen un valor nulo.
Algoritmo 23 Estructura - solo hijos
Entrada: etiqueta
1: nodo etiqueta = etiqueta
2: nodo hijos = nodos[ numeroHijos ]
3: devolver nodo
4.2.1. Representaci on mas a la izquierda-hermano a la
derecha
Para eliminar el costo de memoria al utilizar arreglos para guardar los
hijos de un nodo, se pueden utilizar listas ligadas con un costo en tiempo al
acceder a los hijos de O(i). Cada nodo apuntara a su hijo mas a la izquierda
y a su m as pr oximo hermano a la derecha (Algoritmo 24). Para encontrar
hijos diferentes al de la izquierda se recorrer a la lista hacia mediante las ligas
a los hermanos a la derecha.
4.2.2. Apuntador hacia el Padre
En ocasiones es util incluir en la estructura de cada nodo un apuntador
hacia el padre, dado que el nodo raz no tiene padre, el apuntador sera nu-
86 CAP

ARBOLES
Algoritmo 24 Estructura - m as a la izquierda-hermano a la derecha
1: nodo etiqueta
2: nodo hijoMasIzquierda
3: nodo hermanoDerecha
4: devolver nodo
lo. Por ejemplo pudieran guardarse palabras y deletrearla (a la inversa)
siguiendo la ruta desde una hoja hasta el nodo raz. Para saber cuando se ha
llegado a la raz habr a que evaluar si el apuntador al padre es nulo.
Algoritmo 25 Estructura - apuntador al padre
1: nodo etiqueta
2: nodo hijos
3: nodo padre
4: devolver nodo
4.3. Recursi on en

Arboles
Una de las funciones m as utilizadas de los arboles es la facilidad de escribir
funciones recursivas de manera limpia. La gura 4.4 representa a un arbol
con raz n y sub-arboles T
1
, T
2
, . . . T
n
que a su vez tienen races c
1
, c
2
, . . . c
n
.
n
c
1
c
1
c
n
T
1
T
n
T
2
...
Figura 4.4:

Arbol ejemplo para funciones recursivas
Sea F una funci on recursiva que toma como par ametro un nodo n, la
funci on ejecutara ciertos pasos (quiz a ninguno) y posteriormente har a una
llamada recursiva con el nodo c
1
, luego har a otros pasos, despues se ejecuta
4.3. RECURSI
ON EN

ARBOLES 87
nuevamente la funci on para el nodo c
2
y as sucesivamente. Un ejemplo se
puede ver en el algoritmo 26.
Algoritmo 26 Recursividad en arboles - F(n)
Entrada: nodo n
1: pasos
1
2: F(c
1
)
3: pasos
2
4: F(c
2
)
5:
.
.
.
6: pasos
n
7: F(c
n
)
8: devolver informaci on
Evaluaci on de un arbol de expresiones
Existen distintas maneras de recorrer un arbol, lo que da como resultado
expresiones diferentes. Una de las formas de evaluar se llama evaluacion en
preorden, lo que se hace es realizar las operaciones relacionadas al nodo actual
primero y despues hacer una llamada recursiva con los nodos hermanos como
par ametro. A diferencia de la ejecuci on en preorden, la evaluacion en posjo
primero hace la llamada recursiva con los hermanos para despues realizar
las operaciones concernientes al nodo actual. A continuaci on se presenta la
prueba inductiva de la evaluacion de un arbol.
Base Una hoja produce un valor, que es el valor del nodo y representa al
sub- arbol del mismo.
Inducci on Suponga que se desea calcular el valor de la expresi on repre-
sentada por el sub-arbol con raz n. Se evaluaran las sub-expresiones
representadas por los sub- arboles cuyas races son los hijos c
1
y c
2
de
n. Los valores obtenidos son los operandos para el operador localizado
en el nodo n. Finalmente se aplica el operador a los operandos para
producir el valor de n.
88 CAP

ARBOLES
Evaluaci on en Preorden y Postorden
Para entender mejor los tipos evaluaci on se seguir an los Algoritmos 27 y
28 sobre el arbol representado por la Figura 4.5. La evaluaci on hecha al nodo
ser a simplemente imprimir el valor de la etiqueta del nodo.
+
a
*
_
d
b c
Figura 4.5:

Arbol ejemplo evaluacion preorden y postorden - a+(b-c)*d
Algoritmo 27 Evaluacion en Preorden - F(n)
Entrada: nodo n
1: evaluacion(n)
2: hijo = n hijoMasIzquierda
3: mientras hijo no sea nulo hacer
4: F(hijo)
5: hijo = hijo hermanoDerecha
6: n mientras
La evaluaci on en preorden, como se ve en la tabla 4.1, da como resultado
la expresion +a*-bcd.
En esta ocasi on (tabla 4.2) siendo evaluaci on en postorden se genera la
expresi on abc-d*+.
4.3. RECURSI
ON EN

ARBOLES 89
Cuadro 4.1: Evaluaci on en Preorden
No. Resultado Operaci on No. Resultado Operaci on
1 preorden(+) 9 preorden(b)
2 + imprimir(+) 10 b imprimir(b)
3 preorden(a) 11 preorden(c)
4 a imprimir(a) 12 c imprimir(c)
5 preorden(*) 13 preorden(d)
6 * imprimir(*) 14 d imprimir(d)
7 preorden(-)
8 - imprimir(-)
Algoritmo 28 Evaluacion en Postorden - F(n)
Entrada: nodo n
1: hijo = n hijoMasIzquierda
2: mientras hijo no sea nulo hacer
3: F(hijo)
4: hijo = hijo hermanoDerecha
5: n mientras
6: evaluacion(n)
Cuadro 4.2: Evaluaci on en postorden
No. Resultado Operaci on No. Resultado Operaci on
1 posjo(+) 9 c imprimir(c)
2 posjo(a) 10 - imprimir(-)
3 a imprimir(a) 11 posjo(d)
4 posjo(*) 12 d imprimir(d)
5 posjo(-) 13 * imprimir(*)
6 posjo(b) 14 + imprimir(+)
7 b imprimir(b)
8 posjo(c)
90 CAP

ARBOLES
Es importante hacer notar que ambas expresiones son equivalentes ya que
son evaluadas en diferente orden.
4.4.

Arboles Binarios
Anteriormente se estudiaron arboles con n-cantidad de hijos, existe una
clase especial de arboles que solo tiene un par de espacios para alojar hijos.
A este tipo de arboles se les conoce como arboles binarios. Llamaremos a sus
hijos como izquierdo y derecho, y cualquiera puede ser nulo. La denicion
recursiva para arboles binarios es la siguiente:
Base El arbol vaco (sin nodos) es un arbol binario.
Inducci on Sea r un nodo y T
1
y T
2
arboles binarios, existe un arbol binario
con r como raz, con sub- arbol izquierdo T
1
y sub-arbol derecho T
2
. La
raz del sub- arbol T
1
es el hijo izquierdo de r, a menos que T
1
este vaco,
en cuyo caso r no tendr a hijo izquierdo. De manera similar el nodo raz
del sub-arbol T
2
es el hijo derecho de r, a menos que T
2
este vaco, en
cuyo caso r no tendra hijo derecho.
Es importante notar que los arboles binarios tienen sus hijos ordenados
(por izquierdo y derecho), lo que no necesariamente es cierto para los arboles
comunes.
4.4.1. Estructuras de Datos para

Arboles Binarios
La forma natural de representar un arbol binario ser a mediante nodos
que contengan apuntadores hacia los hijos izquierdo y derecho, como se ve
en el algoritmo 29.
Algoritmo 29 Estructura Nodo

Arbol Binario
1: etiqueta
2: padre
3: hijoIzquierdo
4: hijoDerecho
4.5.

ARBOLES DE B
USQUEDA BINARIOS 91
4.4.2. Recursion sobre

Arboles Binarios
Debido a que los apuntadores a hijos de un nodo en un arbol binario
tienen cierto orden, el recorrido del arbol
Algoritmo 30 Recursi on

Arbol Binario
Entrada: nodo
1:
.
.
.
2: recursion(hijoIzquierdo)
3:
.
.
.
4: recursion(hijoDerecho)
5:
.
.
.
4.4.3. Recurridos en Orden
En los arboles binarios, ademas de los recorridos en preorden y postorden,
se tiene un recorrido llamado en orden. En este tipo de recorridos se eval ua el
nodo actual despues de hacer la llamada recursiva al hijo izquierdo, pero antes
de llamar al hijo derecho. Recorriendo de esta manera el arbol se obtiene una
expresi on muy cercana a la expresi on en injo, para la Figura 4.5 se obtiene
a+b-c*d a la cual solo le hace falta un par de parentesis a+(b-c)*d.
Algoritmo 31 Evaluacion en Orden - F(n)
Entrada: nodo n
1: F(n hijoIzquierda)
2: evaluacion(n)
3: F(n hijoDerecha)
4.5.

Arboles de B usqueda Binarios
En m ultiples programas de c omputo se desea tener la posibilidad de
insertar, borrar y buscar elementos de un conjunto. En un vericador de or-
tografa se deseara insertar nuevas palabras o acr onimos como U.M.N.S.H.;
eliminar palabras en desuso o mal escritas por el usuario, o bien buscar si
92 CAP

ARBOLES
una palabra existe y si est a bien escrita. Se conoce como diccionario a un
conjunto de datos al que se le puede insertar, borrar y buscar elementos.
Una buena forma de implementar diccionarios es mediante arboles de
b usqueda binarios. Las etiquetas deberan poder guardar una relaci on de me-
nor que, como los n umeros enteros, reales u el orden lexicogr aco.
Un arbol de b usqueda binario cumple con los siguientes requisitos para
cada nodo x:
Los nodos a la izquierda de x tienen etiquetas con valores menores a la
del nodo x.
Los nodos a la derecha de x tienen etiquetas con valores mayores a la
del nodo x.
4.5.1. Implementaci on de

Arboles de B usqueda Bina-
rios
Para la implementaci on se utilizara la estructura descrita en el algoritmo
29, la implementaci on de las operaciones requeridas para el diccionario se
detallar an a continuacion.
Algoritmo 32 Inserta en arbol binario
Entrada: dato, nodo
1: si nodo es nulo entonces
2: nodo = nuevoNodo(dato, izquierdo=nulo, derecho=nulo)
3: si no, si dato es menor a nodo entonces
4: nodo izquierda = inserta(dato, nodo izquierda)
5: si no
6: nodo derecha = inserta(dato, nodo derecha)
7: n si
8: devolver nodo
4.5.

ARBOLES DE B
USQUEDA BINARIOS 93
Algoritmo 33 Buscar en arbol binario
Entrada: dato, nodo
2: devolver nulo
3: n si
4: si dato es igual a nodo entonces
5: devolver nodo
6: n si
7: si dato es menor a nodo entonces
8: buscar(dato, nodo izquierda)
9: si no
10: buscar(dato, nodo derecha)
11: n si
Algoritmo 34 Eliminar en arbol binario
Entrada: dato, nodo
2: si dato es menor a nodo entonces
3: eliminar(dato, nodo izquierda)
4: si no, si dato es mayor a nodo entonces
5: eliminar(dato, nodo derecha)
6: si no
7: si nodo izquierda es nulo entonces
8: nodo = nodo derecha
9: si no, si nodo derecha es nulo entonces
10: nodo = nodo izquierda
11: si no
12: nodo etiqueta = minimo( nodo derecha )
13: eliminaMinimo( nodo derecha )
14: n si
15: n si
16: n si
17:
94 CAP

ARBOLES
4.6. Colas de Prioridad y

Arboles Parcial-
mente Ordenados
4.6.1. Colas de Prioridad
Una cola de prioridad es un conjunto cuyos elementos tienen un valor
de prioridad asociado, por ejemplo, los procesos en el sistema operativo. Las
operaciones que requiere el conjunto son:
1. Insertar un elemento al conjunto.
2. Encontrar y eliminar el elemento con mayor prioridad en el conjunto.
4.6.2.

Arboles Parcialmente Ordenados (POT)
Una forma eciente de implementar las colas de prioridad es mediante los
llamados arboles parcialmente ordenados (POT por sus siglas en ingles), el
cual debera cumplir las siguientes condiciones:
1. Las etiquetas de los nodos son estructuras con un valor de prioridad.
2. El elemento guardado en un nodo tiene una prioridad por lo menos tan
alta como la de sus hijos.
La segunda condici on implica que el nodo raz ser a siempre el elemento
con mayor prioridad; los hijos de cualquier nodo no necesariamente estar an
ordenados horizontalmente, es decir, el hijo izquierdo puede ser mayor al
derecho y viceversa.
Para insertar un elemento se buscar a la posici on m as a la izquierda po-
sible en el arbol para introducir el nuevo nodo, dado que es muy probable
que la segunda condici on se vea violada se empujar a el nodo hacia arriba.
Empujar se reere a intercambiar valores entre padre e hijo cumpliendo la
segunda condicionante.
Siempre se eliminara el nodo raz, para llevar esto a cabo se remplaza su
contenido con el del nodo m as a la derecha del ultimo nivel. Al igual que en la
inserci on seguramente se violar a la segunda condici on, as que se empujar a
haca abajo el nuevo nodo raz.
4.6. COLAS DE PRIORIDADY

ARBOLES PARCIALMENTE ORDENADOS95
4.6.3. POTs Balanceados y Montculos (Heaps)
Se dice que un POT esta completo si todos los niveles, excepto el ultimo,
tienen sus hijos completos; el arbol estara balanceado si esta completo y sus
hojas estan lo mas a la izquierda posible. Un arbol parcialmente ordenado se
puede implementar mediante una estructura de datos basada en un arreglo
llamada montculo o heap.
Un heap es un arreglo A con una interpretaci on particular de sus indices,
se comienza desde A[1] que sera la raz (A[0] no se utiliza). El siguiente nivel
de nodos utilizar a dos espacios en el arreglo, el siguiente 4 y as sucesivamen-
te. En cada nivel los nodos estaran ordenados de izquierda a derecha, por
ejemplo el hijo izquierdo de la raz sera A[2] y el derecho A[3]. En general,
el hijo izquierdo del nodo A[i] ser a A[2i] y el derecho A[2i + 1]. El padre de
un elemento A[i] sera A
i
2
A
0
A
1
A
2
A
3
A
4
A
5
A
6
A
7
. . .
R
a
z
N
i
v
e
l

1
N
i
v
e
l

2
Figura 4.6: Heap B asico
Para insertar un elemento en el heap, se hace un procedimiento similar
al de inserci on en el POT, pero la implementaci on con un arreglo ayuda a
acceder directamente al elemento mas a la izquierda posible utilizando un
contador de elementos insertados (algoritmo 35).
Algoritmo 35 Inserta en heap
Entrada: arreglo, dato, contador
1: contador = contador + 1
2: arreglo [contador] = dato
3: empujaHaciaArriba(arreglo, contador)
Eliminar es un procedimiento similar al descrito en el apartado de los
arboles parcialmente ordenados (algoritmo 36).
96 CAP

ARBOLES
Algoritmo 36 Eliminar de heap
Entrada: arreglo, dato, contador
1: arreglo [raiz] = arreglo [contador]
2: contador = contador 1
3: empujaHaciaAbajo(arreglo, raiz, contador)
4.7. Heapsort
A continuaci on se describe el algoritmo de ordenamiento conocido como
heapsort, el cual consiste de dos fases: en la primera se convierte el arreglo
a un heap (fase tambien llamada heapify), posteriormente se mueven los
elementos m as grandes del heap al nal del arreglo hasta llegar a tener el
m as peque no al inicio.
Arreglo Ordenado Heap en Iteracin i
i 1 n
Figura 4.7: Heapsort B asico
Algoritmo 37 Fase 2 de heapsort
Entrada: heap
1: para i desde n hasta 1 hacer
2: intercambia(heap [raiz] , heap [n])
3: empujaHaciaAbajo(heap, raiz, i)
4: n para
Para realizar el ordenamiento habr a que repetir n veces el algoritmo 37,
se puede demostrar que es un algoritmo de orden O(log n). La primer fase
del heapsort (lnea 1 del algoritmo 38) toma un tiempo O(log n), por lo que
el heapsort ser a O(nlog n).
4.8. EJERCICIOS 97
Algoritmo 38 Heapsort
Entrada: datos
1: heap = heapify(datos)
2: para i desde n hasta 1 hacer
3: intercambia(heap [raiz] , heap [n])
4: empujaHaciaAbajo(heap, raiz, i)
5: n para
4.8. Ejercicios
1. Dibuje el arbol binario resultante de insertar la siguiente secuencia 3 2
7 4 9 1 5.
2. Dibuje abol resultante de aplicar dos rotaciones izquierdas sobre el nodo
(ver gura 2) con etiqueta J (dibuje los arboles intermedios).
!
"
#
$
%
&
3. Dibuje abol resultante de aplicar una rotaci on derecha y dos izquierdas
sobre el nodo con etiqueta J (ver gura 2) .
4. Proporcione un algoritmo que dada la raz de un arbol, regrese el n ume-
ro de nodos que hay en el arbol.
5. Proporcione un algoritmo para realizar una doble rotacion izquierda
sobre un nodo.
6. Proporciones un algoritmo para realizar una doble rotacion derecha
sobre un nodo.
7. Dise ne un algoritmo para realizar la union de dos arboles binarios.
8. Dado las siguientes cadenas AYXBZJ y AYJBZX que representan el
recorrido enroden y postorden respectivamente de un arbol binario,
dibujar el arbol binario. Como obtendra el recorrido preorden sin
necesidad de dibujar el arbol?
98 CAP

ARBOLES
9. Proporcione un algoritmo para obtener el recorrido en preorden de un
arbol binario a partir de los recorridos enroden y postorden.
10. Dibuje los estados del heap que seguira el metodo heapsort para la
siguiente secuencia 3 2 7 4 9 1 5.
11. De manera similar a como en clases denimos un Heap, se puede denir
un Min-Heap invirtiendo la propiedad de heap, es decir, haciendo que
un Min-Heap cumpla con que el valor del padre es siempre menor que
el de sus hijos. Implemente un Min-Heap y escriba los metodos de
inserci on y borrado. Finalmente implemente un heapsort que regrese
un arreglo ordenado en forma descendente
Captulo 5
Teora y algoritmos de grafos
99

Notas

Cargado por

Copyright:

Formatos disponibles

Notas

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Notas

Cargado por

Copyright:

Formatos disponibles

Apuntes de Estructuras de Datos

Facultad de Ingeniera Electrica

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 1. MODELO DE DATOS, ITERACI

ITULO 2. EL MODELO DE DATOS DE LISTAS

ASICAS CON LISTAS 45

ITULO 2. EL MODELO DE DATOS DE LISTAS

ASICAS CON LISTAS 47

ITULO 2. EL MODELO DE DATOS DE LISTAS

ASICAS CON LISTAS 49

ITULO 2. EL MODELO DE DATOS DE LISTAS

ASICAS CON LISTAS 51

ITULO 2. EL MODELO DE DATOS DE LISTAS

ASICAS CON LISTAS 53

ITULO 2. EL MODELO DE DATOS DE LISTAS

ON DEL MODELO DE PILAS 55

ITULO 2. EL MODELO DE DATOS DE LISTAS

ON DEL MODELO DE COLAS 57

ITULO 2. EL MODELO DE DATOS DE LISTAS

ON DEL MODELO DE COLAS 59

ITULO 2. EL MODELO DE DATOS DE LISTAS

ON DEL MODELO DE COLAS 61

ITULO 2. EL MODELO DE DATOS DE LISTAS

ON DEL MODELO DE COLAS 63

ITULO 2. EL MODELO DE DATOS DE LISTAS

ITULO 2. EL MODELO DE DATOS DE LISTAS

ITULO 3. EL MODELO DE CONJUNTO DE DATOS

ASICAS YPRINCIPALES OPERACIONES CONCONJUNTOS69

ITULO 3. EL MODELO DE CONJUNTO DE DATOS

ASICAS YPRINCIPALES OPERACIONES CONCONJUNTOS71

ITULO 3. EL MODELO DE CONJUNTO DE DATOS

ASICAS YPRINCIPALES OPERACIONES CONCONJUNTOS73

ITULO 3. EL MODELO DE CONJUNTO DE DATOS

ASICAS YPRINCIPALES OPERACIONES CONCONJUNTOS75

ITULO 3. EL MODELO DE CONJUNTO DE DATOS

ASICAS YPRINCIPALES OPERACIONES CONCONJUNTOS77

ITULO 3. EL MODELO DE CONJUNTO DE DATOS

ITULO 3. EL MODELO DE CONJUNTO DE DATOS

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE

ITULO 4. EL MODELO DE DATOS DE