La complejidad computacional de contar polímeros

Simple item page
dc.contributor.advisorIsaacs Giraldo, Rafael Fernando
dc.contributor.authorGutiérrez Lizarazo, Francisco Javier
dc.date.accessioned2024-03-03T20:17:26Z
dc.date.available2013
dc.date.available2024-03-03T20:17:26Z
dc.date.created2013
dc.date.issued2013
dc.description.abstractLa 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.
dc.description.abstractenglishTheory of computation studies which problems can be resolved with algorithms. But even if we can solve a problem with any algorithm this is not guarantee that we can know its solution in short time for any instance of such a problem. Computational complexity answers which problems are computational tractable and which are not, classifying them in complexity classes. For counting problems some of such classes are FP, #P y #PC classes. In this work we’re going to study the computational complexity of some problems such as the counting of perfect matchings, the counting of general matchings and self avoiding walks. These problems are related two models of the Statistical Mechanics: the monomer-dimer SAW model (self avoiding walks model). We will see that the counting of spanning trees in connected graphs and perfect matchings in planar graphs (on account of Kasteleyn Theorem) are tractable problems; and counting matchings and self avoiding walks are problems that belong to the #PC computational complexity class. When a counting problem is in #PC this means strong evidence to think that it is a intractable counting problem. Then we’re going to study two probabilistic approximation algorithms to solve in approximation way the problems of counting matching and walks in lattices of any dimensión. We finish this work with the study of two tractable subproblems of the counting of self avoiding walks using the Shutzenberger method, namely the problem of counting up-side walks in a bidimensional lattices and the problem of counting hamiltonian walks in rectangular lattices whit a fixed high. ‘Paper work ?Faculty of Sciences, School of Mathematics. Supervisor: Ph.D. Rafael Isaacs Giraldo
dc.description.degreelevelMaestría
dc.description.degreenameMagíster en Matemáticas
dc.format.mimetypeapplication/pdf
dc.identifier.instnameUniversidad Industrial de Santander
dc.identifier.reponameUniversidad Industrial de Santander
dc.identifier.repourlhttps://noesis.uis.edu.co
dc.identifier.urihttps://noesis.uis.edu.co/handle/20.500.14071/29774
dc.language.isospa
dc.publisherUniversidad Industrial de Santander
dc.publisher.facultyFacultad de Ciencias
dc.publisher.programMaestría en Matemáticas
dc.publisher.schoolEscuela de Matemáticas
dc.rightshttp://creativecommons.org/licenses/by/4.0/
dc.rights.accessrightsinfo:eu-repo/semantics/openAccess
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)
dc.rights.licenseAttribution-NonCommercial 4.0 International (CC BY-NC 4.0)
dc.rights.urihttp://creativecommons.org/licenses/by-nc/4.0
dc.subjectTeoría De La Computación
dc.subjectComplejidad Computacional
dc.subjectProblemas De Conteo
dc.subjectMatchings
dc.subjectCaminos Hamiltonianos
dc.subjectAlgoritmos De Aproximación
dc.subjectCadenas De Markov
dc.subjectMonte Carlo
dc.subjectMétodo De Shutzenberger
dc.subjectAutómatas
dc.subjectLenguajes Regulares.
dc.subject.keywordTheory Of Computation
dc.subject.keywordComputational Complexity
dc.subject.keywordCounting Problems
dc.subject.keywordHamiltonian Walks
dc.subject.keywordApproximation Algorithms
dc.subject.keywordMarkov Chains
dc.subject.keywordMonte Carlo
dc.subject.keywordShutzenberger Method
dc.subject.keywordAutomata
dc.subject.keywordRegular Language.
dc.titleLa complejidad computacional de contar polímeros
dc.title.englishThe computational complexity of counting
dc.type.coarhttp://purl.org/coar/version/c_b1a7d7d4d402bcce
dc.type.hasversionhttp://purl.org/coar/resource_type/c_bdcc
dc.type.localTesis/Trabajo de grado - Monografía - Maestria
Files
Original bundle
Now showing 1 - 3 of 3
No Thumbnail Available
Name:
Carta de autorización.pdf
Size:
97.09 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Documento.pdf
Size:
1.08 MB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Nota de proyecto.pdf
Size:
89.25 KB
Format:
Adobe Portable Document Format
Download
Collections
Maestría en Matemáticas