| A nuestros lectores | 5
|
| Prólogo a la serie «Lecciones de Matemática» | 6
|
| Prólogo al décimo tomo | 8
|
| Capítulo 1. Problemas combinatorios | 9
|
| 1.1. La pesadilla exponencial | 9
|
| 1.2. Problemas P y NP | 10
|
| 1.3. El problema central y cuestiones afines | 16
|
| 1.4. Problemas en grafos | 18
|
| 1.5. Programación entera | 25
|
| 1.6. Problemas lógicos | 27
|
| 1.7. Matrices (0,1) | 31
|
| 1.8. Números primos y compuestos | 32
|
| 1.9. Mecanismos combinatorios | 34
|
| Capítulo 2. Instrumentos y «decoraciones» | 36
|
| 2.1. Funciones computables | 36
|
| 2.2. Conjuntos enumerables | 38
|
| 2.3. Problemas indecidibles | 40
|
| 2.4. Máquina de Turing | 42
|
| 2.5. Algoritmos polinomiales | 47
|
| 2.6. Complejidad de los cálculos | 49
|
| 2.7. Problemas de nivel superior | 51
|
| Capítulo 3. Problema P=?NP | 54
|
| 3.1. La clase P | 54
|
| 3.2. La clase NP | 56
|
| 3.3. Reducción y NP-completitud | 59
|
| 3.4. Problema NP-completo universal | 61
|
| 3.5. Teorema de Cook | 62
|
| 3.6. La clase NPC | 64
|
| 3.7. La teoría de Levin | 67
|
| 3.8. Aumento polinomial | 69
|
| 3.9. ¿Será resuelto algún día el problema P=?NP? | 70
|
| Capítulo 4. Anatomía de los problemas de búsqueda exhaustiva | 72
|
| 4.1. Problema co-NP=?NP | 72
|
| 4.2. NP-completitud fuerte | 73
|
| 4.3. Camino mínimo | 75
|
| 4.4. Flujo máximo y corte mínimo | 78
|
| 4.5. Teoría de matroides y algoritmo voraz | 80
|
| 4.6. Variaciones del ARM | 84
|
| 4.7. Problemas PSPACE | 84
|
| 4.8. Complejidad esquemática | 87
|
| 4.9. Protocolos interactivos | 87
|
| 4.10. Relativización y oráculos | 90
|
| 4.11. Problemas de Ramsey | 92
|
| Capítulo 5. Programación lineal | 96
|
| 5.1. Planteamiento del problema | 96
|
| 5.2. Prehistoria de la variante combinatoria | 100
|
| 5.3. Efectos de la precisión limitada | 102
|
| 5.4. Algoritmo del elipsoide | 105
|
| 5.5. La naturaleza del algoritmo | 108
|
| 5.6. Métodos del punto interior | 108
|
| 5.7. El fenómeno de los vértices enteros | 110
|
| Capítulo 6. Aritmética y criptografía | 112
|
| 6.1. Sobre las causas de la exclusividad | 112
|
| 6.2. Test de primalidad | 113
|
| 6.3. Test de primalidad AKS | 116
|
| 6.4. Algoritmos de factorización | 118
|
| 6.5. Sistema RSA | 119
|
| 6.6. Variante de decisión | 122
|
| 6.7. Logaritmo discreto | 123
|
| 6.8. Sistemas de conocimiento cero | 125
|
| 6.9. Otros problemas | 127
|
| 6.10. Complementos técnicos | 129
|
| Capítulo 7. Enfoque geométrico | 132
|
| 7.1. Panorama general | 132
|
| 7.2. Politopos convexos | 136
|
| 7.3. Politopos cíclicos | 140
|
| 7.4. Árboles de separación lineales | 143
|
| 7.5. Algoritmos de tipo directo | 145
|
| 7.6. Politopos de relajación | 149
|
| 7.7. Reducción afín | 151
|
| 7.8. Comentarios y complementos | 152
|
| Capítulo 8. Algoritmos probabilísticos | 154
|
| 8.1. Recordando las estrategias mixtas | 155
|
| 8.2. Demostraciones interactivas | 156
|
| 8.3. Problemática PCP | 159
|
| 8.4. Un camino de rutina | 161
|
| 8.5. Números primos | 163
|
| Capítulo 9. Pragmatismo y heurística | 165
|
| 9.1. Planificación de red como generalización de la programación dinámica | 165
|
| 9.2. Ámbito de aplicación del algoritmo voraz | 167
|
| 9.3. Algoritmos aproximados | 169
|
| 9.4. Método de ramificación y poda | 170
|
| 9.5. Sobre el problema PLE | 172
|
| Capítulo 10. Computación cuántica | 174
|
| 10.1. En qué consiste la idea y cuáles son las consecuencias | 174
|
| 10.2. Conceptos fundamentales | 176
|
| 10.3. El cálculo y el fenómeno de la medición | 182
|
| 10.4. Puertas cuánticas | 183
|
| 10.5. Algoritmo de búsqueda rápida | 184
|
| 10.6. Transformada de Fourier cuántica | 186
|
| 10.7. Algoritmo de factorización de Shor | 188
|
| 10.8. Antípoda del sentido común | 189
|
| 10.9. La paradoja EPR y los parámetros ocultos | 191
|
| 10.10. Tirando de la soga | 194
|
| 10.11. Comentarios y complementos | 194
|
| Capítulo 11. Resumen de las definiciones y resultados fundamentales | 197
|
| 11.1. Lista de problemas NP-completos | 197
|
| 11.2. Algoritmos y computabilidad | 200
|
| 11.3. Problema P=?NP | 202
|
| 11.4. Problema co-NP=?NP | 203
|
| 11.5. Programación lineal | 204
|
| 11.6. Aritmética y criptografía | 206
|
| 11.7. Enfoque geométrico | 207
|
| 11.8. Algoritmos probabilísticos | 211
|
| 11.9. Computación cuántica | 212
|
| Abreviaturas y notaciones | 214
|
| Bibliografía | 215
|
| Índice de materias | 217
|
