Escuela de Matemáticas

Permanent URI for this community

https://noesis.uis.edu.co/handle/20.500.14071/8939

Browse

Browsing Escuela de Matemáticas by browse.metadata.advisor "Isaacs Giraldo, Rafael Fernando"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    La complejidad computacional de contar polímeros
    (Universidad Industrial de Santander, 2013) Gutiérrez Lizarazo, Francisco Javier; Isaacs Giraldo, Rafael Fernando
    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.