Algoritmos Computacionales – Sara Baase, Allen Van Gelder – 3ra Edición

1 Análisis de algoritmos y problemas: principios y ejemplos

1.1 Introducción

1.2 Java como lenguaje algorítmico

1.3 Antecedentes matemáticos

1.4 Análisis de algoritmos y problemas

1.5 Clasificación de funciones por su tasa de crecimiento asintótica

1.6 Búsqueda en un arreglo ordenado

2 Abstracción de datos y estructuras de datos básicas

2.1 Introducción

2.2 Especificación de TDA y técnicas de diseño

2.3 TDA elementales: listas y árboles

2.4 Pilas y colas

2.5 TDA para conjuntos dinámicos

3 Recursión e inducción

3.1 Introducción

3.2 Procedimientos recursivos

3.3 ¿Qué es una demostración?

3.4 Demostraciones por inducción

3.5 Cómo demostrar que un procedimiento es correcto

3.6 Ecuaciones de recurrencia

3.7 Árboles de recursión

4 Ordenamiento

4.1 Introducción

4.2 Ordenamiento por inserción

4.3 Divide y vencerás

4.4 Quicksort

4.5 Fusión de sucesiones ordenadas

4.6 Mergesort

4.7 Cotas inferiores para ordenar comparando claves

4.8 Heapsort

4.9 Comparación de cuatro algoritmos para ordenar

4.10 Shellsort

4.11 Ordenamiento por base

5 Selección y argumentos de adversario

5.1 Introducción

5.2 Determinación de max y min

5.3 Cómo hallar la segunda llave más grande

5.4 El problema de selección

5.5 Una cota inferior para la determinación de la mediana

5.6 Diseño contra un adversario

6 Conjuntos dinámicos y búsquedas

6.1 Introducción

6.2 Doblado de arreglos

6.3 Análisis de tiempo amortizado

6.4 Árboles rojinegros

6.5 Hashing (dispersión)

6.6 Relaciones de equivalencia dinámica y programas Unión-Hallar

6.7 Colas de prioridad con operación de decrementar clave

7 Grafos y recorridos de grafos

7.1 Introducción

7.2 Definiciones y representaciones

7.3 Recorrido de grafos

7.4 Búsqueda de primero en profundidad en grafos dirigidos

7.5 Componentes fuertemente conectados de un grafo dirigido

7.6 Búsqueda de primero en profundidad en grafos no dirigidos

7.7 Componentes biconectados de un grafo no dirigido

8 Problemas de optimización de grafos y algoritmos codiciosos

8.1 Introducción

8.2 Algoritmo de árbol abarcante mínimo de Prim

8.3 Caminos más cortos de origen único

8.4 Algoritmo de árbol abarcante mínimo de Kruskal

9 Cierre transitivo, caminos más cortos de todos los pares

9.1 Introducción

9.2 Cierre transitivo de una relación binaria

9.3 Algoritmo de Warshall para cierre transitivo

9.4 Caminos más cortos de todos los pares en grafos

9.5 Cálculo del cierre transitivo con operaciones de matrices

9.6 Multiplicación de matrices de bits: algoritmo de Kronrod

10 Programación dinámica

10.1 Introducción

10.2 Grafos de subproblema y su recorrido

10.3 Multiplicación de una sucesión de matrices

10.4 Construcción de árboles de búsqueda binaria óptimos

10.5 División de sucesiones de palabras en líneas

10.6 Desarrollo de un algoritmo de programación dinámica

11 Cotejo de cadenas

11.1 Introducción

11.2 Una solución directa

11.3 El algoritmo Knuth-Morris-Pratt

11.4 El algoritmo Boyer-Moore

11.5 Cotejo aproximado de cadenas

12 Polinomios y matrices

12.1 Introducción

12.2 Evaluación de funciones polinómicas

12.3 Multiplicación de vectores y matrices

12.4 La transformada rápida de Fourier y convolución

13 Problemas NP-completos

13.1 Introducción

13.2 P y NP

13.3 Problemas NP-completos

13.4 Algoritmos de aproximación

13.5 Llenado de cajones

13.6 Los problemas de la mochila y de la sumatoria de subconjunto

13.7 Coloreado de grafos

13.8 El problema del vendedor viajero

13.9 Computación por ADN

14 Algoritmos paralelos

14.1 Introducción

14.2 Paralelismo, la PRAM y otros modelos

14.3 Algunos algoritmos de PRAM sencillos

14.4 Manejo de conflictos de escritura

14.5 Fusión y ordenamiento

14.6 Determinación de componentes conectados

14.7 Una cota inferior para la suma de n enteros

A Ejemplos y técnicas en Java

A.1 Introducción

A.2 Un programa principal en Java

A.3 Una biblioteca de entrada sencilla

A.4 Documentación de clases de Java

A.5 Orden genérico y la interfaz "Comparable"

A.6 Las subclases extienden la capacidad de su superclase

A.7 Copiado a través de la interfaz "Clonable"