Estructuras de datos y algoritmos / Mark Allen Weiss.

CONTENIDO
1 Introducción 1
1.1. ¿De qué trata este libro? 1
1.2. Repaso de matemáticas 3
1.2.1. Exponentes 3
1.2.2. Logaritmos 3
1.2.3. Series 4
1.2.4. Aritmética modular 6
1.2.5. La palabra con D 6
1.3. Breve introducción a la recursión 9
Resumen 13
Ejercicios 13
Referencias 15
2 Análisis de algoritmos 17
2.1. Soporte matemático 17
2.2. Modelo 20
2.3. Qué analizar 20
2.4. Cálculo del tiempo de ejecución 22
2.4.1. Un ejemplo sencillo 23
2.4.2. Reglas generales 24
2.4.3. Soluciones al problema de la suma de la subsecuencia máxima 26
2.4.4. Logaritmos en el tiempo de ejecución 32
2.4.5. Verificación del análisis 37
2.4.6. Un grano de sal 38
Resumen 39
Ejercicios 39
Referencias 44
3 Listas, pilas y colas 45
3.1. Tipos de datos abstractos (TDA) 45
3.2. El TDA lista 46
3.2.1. Implantación de listas a base de arreglos sencillos 47
3.2.2. Listas enlazadas 47
3.2.3. Detalles de programación 48
3.2.4. Errores comunes 54
3.2.5. Listas doblemente enlazadas 56
3.2.6. Listas enlazadas circularmente 56
3.2.7. Ejemplos 57
3.2.8. Implantación de listas enlazadas a base de cursores 62
3.3. El TDA pila 66
3.3.1. El modelo pila 66
3.3.2. Implantación de pilas 68
3.3.3. Aplicaciones 74
3.4. El TDA cola 83
3.4.1. El modelo cola 83
3.4.2. Implantación de colas a base de arreglos 83
3.4.3. Aplicaciones de colas 87
Resumen 88
Ejercicios 88
4 Árboles 93
4.1. Preliminares 93
4.1.1. Implantación de árboles 95
4.1.2. Recorridos de árboles con una aplicación 95
4.2. Árboles binarios 100
4.2.1. Implantación 100
4.2.2. Árboles de expresión 101
4.3. El tda árbol de búsqueda: Árboles binarios de búsqueda 105
4.3.1. Crear_vacío 106
4.3.2. Buscar 106
4.3.3. Buscar_mín y buscar_máx 107
4.3.4. Insertar 108
4.3.5. Eliminar 109
4.3.6. Análisis del caso promedio 111
4.4. Árboles AVL 114
4.4.1. Rotación sencilla 116
4.4.2. Rotación doble 119
4.5. Árboles desplegados 126
4.5.1. Una idea sencilla (que no funciona) 127
4.5.2. Despliege 129
4.6. Recorridos de árboles (de nuevo) 137
4.7. Árboles-B 139
Resumen 144
Ejercicios 145
Referencias 152
5 Dispersión 155
5.1. Idea general 155
5.2. Función de dispersión 156
5.3. Dispersión abierta (encadenamiento separado) 159
5.4. Dispersión cerrada (direccionamiento abierto) 162
5.4.1. Exploración lineal 162
5.4.2. Exploración cuadrática 165
5.4.3. Dispersión doble 168
5.5. Redispersión 170
5.6. Dispersión extensible 172
Resumen 175
Ejercicios 176
Referencias 179
6 Colas de prioridad (montículos) 181
6.1. Modelo 182
6.2. Implantaciones simples 182
6.3. Montículo binario 183
6.3.1. Propiedad de la estructura 183
6.3.2. Propiedad de orden de montículo 184
6.3.3. Operaciones básicas sobre montículos 185
6.3.4. Otras operaciones sobre montículos 189
6.4. Aplicaciones de las colas de prioridad 194
6.4.1. El problema de la selección 194
6.4.2. Simulación de eventos 196
6.5. Montículos-d 197
6.6. Montículos a izquierda 198
6.6.1. Propiedad de montículo a izquierda 198
6.6.2. Operaciones sobre montículos a izquierda 200
6.7. Montículos oblicuos 205
6.8. Colas binomiales 207
6.8.1. Estructura de cola binomial 208
6.8.2. Operaciones sobre colas binomiales 209
6.8.3. Implantación de colas binomiales 213
Resumen 216
Ejercicios 216
Referencias 221
7 Ordenación 221
7.1. Preliminares 224
7.2. Ordenación por inserción 224
7.2.1. El algoritmo 224
7.2.2. Análisis de la ordenación por inserción 225
7.3. Una cota inferior para algoritmos de ordenación simples 225
7.4. Ordenación de Shell 227
7.4.1. Análisis del peor caso de la ordenación de Shell 228
7.5. Ordenación por montículo 231
7.6. Ordenación por intercalación 233
7.6.1. Análisis de la ordenación por intercalación 236
7.7. Ordenación rápida 240
7.7.1. Selección del pivote 241
7.7.2. Estrategia de partición 242
7.7.3. Archivos pequeños 245
7.7.4. Rutinas reales de ordenación rápida 245
7.7.5. Análisis de la ordenación rápida 247
7.7.6. Un algoritmo de selección con un tiempo esperado lineal 251
7.8. Ordenación de registros grandes 252
7.9. Una cota inferior general para la ordenación 253
7.9.1. Árboles de decisión 253
7.10. Ordenación por cubetas 255
7.11. Ordenación externa 256
7.11.1. ¿Por qué necesitamos algoritmos nuevos? 256
7.11.2. Modelo para ordenación externa 257
7.11.3. El algoritmo sencillo 257
7.11.4. Intercalación de vías múltiples 258
7.11.5. Intercalación polifásica 260
7.11.6. Selección de sustitución 261
Resumen 262
Ejercicios 263
Referencias 267
8 El TDA conjunto ajeno 271
8.1. Relaciones de equivalencia 271
8.2. El problema de la equivalencia dinámica 272
8.3. Estructura de datos básica 274
8.4. Algoritmos de unión refinados 277
8.5. Compresión de caminos 280
8.6. Peor caso de la unión por rangos y compresión de caminos 281
8.6.1. Análisis del algoritmo unión/búsqueda 282
8.7. Una aplicación 288
Resumen 289
Ejercicios 289
Referencias 291
9 Algoritmos de grafos 293
9.1. Definiciones 293
9.1.1. Representación de grafos 294
9.2. Ordenación topológica 296
9.3. Algoritmos del camino más corto 300
9.3.1. Caminos más cortos no ponderados 302
9.3.2. Algoritmo de Dijkstra 308
9.3.3. Grafos con aristas de costo negativo 315
9.3.4. Grafos acíclicos 316
9.3.5. Camino más corto entre todos los pares 320
9.4. Problemas de flujo en redes 320
9.4.1. Un algoritmo simple de flujo máximo 321
9.5. Árbol de extensión mínimo 325
9.5.1. Algoritmo de Prim 326
9.5.2. Algoritmo de Kruskal 330
9.6. Aplicaciones de la búsqueda en profundidad 332
9.6.1. Grafos no dirigidos 333
9.6.2. Biconectividad 334
9.6.3. Circuitos de Euler 338
9.6.4. Grafos dirigidos 342
9.6.5. Localización de componentes fuertes 344
9.7. Introducción a la compleción NP 346
9.7.1. Fácil vs. difícil 346
9.7.2. La clase NP 347
9.7.3. Problemas NP completos 348
Resumen 351
Ejercicios 351
Referencias 357
10 Técnicas de diseño de algoritmos 361
10.1. Algoritmos ávidos 361
10.1.1. Un problema simple de planificación 362
10.1.2. Códigos de Huffman 366
10.1.3. Empaquetamiento aproximado en recipientes 372
10.2. "Divide y vencerás" 381
10.2.1. Tiempo de ejecución de algoritmos de "divide y vencerás" 382
10.2.2. El problema de los puntos más cercanos 385
10.2.3. El problema de la selección 389
10.2.4. Mejoras teóricas para problemas de aritmética 393
10.3. Programación dinámica 397
10.3.1. Uso de una tabla en vez de la recursión 397
10.3.2. Ordenación de multiplicaciones de matrices 400
10.3.3. Árbol binario de búsqueda óptimo 402
10.3.4. Camino más corto entre todos los pares 407
10.4. Algoritmos aleatorizados 409
10.4.1. Generadores de números aleatorios 410
10.4.2. Listas con saltos 414
10.4.3. Comprobación de primalidad 417
10.5. Algoritmos con retroceso 418
10.5.1. El problema de la reconstrucción del camino de cuota 420
10.5.2. Juegos 425
Resumen 432
Ejercicios 432
Referencias 440
11 Análisis amortizado 445
11.1. Un acertijo no relacionado 446
11.2. Colas binomiales 446
11.3. Montículos oblicuos 452
11.4. Montículos de Fibonacci 454
11.4.1. Corte de nodos en montículo a izquierda 455
11.4.2. Fusión perezosa de colas binomiales 458
11.4.3. Las operaciones del montículo de Fibonacci 461
11.4.4. Demostración de la cota del tiempo 463
11.5. Arboles desplegados 465
Resumen 469
Ejercicios 470
Referencias 471
Vocabulario técnico bilingue 473
Indice de materias 479