Estructuras de datos y algoritmos /
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman.
- Wilmington, Delaware : Addison-Wesley, 1988.
- 438 p.
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