PDF de programación - Algoritmos y Estructuras de Datos

Algoritmos y Estructuras de Datos

Bottazzi, Cristian. [email protected],
Costarelli, Santiago. [email protected],

D’Elía, Jorge. [email protected],

Dalcin, Lisandro. [email protected],
Galizzi, Diego. [email protected],

Giménez, Juan Marcelo. [email protected],

Olivera, José. [email protected],
Novara, Pablo. zaskar [email protected],
Paz, Rodrigo. [email protected],
Prigioni, Juan. [email protected],

Pucheta, Martín. [email protected],

Rojas Fredini, Pablo Sebastián. [email protected],

Romeo, Lautaro. [email protected] ,
Storti, Mario. [email protected],

www: http://www.cimec.org.ar/aed

Facultad de Ingeniería y Ciencias Hídricas

Universidad Nacional del Litoral http://fich.unl.edu.ar

Centro de Investigación de Métodos Computacionales

http://www.cimec.org.ar

Indice

1. Dise ño y análisis de algoritmos

13
1.1. Conceptos básicos de algoritmos . . . . . . . . . . . . . . . . 13

1.1.1. Ejemplo: Sincronización de acceso a objetos en cálculo

distribuido . . . . . . . . . . . . . . . . . . . . . . . . 14
Introducción básica a grafos . . . . . . . . . . . . . . . 16
1.1.2.
1.1.3. Planteo del problema mediante grafos
. . . . . . . . . 17
1.1.4. Algoritmo de búsqueda exhaustiva . . . . . . . . . . . 18
1.1.5. Generación de las coloraciones . . . . . . . . . . . . . 19
1.1.6. Crecimiento del tiempo de ejecución . . . . . . . . . . 22
1.1.7. Búsqueda exhaustiva mejorada . . . . . . . . . . . . . 23
1.1.8. Algoritmo heurístico ávido . . . . . . . . . . . . . . . . 26
1.1.9. Descripción del algoritmo heurístico en seudo-código . 29
1.1.10. Crecimiento del tiempo de ejecución para el algoritmo

ávido . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.1.11. Conclusión del ejemplo . . . . . . . . . . . . . . . . . 36
1.2. Tipos abstractos de datos . . . . . . . . . . . . . . . . . . . . 37

1.2.1. Operaciones abstractas y características del TAD

1.2.2.
1.2.3.

CONJUNTO . . . . . . . . . . . . . . . . . . . . . . . 38
Interfaz del TAD CONJUNTO . . . . . . . . . . . . . . 38
Implementación del TAD CONJUNTO . . . . . . . . . . 40
1.3. Tiempo de ejecución de un programa . . . . . . . . . . . . . . 41
1.3.1. Notación asintótica . . . . . . . . . . . . . . . . . . . . 43
Invariancia ante constantes multiplicativas . . . . . . . 45
1.3.2.
Invariancia de la tasa de crecimiento ante valores en
1.3.3.
un conjunto finito de puntos . . . . . . . . . . . . . . . 45
1.3.4. Transitividad . . . . . . . . . . . . . . . . . . . . . . . 45
1.3.5. Regla de la suma . . . . . . . . . . . . . . . . . . . . . 46
1.3.6. Regla del producto . . . . . . . . . . . . . . . . . . . . 46

3

1.3.7. Funciones típicas utilizadas en la notación asintótica . . 46
1.3.8. Equivalencia . . . . . . . . . . . . . . . . . . . . . . . 48
1.3.9. La función factorial . . . . . . . . . . . . . . . . . . . . 48
1.3.10. Determinación experimental de la tasa de crecimiento . 50
1.3.11. Otros recursos computacionales . . . . . . . . . . . . . 51
1.3.12. Tiempos de ejecución no-polinomiales . . . . . . . . . 52
1.3.13. Problemas P y NP . . . . . . . . . . . . . . . . . . . . 52
1.3.14. Varios parámetros en el problema . . . . . . . . . . . . 53
1.4. Conteo de operaciones para el cálculo del tiempo de ejecución 54
1.4.1. Bloques if . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.4.2. Lazos . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.4.3. Suma de potencias . . . . . . . . . . . . . . . . . . . . 60
1.4.4. Llamadas a rutinas . . . . . . . . . . . . . . . . . . . . 60
1.4.5. Llamadas recursivas . . . . . . . . . . . . . . . . . . . 60

2. Tipos de datos abstractos fundamentales

65
2.1. El TAD Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2.1.1. Descripción matemática de las listas . . . . . . . . . . 66
2.1.2. Operaciones abstractas sobre listas . . . . . . . . . . . 67
2.1.3. Una interfaz simple para listas . . . . . . . . . . . . . . 68
2.1.4. Funciones que retornan referencias . . . . . . . . . . . 71
2.1.5. Ejemplos de uso de la interfaz básica . . . . . . . . . . 73
Implementación de listas por arreglos . . . . . . . . . . 78
2.1.6.
2.1.6.1. Eficiencia de la implementación por arreglos . 84
Implementación mediante celdas enlazadas por punteros 85
2.1.7.1. El tipo posición . . . . . . . . . . . . . . . . . 87
2.1.7.2. Celda de encabezamiento . . . . . . . . . . . 88
2.1.7.3. Las posiciones begin() y end() . . . . . . . 91
2.1.7.4. Detalles de implementación . . . . . . . . . . 91
Implementación mediante celdas enlazadas por cursores 93
2.1.8.1. Cómo conviven varias celdas en un mismo

2.1.7.

2.1.8.

espacio . . . . . . . . . . . . . . . . . . . . . 95
2.1.8.2. Gestión de celdas . . . . . . . . . . . . . . . 96
2.1.8.3. Analogía entre punteros y cursores . . . . . . 97

2.1.9. Tiempos de ejecución de los métodos en las diferentes

implementaciones.

. . . . . . . . . . . . . . . . . . . . 100
2.1.10. Interfaz STL . . . . . . . . . . . . . . . . . . . . . . . 102
2.1.10.1. Ventajas de la interfaz STL . . . . . . . . . . . 102
2.1.10.2. Ejemplo de uso . . . . . . . . . . . . . . . . . 103

2.1.10.2.1. Uso de templates y clases anidadas . 104
2.1.10.2.2. Operadores de incremento prefijo y

postfijo:

. . . . . . . . . . . . . . . . 104
2.1.10.3. Detalles de implementación . . . . . . . . . . 105
2.1.10.4. Listas doblemente enlazadas . . . . . . . . . 108
2.2. El TAD pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
2.2.1. Una calculadora RPN con una pila . . . . . . . . . . . 110
2.2.2. Operaciones abstractas sobre pilas . . . . . . . . . . . 111
2.2.3.
Interfaz para pila . . . . . . . . . . . . . . . . . . . . . 111
Implementación de una calculadora RPN . . . . . . . . 112
2.2.4.
Implementación de pilas mediante listas
2.2.5.
. . . . . . . . 116
2.2.6. La pila como un adaptador . . . . . . . . . . . . . . . . 118
2.2.7.
Interfaz STL . . . . . . . . . . . . . . . . . . . . . . . 118
2.3. El TAD cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Intercalación de vectores ordenados
. . . . . . . . . . 120
2.3.1.1. Ordenamiento por inserción . . . . . . . . . . 120
2.3.1.2. Tiempo de ejecución . . . . . . . . . . . . . . 123
2.3.1.3. Particularidades al estar las secuencias pares

2.3.1.

e impares ordenadas . . . . . . . . . . . . . . 123
2.3.1.4. Algoritmo de intercalación con una cola auxiliar 124
2.3.2. Operaciones abstractas sobre colas . . . . . . . . . . . 126
Interfaz para cola . . . . . . . . . . . . . . . . . . . . . 126
2.3.3.
Implementación del algoritmo de intercalación de vec-
2.3.4.
tores . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
2.3.4.1. Tiempo de ejecución . . . . . . . . . . . . . . 128
2.4. El TAD correspondencia . . . . . . . . . . . . . . . . . . . . . 129
. . . . . . . . . 131

2.4.1.
2.4.2.

Interfaz simple para correspondencias
Implementación de correspondencias mediante conte-
nedores lineales . . . . . . . . . . . . . . . . . . . . . 134
Implementación mediante contenedores lineales orde-
nados . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Implementación mediante listas ordenadas . . 138
2.4.3.1.
2.4.3.2.
Interfaz compatible con STL . . . . . . . . . . 140
2.4.3.3. Tiempos de ejecución para listas ordenadas . 144
Implementación mediante vectores ordenados 144
2.4.3.4.
2.4.3.5. Tiempos de ejecución para vectores ordenados148
2.4.4. Definición de una relación de orden . . . . . . . . . . . 148

2.4.3.

3. Arboles

3.1. Nomenclatura básica de árboles

151
. . . . . . . . . . . . . . . . 151
3.1.0.0.1. Altura de un nodo.
. . . . . . . . . . 154
3.1.0.0.2. Profundidad de un nodo. Nivel. . . . . 154
3.1.0.0.3. Nodos hermanos . . . . . . . . . . . 154
3.2. Orden de los nodos . . . . . . . . . . . . . . . . . . . . . . . 154
3.2.1. Particionamiento del conjunto de nodos . . . . . . . . . 156
3.2.2. Listado de los nodos de un árbol
. . . . . . . . . . . . 157
3.2.2.1. Orden previo . . . . . . . . . . . . . . . . . . 157
3.2.2.2. Orden posterior . . . . . . . . . . . . . . . . . 158
3.2.2.3. Orden posterior y la notación polaca invertida 159
3.2.3. Notación Lisp para árboles . . . . . . . . . . . . . . . . 160
3.2.4. Reconstrucción del árbol a partir de sus órdenes . . . . 161
3.3. Operaciones con árboles . . . . . . . . . . . . . . . . . . . . 164
3.3.1. Algoritmos para listar nodos . . . . . . . . . . . . . . . 164
Inserción en árboles . . . . . . . . . . . . . . . . . . . 165
3.3.2.
3.3.2.1. Algoritmo para copiar árboles . . . . . . . . . 166
3.3.3. Supresión en árboles
. . . . . . . . . . . . . . . . . . 169
3.3.4. Operaciones básicas sobre el tipo árbol . . . . . . . . . 170
Interfaz básica para árboles . . . . . . . . . . . . . . . . . . . 170
3.4.1. Listados en orden previo y posterior y notación Lisp . . 174
3.4.2. Funciones auxiliares para recursión y sobrecarga de

3.4.

3.5.

3.6.

funciones . . . . . . . . . . . . . . . . . . . . . . . . . 175
3.4.3. Algoritmos de copia . . . . . . . . . . . . . . . . . . . 176
3.4.4. Algoritmo de poda . . . . . . . . . . . . . . . . . . . . 176
Implementación de la interfaz básica por punteros . . . . . . . 176
. . . . . . . . . . . . . . . . . . . . . . 177
3.5.1. El tipo iterator
3.5.2. Las clases cell e iterator t
. . . . . . . . . . . . . . . . 179
3.5.3. La clase tree . . . . . . . . . . . . . . . . . . . . . . . 183
Interfaz avanzada . . . . . . . . . . . . . . . . . . . . . . . . 186
3.6.1. Ejemplo de uso de la interfaz avanzada . . . . . . . . . 191
3.7. Tiempos de ejecución . . . . . . . . . . . . . . . . . . . . . . 194
3.8. Arboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . 194
3.8.1. Listados en orden simétrico . . . . . . . . . . . . . . . 195
3.8.2. Notación Lisp . . . . . . . . . . . . . . . . . . . . . . . 195
Árbol binario lleno . . . . . . . . . . . . . . . . . . . . 196
3.8.3.
3.8.4. Operaciones b´