Problemas algorítmicos asociados al modelo Abeliano pilas de arena

Simple item page
dc.contributor.advisorMontoya Arguello, Juan Andrés
dc.contributor.authorMontoya Torres, Sergio Andrés
dc.date.accessioned2024-03-03T18:45:57Z
dc.date.available2011
dc.date.available2024-03-03T18:45:57Z
dc.date.created2011
dc.date.issued2011
dc.description.abstractEl 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.
dc.description.abstractenglishThe abelian sandpile model is a discrete dynamic system (cellular automata) which could represent natural phenomena whose dynamics is dissipative. The abelian sandpile model can be defined and studied on arbitrary graphs but the case has attracted the most interest is about one, two and three dimensional grids, since t. nese are discrete models o: aroused by the model is that this property seems to exhibit self-organized critical, w that the system states co complexity computational of algorithmic problems consists of five chapters, i this himself, in the secon prediction problem (SPP) and shows that the other mverge spontaneously to ¢: n the first defines the mo chapter introduce some a! associated to the abelian sand, problems are reducible to this canonical euclidean space. Part of the interest hich establishes ritic states. This work is in general a study of ile model and el and shows some important properties about gorithmic problems, in particular, the sandpile roblem. Then, in the following chapters study the restriction of the model to one, two an three dimensional grids, showing the results impor ant concerning the compu ational complexity of the algori hmic problems introduced in Chapter 2, in particular, as one result of this work, an algorithm is shown Chapter 4 provides a conjecture about an open problem in dimension 2 which is closely related to the sandpile prediction problem.
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/25859
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.subjectComplejidad Computacional
dc.subjectAlgoritmia
dc.subjectAutómatas Celulares
dc.subjectPilas De Arena
dc.subjectGrafos
dc.subjectComputación
dc.subjectSistemas Dinámicos Discretos.
dc.subject.keywordComputational Complexity
dc.subject.keywordAlgorithmics
dc.subject.keywordCellular Automata
dc.subject.keywordSandpiles
dc.subject.keywordGraphs
dc.subject.keywordComputation
dc.subject.keywordDiscrete Dynamical Systems.
dc.titleProblemas algorítmicos asociados al modelo Abeliano pilas de arena
dc.title.englishAlgorithmic problems associated to the abelian sandpile model
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:
205.52 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Documento.pdf
Size:
752.2 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Nota de proyecto.pdf
Size:
57.52 KB
Format:
Adobe Portable Document Format
Download
Collections
Maestría en Matemáticas