• Author / Uploaded
• Ser Marinn

Citation preview

Apuntes de Estructuras de Datos Facultad de Ingenier´ıa El´ectrica Jos´e Ortiz Bejar [email protected]

Garibaldi Pineda Garc´ıa [email protected]

2

´Indice general 1. Modelo de datos, Iteraci´ on y Recursi´ on 1.1. Programaci´on Iterativa . . . . . . . . . . . . . . . . . . 1.1.1. Iteraci´on mediante FOR . . . . . . . . . . . . . 1.1.2. Iteraci´on WHILE . . . . . . . . . . . . . . . . . 1.1.3. Iteraci´on DO WHILE . . . . . . . . . . . . . . . 1.1.4. Como elegir que estructura de iteraci´on utilizar 1.2. Pruebas inductivas . . . . . . . . . . . . . . . . . . . . 1.2.1. Ejemplo 1 . . . . . . . . . . . . . . . . . . . . . 1.2.2. Ejemplo 2: Suma geom´etrica . . . . . . . . . . . 1.2.3. Ejemplo 3 . . . . . . . . . . . . . . . . . . . . . 1.3. Definiciones y funciones Recursivas . . . . . . . . . . . 1.3.1. El factorial . . . . . . . . . . . . . . . . . . . . 1.3.2. M´aximo com´ un divisor . . . . . . . . . . . . . . 1.3.3. Caminata Rob´otica . . . . . . . . . . . . . . . . 1.3.4. Torres de Hanoi . . . . . . . . . . . . . . . . . . 1.4. Algoritmos de ordenamiento . . . . . . . . . . . . . . . 1.4.1. conceptos preliminares . . . . . . . . . . . . . . 1.4.2. Ordenamiento de Burbuja (BubbleSort) . . . . 1.4.3. Ordenamiento de por mezcla (MergeSort) . . . 1.4.4. Ordenamiento r´apido (QuickSort) . . . . . . . . 1.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . 2. El modelo de datos de listas 2.1. Introducci´on . . . . . . . . . . . . . . . . . . 2.2. Implementaci´on del modelo de Listas ligadas 2.3. Operaciones b´asicas con Listas . . . . . . . . 2.3.1. Inserci´on de nodos . . . . . . . . . . 2.3.2. Borrado de nodos . . . . . . . . . . . 3

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . . . . . . . . . . . . . . . . .

13 13 13 14 15 15 16 19 20 21 21 21 24 25 27 31 31 32 34 36 40

. . . . .

43 43 43 45 45 48

4

´INDICE GENERAL 2.3.3. B´ usqueda e Impresi´on . . . . . . . . . 2.3.4. Algoritmos de Ordenamiento utilizando 2.4. Implementaci´on del modelo de Pilas . . . . . . 2.4.1. Conversi´on de notaci´on infija a posfija 2.5. Implementaci´on del modelo de Colas . . . . . 2.5.1. Programaci´on Din´amica . . . . . . . . 2.5.2. top-down . . . . . . . . . . . . . . . . 2.6. Ejercicios . . . . . . . . . . . . . . . . . . . .

. . . . listas . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

50 51 54 55 56 57 60 65

3. El modelo de conjunto de datos 3.1. Definiciones B´asicas y Principales Operaciones con Conjuntos 3.1.1. Definiciones B´asicas . . . . . . . . . . . . . . . . . . . . 3.1.2. Operaciones con Conjuntos . . . . . . . . . . . . . . . 3.1.3. Implementaci´on de Conjuntos Utilizando Listas . . . . 3.1.4. Relaciones y Funciones . . . . . . . . . . . . . . . . . . 3.2. Proyecto de Programaci´on . . . . . . . . . . . . . . . . . . . . 3.2.1. ´Indices invertidos . . . . . . . . . . . . . . . . . . . . . 3.2.2. Trabajo . . . . . . . . . . . . . . . . . . . . . . . . . .

67 67 67 69 71 76 78 78 79

4. El modelo de datos de ´ arboles 4.1. Terminolog´ıa B´asica . . . . . . . . . . . . . . . . . . . . . . . 4.1.1. Definici´on Recursiva . . . . . . . . . . . . . . . . . . . 4.1.2. Rutas, Antecesores y Descendientes . . . . . . . . . . . 4.1.3. Sub-´arboles . . . . . . . . . . . . . . . . . . . . . . . . 4.1.4. Altura y Profundidad . . . . . . . . . . . . . . . . . . . ´ 4.1.5. Arboler Ordenados . . . . . . . . . . . . . . . . . . . . ´ 4.1.6. Arboles Etiquetados . . . . . . . . . . . . . . . . . . . ´ 4.1.7. Arboles de Expresiones . . . . . . . . . . . . . . . . . . ´ 4.2. Estructuras de Datos para Arboles . . . . . . . . . . . . . . . 4.2.1. Representaci´on m´as a la izquierda-hermano a la derecha 4.2.2. Apuntador hacia el Padre . . . . . . . . . . . . . . . . ´ 4.3. Recursi´on en Arboles . . . . . . . . . . . . . . . . . . . . . . . ´ 4.4. Arboles Binarios . . . . . . . . . . . . . . . . . . . . . . . . . ´ 4.4.1. Estructuras de Datos para Arboles Binarios . . . . . . ´ 4.4.2. Recursi´on sobre Arboles Binarios . . . . . . . . . . . . 4.4.3. Recurridos en Orden . . . . . . . . . . . . . . . . . . . ´ 4.5. Arboles de B´ usqueda Binarios . . . . . . . . . . . . . . . . . . ´ 4.5.1. Implementaci´on de Arboles de B´ usqueda Binarios . . .

81 81 82 82 83 83 83 83 84 85 85 85 86 90 90 91 91 91 92

´INDICE GENERAL ´ 4.6. Colas de Prioridad y Arboles Parcialmente Ordenados 4.6.1. Colas de Prioridad . . . . . . . . . . . . . . . ´ 4.6.2. Arboles Parcialmente Ordenados (POT) . . . 4.6.3. POTs Balanceados y Mont´ıculos (Heaps) . . . 4.7. Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . 4.8. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . 5. Teor´ıa y algoritmos de grafos

5 . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

94 94 94 95 96 97 99

6

´INDICE GENERAL

´Indice de cuadros 1.1. Descomposici´on del problema del factorial . . . . . . . . . . . 22 1.2. Combinaci´on 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 Caracter´ısticos . . . . . . . 74 4.1. Evaluaci´on en Preorden . . . . . . . . . . . . . . . . . . . . . . 89 4.2. Evaluaci´on en postorden . . . . . . . . . . . . . . . . . . . . . 89

7

8

´INDICE DE CUADROS

´Indice de figuras 1.1. 1.2. 1.3. 1.4.

Cubos numerados sobre una mesa . . . . . . . . . . . . . . . 16 Secuencia de movimientos parar 3 discos . . . . . . . . . . . . 28 Descomposici´on del algoritmo de ordenamiento por mezcla . . 35 Parte de mezclado del algoritmo de ordenamiento por mezcla 35

2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 2.8.

Variable de referencia a un objeto Representaci´on de una lista ligada Inserci´on al principio de una lista Inserci´on al final de una lista . . . Borrar al principiol de una lista . Borrar al final de una lista . . . . Proceso de divisi´on de una lista . Subsecunecia com´ un m´as larga . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

44 44 46 47 48 49 52 59

3.1. Operaciones con conjuntos . . . . . . . . . . . . . . . . . . . 69 3.2. Diagrama de Venn . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3. Tabla Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7.

´ Arbol B´asico . . . . . . . . . . . . . . . . . . . . . . . . . . . Relaci´on a la izquierda . . . . . . . . . . . . . . . . . . . . . (E1 + E2 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ Arbol ejemplo para funciones recursivas . . . . . . . . . . . . ´ Arbol ejemplo evaluaci´on preorden y postorden - a+(b-c)*d Heap B´asico . . . . . . . . . . . . . . . . . . . . . . . . . . . Heapsort B´asico . . . . . . . . . . . . . . . . . . . . . . . . .

9

. . . . . . .

81 83 84 86 88 95 96

10

´INDICE DE FIGURAS

Lista de algoritmos 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27.

C´alculo de n factorial . . . . . . . . . . . . . . . . . . . . . C´alculo recursivo del m´aximo com´ un divisor . . . . . . . . . Caminata de un robot . . . . . . . . . . . . . . . . . . . . . Secuencia de movimientos para el juego de Torres de Hanoi Ordenamiento de burbuja . . . . . . . . . . . . . . . . . . . Ordenamiento de mezcla . . . . . . . . . . . . . . . . . . . . Funci´on de mezcla de sublistas . . . . . . . . . . . . . . . . . Ordenamiento r´apido . . . . . . . . . . . . . . . . . . . . . Funci´on que encuentra el elemento de partici´on . . . . . . . Funci´on para saber si un patr´on en una subsecuencia de un texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Uni´on con Listas Desordenadas . . . . . . . . . . . . . . . . Funci´on auxiliar ensambla . . . . . . . . . . . . . . . . . . . Uni´on Listas Ordenadas . . . . . . . . . . . . . . . . . . . . Intersecci´on Listas Ordenadas . . . . . . . . . . . . . . . . . Diferencia Listas Ordenadas . . . . . . . . . . . . . . . . . . Funci´on Hash Letra Inicial . . . . . . . . . . . . . . . . . . . Funci´on Inserta en Tabla Hash . . . . . . . . . . . . . . . . . Funci´on Eliminar de Tabla Hash . . . . . . . . . . . . . . . . Funci´on Buscar en Tabla Hash . . . . . . . . . . . . . . . . . Estructura de Celda Lista Ligada para Funciones . . . . . . Inserta en Tabla Hash para Funciones . . . . . . . . . . . . Estructura - solo padre . . . . . . . . . . . . . . . . . . . . . Estructura - solo hijos . . . . . . . . . . . . . . . . . . . . . Estructura - m´as a la izquierda-hermano a la derecha . . . . Estructura - apuntador al padre . . . . . . . . . . . . . . . . Recursividad en ´arboles - F(n) . . . . . . . . . . . . . . . . . Evaluaci´on en Preorden - F(n) . . . . . . . . . . . . . . . . . 11

. . . . . . . . .

23 25 26 30 34 36 37 38 39

. . . . . . . . . . . . . . . . . .

58 71 71 72 73 74 75 76 76 76 77 78 85 85 86 86 87 88

28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38.

Evaluaci´on en Postorden - F(n) ´ Estructura Nodo Arbol Binario ´ Recursi´on Arbol Binario . . . . Evaluaci´on en Orden - F(n) . . Inserta en a´rbol binario . . . . . Buscar en a´rbol binario . . . . . Eliminar en ´arbol binario . . . . Inserta en heap . . . . . . . . . Eliminar de heap . . . . . . . . Fase 2 de heapsort . . . . . . . Heapsort . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

89 90 91 91 92 93 93 95 96 96 97

Cap´ıtulo 1 Modelo de datos, Iteraci´ on 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 iteraci´on

1.1.1.

Iteraci´ on mediante FOR

Es una estructura iterativa que es controlada mediante un ´ındice o variable de control, la cual se incrementa o decrementa hasta llegar a un valor l´ımite o valor final que representa la condici´on de paro. L a condici´on de paro no es una expresi´on l´ogica sino un valor que indica el final de ciclo. Por su parte, en Java la condici´on de paro si es una expresi´on l´ogica por consiguiente se puede ejecutar tanto un n´ umero predefinido de veces como hasta que se cumpla una determinada condici´on.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 final o de parada que determina cuando termina el ciclo.El incremento/decremento define la forma en que la variable de control del ciclo debe cambiar cada vez que se realiza una iteraci´on. 13

´ Y RECURSION ´ 14 CAP´ITULO 1. MODELO DE DATOS, ITERACION En java for (< inicializaci´ on >; < expresi´ on condicional >; < inc/dec >) { < inst 1 >; s . . < inst n >; } En seudoc´ odigo 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 m´as veces, ya que la condici´on de entrada se verifica al inicio de cada iteraci´on y podr´ıa no cumplirse la primera vez. En java while (< expresi´ on >) { < inst 1 >; . . < inst n >; } En seudoc´ odigo Mientras (< expresi´ on >) Hacer < inst 1 >; .

´ ITERATIVA 1.1. PROGRAMACION

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 condici´on de paro, es decir, hasta que la evaluaci´on de la condici´on de paro sea verdadera. Este bloque de instrucciones se realiza al menos una (1) vez, ya que la condici´on se verifica al final lo cual permite ejecutar el ciclo al menos la primera vez. El comportamiento de do while en seudoc´odigo 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 seudoc´ odigo Repetir < inst1 >; . . < instn >; Hasta (< expresi´ on >);

1.1.4.

Como elegir que estructura de iteraci´ on utilizar

Pueden considerarse los siguientes puntos en la elecci´on del tipo de sentencia 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).

´ Y RECURSION ´ 16 CAP´ITULO 1. MODELO DE DATOS, ITERACION Si se desconoce la cantidad de veces en que se deben repetir las instrucciones o se deben utilizar uno o varios criterios de paro para detener el ciclo, y las condiciones deben verificarse 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 (infinitamente) larga y que algunos cubos est´an marcados con una X (ver Figura1.1). Supongamos que : Proposici´ on 1 El primero de los cubos est´a marcado Proposici´ on 2 Si todos los cubos anteriores al cubo (n + 1) est´an marcados, entonces el cubo (n + 1) tambi´en lo est´a.

# !

$ !

% !

& !

' !

"""

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 afirmaci´on de 1 establece de manera expl´ıcita que el cubo 1 esta marcado. Consideremos el cubo 2. Todos los cubos anteriores al cubo 2, a saber, el cubo 1, est´a marcado, as´ı de acuerdo al 2, el cubo 2 tambi´en est´a 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 tambi´en est´a marcado. De esta forma, podemos mostrar que cada cubo est´a marcado. Por ejemplo supongamos que se ha verificado 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 est´an marcados, de modo que por 2 el cubo 6 tambi´en est´a marcado. El ejemplo anterior ilustra el principio de inducci´ on matem´ atica. Para mostrar c´omo se puede utilizar la inducci´on matem´atica de manera mas profunda, sea Sn la suma de los primeros n enteros positivos Sn = 1 + 2 + 3 + . . . + n

(1.1)

Supongamos que alguien afirma que Sn =

n(n+1) , 2

para n = 1, 2, 3, . . . , n

(1.2)

En realidad se establece la siguiente serie de afirmaciones 1(2) 2 2(3) Sn = 2 .. . n(n + 1) Sn = 2 Supongamos que cada ecuaci´on verdadera tiene una ”X”junto a ella. Como la primera ecuaci´on es verdadera, est´a marcada. Ahora, supongamos que podemos mostrar que si todas la ecuaciones anteriores a una ecuaci´on particular, digamos la ecuaci´on (n + 1), est´an marcadas, entonces la ecuaci´on (n+1) tambi´en esta marcada. Entonces, como en el ejemplo los cubos, todas las ecuaciones est´an marcadas; es decir todas las ecuaciones son verdaderas y se verifica la ecuaci´on 1.2. Debemos mostrar que si todas la ecuaciones anteriores a la ecuaci´on (n+1) son verdaderas, entonces la ecuaci´on (n + 1) tambi´en 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. Sn =

Sn = n

n(n + 1) 2

(1.3)

´ Y RECURSION ´ 18 CAP´ITULO 1. MODELO DE DATOS, ITERACION Debemos mostrar que la ecuaci´on (n + 1) Sn = n

(n + 1)(n + 2) 2

es verdadera. De acuerdo a la ecuaci´on 1.1 Sn+1 = 1 + 2 + 3 + . . . + n + (n + 1) Observamos que Sn est´a contenida dentro de Sn+1 , en el sentido de que Sn+1 = 1 + 2 + 3 + . . . + n + (n + 1) = Sn + (n + 1)

(1.4)

Debido a 1.3 y 1.4, tenemos

Sn+1 = Sn +(n+1) =

n(n + 1) n(n + 1) + 2(n + 1) (n + 2)(n + 1) +n+1 = = 2 2 2

La demostraci´on por inducci´on consto de dos pasos. En primer lugar, verificamos que la afirmaci´on correspondiente a n = 1 era verdadera. En segundo lugar, se supuso que las afirmaciones 1, 2, 3 . . . n eran verdaderas y se demostr´o que la afirmaci´on (n + 1) tambi´en lo era. Al demostrar la afirmaci´on (n+1), pod´ıamos utilizar las afirmaciones 1, 2, 3 . . . n; de hecho, la t´ecnica para construir una demostraci´on por inducci´on matem´atica consiste en relacionar las afirmaciones 1, 2, 3 . . . n con la afirmaci´on (n + 1). A continuaci´on enunciamos de manera formal el principio de inducci´on matem´atica. Principio de inducci´ on matem´ atica Supongamos que para cada entero positivo n tenemos una afirmaci´on S(n) que es verdadera o falsa. Supongamos que. Proposici´ on 3 S(1) es verdadera; Proposici´ on 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

1.2.1.

19

Ejemplo 1

Ahora se ilustra la inducci´on matem´atica mediante otro ejemplo. Utilizar inducci´on matem´atica para mostrar que n! ≥ 2n−1

(1.5)

Paso Base (Condici´on 3 ) Debemos mostrar que 1.5 es verdadera si n = 1. Esto es f´acil de verificar 1! = 1 ≥ 1 = 21−1 . Paso Inductivo (Condici´on 4) Debemos mostrar que si i! ≥ 2i−1 para i = 1, 2, 3, . . . , n entonces (n + 1) ≥ 2n

(1.6)

Supongamos que i ≥ 2i−1 para i = 1, 2, 3, . . . , n. Entonces en particular, para i = n, tenemos n ≥ 2n−1

(1.7)

Podemos relacionar 1.6 y 1.7 observando que (n + 1)! = (n + 1)(n!). Ahora, (n + 1)! = (n + 1)(n!) ≥ (n + 1)2n−1 por 1.7 ≥ 2 ∗ 2n−1 pues n + 1 ≥ 2 = 2n Por tanto, 1.5 es verdadera. Se ha concluido el paso inductivo. Como se ha verificado 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 verificar 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. Esta formulaci´on de la inducci´on matem´atica se le llama la forma fuerte de

´ Y RECURSION ´ 20 CAP´ITULO 1. MODELO DE DATOS, ITERACION la inducci´ on matem´ atica. Con frecuencia, como en le caso de los ejemplos 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 modifica. Puede mostrarse que las dos formas de inducci´on matem´atica son equivalentes. Si queremos verificar que las afirmaciones S(n0 ), S(n0 + 1), . . . , donde n0 6= 1, son verdaderas, debemos cambiar el paso base a S(n0 ) es verdadera. El paso inductivo no se modifica.

1.2.2.

Ejemplo 2: Suma geom´ etrica

Utilizar inducci´on para mostrar que si r 6= 1, a + ar1 + ar2 + · · · + arn =

a(rn+1 − 1) r−1

(1.8)

para n = 0, 1, . . . La suma de la izquierda se llama suma geom´etrica. En una suma geom´etrica, la raz´on entre los t´erminos consecutivos (ari+1 /ari = r es constante. Paso Base . El paso base, que en este caso se obtiene haciendo n = 0, es a=

a(r1 − 1) r−1

lo cual es verdadero. Paso Inductivo . Supongamos que la afirmaci´on 1.8 es verdadera para n. Ahora a + ar1 + ar2 + · · · + arn + arn+1 = = =

a(rn+1 −1) r−1 a(rn+1 −1) r−1 a(rn+2 −1) r−1

+ arn+1 n+1 (r−1) + ar r−1

Como se ha verificado el paso base modificado 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

1.2.3.

21

Ejemplo 3

Utilizar inducci´on para mostrar que 5n − 1 es divisible entre 4 para n = 1, 2, . . . Paso Base . Si n = 1, 5n − 1 = 51 − 1 = 4, que es divisible entre 4. Paso Inductivo . Supongamos que 5n − 1 es divisible entre 4. Debemos mostrar que 5n−1 − 1 es divisible entre 4. Para relacionar el caso (n + 1) con el caso n, escribimos 5n+1 − 1 = 5 ∗ 5n − 1 = (4 + 1) ∗ 5n − 1 = 4 ∗ 5n + (5n − 1) Por hip´otesis 5n − 1 es divisible entre 4, y como 4 ∗ 5n es divisible entre 4, la suma 4 ∗ 5n + (5n − 1) es divisible entre 4. Como se ha verificado el paso base y el paso inductivo, el principio de inducci´on matem´atica dice que 5n − 1 es divisible entre 4 para n = 1, 2, . . ..

1.3.

Definiciones y funciones Recursivas

Un procedimiento recursivo es aquel que se llama a s´ı mismo. La recursi´on es poderosa, elegante y natural de resolver una gran variedad de problemas. Un problema puede resolverse mediante una t´ecnica divide y vencer´as en la cual el problema se descompone en problemas del mismo tipo que el original. Cada subproblema, a su vez, se descompone de nuevo y as´ı hasta que se obtienen subproblemas los cuales pueden resolverse de manera directa. Por u ´ltimo, 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 define como (

n! =

1 si n = 0 n(n − 1)(n − 2) · · · 2 ∗ 1 si n ≥ 1

Observe que n factorial puede escribirse en t´erminos de si mismo pues si quitamos n, el producto restante es s´olo (n − 1)!; es decir,

´ Y RECURSION ´ 22 CAP´ITULO 1. MODELO DE DATOS, ITERACION

n! = n(n − 1)(n − 2) · · · 2 ∗ 1 = n(n − 1)! Por ejemplo 5! = 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 = 5 ∗ 4! La ecuaci´on n(n − 1)!, muestra la forma de descomponer el problema original (calcular n!) en subproblemas cada vez m´as sencillos [calcular (n−1), calcular (n − 2)! ...] 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 simplificado 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 subproblemas, la soluci´on del problema m´as sencillo puede utilizarse para resolver el siguiente subproblema, y as´ı sucesivamente, hasta resolver el problema original. La tabla 1.2 muestra como se combinan los subproblemas para resolver el problema original A continuaci´on escribimos un algoritmo recursivo que calcula factoriales. El algoritmo es una traducci´on 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 l´ınea 3, el valor correcto 1. Si n = 1, como n 6= 0 pasamos a la l´ınea 4. Utilizamos este procedimiento para calcular 0!. Ya hemos observado que el procedimiento calcula 0!. En la l´ınea 4 el procedimiento calcula de forma correcta el valor de 1!.

1.3. DEFINICIONES Y FUNCIONES RECURSIVAS Cuadro 1.2: Combinaci´on de los Problema 0! 1! 2! 3! 4! 5!

23

subproblemas del problema del factorial Soluci´ on 1 1 ∗ 0! = 1 2 ∗ 1! = 2 3 ∗ 2! = 3 ∗ 2 = 6 4 ∗ 3! = 4 ∗ 6 = 24 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: fin si 5: devolver n ∗ factorial (n − 1)

(n − 1)! ∗ n = 0! ∗ 1 = 1 ∗ 1 = 1 Si n = 2, como n 6= 0 pasamos a la l´ınea 4. Utilizamos este procedimiento para calcular 1!. Ya hemos observado que el procedimiento calcula 1 como el valor de 1!. En la l´ınea 4 el procedimiento calcula de forma correcta el valor de 2!. (n − 1)! ∗ n = 1! ∗ 2 = 1 ∗ 2 = 1 Si n = 3, como n 6= 0 pasamos a la l´ınea 4. Utilizamos este procedimiento para calcular 2!. Ya hemos observado que el procedimiento calcula 2 como el valor de 2!. En la l´ınea 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 matem´atica para demostrar que el algoritmo 1 tiene como salida correcta el valor de n! para cualquier entero no negativo n.

´ Y RECURSION ´ 24 CAP´ITULO 1. MODELO DE DATOS, ITERACION 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 l´ınea 4. Por la hip´otesis de inducci´on, el procedimiento calcula correctamente el valor de (n − 1)!. En la l´ınea 4, el procedimiento calcula correctamente el valor (n − 1)! ∗ 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 llamar´ıa 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 matem´atica puede utilizarse para demostrar que un algoritmo recursivo calcula el valor que afirma calcular. El v´ınculo entre la inducci´on matem´atica y los algoritmos es mucho m´as profundo. Con frecuencia, una demostraci´on por inducci´on matem´atica puede considerarse como algoritmo para calcular un valor o realizar una construcci´on particular. El paso base de una demostraci´on 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.

M´ aximo 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 m´aximo com´ un

1.3. DEFINICIONES Y FUNCIONES RECURSIVAS

25

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 m´aximo 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: fin si 6: si b = 0 entonces 7: devolver a 8: fin 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 1 2 3 4

Serie de pasos 1 1,1 o 2 1,1,1 o 1,2 o 2,1 1,1,1,1 o 1,1,2 1,2,1 o 2,1,1 o 2,2

N´ umero de formas de recorrerlos 1 2 3 5

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

´ Y RECURSION ´ 26 CAP´ITULO 1. MODELO DE DATOS, ITERACION 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 definici´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 f´ormula 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) traduciendo 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 definida como   

1 si n = 1 si n = 2 walk (n) =  2  walk (n − 1) + walk (n − 2) si n > 2 Algoritmo 3 Caminata de un robot Entrada: n, Salida: walk (n) 1: robot walk l(n) 2: si n = 1 o n = 2 entonces 3: devolver n 4: fin si 5: devolver robot walk l(n − 1) + robot walk l(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 matem´atico italiano. En lo sucesivo denotaremos la sucesi´on de Fibonacci como f1 , f2 , · · ·. Esta sucesi´on queda definida mediante la ecuaciones

1.3. DEFINICIONES Y FUNCIONES RECURSIVAS

27

f1 = 1 f2 = 2 fn = fn−1 + fn−2 , n > 2

1.3.4.

Torres de Hanoi

Las torres de Hanoi son un juego inventado en la d´ecada de los 80’s por Edouard Lucas, un matem´atico franc´es. La soluci´on a este juego constituye una ilustraci´on de la utilidad de la recursi´on. 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 di´ametro 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. S´olo 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 figura 1.2 muestra la soluci´on 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 m´as peque˜ nos hayan sido apartados, coloc´andolos 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 considerarse 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 final, los u ´ltimos tres movimientos colocan los discos m´as peque˜ nos en su destino final, sobre el disco de mayor di´ametro.

´ITULO 1. MODELO DE DATOS, ITERACION ´ Y RECURSION ´ Solución28para 3 discos CAP

Según la leyenda, los monjes de un templo tenían que mover una pila de 64 Figura 1.2: Secuencia de movimientos parar 3 discos discos sagrados de un sitio a otro. Sólo podían mover un disco al día y, en el templo, sólo había otro sitio en el que podían dejarlos, siempre ordenados de forma que los mayores quedasen en la base. El día en que los monjes realizasen el último movimiento, el final del mundo habría llegado…

1.3. DEFINICIONES Y FUNCIONES RECURSIVAS

29

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 N − 1 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 situaci´on an´aloga se produce despu´es 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 directamente y sin necesidad de recursi´on. El Algoritmo 4 considera primero el caso base (una pila de un disco). Cuando se produce este caso, ejecuta la l´ınea 3, que imprime una u ´nica l´ınea que describe el movimiento. Si la pila contiene m´as de un disco, se invoca de nuevo moveTower (en la l´ınea 5) para apartar los N − 1 discos, luego se mueve el disco de mayor tama˜ no (l´ınea 6) y despu´es los N − 1 discos hasta su destino final con otra llamada a moveTower (l´ınea 7). Observe que los par´ametros 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

´ Y RECURSION ´ 30 CAP´ITULO 1. MODELO DE DATOS, ITERACION 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 ) 2: si n = 1 entonces 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: fin si Cuadro 1.3: Simulaci´on 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 (3, o, d, t) Mover disco de Origen a Destino mT (1, t, o, d) Mover disco de Temporal a Origen mT (2, t, d, o) Mover disco de Temporal a Destino mT (1, o, d, t) Mover disco de Origen a Destino llamada recursiva hace que el m´etodo 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 producir´a el desplazamiento de un disco; si ejecutamos moveTower para 2, se producir´a el desplazamiento de 3 discos; si ejecutamos moveTower para 3, se producir´a 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: para n > 1,

f (n) = 1 cuando n = 1 f (n) = 2 ∗ (f (n − 1) + 1) = 2n − 1

En contraste con su implementaci´on breve y elegante, la soluci´on es muy

1.4. ALGORITMOS DE ORDENAMIENTO

31

ineficiente, ya que para resolver un juego con una pila de N discos, se tienen que realizar 2n − 1 movimientos de discos individuales.

1.4.

Algoritmos de ordenamiento

El ordenamiento es una tarea com´ un que realizamos continuamente. Ordenar es algo tan com´ un que no nos detenemos a pensar en ello. Ordenar es simplemente colocar informaci´on de una manera especial bas´andonos en un criterio de ordenamiento. En la computaci´on el ordenamiento de datos tiene una funci´on muy importante, ya sea como un fin en s´ı o como parte de otros procedimientos m´as complejos. Se han desarrollado muchas t´ecnicas en este ´ambito, cada una con caracter´ısticas espec´ıficas, y con ventajas y desventajas sobre las dem´as. En est´a secci´on se revisar´an algunos de los algoritmos de ordenamiento m´as 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 tel´efono se puede ordenar alfab´eticamente de acuerdo a la clave nombre. En este caso los campos direcci´on y tel´efono 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 m´as 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 m´as comunes: Estabilidad : C´omo se comporta con registros que tienen claves iguales. A los algoritmos que mantienen el orden relativo entre ´estos se les llama

´ Y RECURSION ´ 32 CAP´ITULO 1. MODELO DE DATOS, ITERACION 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 alfab´eticamente por la letra con un algoritmo estable quedar´ıa as´ı: [(A,5), (B,9), (B,8), (C,4), (J,19), (J,0), (Z,4)]. Un algoritmo no estable podr´ıa dejar a (B, 8) antes de (B,9) o (J,0) antes que (J,19). Tiempo de ejecuci´ on : La complejidad del algoritmo, la cual tiene que ver con rendimiento. Es una funci´on independiente de la implementaci´on. En este caso se tiene que identificar 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 t´erminos 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 cuadr´atica. O(nlog(n)): Complejidad logar´ıtmica. On2 : Complejidad cuadr´atica Es posible decir que un algoritmo de complejidad O(n) es m´as r´apido que uno de complejidad O(n2 ). Otro aspecto a considerar es la diferencia entre el peor y el mejor caso. Cada algoritmo se comporta de modo diferente de acuerdo a c´omo se le entregue la informaci´on; 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 adicional para realizar su labor. En general es preferible que no sea as´ı, pero es com´ un en la programaci´on tener que sacrificar memoria por rendimiento.

1.4.2.

Ordenamiento de Burbuja (BubbleSort)

Este es probablemente el algoritmo m´as sencillo. Consiste en iterar repetidamente la lista, comparando elementos los adyacentes de dos en dos. Si un elemento es mayor que el que est´a en la siguiente posici´on se intercambian.

1.4. ALGORITMOS DE ORDENAMIENTO

33

La estrategia general del m´etodo es la siguiente: explorar la lista comparando 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 u ´ltima posici´on de la lista, que es la posici´on que le corresponde dentro de la lista final ordenada. A continuaci´on se repite la operaci´on, haciendo que se desplace el segundo valor m´as 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 final. A lo largo de una iteraci´on, tambi´en pueden reposicionarse otros elementos. Por ejemplo, si comenz´aramos con la lista: 9 6 8 12 3 1 7 primero se comparar´ıan el 9 y el 6 y, como no est´an en el orden correcto, se intercambian con lo que quedar´ıa: 6 9 8 12 3 1 7 Despu´es se compara el 9 con el 8 y, de nuevo al ver que no est´an en orden, se intercambian obteni´endose: 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 est´an 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 Despu´es 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 iteraci´on a trav´es de los datos que hay que ordenar. Despu´es de esta primera iteraci´on el valor de mayor de la lista se encuentra en la posici´on 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 m´as. Por tanto tendremos que hacer n − 1 iteraciones, por que cuando se tienen n − 1 elementos en la posici´on correcta el elemento n tambi´en estar´a en la posici´on correcta. El algoritmo 5 implementa el ordenamiento mediante el m´etodo de burbuja. Del algoritmo 5 puede observarse en la l´ınea 4 que el debemos iterar n veces los datos para poder asegurar que los n elementos terminan en su

´ Y RECURSION ´ 34 CAP´ITULO 1. MODELO DE DATOS, ITERACION posici´on correcta. En la l´ınea 5 observamos que solo es necesario comparar hasta lo posici´on n − i (el −1 es debido a que solo podemos compara hasta el elemento n − 1 con es n) ya que despu´es de la i-´esima iteraci´on los u ´ltimos 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: fin si 9: fin para 10: fin 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, n−2 y as´ı sucesivamente. De lo anterior es posible observar que la complejidad (n´ umero de operaciones necesarias) est´a dada por (n − 1) + (n − 2) + (n − 3) + · · · + 1 como ya se demostr´o en la secci´on 1.2 es sumatoria est´a dada por la funci´on (n − 1)(n − 2)/2 = n2 − n + 2 lo cual es O(n2 ), 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 recursi´on, que es el caso en que se tienen listas de longitud uno, que estar´an por definici´on ordenadas. A continuaci´on, a medida que

1.4. ALGORITMOS DE ORDENAMIENTO

35

se devuelve el control hacia arriba a trav´es de la estructura recursiva de llamadas, el algoritmo va mezclando es una u ´nica 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 dar´ıa 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 recombinar´ıa 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 an´alisis de complejidad (simple), suponemos que n es una potencia de 2, por tanto n puede expresarse como n = 2x y de la definici´on del logaritmo tenemos que log b (n) = x ⇐⇒ n = bx , con lo anterior podemos deducir que el n´ umero m´aximo de sublista es x = log 2 (n) y cada una de

´ Y RECURSION ´ 36 CAP´ITULO 1. MODELO DE DATOS, ITERACION 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 funciones, una que representa el ordenamiento y otra para el mezclado de las sublistas. La funci´on 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: Ao [] lista ordenada 1: mergeSort(A) 2: n = longitud (n) 3: si n = 1 entonces 4: devolver A 5: fin si 6: L1 =A[1],A[2], · · · , A[n/2] 7: L2 =A[n/2 + 1],A[n/2 + 2], · · · , A[n] 8: mergesort(L1 ) 9: mergesort(L2 ) 10: devolver merge(L1 , L2 )

1.4.4.

Ordenamiento r´ apido (QuickSort)

El Algoritmo QuickSort ordena una lista dividiendo una lista mediante un elemento de partici´on elegido arbitrariamente y luego ordenando recursivamente las sublistas situadas a ambos lados del elemento de partici´on. La estrategia general del algoritmo es la siguiente: en primer lugar, se selecciona un elemento de la lista para que act´ ue como elemento de partici´on; a continuaci´on, 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; finalmente, se aplica esta estrategia (recursivamente) a ambas particiones. La selecci´on del elemento de partici´on es arbitraria, as´ı que para este caso se utiliza el primer elemento de la lista. Por razones de eficiencia, ser´ıa

1.4. ALGORITMOS DE ORDENAMIENTO

Algoritmo 7 Funci´on 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: fin si 14: fin mientras 15: mientras i < n hacer 16: C[i + j]=A[i] 17: i=i+1 18: fin mientras 19: mientras j < m hacer 20: C[i + j]=B[j] 21: j =j+1 22: fin mientras 23: devolver C

37

´ Y RECURSION ´ 38 CAP´ITULO 1. MODELO DE DATOS, ITERACION conveniente que el elemento de partici´on dividiera la lista aproximadamente en dos mitades, pero el algoritmo funciona igual independientemente de qu´e elemento se seleccione para realizar la partici´on. Examinemos un ejemplo. Si comenz´aramos con la siguiente lista: 9 6 7 30 12 11 8 se elegir´ıa 9 como el elemento de partici´on. Despu´es 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 Despu´es se aplica el algoritmo de ordenamiento por separado a ambas particiones. Este proceso continua hasta que una partici´on s´olo contenga un elemento, que estar´a inherentemente ordenado. As´ı despu´es de aplicar el algoritmo recursivamente en ambos lados, la lista entera estar´a ordenada. Una vez determinado y colocado el elemento de partici´on 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 m´ınimo (max ) de los elementos del arreglo por ordenar. Al inicio del algoritmo, los valores min y max abarcan todo el arreglo de elementos. Algoritmo 8 Ordenamiento r´apido Entrada: A[], un arreglo desordenado y min ´ındice donde inicia la sublista y max ´ındice donde termina la sublista Salida: No regresa nada, ordena A en sitio. 1: quickSort(A, min, max ) 2: si max − min > 0 entonces 3: pivote = f indP artition(A, min, max ) 4: quickSort(A, min, pivote − 1) 5: quickSort(A, pivote + 1, max ) 6: fin si El Algoritmo ?? se basa en el m´etodo findPartition, al que llama para dividir el arreglo en dos particiones. El m´etodo findPartition 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 recursi´on, representado por la instrucci´on IF del m´etodo quickSort, es cuando se tiene una lista de un elemento o menos, que estar´a inherentemente ordenada. El Algoritmo que determina el ´ındice pivote se muestra a

1.4. ALGORITMOS DE ORDENAMIENTO

39

continuaci´on (ver Algoritmo 9): Algoritmo 9 Funci´on que encuentra el elemento de partici´on Entrada: A[], un arreglo desordenado y min ´ındice donde inicia la sublista y max ´ındice donde termina la sublista Salida: rigth ´ındice de la partici´on 1: findPartition(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: fin mientras 9: mientras A[rigth]> partitionElement hacer 10: rigth = right − 1 11: fin mientras 12: si left < right entonces 13: temp = A[left] 14: A[left]= A[right] 15: A[right]= temp 16: fin si 17: fin mientras 18: temp = A[min] 19: A[min]= A[right] 20: A[right]= temp 21: devolver right Los dos ciclos WHILE internos del m´etodo findPartition 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 buscando 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 partici´on. Una vez encontrados los dos elementos, se intercambian. Este proceso continua hasta que los ´ındices derecho e izquierdo se encuentran en el “medio” de la lista. La ubicaci´on en la que se encuentran tambi´en indica d´onde debe situarse elemento de partici´on (que no se mueve de su posici´on hasta el final).

´ Y RECURSION ´ 40 CAP´ITULO 1. MODELO DE DATOS, ITERACION

1.5.

Ejercicios

1. En los siguiente ejercicios utilice inducci´on para verificar que cada ecuaci´on es verdadera a) 1 + 2 + 5 + . . . + 2(n − 1) = n2 b) 1 ∗ 2 + 2 ∗ 3 + 3 ∗ 4 + . . . + n(n + 1) = c) 12 − 22 + 32 + . . . + n2 =

n(n+1)(n+2) 3

n(n+1)(2n+1) 6

2. En los siguiente ejercicios utilice inducci´on para verificar la desigualdad a) 2n + 1 ≤ 2n , n = 3, 4, . . . b) 2n ≥ n2 , n = 4, 5, . . . c) (1 + x)n ≥ 1 + nx, para x ≥ −1 y n = 1, 2, . . . 3. En los siguiente ejercicios utilice inducci´on para demostrar cada afirmaci´on a) 7n − 1 es divisible entre 6, para n = 1, 2, . . . b) 3n + 7n − 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 m´as puede cobrarse utilizando solo estampillas de 5 y 7 centavos. 4. Proporcione un algoritmo que invierta un n´ umero decimal(sin convertirlo a cadena) solo utilizando operaciones aritm´eticas. 5. Proporciones versiones iterativas y recursivas de algoritmos que soluciones los siguientes problemas. 6. Escriba una definici´on recursiva para la multiplicaci´on entera n*m para n > 0. Defina la multiplicaci´on en t´erminos de la suma de enteros. Por ejemplo 3*4 es igual a sumar 3 el 4. 7. D´e un algoritmo recursivo para la divisi´on entera n/m para m > 0. Defina la divisi´on en t´erminos 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 inter´es 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 B un programa calcule A . c) Escriba un programa que, dado como dato un n´ umero entero positivo regrese 1 si todos los d´ıgitos 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 posici´on 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 m´etodo 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 primo (recuerde que los n´ umeros primos son aquellos que solo son divisibles entre ellos mismos y la unidad). 9. Definir el/los caso(s) base y recursivo para determinar si una cadena es o no un pal´ındromo. Los pal´ındromos son palabras, n´ umeros o frases que se lee igual hacia adelante que hacia atr´as(ana, 00100, 0110, etc).

´ Y RECURSION ´ 42 CAP´ITULO 1. MODELO DE DATOS, ITERACION 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 ejecuci´on para los siguientes algoritmos: a) ordenamiento de la burbuja b) ordenamiento por mezcla c) ordenamiento r´apido 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 u ´ltimo elemento y el oredenamiento de burbuja. Explique sus respuestas. 13. Modifique los algoritmos de ordenamiento presentados en el cap´ıtulo (burbuja, mezcla y r´apido) a˜ nadiendo c´odigo a cada uno de los m´etodos con el fin 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 graficar 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 ...).

Cap´ıtulo 2 El modelo de datos de listas 2.1.

Introducci´ on

Frecuentemente utilizamos el concepto de lista. Es muy com´ un hacer listas de compras, lista de tareas pendientes o listas de invitados a una fiesta. Las listas suelen estar enumeradas y ordenadas de acuerdo a alg´ un criterio. En est´a 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 ligadas

Las estructura de datos se implementa mediante el uso de referencias para crear enlaces entre objetos. Est´a soluci´on tiene ventajas y desventajas respecto a soluciones equivalentes haciendo uso de arreglos. Las listas ligadas implementadas utilizan variables de referencia a objetos con el fin de crear enlaces entre objetos. Recuerde que con una variable de referencia a objeto almacena la direcci´on del objeto, que indica donde est´a ese objeto almacenado en memoria. Usualmente, una variable de referencia a objeto es s´olo importante para poder accede a un objeto, pero generalmente no tiene ninguna importancia que ubicaci´on espec´ıfica 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

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

44

referencia

Figura 2.1: Variable de referencia a un objeto

Si se define una clase que tiene como dato una referencia a otro objeto de la misma clase. Por ejemplo considere el c´odigo del listado 2.1. Listing 2.1: Definici´on 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 tambi´en contendr´a una referencia a un objeto Nodo, que a su vez contendr´a otra, etc. Este tipo de relaci´on 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: Representaci´on de una lista ligada

De la Figura 2.2 puede observarse que se necesita una variable de referencia 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 BASICAS CON LISTAS

45

(representado por el s´ımbolo de tierra). El c´odigo para la representaci´on de una lista ligada se muestra en el listado 2.2 Listing 2.2: Definici´on de nodo public class Lista { Nodo primero ; public Lista (){ primero = null ; } } A diferencia de los arreglos que tienen un tama˜ no fijo, las lista no tienen un l´ımite 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 b´ asicas 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. Espec´ıficamente 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 ubicaci´on de la misma: al inicio, al final 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 reci´en agregado. Observe que podr´ıa haber dificultades si se invirtiera el orden le los pasos de la inserci´on . Si se reinicializara la referencia primero se perder´ıa la u ´nica referencia a la lista y ya no podr´ıa recuperarse. El c´odigo java para la operaci´on insertar al principio(insertaP) se muestra en el listado 2.3 .

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

46

nuevo

2

primero

X

1

... 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 est´a vac´ıa solo se ejecuta la l´ınea 4 haciendo el u ´nico nodo igual al primero de la lista. En el caso donde la lista contiene al menos un elemento se ejecutan las l´ıneas 3 y 4, realizando el proceso descrito en la Figura 2.3 . La inserci´on de un al final (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 trav´es de los nodos de la lista, hasta encontrar el nodo deseado (en este caso el u ´ltimo de la lista). En este caso a dicha referencia se le denominar´a actual (indica el nodo actual que se est´a procesando). En el proceso de insertar al final es necesario hacer que la referencia actual apunte al nodo al final de la lista, y una ves encontrado poner el nuevo nodo como el siguiente de actual (ver Figura 2.4). Es posible encontrar el u ´ltimo elemento en una lista mediante dos aproximaciones: utilizando inicializando

´ 2.3. OPERACIONES BASICAS CON LISTAS

47

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 vac´ıa, 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 u ´ltimo de la lista, entonces insertamos al final utilizando como actual al siguiente de actual. El Listado 2.4 muestra el c´odigo java para insertaF. Las l´ıneas 2 y 3 son el caso donde la lista est´a vac´ıa. Las lineas 6 y 7 el caso donde actual ha alcanzado el final de la lista, en 7 se hace la referencia de siguiente a nuevo. Las l´ıneas 4 y 5 son el caso recursivo, se prueba que actual no es el u ´ltimo en la l´ınea 4, sino se procede a hacer la llamada recursiva con el siguiente de actual. nuevo

actual

...

X

primero

Figura 2.4: Inserci´on al final de una lista

Listing 2.4: Inserci´on de un nodo al final de una lista 1: public void insertaF ( Nodo actual , Nodo nuevo ){ 2: if ( actual == null )

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

48 3: 4: 5: 6: 7: 8: 9:}

primero = nuevo ; else if ( actual . siguiente != null ) insertaF ( actual . siguiente , nuevo ); else if ( actual . siguiente == null ){ actual . siguiente = nuevo ; }

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 u ´tlimo 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. .

X

primero

... Figura 2.5: Borrar al principiol de una lista

El c´odigo en java para insertar un elemento al inicio de una lista se muestra en el listado 2.5. En la l´ınea 2 se guarda una referencia al nodo que se va a eliminar. La l´ınea 3 verifica si la lista esta vacia, si no esta vacia se apunta primeroa a primero.siguiente. En la l´ınea 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 BASICAS CON LISTAS

49

6:} Para borrar el u ´ltimo nodo de una lista, primero debe encontrarse el nodo anterior al elemeto del final. Esto requiere utilizar dos referencias una que apunte el nodo del final y otra que apunte al nodo precedente. Esas referecias se denominan actual y previo como se observa en la Figura 2.5. primero

previo

...

X

actual

Figura 2.6: Borrar al final de una lista

En el listado 2.6 muestra el c´odigo en java que implementa el algoritmo recursivo para borrar al final de una lista ligada. Listing 2.6: Borrado de un nodo al final de una lista 1: public Nodo borraF ( Nodo previo , Nodo actual ){ 2: if ( actual == null ) 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 m´etodo 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 l´ınea 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´ITULO 2. EL MODELO DE DATOS DE LISTAS

apunte al final de la lista, esto es necesario , ya que previo y actual apuntan al mismo elemento. El segundo caso base (l´ınea 4) es cuando; actual est´a al final de la lista, en ´esta situaci´on se realiza la operaci´on indicada en la l´ınea 9 y se regresa el valor de nodo que se acaba de borrar. El caso recursivo ocurre cuando actual todav´ıa tiene un nodo siguiente lo cual quiere decir que no es el u ´ltimo 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 l´ınea 1 es cuando se quiere borrar un elemento de una lista vacia, aunque tambi´en podr´ıa manejarse como una excepcion aqu´ı se considera como una un caso especial, para simplificar el c´odigo. Tambi´en es posible borrar un elemeto intermedio de una lista, pero ´esto se deja como ejercicio al alumno, as´ı como las implementaciones iterativas de los m´etodos de borrado.

2.3.3.

B´ usqueda e Impresi´ on

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 final 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 m´etodo de b´ usqueda con el nodo siguiente . Una vez que se alcanza el final de la lista (es decir el nodo actual es nulo) se puede afirmar 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 encuentra en la lista.

´ 2.3. OPERACIONES BASICAS CON LISTAS

51

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.

1: 2: 3: 4: 5: 6: 7: 8:

Listing 2.7: Buscar un elemento x en una lista public boolean busca ( Nodo actual , Nodo x ){ if ( actual == null ) return false ; else if ( actual . compareTo ( x )==0) return true ; else return busca ( actual . siguiente , x ); }

La l´ınea dos es el caso cuando se ha alcanzado el final 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 l´ınea 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 l´ınea 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 impresi´on 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 m´etodo de impresi´on con el nodo siguiente del actual. Los caso para ´este m´etodo 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 m´etodo que imprime la lista.

2.3.4.

Algoritmos de Ordenamiento utilizando listas

Los algoritmos de ordenamiento previamente vistos pueden ser implementados 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

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

52

para finalmente 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 divisi´on podr´ıa ser tan simple como contar los elementos de la lista y despu´es 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 divisi´on. 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 figura 2.7. De manera formal podemos definir el algoritmo que divide la lista como sigue:





   

       


 

Figura 2.7: Proceso de divisi´on de una lista

caso base : Si la lista est´a vac´ıa o contiene un solo elemento, la segunda lista es una lista vac´ıa. caso recursivo : Si la lista tiene m´as 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 BASICAS CON LISTAS

53

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 l´ıneas 3 y 4, el segundo de la l´ınea 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 definici´on recursiva del algoritmo queda como sigue: caso base : Si una de las dos listas est´a vac´ıa, se regresa la otra lista. caso recursivo : Si el nodo actual de la lista1 es el mayor que el nodo actual de la lista2 entonces seleccionar el nodo de la lista2 y asignar al siguiente de ´este la mezcla de la lista1 con el resto de los nodos de la lista2 . En contrario caso tomar el nodo siguiente de la lista1 y asignar a su siguiente el resultado de la mezcla de la lista2 con el resto de los nodos en la lista1 El c´odigo java para el algoritmo de mezcla se muestra se muestra en 2.9

54

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

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 l´ıneas 2 a 5 contemplan el caso base. El caso recursivo se implementa de la l´ınea 6 a 13. Una vez implementados los m´etodos de divisi´on 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 final), 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 estanter´ıa, 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 operaci´on mediante la funci´on insertaP pop Elimina lo que hay en el tope de la pila. Se implementa utilizando el m´etodo borraP de una lista

´ DEL MODELO DE PILAS 2.4. IMPLEMENTACION

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 Verifica 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 final de la lista. Se utilizan las funciones que insertan/borran al principio por cuestiones de eficiencia.

2.4.1.

Conversi´ on de notaci´ on infija a posfija

Una pila puede ser utilizada para convertir una expresi´on infija a notaci´on posfija. La notaci´on infija es la utilizamos cotidianamente para escribir expresiones aritm´eticas por ejemplo 3 ∗ 2 + 5. La notaci´on infija necesita reglas de precedencia, por ejemplo en la expresi´on anterior hacemos primero la operaci´on 3 ∗ 2 y despu´es 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 tendr´ıa que expresarlo median el uso de par´entesis reescribiendo la expresi´on como 3 ∗ (2 + 5). La notaci´on posfija es m´as sencilla de procesar para una computadora ya que no necesita precedencia y por tanto no es necesario el uso de par´entesis. En una expresi´on posfija el operador siempre est´a a la derecha de sus dos operandos, por ejemplo la notaci´on posfija de 3 + 2 se reescribe como 32+. Es posible convertir cualquier expresi´on infija a posfijo mediante el uso del siguiente procedimiento. Si el car´acter actual es un d´ıgito poner en posfijo Si el car´acter es un par´entesis 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 posfijo • Meter en la pila el car´acter actual

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

56

Si el car´acter actual en infijo es un par´entesis derecho • Sacar los operadores de la parte superior de la pila e insertarlos en posfijo, hasta encontrar un par´entesis izquierdo en la pila • Sacar y descartar el par´entesis 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 tambi´en como FIFO (del ingl´es first-in first-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 operaciones de inserci´on y borrado se hace por un extremo diferente(por ejemplo insertamos al inicio y borramos al final 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 m´etodo 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 Verifica si la cola est´a vacia. Regresa verdadero si primero apunta a nulo. En ´esta instancia ser´ıa relativamente sencillo implementar un modelo de colas utilizando el modelo de listas ya visto, por lo que se deja como ejercicio al lector.

´ DEL MODELO DE COLAS 2.5. IMPLEMENTACION

2.5.1.

57

Programaci´ on Din´ amica

Subsecuencia Com´ un m´ as 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 din´amica se basa en la siguiente idea: primero se obtiene un algoritmo recursivo, el cual puede ser ineficiente debido a que se ejecuta repetidamente en los mismos subproblemas. La t´ecnica consiste en almacenar la soluci´on a cada subproblema la primera vez que se computa, para despu´es recuperarla en lugar de volverla a computar. El incremento en la eficiencia 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 m´etodo Top-down es muy parecido al algoritmo de la soluci´on recursiva, por tanto m´as f´acil de entender, pero el m´etodo bottom-up es usualmente m´as eficiente.

subsecuencia Antes de definir el problema de la subsecuencia com´ un m´as larga, se resolver´a un problema m´as simple. Suponiendo que se proporciona una cadena peque˜ na (patr´on) 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 patr´on 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 ”ingenier´ıa en computaci´on”. La forma m´as sencilla de visualizarlo es capitalizando la subsecuencia ”inGenier´ıA en compuTAci´on”. Es posible verificar si un patr´on es subsecuencia de un texto con el algoritmo 10

Subsecuencia com´ un m´ as 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 patr´on 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´ITULO 2. EL MODELO DE DATOS DE LISTAS

Algoritmo 10 Funci´on para saber si un patr´on en una subsecuencia de un texto Entrada: p y T el patr´on 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 == m − 1 entonces 5: devolver cierto 6: fin si 7: si T [i] == p[j] entonces 8: j =j+1 9: fin si 10: i=i+1 11: fin mientras 12: devolver falso En biolog´ıa molecular. Las secuencias de ADN pueden ser representadas por cuatro letras ACGT, correspondientes a las cuatro submol´eculas que conforman el ADN. Cuando los bi´ologos encuentran una nueva secuencia, t´ıpicamente se quiere saber a que otras subsecuencias se parece 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 diff de Unix es utilizado para comparar dos versiones del mismo archivo, para determinar que cambios han sido realizados. Este funciona encontrando la LCS de las lineas de los dos archivos; cualquier linea en la subsecuencia no ha sido cambiada, entonces despliega el conjunto de l´ıneas restantes que son las que fueron modificadas.

Soluci´ on recursiva Para obtener la soluci´on de programaci´on din´amica para LCS , primero es necesario obtener la soluci´on recursiva. Programaci´on din´amica no nos proporciona una soluci´on al problema, solo nos ayuda a hacer la soluci´on m´as eficiente una vez que ya se ha obtenido.

´ DEL MODELO DE COLAS 2.5. IMPLEMENTACION

59

Se puede observar que el problema lo podemos resolver alineando la letras que coinciden de ambas cadenas, por ejemplo para ”hola mundo” y ”landa”quedar´ıa como en la figura 2.8


    Figura 2.8: Subsecunecia com´ un m´as larga

Si se dibujan lineas conectando las letras de la primera cadena que coinciden con la segunda, sin que haya l´ıneas que se crucen. En consecuencia cualquier conjunto de l´ıneas que se dibujen y las cuales no se crucen representan una subsecuencia. De lo anterior se puede observar el siguiente hecho: si dos cadenas comienzan 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 subsecuencia, representado como en el figura 2.8, puede moverse la linea de m´as 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 podr´ıan ser eliminadas de la subsecuencia . Finalmente se puede observar que una vez decidido que hacer con el primer caracter de las cadenas, el problema restante es nuevamente el problema de LCS, con dos cadenas m´as cortas. Por tanto se puede resolver recursivamente. En lugar de encontrar la subsecuencia, es m´as eficiente encontrar la longitud de la misma. Entonces en el caso donde el primer caracter difiere, puede determinarse cual subproblema proporciona la soluci´on correcta mediante la resoluci´on de ambos y tomando la longitud m´axima 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

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

60 algoritmo.

caso base : Si una de las cadenas est´a vac´ıa, 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 l´ıneas 4 a 6, en este caso se resuelve el problema de LCS utilizando los sufijos de A y B. El caso recursivo 2 es la l´ınea 7.

1: 2: 3: 4: 5: 6: 7: 8:}

Listing 2.10: Soluci´on recursiva para LCS public static int lcs ( String A , String B ){ if ( A . length ()==0 || B . length ()==0) return 0; else if ( A . charAt (0)== B . charAt (0)){ return 1+ lcs ( A . substring (1) , B . substring (1)); } return Math . max ( lcs (A , B . substring (1)) , lcs ( A . substring (1) , B ))

´ Esta es una soluci´on correcta pero muy ineficiente. 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 2n .

2.5.2.

top-down

El problema con la soluci´on recursiva es que el mismo subproblema es resuelto muchas veces. Un subproblema consiste en todas las llamadas recursivas a LCS, con los sufijos de A y B, entonces existen exactamente

´ DEL MODELO DE COLAS 2.5. IMPLEMENTACION

61

(n + 1)(m + 1) posible subproblemas. Los subproblemas que deben ser recordados es la combinaci´on de los n + 1 sufijos de A(aunque la longitud de A es n tambi´en la cadena vac´ıa es un sufijo de A y de ah´ı el +1) y los m + 1 sufijos de B, por tanto necesitamos resolver (n + 1) ∗ (m + 1) posibles soluciones. Si hay cerca de 2n llamadas recursivas, eso implica que algunos de eso subproblemas son resueltos varias veces. La soluci´on mediante programaci´on din´amica consiste en verificar si cada subproblema ya ha sido resuelto. Si ya fue resuelto s´olo se recupera en lugar de volver a computarlo. La implementaci´on de la soluci´on de programaci´on din´amica consiste en modificar 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 sufijos de las cadenas de entrada. Para hacer facilitar almacenar y recuperar las soluciones parciales, se utilizar´an la posiciones en las que comienzan los sufijos. LSC recursivo con indixes Con en objeto de facilitar la deducci´on de la soluci´on utilizando programaci´on din´amica, primero se modifica la soluci´on recursiva, para que, utilice ´ındices. La soluci´on queda como en el listado 2.11 1: 2: 3: 4: 5: 6: 7: 8:}

Listing 2.11: Soluci´on recursiva para LCS utilizando ´ındices public static int lcs_index ( String A , String B , int i , int j ){ if ( A . length ()== i || B . length ()== i ) return 0; else if ( A . charAt ( i )== B . charAt ( j )){ return 1+ lcs_index (A ,B , i +1 , j +1); } return Math . max ( lcs (A ,B ,i , j +1) , lcs_index (A ,B , i +1 , j ));

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 sufijo 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 sufijo que se est´a procesando. Ahora ya es posible convertir la soluci´on recursiva en un algoritmo de programaci´on din´amica, s´olo se necesita usar un arreglo para almacenar el

62

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS

resultado de cada subproblema. Cuando se quiere la soluci´on de un subproblema dado, primero se verifica 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 [][] , 2: if ( L [ i ][ j ] =0; i - -){ 7: for ( int j = m ;j >=0; j - -){ 8: if ( n == i || m == j ) 9: L [ i ][ j ]=0; 10: else if ( A . charAt ( i )== B . charAt ( j )){ 11: L [ i ][ j ]=1+ L [ i +1][ j +1]; 12: }

2.6. EJERCICIOS 13: 14: 15: 16: 17: 18:}

65 else L [ i ][ j ]= Math . max ( L [ i +1][ j ] , L [ i ][ j +1]);

} } return L [0][0];

Las ventajas del m´etodo en el listado 2.14 incluyen en hecho de que la iteraci´on es normalmente m´as r´apida que la recursi´on, no es necesario inicializar 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 podr´ıa 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, especificar un algoritmo que inserte el valor en el lugar apropiado y sin repetici´on, es decir si el valor ya esta en la lista no se realiza la inserci´on. 2. Dada una lista y un valor , especificar 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 deber´a 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 representaci´on(del ejercicio anterior) implemente un algoritmo que calcule la derivada de un polinomio

66

CAP´ITULO 2. EL MODELO DE DATOS DE LISTAS 7. Escriba los estados de una pila en el proceso de conversi´on a posfijo de la siguiente expresi´on (3 + 4) ∗ (5 − 3)/2 8. Implementar un evaluador de expresiones en posfijo. 9. Describa como podr´ıa implementar una cola con dos pilas.

10. Describa como podr´ıa 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 implementaci´on del algoritmo de ordenamiento de burbuja utilizando listas ligadas. 13. Proporcione una versi´on modificada del algoritmo visto en clase para obtener la longitud el patr´on LCS, el cu´al 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 soluci´on de programaci´on lineal para el problema de los coeficiente binomiales. B A 15. Dados los siguiente pares de cadenas: abracadabra abracadabra diabracadabra barba ga cual es la matriz resultante L de aplicar la soluci´on de programaci´on din´amica top-down para el problema de LCS, a cada uno de los pares.

Cap´ıtulo 3 El modelo de conjunto de datos 3.1. 3.1.1.

Definiciones B´ asicas y Principales Operaciones con Conjuntos Definiciones B´ asicas

Generalmente un conjunto no se define expl´ıcitamente, m´as bien se define 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 consiste de todos los elementos x para los que el predicado x pertenece a S es verdadero. La notaci´on estandar para conjuntos se muestra a continuaci´on 1. La expresi´on x ∈ S significa que x pertenece al conjunto S. 2. Si x1 , x2 , . . . , xn son elementos del conjunto S, entonces se puede escribir: S = {x1 , x2 , . . . , xn } N´otese que cada x es distinta y el orden en que se presentan los elementos es irrelevante. 3. El conjunto vac´ıo (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 teor´ıa de conjuntos solo existen conjuntos, sin embargo, en estructuras de datos o algoritmos es conveniente tener elementos (´atomos) que no sean conjuntos. Un a´tomo puede ser miembro de un conjunto, pero no contener elementos. En ocasiones es necesario que los a´tomos sean informaci´on compleja, por lo que un ´atomo puede ser una estructura o un arreglo. Definici´ on de Conjuntos por Comprensi´ on Anteriormente se propuso que un conjunto debe ser definido enlistando a todos sus miembros (definici´on por extensi´on), lo que puede llegar a ser inconveniente. Para realizar una definici´on por comprensi´on de un conjunto A se requiere de un conjunto S y, al menos, una regla o proposici´on 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 Infinitos Algunos conjuntos tienen un n´ umero finito de elementos, por lo que se puede establecer su cardinalidad con un n´ umero entero. Existen conjuntos cuya cardinalidad es infinita, que tienen un n´ umero infinito de elementos, por ejemplo los n´ umeros Naturales (N ), Enteros (Z ), Reales (R) y Complejos (C ).

´ 3.1. DEFINICIONES BASICAS Y PRINCIPALES OPERACIONES CON CONJUNTOS69

3.1.2.

Operaciones con Conjuntos

En ´este apartado se revisan las operaciones con conjuntos y se discuten sus implementaciones. Uni´ on, Intersecci´ on, 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´aficamente: Unión

Intersección

Resta

Figura 3.1: Operaciones con conjuntos

Diagramas de Venn Los diagramas de Venn son una herramienta grafica 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´ITULO 3. EL MODELO DE CONJUNTO DE DATOS 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 combinaci´on de las regiones 2, 3 y 4 representa la uni´on de los conjuntos S y T (S ∪ T ) ´ Algebra de Conjuntos En lo sucesivo S, T , y R son conjuntos no vac´ıos y la equivalencia entre expresiones se denota por ≡. Conmutatividad de la uni´on. (S ∪ T ) ≡ (T ∪ S), Asociatividad de la uni´on. (S ∪ (T ∪ R)) ≡ ((S ∪ T ) ∪ R) Conmutatividad de la intersecci´on. (S ∩ T ) ≡ (T ∩ S) Asociatividad de la intersecci´on. (S ∩ (T ∩ R)) ≡ ((S ∩ T ) ∩ R) Distributividad de la intersecci´on sobre la uni´on. (S ∩ (T ∪ R)) ≡ ((S ∩ T ) ∪ (S ∩ R)) Distributividad de la uni´on sobre la intersecci´on. (S ∪ (T ∩ R)) ≡ ((S ∪ T ) ∩ (S ∪ R)) Asociatividad de la uni´on y la diferencia. (S − (T ∪ R)) ≡ ((S − T ) − R) Distributividad de la diferencia sobre la uni´on. ((S ∪ T ) − R) ≡ ((S − R) ∪ (T − R)) Identidad de la uni´on.(S ∪ ∅) ≡ ∅ Idempotencia de la uni´on. (S ∪ S) ≡ S Idempotencia de la intersecci´on. (S ∩ S) ≡ S Otras leyes del conjunto vac´ıo. (S − S) ≡ ∅, (∅ − S) ≡ ∅, (∅ ∩ S) ≡ ∅

´ 3.1. DEFINICIONES BASICAS Y PRINCIPALES OPERACIONES CON CONJUNTOS71

3.1.3.

Implementaci´ on de Conjuntos Utilizando Listas

Se recomienda utilizar listas ligadas ordenadas, de lo contrario se tendr´ıa 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: lista1 ,lista2 1: copiar lista1 a listanueva 2: para todo elemento en lista2 hacer 3: si elemento no es miembro de lista1 entonces 4: agregar elemento a listanueva 5: fin si 6: fin para 7: devolver listanueva cada uno de los m elementos de T se compara con los n elementos de S, por lo que su tiempo de ejecuci´on ser´a O(nm). Operaciones B´ asicas con Listas Ligadas Ordenadas Uni´on. Realizar las operaciones b´asicas de conjuntos con listas previamente 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 entre cabeceras de los conjuntos, el procedimiento es similar a un ordenamiento por mezcla (merge sort). Algoritmo 12 Funci´on auxiliar ensambla Entrada: elemento,lista1 ,lista2 1: listanueva = nueva (lista) 2: listanueva → elemento = elemento 3: listanueva → siguiente = union(lista1 , lista2 ) 4: devolver listanueva 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´ITULO 3. EL MODELO DE CONJUNTO DE DATOS

Algoritmo 13 Uni´on Listas Ordenadas Entrada: lista1 ,lista2 1: si lista1 == null y lista2 == null entonces 2: devolver null 3: si no, si lista1 == null entonces 4: devolver ensambla(lista2 → element, null, lista2 → siguiente) 5: si no, si lista2 == null entonces 6: devolver ensambla(lista1 → element, lista1 → siguiente , null) 7: si no, si lista1 → elemento == lista2 → elemento entonces 8: devolver ensambla(lista1 → element, lista1 → siguiente, lista2 → siguiente) 9: si no, si lista1 → elemento < lista2 → elemento entonces 10: devolver ensambla(lista1 → element, lista1 → siguiente, lista2 ) 11: si no 12: devolver ensambla(lista2 → element, lista1 , lista2 → siguiente) 13: fin si los conjuntos, adem´as 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 vac´ıas (l´ıneas 1 y 2) se terminan las llamadas recursivas porque no hay mas elementos a procesar. 2. Si una lista est´a vac´ıa y la otra no (l´ıneas 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 u ´ltimos 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 est´en 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 elementos del otro. Intersecci´on. El Algoritmo 14 denota el proceso de intersecci´on entre dos listas ordenadas, utiliza la funci´on ensambla (modificada) para crear la nueva

´ 3.1. DEFINICIONES BASICAS Y PRINCIPALES OPERACIONES CON CONJUNTOS73 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 (l´ıneas 3 y 4).

Algoritmo 14 Intersecci´on Listas Ordenadas Entrada: lista1 ,lista2 1: si lista1 == null o lista2 == null entonces 2: devolver null 3: si no, si lista1 → elemento == lista2 → elemento entonces 4: devolver ensambla(lista1 → element, lista1 → siguiente, lista2 → siguiente) 5: si no, si lista1 → elemento < lista2 → elemento entonces 6: devolver interseccion(lista1 → siguiente, lista2 ) 7: si no 8: devolver interseccion(lista1 , lista2 → siguiente) 9: fin si Diferencia. En el caso de la diferencia el Algoritmo 15 tiene las siguientes consideraciones: Cuando la primer lista (minuendo) est´a vac´ıa se termina la recursividad, 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´ITULO 3. EL MODELO DE CONJUNTO DE DATOS

Algoritmo 15 Diferencia Listas Ordenadas Entrada: lista1 ,lista2 1: si lista1 == null entonces 2: devolver null 3: si no, si lista2 == null entonces 4: devolver ensambla(lista1 → elemento, lista1 → siguiente, lista2 ) 5: si no, si lista1 → elemento == lista2 → elemento entonces 6: devolver diferencia(lista1 → siguiente, lista2 → siguiente) 7: si no, si lista1 → elemento < lista2 → elemento entonces 8: devolver ensambla(lista1 → elemento, lista1 → siguiente, lista2 ) 9: si no 10: devolver ensambla(lista1 → elemento, lista1 → siguiente, lista2 → siguiente) 11: fin si

Operaciones B´ asicas con Vectores Caracter´ısticos Cuando los conjuntos con los que se har´an operaciones son todos subconjuntos de un conjunto finito y de cardinalidad peque˜ na se puede hacer uso de vectores de n´ umeros binarios.

Cuadro 3.1: Equivalencia Operaciones Vectores Caracter´ısticos Operaci´on Uni´on Intersecci´on Resta

Equivalencia Ejemplo OR 001100 OR 111001 = 111101 AND 001100 AND 111001 = 001000 AND y NOT 001100 AND NOT(111001) = 000100

N´otese que la representaci´on de cada subconjunto tiene todos los elementos del conjunto “universo” y los elementos que pertenecen al subconjunto est´an “encendidos” (valor 1 o verdadero) y los que no son miembros estar´an “apagados” (valor 0 o falso). Esta es una forma eficiente de representar conjuntos en cuanto a velocidad, sin embargo, el tama˜ no puede llegar a ser un problema. El conjunto universo se representar´a en una estructura de datos separada.

´ 3.1. DEFINICIONES BASICAS Y PRINCIPALES OPERACIONES CON CONJUNTOS75 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 ...

x

h

a1

h(x)

a2

...

an

...

B-1

Figura 3.3: Tabla Hash

La funci´on 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 Funci´on Hash Letra Inicial Entrada: palabra 1: devolver numero( letraInicial(palabra) ) La funci´on hash es, quiz´a, la parte m´as importante de la implementaci´on 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´ITULO 3. EL MODELO DE CONJUNTO DE DATOS

Insertar, Eliminar y Buscar Los Algoritmos 17, 18 y 19 esbozan las funciones insertar, eliminar y buscar para una tabla hash. En general se obtiene la llave que corresponde a la entrada y posteriormente se realiza la operaci´on como si la lista seleccionada fuese el conjunto completo. Algoritmo 17 Funci´on Inserta en Tabla Hash Entrada: palabra 1: h = hash(palabra) 2: tabla[h]→inserta(palabra)

Algoritmo 18 Funci´on Eliminar de Tabla Hash Entrada: palabra 1: h = hash(palabra) 2: devolver tabla[h]→eliminar(palabra)

Algoritmo 19 Funci´on Buscar en Tabla Hash Entrada: palabra 1: h = hash(palabra) 2: devolver tabla[h]→buscar(palabra)

3.1.4.

Relaciones y Funciones

Hasta ahora se han utilizado elementos at´omicos (indivisibles) como miembros 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 llamar´an unaria para grado uno, binaria para grado dos, etc. Producto Cartesiano El producto cartesiano de dos conjuntos se define 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 BASICAS Y PRINCIPALES OPERACIONES CON CONJUNTOS77 Relaciones Binarias Una relaci´on 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 relaci´on R, n´otese 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 relaci´on de A a B donde los elementos del dominio se relacionan a lo m´as con un elemento del rango. Una funci´on (total) f es la relaci´on 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 funci´on es un conjunto de pares, esta se puede representar como una lista ligada. En general se definir´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 estar´a 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´ITULO 3. EL MODELO DE CONJUNTO DE DATOS

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 Programaci´ on

3.2.1.

´Indices invertidos

Un ´ındice invertido (tambi´en conocido como listas de posteo) es una estructura 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 datos, o en un documento o conjunto de documentos. El prop´osito 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 recuperaci´on de documentos. Ejemplo Dado el conjunto de textos A = {T0 , T1 , T2 } donde T0 =”compro paco pocas copas” T1 =”y como pocas copas compro”’, T2 =”pocas copas paco pago”, se obtiene el siguiente ´ındice invertido: Palabra compro paco pocas copas y como pago

ocurrencias 0,1 0,2 0,1,2 0,1,2 1 1 2

´ 3.2. PROYECTO DE PROGRAMACION

79

La b´ usqueda de las palabra paco, pocas y pago regresar´ıa 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 T0 y T2 , pero solo aparece en le orden el mismo orden en T2 .

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 pel´ıculas, etc) y crear su archivo de ´ındice invertido (En est´a parte tendr´an que procesar los documentos para generar los ´ındices). 3. Implementar b´ usqueda utilizando intersecci´on de conjuntos 4. Proporcionar una interfaz para hacer consultas Reporte t´ ecnico Presentar un reporte t´ecnico de su trabajo el cu´al deber´a incluir los siguientes apartados. 1. Portada 2. Introducci´on. 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 implementaci´on de la b´ usqueda. 4. Conclusiones. Utilidad de lo que se hizo. Como se puede mejorar?

80

CAP´ITULO 3. EL MODELO DE CONJUNTO DE DATOS

Cap´ıtulo 4 El modelo de datos de ´ arboles En muchas ocasiones la informaci´on tiene una estructura jer´arquica o anidada, como los a´rboles familiares o diagramas organizacionales. La estructura 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.

Terminolog´ıa B´ asica

Los a´rboles son un conjunto de puntos y l´ıneas, llamados nodos y ejes respectivamente. Para formar un a´rbol 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 podr´a tener varios padres. Los hijos de un mismo padre se conocen como hermanos.

R N1 N3

N2 N4

N5

´ 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 ra´ız, se denota R en la Figura 4.1. Los nodos N3 , N4 y N5 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 ra´ız.

4.1.1.

Definici´ on Recursiva

Es posible determinar un ´arbol mediante una definici´on inductiva que construye a´rboles grandes a partir de peque˜ nos. Base Sea n la ra´ız de un a´rbol con un u ´nico nodo. Inducci´ on Sea r un nodo nuevo y T1 , T2 , . . . , Tn a´rboles con ra´ıces c1 , c2 , . . . , cn respectivamente. Se requiere que ning´ un nodo se repita en los ´arboles Ti , dado que r es un nodo nuevo, tampoco estar´a en alguno de los a´rboles existentes. Se formar´a un nuevo ´arbol de la siguiente manera: a) Sea r la ra´ız del ´arbol T . b) Agregar ejes que conecten cada uno de los nodos c1 , c2 , . . . , cn a r, con lo que se hace a r la ra´ız de cada Ti .

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 relaci´on de un nodo a su padre, y este a su padre, y este u ´ltimo a su padre y as´ı sucesivamente. La relaci´on descendiente es la inversa de la de antecesor. Supongase que m1 , m2 , . . . , mk son una secuencia de nodos donde el nodo mi es padre del nodo mi+1 , se conoce a esta secuencia como la ruta de m1 a mk y tiene una longitud de k − 1. Si m1 , m2 , . . . , mk es una ruta de un ´arbol, entonces m1 es un antecesor propio de mk , similarmente mk es un descendiente propio de m1 . 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 ra´ız es el antecesor de todos los nodos en el a´rbol y cada uno de estos nodos ser´a su descendiente.

´ 4.1. TERMINOLOG´IA BASICA

4.1.3.

83

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 a´rbol, 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 ra´ız. La profundidad de un nodo n es la distancia entre la ra´ız 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 x

n 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´ITULO 4. EL MODELO DE DATOS DE ARBOLES

como el texto completo de un documento. La etiqueta de un nodo puede ser modificada, 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 aritm´eticas pueden ser representadas mediante ´arboles etiquetados, de hecho, un ´arbol de expresi´on especifica la asociaci´on entre operadores y operandos en una forma consistente. Se puede definir un ´arbol de expresiones como sigue: Base Un operando at´omico es una expresi´on y el a´rbol que la representa es un nodo cuya etiqueta es el mismo operando. Inducci´ on Sean E1 y E2 expresiones representadas por los ´arboles T1 y T2 , respectivamente. Entonces la expresi´on (E1 + E2 ) se representar´a con un a´rbol cuya ra´ız ser´a un nodo con etiqueta + con hijos T1 y T2 , como se ve en la figura 4.3. De forma similar las expresiones (E1 + E2 ), (E1 + E2 ) y (E1 + E2 ), es decir, se definir´an por un ´arbol cuya ra´ız 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 ra´ız y conectado a la ra´ız del ´arbol que representa al operando.

+ T1

T2

Figura 4.3: (E1 + E2 )

´ 4.2. ESTRUCTURAS DE DATOS PARA ARBOLES

4.2.

85

´ Estructuras de Datos para Arboles

Existen distintas formas de representar ´arboles en una estructura de datos, esto depender´a, mayormente, de las necesidades del programa. Por ejemplo, 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 mayor´ıa 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 m´ as 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 m´as 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 u ´til incluir en la estructura de cada nodo un apuntador hacia el padre, dado que el nodo ra´ız no tiene padre, el apuntador ser´a nu-

86

´ CAP´ITULO 4. EL MODELO DE DATOS DE 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 ra´ız. Para saber cuando se ha llegado a la ra´ız 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 a´rboles es la facilidad de escribir funciones recursivas de manera “limpia”. La figura 4.4 representa a un ´arbol con ra´ız n y sub-´arboles T1 , T2 , . . . Tn que a su vez tienen ra´ıces c1 , c2 , . . . cn .

n c1

c1

T1

T2

...

cn

Tn

´ 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 c1 , luego har´a otros pasos, despu´es se ejecuta

´ EN ARBOLES ´ 4.3. RECURSION

87

nuevamente la funci´on para el nodo c2 y as´ı sucesivamente. Un ejemplo se puede ver en el algoritmo 26. Algoritmo 26 Recursividad en ´arboles - F(n) Entrada: nodo n 1: pasos1 2: F(c1 ) 3: pasos2 4: F(c2 ) . 5: .. 6: 7: 8:

pasosn F(cn ) 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 evaluaci´on en preorden, lo que se hace es realizar las operaciones relacionadas al nodo actual primero y despu´es hacer una llamada recursiva con los nodos hermanos como par´ametro. A diferencia de la ejecuci´on en preorden, la evaluaci´on en posfijo primero hace la llamada recursiva con los hermanos para despu´es realizar las operaciones concernientes al nodo actual. A continuaci´on se presenta la prueba inductiva de la evaluaci´on de un a´rbol. 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 representada por el sub-´arbol con ra´ız n. Se evaluar´an las sub-expresiones representadas por los sub-´arboles cuyas ra´ıces son los hijos c1 y c2 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´ITULO 4. EL MODELO DE DATOS DE ARBOLES

Evaluaci´ on en Preorden y Postorden Para entender mejor los tipos evaluaci´on se seguir´an los Algoritmos 27 y 28 sobre el a´rbol representado por la Figura 4.5. La evaluaci´on hecha al nodo ser´a simplemente imprimir el valor de la etiqueta del nodo.

+

*

a

_ b

d c

´ Figura 4.5: Arbol ejemplo evaluaci´on preorden y postorden - a+(b-c)*d

Algoritmo 27 Evaluaci´on 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: fin mientras La evaluaci´on en preorden, como se ve en la tabla 4.1, da como resultado la expresi´on “+a*-bcd”. En esta ocasi´on (tabla 4.2) siendo evaluaci´on en postorden se genera la expresi´on “abc-d*+”.

´ EN ARBOLES ´ 4.3. RECURSION

89

Cuadro 4.1: Evaluaci´on en Preorden No. Resultado Operaci´on 1 preorden(+) 2 + imprimir(+) 3 preorden(a) 4 a imprimir(a) 5 preorden(*) 6 * imprimir(*) 7 preorden(-) 8 imprimir(-)

No. 9 10 11 12 13 14

Resultado Operaci´on preorden(b) b imprimir(b) preorden(c) c imprimir(c) preorden(d) d imprimir(d)

Algoritmo 28 Evaluaci´on 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: fin mientras 6: evaluacion(n)

Cuadro 4.2: Evaluaci´on en postorden No. Resultado Operaci´on 1 posfijo(+) 2 posfijo(a) 3 a imprimir(a) 4 posfijo(*) 5 posfijo(-) 6 posfijo(b) 7 b imprimir(b) 8 posfijo(c)

No. Resultado Operaci´on 9 c imprimir(c) 10 imprimir(-) 11 posfijo(d) 12 d imprimir(d) 13 * imprimir(*) 14 + imprimir(+)

90

´ CAP´ITULO 4. EL MODELO DE DATOS DE ARBOLES

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

4.4.

´ Arboles Binarios

Anteriormente se estudiaron a´rboles con n-cantidad de hijos, existe una clase especial de a´rboles que solo tiene un par de “espacios” para alojar hijos. A este tipo de a´rboles se les conoce como ´arboles binarios. Llamaremos a sus hijos como izquierdo y derecho, y cualquiera puede ser nulo. La definici´on recursiva para ´arboles binarios es la siguiente: Base El ´arbol vac´ıo (sin nodos) es un a´rbol binario. Inducci´ on Sea r un nodo y T1 y T2 a´rboles binarios, existe un ´arbol binario con r como ra´ız, con sub-´arbol izquierdo T1 y sub-´arbol derecho T2 . La ra´ız del sub-´arbol T1 es el hijo izquierdo de r, a menos que T1 est´e vac´ıo, en cuyo caso r no tendr´a hijo izquierdo. De manera similar el nodo ra´ız del sub-´arbol T2 es el hijo derecho de r, a menos que T2 est´e vac´ıo, en cuyo caso r no tendr´a hijo derecho. Es importante notar que los a´rboles binarios tienen sus hijos ordenados (por izquierdo y derecho), lo que no necesariamente es cierto para los a´rboles 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 BUSQUEDA BINARIOS

4.4.2.

91

´ Recursi´ on sobre Arboles Binarios

Debido a que los apuntadores a hijos de un nodo en un ´arbol binario tienen cierto orden, el recorrido del a´rbol ´ Algoritmo 30 Recursi´on Arbol Binario Entrada: nodo . 1: .. 2: recursion(hijoIzquierdo) . 3: .. recursion(hijoDerecho) . 5: .. 4:

4.4.3.

Recurridos en Orden

En los ´arboles binarios, adem´as 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 despu´es de hacer la llamada recursiva al hijo izquierdo, pero antes de llamar al hijo derecho. Recorriendo de esta manera el a´rbol se obtiene una expresi´on muy cercana a la expresi´on en infijo, para la Figura 4.5 se obtiene “a+b-c*d” a la cual solo le hace falta un par de par´entesis “a+(b-c)*d”. Algoritmo 31 Evaluaci´on 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 verificador de ortograf´ıa se desear´ıa 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

´ CAP´ITULO 4. EL MODELO DE DATOS DE ARBOLES

92

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 deber´an poder guardar una relaci´on de “menor que”, como los n´ umeros enteros, reales u el orden lexicogr´afico. Un a´rbol 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 Binarios

Para la implementaci´on se utilizar´a la estructura descrita en el algoritmo 29, la implementaci´on de las operaciones requeridas para el diccionario se detallar´an a continuaci´on. Algoritmo 32 Inserta en a´rbol 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: fin si 8: devolver nodo

´ ´ 4.5. ARBOLES DE BUSQUEDA BINARIOS

Algoritmo 33 Buscar en a´rbol binario Entrada: dato, nodo 1: si nodo es nulo entonces 2: devolver nulo 3: fin si 4: si dato es igual a nodo entonces 5: devolver nodo 6: fin si 7: si dato es menor a nodo entonces 8: buscar(dato, nodo → izquierda) 9: si no 10: buscar(dato, nodo → derecha) 11: fin si

Algoritmo 34 Eliminar en a´rbol binario Entrada: dato, nodo 1: si nodo es nulo entonces 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: fin si 15: fin si 16: fin si 17:

93

´ CAP´ITULO 4. EL MODELO DE DATOS DE ARBOLES

94

4.6. 4.6.1.

´ Colas de Prioridad y Arboles Parcialmente Ordenados 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 eficiente de implementar las colas de prioridad es mediante los llamados ´arboles parcialmente ordenados (POT por sus siglas en ingl´es), el cual deber´a 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 ra´ız 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 posible en el a´rbol 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 refiere a intercambiar valores entre padre e hijo cumpliendo la segunda condicionante. Siempre se eliminar´a el nodo ra´ız, para llevar esto a cabo se remplaza su contenido con el del nodo m´as a la derecha del u ´ltimo nivel. Al igual que en la inserci´on seguramente se violar´a la segunda condici´on, as´ı que se “empujar´a” hac´ıa abajo el nuevo nodo ra´ız.

´ 4.6. COLAS DE PRIORIDAD Y ARBOLES PARCIALMENTE ORDENADOS95

4.6.3.

POTs Balanceados y Mont´ıculos (Heaps)

Se dice que un POT est´a completo si todos los niveles, excepto el u ´ltimo, tienen sus hijos completos; el ´arbol estar´a balanceado si est´a completo y sus hojas est´an lo m´as a la izquierda posible. Un ´arbol parcialmente ordenado se puede implementar mediante una estructura de datos basada en un arreglo llamada mont´ıculo o heap.

l2 Nive

Nive

Raíz

l1

Un heap es un arreglo A con una interpretaci´on particular de sus indices, se comienza desde A [1] que ser´ıa la ra´ız (A [0] no se utiliza). El siguiente nivel de nodos utilizar´a dos espacios en el arreglo, el siguiente 4 y as´ı sucesivamente. En cada nivel los nodos estar´an ordenados de izquierda a derecha, por ejemplo el hijo izquierdo de la ra´ız sera A [2] y el derecho A [3]. En general, el hijo izquierdo del nodohjA ki [i] ser´a A [2i] y el derecho A [2i + 1]. El padre de i un elemento A [i] ser´a A 2

A0 A1 A2 A3 A4 A5 A6 A7

...

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 m´as 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 a´rboles parcialmente ordenados (algoritmo 36).

´ CAP´ITULO 4. EL MODELO DE DATOS DE ARBOLES

96

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 tambi´en llamada heapif y), posteriormente se mueven los elementos m´as grandes del heap al final del arreglo hasta llegar a tener el m´as peque˜ no al inicio.

Heap en Iteración i 1

Arreglo Ordenado i

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: fin 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 (l´ınea 1 del algoritmo 38) toma un tiempo O (log n), por lo que el heapsort ser´a O (n log 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: fin para

4.8.

Ejercicios

1. Dibuje el a´rbol 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 figura 2) con etiqueta J (dibuje los a´rboles intermedios). J

C

E

A

D

B

3. Dibuje a´bol resultante de aplicar una rotaci´on derecha y dos izquierdas sobre el nodo con etiqueta J (ver figura 2) . 4. Proporcione un algoritmo que dada la ra´ız de un ´arbol, regrese el n´ umero de nodos que hay en el ´arbol. 5. Proporcione un algoritmo para realizar una doble rotaci´on izquierda sobre un nodo. 6. Proporciones un algoritmo para realizar una doble rotaci´on 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 a´rbol binario, dibujar el a´rbol binario. ¿Como obtendr´ıa el recorrido preorden sin necesidad de dibujar el ´arbol?

98

´ CAP´ITULO 4. EL MODELO DE DATOS DE ARBOLES 9. Proporcione un algoritmo para obtener el recorrido en preorden de un a´rbol binario a partir de los recorridos enroden y postorden.

10. Dibuje los estados del heap que seguir´ıa el m´etodo heapsort para la siguiente secuencia 3 2 7 4 9 1 5. 11. De manera similar a como en clases definimos un Heap, se puede definir 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 m´etodos de inserci´on y borrado. Finalmente implemente un heapsort que regrese un arreglo ordenado en forma descendente

Cap´ıtulo 5 Teor´ıa y algoritmos de grafos

99