Algoritmos computacionales: Introducción al análisis y diseño, 3ra Edición – Sara Baase y Allen Van Gelder [MEGA]

Este libro fue escrito para un curso completo sobre algoritmos; cuenta con suficiente material como para adoptar diversas orientaciones.

El objetivo del mismo incluye tres aspectos. Pretende enseñar algoritmos que se aplicarán en la resolución de problemas reales que se presentan a menudo en aplicaciones para computadora, enseñar principios y técnicas básicos de complejidad computacional (comportamiento de peor caso y caso promedio, consumo de espacio y cotas inferiores de la complejidad de un problema), e introducir las áreas de los problemas NP-completos y los algoritmos paralelos.

Otra de las metas del libro, no menos importante que enseñar los temas que contiene, es desarrollar en el lector el hábito de siempre responder a un algoritmo nuevo con las preguntas: ¿Qué tan bueno es? ¿Hay una manera mejor? Por ello, en lugar de presentar una serie de algoritmos completos, “sacados de la manga”, con su análisis, el libro normalmente comenta primero un problema, considera una o más estrategias para resolverlo (como podría hacer el lector que enfrenta el problema por primera vez) y luego comienza a desarrollar un algoritmo, lo analiza y lo modifica o lo rechaza hasta obtener un resultado satisfactorio. (Los enfoques alternativos que finalmente se rechazan también se examinan en los ejercicios; para el lector es útil saber por qué se les rechazó.)

Preguntas del tipo de ¿Cómo puede hacerse esto de forma más eficiente? ¿Qué estructura de datos sería útil en este caso? ¿En qué operaciones debemos concentrarnos para analizar este algoritmo? ¿Qué valor inicial debe asignarse a esta variable (o estructura de datos)?, aparecen a menudo en todo el texto. Por lo general damos la respuesta inmediatamente después de la pregunta, pero sugerimos a los lectores hacer una pausa antes de continuar la lectura y tratar de idear su propia respuesta. El aprendizaje no es un proceso pasivo.

Tenemos la esperanza de que los lectores también aprendan a visualizar cómo se comporta en la realidad un algoritmo con diversas entradas; es decir, ¿Qué ramas sigue? ¿Qué patrón de crecimiento y encogimiento siguen las pilas? ¿Cómo afecta al comportamiento presentar las entradas en diferentes formas (por ejemplo, enumerando los vértices o aristas de un grafo en distintos órdenes)? Tales preguntas se plantean en algunos de los ejercicios, pero no hacemos hincapié en ellas en el texto porque requieren un estudio minucioso de los pormenores de un gran número de ejemplos.

Contenido:

Prefacio vii

1 Análisis de algoritmos y problemas: principios y ejemplos 1
1.1 Introducción 2
1.2 Java como lenguaje algorítmico 3
1.3 Antecedentes matemáticos 11
1.4 Análisis de algoritmos y problemas 30
1.5 Clasificación de funciones por su tasa de crecimiento asintótica 43
1.6 Búsqueda en un arreglo ordenado 53
Ejercicios 61
Notas y referencias 67

2 Abstracción de datos y estructuras de datos básicas 69
2.1 Introducción 70
2.2 Especificación de TDA y técnicas de diseño 71
2.3 TDA elementales: listas y árboles 73
2.4 Pilas y colas 86
2.5 TDA para conjuntos dinámicos 89
Ejercicios 95
Notas y referencias 100

3 Recursión e inducción 101
3.1 Introducción 102
3.2 Procedimientos recursivos 102
3.3 ¿Qué es una demostración? 108
3.4 Demostraciones por inducción 111
3.5 Cómo demostrar que un procedimiento es correcto 118
3.6 Ecuaciones de recurrencia 130
3.7 Árboles de recursión 134
★ Ejercicios 141
Notas y referencias 146

4 Ordenamiento 149
4.1 Introducción 150
4.2 Ordenamiento por inserción 151
4.3 Divide y vencerás 157
4.4 Quicksort 159
4.5 Fusión de sucesiones ordenadas 171
4.6 Mergesort 174
4.7 Cotas inferiores para ordenar comparando claves 178
4.8 Heapsort 182
4.9 Comparación de cuatro algoritmos para ordenar 197
4.10 Shellsort 197
4.11 Ordenamiento por base 201
Ejercicios 206
Programas 221
Notas y Referencias 221

5 Selección y argumentos de adversario 223
5.1 Introducción 224
5.2 Determinación de max y min 226
5.3 Cómo hallar la segunda llave más grande 229
5.4 El problema de selección 233
5.5 Una cota inferior para la determinación de la mediana 238
5.6 Diseño contra un adversario 240
Ejercicios 242
Notas y referencias 246

6 Conjuntos dinámicos y búsquedas 249
6.1 Introducción 250
6.2 Doblado de arreglos 250
6.3 Análisis de tiempo amortizado 251
6.4 Árboles rojinegros 253
6.5 Hashing (dispersión) 275
6.6 Relaciones de equivalencia dinámica y programas Unión-Hallar 283
6.7 Colas de prioridad con operación de decrementar clave 295
Ejercicios 302
Programas 309
Notas y referencias 309

7 Grafos y recorridos de grafos 313
7.1 Introducción 314
7.2 Definiciones y representaciones 314
7.3 Recorrido de grafos 328
7.4 Búsqueda de primero en profundidad en grafos dirigidos 336
7.5 Componentes fuertemente conectados de un grafo dirigido 357
7.6 Búsqueda de primero en profundidad en grafos no dirigidos 364
7.7 Componentes biconectados de un grafo no dirigido 366
Ejercicios 375
Programas 384
Notas y referencias 385

8 Problemas de optimización de grafos y algoritmos codiciosos 387
8.1 Introducción 388
8.2 Algoritmo de árbol abarcante mínimo de Prim 388
8.3 Caminos más cortos de origen único 403
8.4 Algoritmo de árbol abarcante mínimo de Kruskal 412
Ejercicios 416
Programas 421
Notas y referencias 422

9 Cierre transitivo, caminos más cortos de todos los pares 425
9.1 Introducción 426
9.2 Cierre transitivo de una relación binaria 426
9.3 Algoritmo de Warshall para cierre transitivo 430
9.4 Caminos más cortos de todos los pares en grafos 433
9.5 Cálculo del cierre transitivo con operaciones de matrices 436
9.6 Multiplicación de matrices de bits: algoritmo de Kronrod 439
Ejercicios 446
Programas 449
Notas y referencias 449

10 Programación dinámica 451
10.1 Introducción 452
10.2 Grafos de subproblema y su recorrido 453
10.3 Multiplicación de una sucesión de matrices 457
10.4 Construcción de árboles de búsqueda binaria óptimos 466
10.5 División de sucesiones de palabras en líneas 474
10.6 Desarrollo de un algoritmo de programación dinámica 474
Ejercicios 475
Programas 481
Notas y referencias 482

11 Cotejo de cadenas 483
11.1 Introducción 484
11.2 Una solución directa 485
11.3 El algoritmo Knuth-Morris-Pratt 487
11.4 El algoritmo Boyer-Moore 495
11.5 Cotejo aproximado de cadenas 504
Ejercicios 508
Programas 512
Notas y referencias 512

12 Polinomios y matrices 515
12.1 Introducción 516
12.2 Evaluación de funciones polinómicas 516
12.3 Multiplicación de vectores y matrices 522
12.4 La transformada rápida de Fourier y convolución 528
Ejercicios 542
Programas 546
Notas y referencias 546

13 Problemas NP-completos 547
13.1 Introducción 548
13.2 P y NP 548
13.3 Problemas NP-completos 559
13.4 Algoritmos de aproximación 570
13.5 Llenado de cajones 572
13.6 Los problemas de la mochila y de la sumatoria de subconjunto 577
13.7 Coloreado de grafos 581
13.8 El problema del vendedor viajero 589
13.9 Computación por ADN 592
Ejercicios 600
Notas y referencias 608

14 Algoritmos paralelos 611
14.1 Introducción 612
14.2 Paralelismo, la PRAM y otros modelos 612
14.3 Algunos algoritmos de PRAM sencillos 616
14.4 Manejo de conflictos de escritura 622
14.5 Fusión y ordenamiento 624
14.6 Determinación de componentes conectados 628
14.7 Una cota inferior para la suma de n enteros 641
Ejercicios 643
Notas y referencias 647

A Ejemplos y técnicas en Java 649
A.1 Introducción 650
A.2 Un programa principal en Java 651
A.3 Una biblioteca de entrada sencilla 656
A.4 Documentación de clases de Java 658
A.5 Orden genérico y la interfaz “Comparable” 659
A.6 Las subclases extienden la capacidad de su superclase 663
A.7 Copiado a través de la interfaz “Clonable” 667
Bibliografía 669
Índice 679

Link:

https://mega.co.nz/#!JMdGxZyI!GEyZRcfPYK8xNk97k10sKqoNfNVxwYTxjjI0m3QiJZc