La complejidad computacional de contar polímeros
No Thumbnail Available
Date
2013
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
La teoría de la computación es el estudio de aquellos problemas que pueden ser resueltos algorítmicamente. Pero aunque podamos resolver un problema algorítmicamente esto no garantiza que podamos conocer su solución en un tiempo razonable para todas las instancias de dicho problema. La Complejidad Computacional se encarga de responder cuáles problemas son computacionalmente tratables y cuáles no, clasificándolos en lo que se conocen como clases de complejidad. Para los problemas de conteo algunas de estas son las clases FP, AP y F¿P-completos. En este trabajo estudiaremos la complejidad computacional de algunos problemas de conteo entre los que se destacan el conteo de emparejamientos perfectos en grafos planos, el de emparejamientos en general y el de caminos que se auto evitan, que están relacionados con dos modelos de la Mecánica Estadística: El modelo monómero-dímero y el modelo SAW de la termodinámica de polímeros. Mostraremos que contar los árboles generadores de un grafo conexo y los matchings perfectos en grafos planos es computacionalmente tratable gracias al ingenioso teorema de Kasteleyn, y que contar matchings y caminos que se auto evitan son problemas en la clase computacional de los problemas ¿4¿P-completos. Evidencia suficiente para creer que estos dos problemas son computacionalmente intratables. Después de esto estudiaremos dos algoritmos de aproximación probabilística que nos permitirá aproximar la solución de dichos problemas, para finalizar con el estudio de dos subproblemas tratables acerca de caminos que se auto evitan utilizando el método de Shutzenberger: el problema de contar caminos sin descenso en el retículo bidimensional y el problema de contar caminos hamiltonianos en retículos rectangulares de altura fija.
Description
Keywords
Teoría De La Computación, Complejidad Computacional, Problemas De Conteo, Matchings, Caminos Hamiltonianos, Algoritmos De Aproximación, Cadenas De Markov, Monte Carlo, Método De Shutzenberger, Autómatas, Lenguajes Regulares.