Este libro presenta una amplia variedad de estructuras de datos y de métodos algorítmicos con el objetivo de servir como texto base para uno o dos cursos avanzados de programación. El contenido es apropiado para un semestre en estructuras de datos eficientes y otro semestre en métodos algorítmicos. Supone una exposición previa a dos o tres semestres de asignaturas de programación donde se hayan tratado los conceptos básicos, la sintaxis y semántica de un lenguaje de programación, la recursión, las estructuras de datos lineales y las nociones de clase y objeto. Es también recomendable una exposición previa o simultánea al paradigma de programación funcional, a los fundamentos de la especificación y verificación formal de programas y a asignaturas de lógica y matemática discreta.
En esta segunda edición se han corregido erratas detectadas en la edición anterior, se ha actualizado la bibliografía y se añadido una sección nueva en el capítulo 5 dedicado a la La unión de dos AVL en tiempo lineal.
El enfoque del libro es original por el hecho de que casi las dos terceras partes de los algoritmos se presentan especificados y verificados formalmente en la plataforma Dafny de verificación asistida. Como material asociado al mismo, se distribuyen los ficheros Dafny con el texto completo de todos los algoritmos, junto con sus especificaciones formales y asertos intermedios necesarios. El lector puede reproducir la verificación de los programas sin más que procesarlos con dicha plataforma. Dicho material puede descargarse de la página web que el libro tiene en la editorial Garceta: http://www.garceta.es.
Ricardo Peña Marí es Catedrático de Universidad del Departamento de Sistemas Informáticos y Computación de la Universidad Complutense de Madrid. Ha sido Profesor Titular, hasta 1991, de la Universidad Politécnica de Cataluña y ha trabajado anteriormente en dos empresas privadas en el desarrollo de grandes programas dentro de las áreas de telefonía y diseño asistido. Sus áreas actuales de investigación son el análisis estático de programas, la verificación asistida y las herramientas automáticas de pruebas
1. Preliminares
1.1. El coste de los algoritmos
1.1.1. El criterio asintótico
1.1.2. El coste en el caso peor
1.1.3. Resolución de recurrencias
1.1.4. El coste en el caso promedio
1.1.5. El coste amortizado
1.2. La lógica de Hoare para la verificación de programas
1.3. Introducción a Dafny
1.3.1. Tipos en Dafny
1.3.2. Especificaciones
1.3.3. Verificación
1.4. Ejercicios
1.5. Notas bibliográficas
2. Arboles equilibrados
2.1. Arboles binarios de búsqueda
2.2. Arboles AVL
2.3. Arboles rojinegros
2.3.1. Arboles 2-3-4
2.3.2. Arboles rojinegros escorados a la izquierda
2.4. Arboles autoajustables
2.5. Ejercicios
2.6. Notas bibliográficas
3. Montículos
3.1. Montículos de Williams
3.1.1. Ordenación por el método del montículo
3.2. Montículos zurdos
3.3. Montículos sesgados
3.4. Montículos binomiales
3.5. Montículos de Fibonacci
3.6. Ejercicios
3.7. Notas bibliográficas
4. Grafos y particiones
4.1. Terminología
4.2. Representaciones de grafos
4.3. Recorridos
4.4. Ordenación topológica
4.5. Cálculo de componentes fuertemente conexas
4.6. La estructura de partición
4.7. Ejercicios
4.8. Notas bibliográficas
5. El método divide y vencerás
5.1. La búsqueda binaria y los algoritmos de ordenación
5.2. El algoritmo de Karatsuba y Ofman
5.2.1. El algoritmo generalizado de Toom-Cook
5.3. La unión de dos AVL en tiempo lineal
5.4. El problema del par de puntos más cercano
5.5. La determinación del umbral
5.6. Ejercicios
5.7. Notas bibliográficas
6. El método voraz
6.1. Emparejando alfombras y pasillos
6.2. La mochila con fraccionamiento
6.3. El algoritmo de Dijkstra de caminos mínimos
6.4. Arboles de recubrimiento de coste mínimo
6.4.1. Algoritmo de Prim
6.4.2. Algoritmo de Kruskal
6.5. Arboles de Huffman
6.5.1. Algoritmo voraz para calcular el árbol de Huffman optimo
6.5.2. Orden óptimo de mezcla de ficheros ordenados
6.6. Ejercicios
6.7. Notas bibliográficas
7. Programación dinámica
7.1. Cortando troncos eficientemente
7.2. La subsecuencia común más larga
7.3. El rapero con sueltecillo
7.4. El algoritmo de Floyd de caminos mínimos
7.5. Triangulación optima de polígonos
7.6. Ejercicios
7.7. Notas bibliográficas
8. Precondicionamiento: ajuste de cadenas
8.1. El algoritmo de Rabin-Karp
8.2. Precondicionamiento con autómata
8.3. El algoritmo de Knuth-Morris-Pratt
8.4. El algoritmo de Boyer-Moore
8.5. Ejercicios
8.6. Notas bibliográficas
9. Exploración del espacio de soluciones
9.1. Esquema de vuelta atrás
9.1.1. El problema de la mochila sin fraccionamiento
9.2. Esquema optimista-pesimista de ramificación y poda
9.2.1. Asignando tareas a procesadores
9.2.2. Optimizando la preparación de exámenes
9.2.3. El problema del viajante de comercio
9.3. Ejercicios
9.4. Notas bibliográficas
10.Problemas NP-completos y NP-difíciles
10.1. Introducción a la complejidad computacional
10.2. Cálculo de cotas inferiores al coste de los problemas
10.2.1. Arboles de decisión
10.2.2. El método del adversario
10.3. Teoría de la NP-completitud
10.3.1. Las clases P y NP
10.3.2. La reducibilidad de problemas
10.3.3. Demostraciones de problemas NP-completos y NP-difíciles
10.4. Algoritmos aproximados
10.4.1. El problema del viajante euclídeo
10.4.2. Minimizando el número de envases
10.5. Ejercicios
10.6. Notas bibliográficas
(0 Comentarios)
