Apuntes de complejidad computacional
Ciudad de México, UNAM, Facultad de Ingeniería, versión digital 2023.
La obra se encuentra disponible en la siguiente liga directa::
http://www.ptolomeo.unam.mx:8080/xmlui/handle/RepoFi/18275
La solución de problemas de toda índole requiere dedicar suficiente esfuerzo para conocer lo más posible del “enemigo” que se enfrenta. La mayoría de los problemas de optimización presentan características de complejidad que los puede hacer difíciles o aún imposibles de resolver en tiempos razonables. Sin embargo, conociendo un poco más de su naturaleza, recovecos y misterios, se logra desarrollar estrategias poderosas para atacarlos y vencerlos.
Este libro introduce al conocimiento necesario para poder someterlos diseñando estrategias de solución, es decir, la Complejidad Computacional. El libro aborda temas como la medida de dificultad de problemas, algoritmos de solución eficientes, la definición de problemas polinomiales deterministas y no deterministas, y técnicas de reducciones y transformaciones entre problemas. En la aventura de resolver problemas de optimización, un principio esencial es que: “conocimiento mata esfuerzo computacional”.
CONTENIDO: Prólogo; Sobre la autora; Problemas y algoritmos 2. Máquinas de Turing y complejidad computacional 3. Problema de decisión, problema de Satisfactibilidad y otros problemas fundamentales 4. Clases P y NP 5. Reducciones polinomiales y NP-completez; Apéndice; Bibliografía.