Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)Isaacs Giraldo, Rafael FernandoGutiérrez Lizarazo, Francisco Javier2024-03-0320132024-03-0320132013https://noesis.uis.edu.co/handle/20.500.14071/29774La 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.application/pdfspahttp://creativecommons.org/licenses/by/4.0/Teoría De La ComputaciónComplejidad ComputacionalProblemas De ConteoMatchingsCaminos HamiltonianosAlgoritmos De AproximaciónCadenas De MarkovMonte CarloMétodo De ShutzenbergerAutómatasLenguajes Regulares.Universidad Industrial de SantanderTesis/Trabajo de grado - Monografía - MaestriaUniversidad Industrial de Santanderhttps://noesis.uis.edu.coTheory Of ComputationComputational ComplexityCounting ProblemsHamiltonian WalksApproximation AlgorithmsMarkov ChainsMonte CarloShutzenberger MethodAutomataRegular Language.info:eu-repo/semantics/openAccessAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)