3 results
Search Results
Now showing 1 - 3 of 3
Item Modelado del 3-coloreo de grafos planares usando satisfactibilidad Incremental(2021-01) López Ramírez, Cristina; LOPEZ RAMIREZ, CRISTINA; 80296; DE ITA LUNA, GUILLERMO; 57559"Uno de los problemas fundamentales en el razonamiento automático es el problema de satisfactibilidad proposicional (SAT), el SAT es un problema de la clase de complejidad NP-Completo. Las aplicaciones de SAT rara vez se limitan a resolver sólo una fórmula de entrada, una aplicación normalmente resolverá una secuencia de fórmulas relacionadas.En esta investigación se propone una estrategia para utilizar estructuras que se formen en la fase 1 de 2-ISAT y que sean usadas durante la fase 2 del problema. Se propone revisar si pueden haber estructuras computacionales que creadas en la primer fase, resuelvan 2-ISAT en tiempo polinomial, o bien, el problema 2-ISAT es de complejidad NP."Item Cómputo de la anchura arbórea de un grafo(2016-01) Arachi Merced, Oscar Rafael; ARACHI MERCED, OSCAR RAFAEL; 901921; GUILLEN GALVAN, CARLOS; 78563En esta tesis se presentan los conceptos y resultados necesarios para computar la anchura arbórea de un grafo a través de uno de sus árboles de descomposición. Puesto que el concepto de anchura arbórea inicialmente es dado sobre la familia de todos los ´arboles de descomposición del grafo, se presentan resultados de la posibilidad de realizar este computo sobre cualquier elemento de dicha familia. También, se muestra un algoritmo de parámetro fijo tratable (PFT) junto con su implementación en Java. Finalmente, se muestran relaciones de tratabilidad con la posibilidad de expresar una propiedad grafica en lenguaje de lógica monádica de segundo orden y la condición adicional de que la anchura arbórea del grafo sea acotada.”Item Construcción de un algoritmo para contar modelos de fórmulas en 2 - FC(2015) Perez Barrios, Omar; PEREZ BARRIOS, OMAR; 552900; DE ITA LUNA, GUILLERMO; 57559“Dentro del área de ciencias de la computación se han definido gran diversidad de problemas, de los cuales se ha encontrado algoritmos para resolver gran parte de éllos. Sin embargo, conocer un conjunto de pasos para llegar a la solución de un problema no siempre es suficiente, existen algunos problemas en el área de computación en los cuales el número de operaciones que se requieren para llegar a la solución del problema aumenta mucho más rápido de lo que se incrementan los datos de entrada del problema. El estudio de estas características de un algoritmo son consideradas dentro del área de teoría de la complejidad computacional, la cual tiene sus orígenes en los inicios de la década de los 60’s, cuando los primeros usuarios de computadoras electrónicas comenzaron a prestar peculiar interés al desempeño de sus programas. Encontrar técnicas satisfactorias para resolver problemas computacionales ha eludido a investigadores por años, entre los problemas más desafiantes computacionalmente, destaca el problema de satisfactibilidad de restricciones, introducido por Stephen Arthur Cook [5], tras el cual se han desarrollado diversas líneas de investigación enfocadas en el campo de complejidad computacional.”