Fundamentos de algoritmia / Gilles Brassard, Paul Bratley.

CONTENIDO
1. PRELIMINARES 1
1.2 ¿QUE ES UN ALGORITMO? 2
1.3 NOTACION PARA LOS PROGRAMAS 7
1.4 NOTACION MATEMATICA 8
1.4.1 Cálculo proposicional 8
1.4.2 Teoría de conjuntos 9
1.4.3 Enteros, reales e intervalos 10
1.4.4 Funciones y relaciones 11
1.4.5 Cuantificadores 11
1.4.6 Sumas y productos 13
1.4.7 Miscelánea 14
1.5 TECNICA DE DEMOSTRACION 1: CONTRADICCION 15
1.6 TECNICA DE DEMOSTRACION 2: INDUCCION MATEMATICA 18
1.6.1 El principio de inducción matemática 21
1.6.2 Un asunto completamente distinto 26
1.6.3 Inducción matemática generalizada 28
1.6.4 Inducción constructiva 31
1.7 RECORDATORIOS 35
1.7.1 Límites 35
1.7.2 Series sencillas 39
1.7.3 Combinatoria básica 44
1.7.4 Probabilidad elemental 48
2. ALGORITMIA ELEMENTAL 65
2.2 PROBLEMAS Y EJEMPLARES 66
2.3 EFICIENCIA DE LOS ALGORITMOS 67
2.4 ANALISIS DE CASO MEDIO Y DE CASO PEOR 70
2.5 ¿QUE ES UNA OPERACION ELEMENTAL? 73
2.6 ¿POR QUE HAY QUE BUSCAR LA EFICIENCIA? 76
2.7.1 Cálculo de determinantes 78
2.7.2 Ordenación 79
2.7.3 Multiplicación de enteros muy grandes 80
2.7.4 Cálculo del máximo común divisor 82
2.7.5 Cálculo de la sucesión de Fibonacci 83
2.7.6 Transformada de Fourier 85
2.8 ¿CUANDO QUEDA ESPECIFICADO UN ALGORITMO? 85
3. NOTACION ASINTOTICA 91
3.2 UNA NOTACION PARA "EL ORDEN DE" 91
3.3 OTRA NOTACION ASINTOTICA 98
3.4 NOTACION ASINTOTICA CONDICIONAL 101
3.5 NOTACION ASINTOTICA CON VARIOS PARAMETROS 104
3.6 OPERACIONES SOBRE NOTACION ASINTOTICA 105
4. ANALISIS DE ALGORITMOS 111
4.2 ANALISIS DE LAS ESTRUCTURAS DE CONTROL 111
4.2.1 Secuencias 112
4.2.2 Bucles "para" (desde) 112
4.2.3 Llamadas recursivas 114
4.2.4 Bucles "mientras" y "repetir" 116
4.3 USO DE UN BAROMETRO 118
4.5 ANALISIS DEL CASO MEDIO 126
4.6 ANALISIS AMORTIZADO 127
4.7 RESOLUCION DE RECURRENCIAS 132
4.7.1 Suposiciones inteligentes 132
4.7.2 Recurrencias homogéneas 135
4.7.3 Recurrencias no homogéneas 140
4.7.4 Cambios de variable 148
4.7.5 Transformaciones de intervalo 156
4.7.6 Recurrencias asintóticas 157
5. ESTRUCTURA DE DATOS 167
5.1 MATRICES (ARRAYS), PILAS Y COLAS 167
5.2 REGISTROS Y PUNTEROS (APUNTADORES) 170
5.3 LISTAS 171
5.4 GRAFOS 173
5.5 ARBOLES 175
5.6 TABLAS ASOCIATIVAS 181
5.7 MONTICULOS (HEAPS) 184
5.8 MONTICULOS BINOMIALES 193
5.9 ESTRUCTURAS DE CONJUNTOS DISJUNTOS (PARTICION) 198
6. ALGORITMOS VORACES 211
6.1 DAR LA VUELTA (1) 211
6.2 CARACTERISTICAS GENERALES DE LOS ALGORITMOS VORACES 213
6.3 GRAFOS: ARBOLES DE RECUBRIMIENTO MINIMO 215
6.3.1 Algoritmo de Kruskal 217
6.3.2 Algoritmo de Prim 220
6.4 GRAFOS: CAMINOS MINIMOS 223
6.5 EL PROBLEMA DE LA MOCHILA (1) 227
6.6 PLANIFICACION 230
6.6.1 Minimización del tiempo del sistema 231
6.6.2 Planificación con plazo fijo 233
7. DIVIDE Y VENCERAS 247
7.1 INTRODUCCION: MULTIPLICACION DE ENTEROS MUY GRANDES 247
7.2 EL CASO GENERAL 251
7.3 BUSQUEDA BINARIA 255
7.4 ORDENACION 257
7.4.1 Ordenación por fusión 258
7.4.2 Ordenación rápida (Quicksort) 260
7.5 BUSQUEDA DE LA MEDIANA 266
7.6 MULTIPLICACION DE MATRICES 272
7.7 EXPONENCIACION 274
7.8 ENSAMBLANDO TODAS LA PIEZAS: INTRODUCCION A LA CRIPTOGRAFIA 279
8. PROGRAMACION DINAMICA 291
8.1 DOS EJEMPLOS SENCILLOS 292
8.1.1 Cálculo del coeficiente binomial 292
8.1.2 El campeonato mundial 293
8.2 DEVOLVER CAMBIO (2) 295
8.3 EL PRINCIPIO DE OPTIMALIDAD 298
8.4 EL PROBLEMA DE LA MOCHILA (2) 299
8.5 CAMINOS MINIMOS 301
8.6 MULTIPLICACION ENCADENADA DE MATRICES 304
8.7 ENFOQUES QUE APLICAN RECURSION 309
8.8 FUNCIONES CON MEMORIA 311
9. EXPLORACION DE LOS GRAFOS 319
9.1 GRAFOS Y JUEGOS: INTRODUCCION 319
9.2 RECORRIDO DE ARBOLES 326
9.2.1 Preacondicionamiento 327
9.3 RECORRIDO EN PROFUNDIDAD: GRAFOS NO DIRIGIDOS 329
9.3.1 Puntos de articulación 332
9.4 RECORRIDO EN PROFUNDIDAD: GRAFOS DIRIGIDOS 334
9.4.1 Grafos acíclicos: ordenación topológica 336
9.5 RECORRIDO EN ANCHURA 337
9.6 VUELTA ATRAS 342
9.6.1 El problema de la mochila (3) 343
9.6.2 El problema de las ocho reinas 345
9.6.3 El caso general 348
9.7 RAMIFICACION Y PODA 348
9.7.1 El problema de la asignación 349
9.7.2 El problema de la mochila (4) 353
9.7.3 Consideraciones generales 354
9.8 EL PRINCIPIO DE MINIMAX 354
10. ALGORITMOS PROBABILISTAS 365
10.2 PROBABILISTA NO IMPLICA INCIERTO 366
10.3 TIEMPO ESPERADO FRENTE A TIEMPO PROMEDIO 368
10.4 GENERACION DE NUMEROS PSEUDOALEATORIOS 369
10.5 ALGORITMOS PROBABILISTAS NUMERICOS 371
10.5.1 La aguja de Buffon 371
10.5.2 Integración numérica 375
10.5.3 Conteo probabilista 377
10.6 ALGORITMOS DE MONTE CARLO 379
10.6.1 Verificación de la multiplicación de matrices 380
10.6.2 Comprobación de primalidad 383
10.6.3 ¿Puede un número ser probablemente primo? 387
10.6.4 Amplificación de la ventaja estocástica 390
10.7 ALGORITMOS DE LAS VEGAS 393
10.7.1 El problema de las ocho reinas, segunda parte 396
10.7.2 Selección y ordenación probabilistas 400
10.7.3 Tablas de dispersión universales 402
10.7.4 Factorización de enteros muy grandes 404
11. ALGORITMO S PARALELOS 419
11.1 UN MODELO PARA LA COMPUTACION PARALELA 419
11.2 TECNICAS BASICAS 422
11.2.1 Cómputo con un árbol binario completo 422
11.2.2 Duplicación de punteros 424
11.3 TRABAJO Y EFICIENCIA 428
11.4 DOS EJEMPLOS DE TEORIA DE GRAFOS 431
11.4.1 Caminos mínimos 431
11.4.2 Componentes conexos 432
11.5 EVALUACION DE EXPRESIONES EN PARALELO 435
11.6 REDES DE ORDENACION EN PARALELO 443
11.6.1 El principio cero-uno 445
11.6.2 Redes de fusión en paralelo 446
11.6.3 Redes de ordenación mejoradas 448
11.7 ORDENACION EN PARALELO 449
11.7.1 Preliminares 450
11.7.2 La idea clave 450
11.7.3 El algoritmo 451
11.7.4 Un esbozo de los detalles 452
11.8 COMENTARIOS ACERCA DE LAS P-RAM EREW Y CRCW 453
11.9 COMPUTO DISTRIBUIDO 455
12. COMPLEJIDAD COMPUTACIONAL 461
12.1 INTRODUCCION: UN EJEMPLO SENCILLO 462
12.2 ARGUMENTOS DE LA TEORIA DE LA INFORMACION 462
12.2.1 La complejidad de la ordenación 466
12.2.2 La complejidad, al rescate de la algorítmica 470
12.3 ARGUMENTOS DEL ADVERSARIO 472
12.3.1 Búsqueda del máximo en una matriz 473
12.3.2 Comprobación de la conectividad de un grafo 474
12.3.3 La mediana, segunda parte 475
12.4 REDUCCIONES LINEALES 476
12.4.1 Definiciones formales 480
12.4.2 Reducciones entre problemas matriciales 482
12.4.3 Reducciones entre problemas caminos mínimos 487
12.5 INTRODUCCION A LA NP-COMPLETITUD 491
12.5.1 Las clases P y NP 491
12.5.2 Reducciones polinómicas 496
12.5.3 Problemas NP completos 500
12.5.4 Algunas demostraciones de NP-completitud 504
12.5.5 Problemas NP-difíciles 507
12.5.6 Algoritmos no deterministas 508
12.6 UN ZOO DE CLASES DE COMPLEJIDAD 511
13. ALGORITMOS HEURISTICOS Y APROXIMADOS 525
13.1 ALGORITMOS HEURISTICOS 526
13.1.1 Coloreado de un grafo 526
13.1.2 El viajante 528
13.2 ALGORITMOS APROXIMADOS 529
13.2.1 El viajante métrico 529
13.2.2 El problema de la mochila (5) 532
13.2.3 Llenado de cajas 534
13.3 PROBLEMAS DE APROXIMACION CON DIFICULTAD NP 536
13.3.1 Problemas de aproximación con dificultad absoluta 538
13.3.2 Problemas de aproximación con dificultad relativa 539
13.4 LO MISMO, PERO DISTINTO 541
13.5 ENFOQUES DE APROXIMACION 545
13.5.1 Llenado de cajas, segunda parte 546
13.5.2 El problema de la mochila (6) 547
REFERENCIAS 555
NOTAS FINALES 569
INDICE ANALITICO 571