30 research outputs found
Diseño de un algoritmo para el conteo de modelos de formulas booleanas en dos forma normal conjuntiva
No full textTesis de Maestría para obtención de gradoEl conteo de modelos sobre fórmulas booleanas es el problema conocido como #SAT, el cual forma parte de los problemas catalogados como #P-Completos. #2SAT es una restricción a #SAT, donde las cláusulas que componen una fórmula contienen a lo m as dos variables, uno de los métodos usados para resolver este problema es la descomposición de la fórmula, la cual puede realizarse por la asignación de valores de verdad a una variable o a una cláusula. La descomposición de una fórmula por variable requiere un procedimiento de selección para la variable o cláusula a eliminar, el método m as utilizado es seleccionar la variable que tiene una mayor aparición en la fórmula, de esta forma se puede reducir el número de cláusulas dado el número de apariciones de la variable seleccionada. Por otro lado, la descomposición de una fórmula por cláusula requiere un método para seleccionar la cláusula m as viable a eliminar, este segundo método permite reducir la cantidad de procesos de descomposición de la fórmula con respecto a la descomposición por variable. Si se quieren eliminar dos variables por el primer procedimiento es necesario generar cuatro subfórmulas, sin embargo, con el segundo procedimiento es posible generar tres subfórmulas aprovechando la relación existente entre las dos variables que se encuentran dentro de la cláusula. El objetivo de la descomposición de la fórmula es aplicar el método de forma iterativa hasta encontrar subfórmulas que puedan ser resueltas en tiempo polinomial. Una clase de fórmulas en las cuales existe un procedimiento polinomial para calcular #2SAT es aquella en la cual sus variables aparecen a lo m as cuatro veces en la fórmula. En esta tesis se estudian clases de fórmulas cuyo conteo de modelos puede realizarse en tiempo polinomial, además se desarrollan métodos para resolverlas basados en la topología inducida por su gr a ca signada. Las topologías para las cuales se presentan algoritmos polinomiales se conocen como cactus y outerplanar. As mismo, demostramos experimentalmente que los algoritmos obtenidos son competitivos respecto a la herramienta más reciente reportada en la literatura que es sharpSAT tanto en fórmulas cactus y outerplanar como en instancias generales.Conacy
Desarrollo de una política de selección para general Game Playing basada en el problema del bandido multi-armado
Full text linkDurante la historia de la Inteligencia Artificial se han desarrollo diversos agentes inteligentes capaces de jugar juegos de tablero de entre los m´as destacados se tiene a DeepBlue para el ajedrez y AlphaGo para el juego de Go. Sin embargo, estos agentes solo est´an enfocados en un solo juego por lo cual el paso natural es desarrollar agentes capaces de jugar m´as de un juego, idea que persigue el ´area General Game Playing la cual se enfoca en desarrollar agentes completamente aut´onomos que puedan jugar cualquier juego de tablero sin intervenci´on humana y sin conocimiento previo. La mayor´ıa de los agentes est´an basados en el m´etodo de Arbol de B´usqueda Monte Carlo que usa ´ simulaciones Monte Carlo para estimar movimientos prometedores, este m´etodo consiste en cuatro pasos: Selecci´on, Expansi´on, Simulaci´on y Propagaci´on Hacia Atr´as. Los esfuerzos para incrementar el rendimiento del Arbol de B´usqueda Monte Carlo se enfocan en el paso de simulaci´on, sin embargo, ´ es tambi´en el paso de Selecci´on el que repercute en dicho rendimiento. El paso de selecci´on controla la forma en que se recorre el ´arbol asociado al juego de tablero, dicho recorrido es guiado por una Pol´ıtica de Selecci´on de la cual Upper Confidence Bound es la popularmente usada. En esta tesis de investigaci´on se presentan dos pol´ıticas de selecci´on UCBα1 y UCBα2, las cuales est´an basadas en Upper Confidence Bound pero est´an pensadas completamente para su aplicaci´on en General Game Playing. UCBα1 y UCBα2 a diferencia de Upper Confidence Bound aprovechan la estructura del ´arbol asociados a los juegos de tablero para determinar para un nodo padre, cu´anto se debe explorar los nodos hijos que representan los movimientos disponibles antes de decidirse por explotar un nodo hijo con un movimiento prometedor. Upper Confidence Bound controla la exploraci´on de nodos hijos por medio de una constante de exploraci´on, sin embargo, esta constante permanece fija en todo el ´arbol sin importar el n´umero de nodos hijos. UCBα1 y UCBα2 usan una funci´on que depende del
Algoritmos híbridos para la localización automática de puntos cefalométricos en volúmenes de tomografía computarizada de haz cónico para cefalometría 3D
Full text linkLa cefalometría es un método de diagnóstico para obtener mediciones del cráneo que depende de la correcta localización de puntos anatómicos, conocidos como puntos cefalométricos. Dicha localización, generalmente se realiza de forma manual utilizando radiografías, y recientemente, tomografías de haz cónico (CBCT, Cone Beam Computed Tomography). La cefalometría una tarea que consume tiempo clínico y se considera repetitiva y tediosa (Guia, 2004), por tanto, la localización automática se establece como un problema de visión computacional estudiado recientemente en volúmenes CBCT. En esta tesis se presentan tres nuevos algoritmos híbridos para la localización automática de puntos cefalométricos en volúmenes CBCT así como su evaluación y comparación experimental con técnicas recientes del estado del arte. El primer algoritmo, está basado en conocimiento y en modelos deformables. Este algoritmo utiliza modelos de forma activa (ASM, Active Sha- pe Model) (Cootes et al., 1993) entrenados para realizar la búsqueda de puntos cefalométricos en proyecciones DRR (Digitally Reconstructed Radiographs) laterales y frontales independientes. Finalmente, en un proceso de correlación de ambas proyecciones, se estima la ubicación tridimensional de los puntos cefalométricos. El segundo algoritmo está fundamentado en el algoritmo basado en conocimiento propuesto por Gupta et al. (2015a). En este algoritmo se cambia totalmente la inicialización de Gupta por una inicialización en correlación de proyecciones. Posteriormente, dicha inicialización permite segmentar sub-volúmenes y llevar a cabo una búsqueda tridimensional local para la localización individual de cada punto estudiado. El tercer algoritmo para la localización automática de puntos cefalométricos en volúmenes CBCT, está basado en el registro de superficies no rígidas. En este algoritmo, se construyen imágenes 3D estructuradas a partir de la obtención de mapas de profundidad simulados desde cada volumen de prueba. Enseguida, mediante ICP (Iterative Closest Point) no-rígido, el registro 3D de una superficie de referencia con las superficies extraídas de los volúmenes de prueba es lleva- do a cabo. Así, los puntos cefalométricos anotados manualmente en la superficie de referencia, son reparametrizados a las demás superficies. Los algoritmos desarrollados probaron su eficiencia en la localización de 18 puntos cefalométricos comunes en un conjunto de 24 volúmenes CBCT seleccionados de una base de datos pública: The Virtual Skeleton Database (Kistler et al., 2013a). Luego del análisis de resultados, se concluye que la ubicación de los puntos cefalométricos puede lograrse por medio del uso de algoritmos híbridos de forma simple y eficiente. Estos resultados indican que los algoritmos son competitivos en comparación con algoritmos del estado del arte (Codari et al., 2016; Gupta et al., 2015a) alcanzando un error le localización medio de 2.07 mm con 1.16 mm de desviación estándar. Asimismo, el tiempo de procesamiento de los algoritmos desarrollados permite cálculos en un tiempo clínicamente aceptable al realizar el análisis por volumen en un tiempo medio de 12 minutos. Por otro lado, se debe notar que la base de datos CBCT experimentada es aún insuficiente para generalizar los resultados debido al número de sujetos, así como la ausencia de información de captura, origen y homogeneidad de los datos. Una forma de atender esta necesidad, puede ser promover la colaboración con instituciones médicas
Calculo del clique-width en graficas simples de acuerdo a su estructura
Full text linkEl cálculo del cliquewidth, un número entero que es un invariante para gráficas, ha sido estudiado de manera activa, ya que existen problemas catalogados como NP-Completos que tienen complejidad baja si su representación en gráficas tiene cliquewidth acotado. De cierta manera este parametro mide la dificultad de descomponer una gráfica en una estructura llamada árbol (por su topología). La importancia de este invariante radica en que si un problema de gráficas puede ser acotado por ella entonces puede ser resuelto en tiempo polinomial según el teorema principal de Courcelle. Por otra parte el cliquewidth tiene una relación directa con el invariante tree-width con la distinción de que el primero es más general que el segundo. Para calcular este tipo de invariantes se han propuesto en la literatura diferentes procedimientos que dividen la gráfica original en subgráficas las cuales determinan la complejidad, por lo que en la investigación aquí reportada se ha utilizado una descomposición particular de una gráfica simple, la cual consiste en descomponer la gráfica en ciclos simples y árboles. Las gráficas que consisten de ciclos simples y árboles se denominan cactus, sobre las cuales hemos demostrado que el clique-width es menor o igual a 4 lo que mejora la cota establecida por la relación entre el clique-width y el invariante treewidth la cual establece que el cwd(G) ≤ 3·2twd(G)−1. De igual manera se han estudiado otro tipo de gráficas denominadas poligonales, formadas por polígonos con mismo número de lados los cuales comparten entre si una única arista; sobre este tipo de gráficas en esta investigación se ha demostrado que el cliquewidth es igual a 5, de igual manera mejorando la cota conocida por la relación de las invariantes mencionadas anteriormente. Finalmente, estudiando el comportamiento de operaciones de union de estas subgráficas se ha propuesto un método de aproximación para el cálculo del cliquewidth de una gráfica simple de manera general. El algoritmo esta basado en el clásico algoritmo de Disjktra que encuentra el camino mas corto entre dos vértices de una gráfica. Del planteamiento de los algoritmos mencionados anteriormente se obtuvo la publicación de tres artículos, en los que se incluye el desarrollo de las demostraciones para el cálculo del clique-width en los diferentes escenarios de estudio.CONACy
Calculo del clique-width en graficas simples de acuerdo a su estructura
No full textEl cálculo del cliquewidth, un número entero que es un invariante para gráficas, ha sido estudiado de manera activa, ya que existen problemas catalogados como NP-Completos que tienen complejidad baja si su representación en gráficas tiene cliquewidth acotado. De cierta manera este parametro mide la dificultad de descomponer una gráfica en una estructura llamada árbol (por su topología). La importancia de este invariante radica en que si un problema de gráficas puede ser acotado por ella entonces puede ser resuelto en tiempo polinomial según el teorema principal de Courcelle.
Por otra parte el cliquewidth tiene una relación directa con el invariante tree-width con la distinción de que el primero es más general que el segundo. Para calcular este tipo de invariantes se han propuesto en la literatura diferentes procedimientos que dividen la gráfica original en subgráficas las cuales determinan la complejidad, por lo que en la investigación aquí reportada se ha utilizado una descomposición particular de una gráfica simple, la cual consiste en descomponer la gráfica en ciclos simples y árboles. Las gráficas que consisten de ciclos simples y árboles se denominan cactus, sobre las cuales hemos demostrado que el clique-width es menor o igual a 4 lo que mejora la cota establecida por la relación entre el clique-width y el invariante treewidth la cual establece que el cwd(G) ≤ 3·2twd(G)−1. De igual manera se han estudiado otro tipo de gráficas denominadas poligonales, formadas por polígonos con mismo número de lados los cuales comparten entre si una única arista; sobre este tipo de gráficas en esta investigación se ha demostrado que el cliquewidth es igual a 5, de igual manera mejorando la cota conocida por la relación de las invariantes mencionadas anteriormente.
Finalmente, estudiando el comportamiento de operaciones de union de estas subgráficas se ha propuesto un método de aproximación para el cálculo del cliquewidth de una gráfica simple de manera general. El algoritmo esta basado en el clásico algoritmo de Disjktra que encuentra el camino mas corto entre dos vértices de una gráfica.
Del planteamiento de los algoritmos mencionados anteriormente se obtuvo la publicación de tres artículos, en los que se incluye el desarrollo de las demostraciones para el cálculo del clique-width en los diferentes escenarios de estudio.CONACy
Diseño de un algoritmo para aproximar el coloreo de una gráfica mediante conjuntos maximales independientes
No full textEl problema del coloreo de gráficas por su importancia se ha tratado de solucionar por diferentes algoritmos, entre los más usados se encuentran los heurísticos, los cuales aproximan la solución, además existen diferentes metodologías de solución. En particular, el presente trabajo de Tesis se ha centrado en tres algoritmos heurísticos, el algoritmo greedy de JGraphT, el algoritmo determinista propuesto por Guzmán et al. y las propuestas híbridas de combinar un algoritmo determinista con un algoritmo genético. Derivado de los resultados obtenidos se puede concluir que en términos de n umero de colores las propuestas de Guzmán et al.(Apéndice A) y la que se presenta como trabajo final de tesis son competitivas, debido a que, el promedio de colores obtenidos en 20 ejecuciones, los resultados obtenidos por la propuesta híbrida de esta tesis, son mejores en gran medida que los obtenidos por Guzmán et al. debido a que el número de colores no está disperso con respecto al promedio obtenido, esto se observa en la desviación estándar obtenida para cada prueba. Adicionalmente, de los resultados de coloreo obtenidos por JGraphT el 62.5% excede el coloreo de una a diez unidades de color, mientras que la propuesta de esta Tesis en s olo 45.83% de las instancias el coloreo excede de una a cinco unidades de color, mientras que para Guzmán et al. en un 58.33% el coloreo obtenido excede de una a seis unidades de color. Los resultados obtenidos en esta investigación y concluidos como los que mantienen una mejor aproximación al coloreo, se deben a la implementación de la Fase de regeneración, la cual favoreció en la mayoría de las instancias, que de la gráfica conocida como residual, a que la aproximación al coloreo se cumpliera con el número de colores restantes, es decir el número k conocido como el mejor coloreo obtenido hasta el momento, se le resta el número de MISes extraídos de la primera fase, debido a que los MISes de la fase de extracción son considerados de la completa, dejando una gráfica residual densa, la cual complica que el coloreo sea propio con k-MISes. Por otro lado, de los análisis realizados en la Sección 4 se encuentra el de tiempo de ejecución, donde se muestra el tiempo en segundos que tardó cada algoritmo en obtener una aproximación, de esto se puede concluir que en términos de tiempo de ejecución el algoritmo híbrido propuesto, toma un mayor tiempo de ejecución en comparación con el resto de los algoritmos comparados, debido a que en la fase de regeneración se considera un número de iteraciones para reconstruir un MIS, así como también el volver a implementar la fase completa de coloreo, dentro de la cual el tiempo que se toma en ejecutar la búsqueda Tabú incrementa el tiempo de ejecución. Sin embargo, ya que el objetivo general fue mejorar la aproximación al coloreo, se considera que se cumplió el objetivo y se verificó la hipótesis propuesta.Dada una gráfíca no dirigida G = (V;E) con un conjunto de vértices V y un conjunto de aristas E, el problema del coloreo de gráfícacas consiste en particionar todos los vértices de V en el mínimo número K de conjuntos (colores), con la característica de que cada par de vértices en un conjunto no compartan arista. El problema de coloreo se ha estudiado desde 3 perspectivas, la primera es el problema original, encontrar el mínimo número de colores con los cuales una gráfíca puede ser coloreado, la segunda trata de decidir si una gráfíca es k colorable, mientras que la última, aproxima el coloreo con respecto al mejor valor reportado en la literatura (ya que puede no conocerse el mínimo). Diversas propuestas de algoritmos se han desarrollado de manera exacta o heurísticas. En esta Tesis se propone un algoritmo de tipo heurístico resultado de la combinación de un algoritmo determinista y un algoritmo evolutivo para aproximar el coloreo de gráficas con respecto al mejor valor reportado en la literatura. El algoritmo propuesto se evalúa con un conjunto de gráficas propuestas en la literatura. Los resultados obtenidos validan la viabilidad de la propuesta con respecto a otros algoritmos reportados en la literatura.Conacyt: 702275/58443
Lenguaje de programación cuántico QML con historial, reversibilidad y cálculo lambda con mediciones
Full text linkResearch in quantum computing allows us to think about computing in a new and different way, having the ambition to solve problems more efficiently than with classical computing. Now a days, conventional tasks cannot be practically developed in a quantum computer, however, it is possible to think and develop abstractions of them, for example through quantum programming languages, being the core of this research, in particular the Quantum Meta Language (QML). We present a semantic model that incorporates reversibility via a history track for the quantum programming language QML, considering classical and quantum data, omitting measurements. With the history, the reversibility can be explicitly and naturally applied from the proposed rules. The language is worked first with classical data and extrapolated to quantum data. Also, the QML language and quantum lambda calculus were linked, giving as product a syntax with quantum measurements, operational semantics, typing rules and some formal proofs.La investigación en el cómputo cuántico permite pensar de una forma nueva y diferente la computación, teniendo la ambición de solucionar problemas de manera más eficiente que con el cómputo clásico. Por ahora, las tareas convencionales no se pueden desarrollar de manera práctica en una computadora cuántica, sin embargo, sí se puede pensar y desarrollar abstracciones de éstas, por ejemplo a través de lenguajes de programación cuánticos, siendo el núcleo de esta investigación, en particular el lenguaje Quantum Meta Language (QML). Se presenta un modelo semántico que incorpora reversibilidad a través de una pista de historial para el lenguaje de programación cuántico QML, considerando datos clásicos y cuánticos, omitiendo mediciones. Con la pila de historial, la reversibilidad puede aplicarse explícita y naturalmente a partir de las reglas propuestas. El lenguaje se trabaja gradualmente, inicialmente con datos clásicos y un procedimiento similar al clásico se extrapola con datos cuánticos. Además, se vincularon los lenguajes QML y cálculo lambda cuántico, dando como producto una sintaxis con mediciones cuánticas, semántica operacional, reglas de tipado y ciertas pruebas formales
Functional first order definability of LRTp
No full textThe language LRTp is a non-deterministic language for exact real number computation. It has been shown that all computable rst order relations in the sense of Brattka are denable in the language. If we restrict the language to single-valued total relations (e.g. functions), all polynomials are denable in the language. This paper is an expanded version of [12] in which we show that the non-deterministic version of the limit operator, which allows to dene all computable rst order relations, when restricted to single-valued total inputs, produces single-valued total outputs. This implies that not only the polynomials are denable in the language but also allcomputable rst order functions
Functional first order definability of LRTp
No full textThe language LRTp is a non-deterministic language for exact real number computation. It has been shown that all computable rst order relations in the sense of Brattka are denable in the language. If we restrict the language to single-valued total relations (e.g. functions), all polynomials are denable in the language. This paper is an expanded version of [12] in which we show that the non-deterministic version of the limit operator, which allows to dene all computable rst order relations, when restricted to single-valued total inputs, produces single-valued total outputs. This implies that not only the polynomials are denable in the language but also allcomputable rst order functions
The Incremental Satisfiability Problem for a Two Conjunctive Normal Form
Full text linkWe propose a novel method to review K ⊢ φ when K and φ are both in Conjunctive Normal Forms (CF). We extend our method to solve the incremental satisfiablity problem (ISAT), and we present different cases where ISAT can be solved in polynomial time. Especially, we present an algorithm for 2-ISAT. Our last algorithm allow us to establish an upper bound for the time-complexity of 2-ISAT, as well as to establish some tractable cases for the 2-ISAT problem
