Algorítmica : concepción y análisis / por Gilles Brassard, Paul Bratley ; versión española y compaginación, Ricardo Peña Marí, Celestí Rosselló Balanyá.

AUTOR: Gilles Brassard -  Paul Bratley
ISBN: 8431105313
IDIOMA: spa
PÁGINAS: XVI, 368
AÑO: 1990

 
   
RECOMENDADO EN LAS SIGUIENTES ASIGNATURAS
Tecnología de la Programación
 
RESUMEN

La algorítmica trata sistemáticamente de técnicas fundamentales para la concepción y el análisis de algoritmos eficientes. Esta obra, ni es un manual de programación, ni es un tratado sobre las estructuras de datos. Aún menos, no es un “libro de recetas” bajo la forma de un catálogo de algoritmos listos para ser introducidos en el computador con el fin de resolver problemas específicos, pero que no da sino una idea vaga de los principios que han conducido a dichos algoritmos. Por el contrario, el objetivo principal de este libro es dar al lector las herramientas fundamentales para facilitarle el desarrollo de sus propios algoritmos, cualesquiera que sean sus intereses. Se presenta de esta manera el enfoque norteamericano de la algorítmica. El libro se concentra en las técnicas de concepción y análisis de algoritmos eficientes. Cada técnica se presenta primero en toda su generalidad y se ilustra después con ejemplos concretos de algoritmos tomados de dominios de aplicación tan variados como la optimización, el álgebra lineal, la criptografía, la investigación operativa, la manipulación simbólica, la inteligencia artificial, el análisis numérico y las ciencias humanas. A pesar del enfoque riguroso y teórico, esta obra no olvida tampoco a los informáticos prácticos: además de ilustrar las técnicas de concepción y análisis, la mayoría de los algoritmos presentados tienen una aplicación real. Para sacar el mayor provecho de este libro, el lector debe tener experiencia previa en programación. No obstante, no utilizamos un lenguaje específico de programación ni un computador en especial. Por ello mismo y por el carácter básico y general de las materias tratadas, la obra no corre el riesgo de una obsolescencia rápida. En contrapartida, el lector no debe pretender poder utilizar directamente los algoritmos presentados: necesitará en todos los casos un trabajo de adaptación para transcribirlos a un lenguaje de programación concreto. El uso del lenguaje Pascal u otro de estructura similar permitirá reducir al mínimo este esfuerzo. Para la buena comprensión del libro se requieren ciertas nociones básicas de matemáticas. En general, basta con dominar el contenido de los cursos elementales de álgebra y análisis. Sin embargo, es más importante una cierta madurez matemática. Suponemos que el lector está familiarizado con temas como la inducción matemática, la teoría de conjuntos y el concepto de grafo. Ocasionalmente, ciertas partes necesitan conocimientos matemáticos más profundos, pero pueden ser ignorados en una primera lectura.
 
INDICE

Prólogo
Nota de los traductores
1. Preliminares
1.1. ¿Qué es un algoritmo?
1.2. Problemas y ejemplares de un problema
1.3. La eficiencia de los algoritmos
1.4. Análisis de los casos peor y medio
1.5. ¿Qué es una operación elemental?
1.6. ¿Por qué buscar algoritmos eficientes?
1.7. Algunos ejemplos concretos
1.7.1. La ordenación
1.7.2. La multiplicación de enteros grandes
1.7.3. El cálculo del determinante
1.7.4. El cálculo del máximo común divisor
1.7.5. La sucesión de Fibonacci
1.7.6. La transformada de Fourier
1.8. ¿Cuándo un algoritmo está completamente especificado?
1.9. Estructuración de los datos
1.9.1. Las listas
1.9.2. Los grafos
1.9.3. Los árboles
1.9.4. Los montículos
1.9.5. La estructura de partición
1.10. Referencias bibliográficas
2. Análisis de la eficiencia de los algoritmos
2.1. Notaciones asintóticas
2.1.1. La notación “del orden de”
2.1.2. Otras notaciones asintóticas
2.1.3. Notaciones asintóticas con varios parámetros
2.1.4.Operaciones con las notaciones asintóticas
2.1.5. Notaciones asintóticas condicionales
2.1.6. Ecuaciones recurrentes asintóticas
2.1.7. La técnica de inducción constructiva
2.1.8. Para una segunda lectura
2.2. El análisis de algoritmos
2.3. Resolución de recurrencias por el método de la ecuación característica
2.3.1. Recurrencias homogénea
2.3.2. Recurrencias no homogéneas
2.3.3. Cambio de variable
2.3.4. Transformación de la imagen
2.3.5. Problemas adicionales
2.4. Referencias bibliográficas
3. Los algoritmos voraces
3.1. Introducción
3.2. Algoritmos voraces en grafos
3.2.1. Árboles de expansión mínimos
3.2.2. Caminos mínimos
3.3. Algoritmos voraces para la planificación de tareas
3.3.1. Minimización del tiempo de espera
3.3.2. Planificación de tareas a plazo fijo
3.4. Heurísticas voraces
3.4.1. Coloreado de grafos
3.4.2. El problema del viajante de comercio
3.5. Referencias bibliográficas
4. Divide y vencerás
4.1. Introducción
4.2. Determinación del umbral
4.3. La búsqueda dicotómica
4.4. La ordenación por fusión
4.5. El algoritmo de ordenación de loare
4.6. Algoritmos de selección y de búsqueda de la mediana
4.7. La aritmética de los enteros grandes
4.8. La exponenciación (introducción a la criptografía)
4.9 La multiplicación de matrices
4.10 Intercambio de dos secciones de un vector
4.11 Problemas adicionales
4.12 Referencias bibliográficas
5. La programación dinámica
5.1. Introducción
5.2. La competición internacional
5.3. Producto de matrices
5.4. Caminos mínimos
5.5. Árboles de búsqueda óptimos
5.6. El viajante de comercio
5.7. Funciones con memoria
5.8. Problemas adicionales
5.9. Referencias bibliográficas
6. Exploración de grafos
6.1. Introducción
6.2. Recorrido de árboles
6.3. El recorrido en profundidad: grafos no orientados
6.3.1. Puntos de articulación
6.4. El recorrido en profundidad: grafos orientados
6.4.1. Grafos orientados acíclicos
6.4.2. Componentes fuertemente conexas
6.5. El recorrido en anchura
6.6. Algoritmos de vuelta atrás
6.7. Introducción a los grafos de juego
6.7.1. La técnica del minimax
6.7.2. El método alfa-beta
6.8. Branch and bound
6.9. Problemas adicionales
6.10. Referencias bibliográficas
7. Precondicionamiento y materias afines
7.1. Precondicionamiento
7.1.1. Introducción
7.1.2. Ascendientes en un árbol
7.1.3. Evaluación repetida de un polinomio
7.2. Reconocimiento de patrones
7.2.1. Firmas
7.2.2. El algoritmo de Knuth, Morris y Pratt
7.2.3. El algoritmo de Boyer y Moore
7.3. Referencias bibliográficas
8. Algoritmos probabilistas
8.1. Introducción
8.2. Clasificación de los algoritmos probabilistas
8.3. Algoritmos probabilistas numéricos
8.3.1. El experimento del Conde de Buffon
8.3.2. Integración numérica
8.3.3. Conteo probabilista
8.3.4. Conteo probabilista (bis)
8.4. Algoritmos de Sherwood
8.4.1. La selección y la ordenación
8.4.2. Preproceso estocástico
8.4.3. Búsqueda en una lista ordenada
8.4.4 Direccionamiento disperso universal
8.5. Algoritmos de Las Vegas
8.5.1. El problema de las ocho reinas
8.5.2. Extracción de raíces cuadradas módulo p
8.5.3. La factorización entera
8.5.4. La elección de un jefe
8.6. Algoritmos de Monte Carlo
8.6.1. El problema del vector mayoritario
8.6.2. Comprobación probabilista de primalidad
8.6.3. Comprobación probabilista de igualdad de conjuntos
8.7. Referencias bibliográficas
9. Transformaciones de dominio
9.1. Introducción
9.2. La transformada de Fourier
9.3. La transformación inversa
9.4. Manipulación simbólica de polinomios
9.5. La multiplicación de enteros grandes
9.6. Referencias bibliográficas
10. Elementos de complejidad del cálculo
10.1. Árboles de decisión
10.2. La reducción
10.2.1. Reducciones entre problemas matriciales
10.2.2. Reducción entre problemas de grafos
10.2.3. Reducciones entre problemas aritméticos y polinómicos
10.3. Introducción a la NP-completitud
10.3.1. Las clases P y NP
10.3.2. Problemas NP-completos)
10.3.3. Teorema de Cook
10.3.4. Algunas reducciones
10.3.5. No-determinismo
10.4. Referencias bibliográficas
Apéndice. Tabla de notaciones
Bibliografía
Índice de algoritmos
Índice de nombres y materias