Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)Montoya Arguello, Juan AndrésMontoya Torres, Sergio Andrés2024-03-0320112024-03-0320112011https://noesis.uis.edu.co/handle/20.500.14071/25859El 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.application/pdfspahttp://creativecommons.org/licenses/by/4.0/Complejidad ComputacionalAlgoritmiaAutómatas CelularesPilas De ArenaGrafosComputaciónSistemas Dinámicos Discretos.Universidad Industrial de SantanderTesis/Trabajo de grado - Monografía - MaestriaUniversidad Industrial de Santanderhttps://noesis.uis.edu.coComputational ComplexityAlgorithmicsCellular AutomataSandpilesGraphsComputationDiscrete Dynamical Systems.info:eu-repo/semantics/openAccessAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)