Maestría en Matemáticas
Permanent URI for this collection
Browse
Browsing Maestría en Matemáticas by browse.metadata.advisor "Montoya Arguello, Juan Andrés"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Funciones de censo de lenguajes libre del contexto(Universidad Industrial de Santander, 2011) Zambrano Fernández, Luis Eduardo; Montoya Arguello, Juan AndrésEn este trabajo, estudiamos algunos de los resultados más relevantes acerca de las funciones de censo de los lenguajes libres del contexto y usamos estos resultados para resolver dos problemas de conteo delgado (tally counting problems) cuando son restringidos a grillas rectangulares de altura fija. Estos problemas surgen de la tomografía discreta y la mecánica estadística. Nuestras soluciones se basan en el método de Schützenberger-Bertoni, una importante técnica de conteo que permite reducir varios problemas de conteo al cálculo de las funciones de censo de ciertos lenguajes formales. La complejidad de calcular la función de censo de lenguajes libres del contexto está estrechamente relacionada con la ambigüedad del lenguaje. Para lenguajes regulares, existen algoritmos de tiempo lineal que permiten calcularla, para lenguajes libres del contexto no ambiguos, existen algoritmos en paralelo que permiten calcularla en tiempo polilogarítmico, sin embargo, para lenguajes libres del contexto ambiguos no se conocen algoritmos determinísticos de tiempo polinomial que permitan calcular su función de censo, solo se conocen esquemas de aproximación aleatorios completamente polinomiales que permiten aproximarla. Nuestro principal aporte consiste en reducir el problema de conteo de poliominoes en grillas rectangulares de altura fija al cálculo de la función de censo de un lenguaje libre del contexto determinístico y reducir el problema de conteo de caminos que se auto-evitan en grillas rectangulares de altura fija al cálculo de la función de censo de un lenguaje regular.Item Pilas de arena y grafos de ramanujan(Universidad Industrial de Santander, 2011) Castaneda Jaimes, Sterling; Montoya Arguello, Juan AndrésEl Modelo Abeliano de Pila de Arena y los Grafos de Ramanujan son los protagonistas de esta historia. El Modelo de Pila de Arena o modelo BTW, (introducido por los físicos Per Bak, Chao Tang y Kurt Wiesenfeld en 1988), es un sistema dinámico disipativo discreto definido sobre un grafo en el que hay intercambio de información entre los vértices del grafo. Decimos que un grafo G es óptimo para el Modelo de Pila de Arena si y sólo si la dinámica del modelo se estabiliza rápidamente. En este trabajo se estudia el comportamiento asintótico del Modelo Abeliano de Pilas de Arena sobre grafos de alta conectividad. Centramos nuestra atención en grafos de Ramanujan. Nosotros conjeturábamos que el proceso de estabilización es veloz (eficiente) sobre clases de grafos de Ramanujan, esto es: conjeturábamos que sobre esta clase de grafos las avalanchas eran mucho más cortas. La mejor cota superior para la longitud de avalanchas críticas sobre grafos generales es la cota de Tardos, la cual estipula que las avalanchas tienen una longitud acotada por O(n³), donde n es el número de vértices del grafo, siendo esta cota óptima. Nosotros probamos que sobre grafos de Ramanujan, las avalanchas críticas tienen una longitud acotada por O(n1,5).Item Problemas algorítmicos asociados al modelo Abeliano pilas de arena(Universidad Industrial de Santander, 2011) Montoya Torres, Sergio Andrés; Montoya Arguello, Juan AndrésEl modelo abeliano pilas de arena es un sistema dinámico discreto (un autómata celular) el cual podría llegar a representar fenómenos de la naturaleza cuya dinámica es disipativa. El modelo abeliano pilas de arena puede ser definido y estudiado sobre grafos arbitrarios pero el caso que más interés ha despertado es el de las grillas unidimiensionales, bidimensionales y tridimensionales, dado que estas son los modelos canónicos discretos del espacio euclidiano. Parte del interés que suscita el modelo se debe a que este parece exhibir la propiedad de auto-organización crítica, la cual estipula que el sistema converge espontáneamente a estados críticos. Este trabajo es en general un estudio de la complejidad computacional de algunos problemas algorítmicos asociados al modelo abeliano pilas de arena y está compuesto por cinco capítulos; en el primero se define el modelo y se muestran algunas características importantes acerca de éste mismo, en el segundo capítulo se introducen algunos problemas algorítmicos, en particular, el problema de la predicción SPP (sandpile prediction problem) y se muestra que los demás problemas son reducibles a tal problema. En los capítulos posteriores se estudia la restricción del modelo a las grillas de dimensión 1,2 y 3, mostrando los resultados más importantes referentes a la complejidad computacional de los problemas algorítmicos introducidos en el capítulo 2, en particular, como uno de los resultados de este trabajo, se exhibe un algoritmo en el capítulo 4 que proporciona una conjetura acerca de un problema abierto que aún se mantiene en dimensión 2 y que está estrechamente relacionado con el problema de la predicción.