CONTENIDO
Capítulo 1: Diseño y análisis de algoritmos
De los problemas a los programas 1
Tipos de datos abstractos 10
Tipos de datos, estructuras de datos y tipos de datos abstractos 13
Tiempo de ejecución de un programa 16
Cálculo del tiempo de ejecución de un programa 21
Buenas prácticas de programación 28
Súper Pascal 30
Capítulo 2: Tipos de datos abstractos fundamentales
El tipo de datos abstracto lista 38
Realización de listas 41
Pilas 53
Colas 57
Correspondencias 61
Pilas y procedimientos recursivos 65
Capítulo 3: Arboles
Terminología fundamental 76
El TDA ARBOL 83
Realizaciones de árboles 85
Arboles binarios 94
Capítulo 4: Operaciones básicas con conjuntos
Introducción a los conjuntos 107
Un TDA con UNION, INTERSECCION y DIFERENCIA 110
Realización de conjuntos mediante vectores de bits 113
Realización de conjuntos mediante listas enlazadas 115
El diccionario 118
Realizaciones sencillas de diccionarios 120
La estructura de datos tabla de dispersión 122
Estimación de la eficiencia de las funciones de dispersión 129
Realización del TDA CORRESPONDENCIA 136
Colas de prioridad 137
Realización de colas de prioridad 139
Algunas estructuras complejas de conjuntos 146
Capítulo 5: Métodos avanzados de representación de conjuntos
Arboles binarios de búsqueda 157
Análisis en tiempo de las operaciones para árboles binarios de búsqueda 161
Tries 165
Realización de conjuntos con árboles balanceados 171
Conjuntos con las operaciones COMBINA y ENCUENTRA 182
TDA con COMBINA y DIVIDE 191
Capítulo 6: Grafos dirigidos
Definiciones fundamentales 200
Representaciones de grafos dirigidos 201
Problema de los caminos más cortos con un solo origen 205
Problema de los caminos más cortos entre todos los pares 209
Recorridos en grafos dirigidos 216
Grafos dirigidos acíclicos 219
Componentes fuertes 223
Capítulo 7: Grafos no dirigidos
Definiciones 230
Arboles abarcadores de costo mínimo 233
Recorridos 239
Puntos de articulación y componentes biconexos 243
Pareamiento de grafos 245
Capítulo 8: Clasificación
El modelo de clasificación interna 252
Algunos esquemas simples de clasificación 253
Clasificación rápida (quicksort) 260
Clasificación por montículos (heapsort) 270
Clasificación por urnas (binsort) 274
Cota inferior para la clasificación por comparaciones 281
Estadísticas de orden 285
Capítulo 9: Técnicas de análisis de algoritmos
Eficiencia de los algoritmos 293
Análisis de programas recursivos 294
Resolución de ecuaciones de recurrencia 296
Solución general para una clase grande de recurrencias 299
Capítulo 10: Técnicas de diseño de algoritmos
Algoritmos dividir para vencer 307
Programación dinámica 312
Algoritmos ávidos 321
Método de retroceso (backtracking) 324
Algoritmos de búsqueda local 335
Capítulo 11: Estructuras de datos y algoritmos para almacenamiento externo
Un modelo para cómputos con almacenamiento externo 346
Clasificación externa 348
Almacenamiento de información en archivos 360
Arboles de búsqueda externa 368
Capítulo 12: Administración de memoria
Aspectos de la administración de memoria 379
Administración de bloques de igual tamaño 383
Algoritmos de recolección de basura para bloques de igual tamaño 385
Asignación de almacenamiento para objetos de diferentes tamaños 393
Sistemas de manejo de memoria por afinidades (buddy systems) 401
Compactación del almacenamiento 405
Bibliografía 413
Indice de materias 419
Vocabulario biling e de términos técnicos 429