E n c i c l o p e d i a
de Conocimientos Fundamentales
UNAM ˜ SIGLO XXI
TEMA 1
COMPUTACIÓN
1.1 INTRODUCCIÓN: ENTRE EL POLVO Y LA DIVINIDAD
1.2 PROBLEMAS
1.2.1 El problema de los regalos de Arcadio
La visión del computólogo
1.3 PROBLEMAS DE LA VIDA COTIDIANA
1.3.1 El significado de resolver un problema
1.4 ALGORITMOS: RESOLVIENDO EL PROBLEMA
1.4.1 Una solución: búsqueda exhaustiva
1.4.2 Análisis de la solución de una búsqueda exhaustiva
1.4.3 Análisis del caso general de la búsqueda exhaustiva
1.5 CRECIMIENTO EXPONENCIAL
1.5.1 Crecimiento exponencial en computación
1.5.2 Crecimiento exponencial en la sociedad y en la naturaleza
Velocidad de crecimiento
1.5.3 Ejemplos de crecimiento exponencial
Variantes del problema de Arcadio
Crecimiento poblacional
Crecimiento "virulento"
1.5.4 Árboles
1.5.5 Qué tan rápida es una computadora
Una computadora muy personal: el cerebro
1.5.6 Ejemplos de crecimiento exponencial benéficos
1.6 PROBLEMAS PROBABLEMENTE DIFÍCILES, SEGURAMENTE DIFÍCILES Y AUN PEORES
1.6.1 Problemas exponenciales
1.6.2 Problemas NP-completos
1.6.3 Problemas peores que los exponenciales
1.7 RESUMEN
