Please use this identifier to cite or link to this item: http://www.ptolomeo.unam.mx:8080/xmlui/handle/RepoFi/18275
Title: Apuntes de complejidad computacional
Authors: Elizondo Cortés, Mayra
Keywords: omptimización
computabilidad
algoritmos
máquinas de Turing
clase P
clase NP
reducciones polinomiales
problemas NP-completos
Issue Date: 1-Jul-2014
Publisher: Facultad de Ingeniería
Abstract: 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”.
Description: 1. 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
URI: http://www.ptolomeo.unam.mx:8080/xmlui/handle/RepoFi/18275
Appears in Collections:División de Ingeniería Mecánica e Industrial

Files in This Item:
File Description SizeFormat 
2023_Apuntes_de_complejidad_computacional.pdfApuntes de complejidad computacional26.37 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.