In contrast to established approaches that analyze networks based on their structural properties, networks can also be studied by investigating the patterns that are evolved by a discrete dynamical system built upon them, such as cellular automata (CAs). Combined with networks these tools can be used to map the relationship between the network architecture and its impact on the patterns evolved by the governing spatially discrete dynamical system. This thesis focuses on the investigation of discrete spatially explicit models (SEMs), among which are CAs, for network analysis and characterization. The relationship between network architecture and its dynamic aspects concerning pattern formation is studied. Additionally, this work aims at the development of evolutionary methods that can be employed for extracting features from such patterns and then be used as network descriptors. In order to achieve this goal, methods that integrate the network structure with the SEMs were proposed, implemented and analyzed. The proposed family of network automata is characterized by birth-survival dynamics that results in different categories of spatio-temporal patterns. Such patterns were quantitatively assessed and used to characterize different network topologies and perform classification tasks in the context of pattern recognition. Inspired by the classic Life-like CA, the proposed Life-like Network Automata (LLNA) illustrate how such tasks can be performed in real-world applications. In addition, the rock-paper-scissors (RPS) model, normally implemented on square lattices, was investigated by defining it on networks. The obtained results confirm the potential of the proposed quantitative analysis of the spatio-temporal patterns for network classification. This quantitative analysis was performed for a set of different pattern recognition tasks and for the majority of them, the classification performance improved. In addition, the reliability of LLNA as a general tool for pattern recognition applications was demonstrated in a diverse scope of classification tasks. The applicability of structural network descriptors was also highlighted in the context of shape characterization in computer vision. Through the proposed approach, the link between these network descriptors and the shape properties, such as angle and curvature, was illustrated. Moreover, when chosen adequately, the network descriptors led to a better classification performance for different shape recognition tasks. Regarding the RPS model, we demonstrated that the presence of long-range correlations in some networks directly influence the RPS dynamics. Finally, it was shown how a commuter network can be used to predict influenza outbreaks. All the proposed methods use different aspects of network analysis and contribute to the study of CAs and other SEMs on irregular tessellations, in contrast to the commonly used regular topologies. In addition, new insights were obtained concerning pattern recognition in networks through the use of spatio-temporal patterns as network descriptors. / Em contraste às abordagens clássicas que analisam redes com base em suas propriedades estruturais, as redes também podem ser estudadas investigando-se os padrões desenvolvidos por um sistema dinâmico discreto construído sobre essas redes, como os autômatos celulares (CAs). Combinadas às redes, essas ferramentas podem ser usadas para se mapear a relação entre a arquitetura da rede e seu impacto nos padrões obtidos pelo sistema dinâmico subjacente. Esta tese está focada na investigação de modelos discretos espacialmente explícitos (SEMs), entre os quais os CAs, para análise e caracterização de redes. A relação entre a arquitetura da rede e seu aspecto dinâmico em relação à formação de padrões é investigada. Além disso, este trabalho visa o desenvolvimento de métodos evolutivos que podem ser usados para extrair características de tais padrões para, então, serem usados como descritores de redes. Para atingir este objetivo, métodos que integram a estrutura da rede com os SEMs foram propostos, implementados e analisados. A família de redes-autômatos proposta é caracterizada por uma dinâmica de nascimento-sobrevivência que resulta em diferentes categorias de padrões espaço-temporais. Tais padrões foram avaliados quantitativamente e utilizados para caracterizar diferentes topologias de redes e realizar tarefas de classificação no contexto do reconhecimento de padrões. Inspirados pelo clássico Life-Like CA, a rede-autômato proposta, Life-like (LLNA), ilustra como tais tarefas podem ser realizadas em aplicações mais realistas. Além disso, o modelo de rock-paper-scissors (RPS), normalmente implementado em reticulados quadrados, foi investigado usando-se redes como tesselações. Os resultados obtidos confirmam o potencial da análise quantitativa proposta dos padrões espaço-temporais para classificação de redes. Essa análise quantitativa foi realizada para um conjunto de tarefas de reconhecimento de padrões, e, para a maioria dessas tarefas, o desempenho da classificação melhorou. Além disso, a confiabilidade do LLNA como uma ferramenta genérica para reconhecimento de padrões foi demonstrada para várias tarefas de classificação de diferentes escopos. A aplicabilidade de descritores estruturais de redes também foi destacada no contexto de caracterização de formas em visão computacional. Através da abordagem proposta, a ligação entre esses descritores de rede e as propriedades da forma, como ângulo e curvatura, foi ilustrada. Além disso, quando escolhidos adequadamente, os descritores de rede levam a um melhor desempenho de classificação para diferentes tarefas de categorização de formas. No que diz respeito ao modelo RPS, demonstramos que a presença de correlações de longo alcance nas redes afeta diretamente a dinâmica do modelo. Finalmente, foi apresentado como uma rede de transporte pode ser usada para prever surtos de gripe. Todos os métodos propostos utilizam diferentes aspectos da análise de redes e contribuem para o estudo de CAs e outras SEMs em tesselações irregulares, uma vez que estes modelos são geralmente descritos em topologias regulares. Além disso, uma nova metodologia foi proposta em relação ao reconhecimento de padrões em redes através do uso de padrões espaço-temporais como descritores da rede.

Le sujet abordé dans cette thèse concerne la contrôlabilité d’une classe de systèmes spatio-temporels, entièrement discrets de type automates cellulaires (AC). Le but de cette étude est de mettre en lumière de nouvelles pistes pour prouver la contrôlabilité des systèmes complexes. Plus spécifiquement, cette thèse se focalise sur la contrôlabilité régionale qui consiste à se restreindre à une région du domaine où le système devra atteindre un objectif donné à travers des actions ciblées. Le cas d’AC Booléens a été particulièrement examiné tout au long de cette thèse. La première partie est consacrée à l’étude du problème de la contrôlabilité régionale des AC déterministes lorsque les actions sont exercées sur la frontière de la régioncontrôlée. Une première démarche que nous avons utilisée s’appuie sur les chaines de Markov et la contrôlabilité est caractérisée en établissant une matrice similaire à leur matrice de transition en utilisant les définitions d’une chaîne ergodique et régulière. Cette étude a été étendue au cas des AC probabilistes qui sont largement utilisés pour modéliser de nombreux phénomènes réels. Le même problème a été appréhendé en utilisant des outils de la théorie des graphes. Nous proposons des conditions nécessaires et suffisantes pour la contrôlabilité régionale des AC déterministes en utilisant les notions de circuit hamiltonien et de composante fortement connexe. Le contrôle qui assure la contrôlabilité régionale est défini à travers un algorithme préimages. La deuxième partie est dédiée au problème de la contrôlabilité régionale frontière des AC Booléens qui consiste à agir sur la frontière du domaine pour atteindre un objectif sur une région cible. Nous considérons d’abord des AC linéaires pour lesquels nousdonnons un résultat de caractérisation grâce à la condition de Kalman. Nous proposons un algorithme pour déterminer le contrôle qui permet de forcer l’apparition d’une configuration désirée dans la région d’étude. Le cas des AC non linéaires a été également considéré en utilisant un algorithme de recherche des préimages. / The issue addressed in this thesis concerns the controllability of a class of discrete spatio-temporal systems named cellular automata (CA). The purpose of this study is to highlight new ways to prove the controllability of complex systems. Morespecifically, this thesis focuses on regional controllability which consists in restricting the study to a subregion of the domain where the system will have to achieve a given objective through targeted actions. The case of Boolean CA have been particularly examined throughout this thesis. The first part is devoted to the study of the problem of the regional controllability of deterministic CAs when the actions are exerted on the boundaries of the controlled region. A first approach that we used relies on Markov chains and controllability is characterized by establishing a matrix similar to their transition matrix using the definitions of a regular and ergodic chain. This study has been extended to the case of probabilistic CAs that are widely used tomodel many real phenomena. The same problem has been apprehended using tools of graph theory. We proposenecessary and sufficient conditions for the regional controllability of deterministic CAs using the notions of Hamiltonian circuit and strongly connected component. The control that ensures regional controllability is defined through a preimage algorithm.The second part is devoted to the problem of the boundary regional controllability of Boolean CAs, which consists of acting on the boundary of the domain in order to reach a desired goal in a target region. We first consider linear CAs for which we givea characterization result using the Kalman condition. We propose an algorithm to determine the control that allows to force the appearance of a desired configuration in the study area. The case of nonlinear CAs was also considered using a preimagesearch algorithm.

La prévention du risque volcanique est un enjeu majeur, notamment pour l'Etna, dont les éruptions fréquentes menacent la province de Catane. Sont exposés les éléments physiques nécessaires à la compréhension des mécanismes intervenant dans un écoulement de lave basaltique. Un système d'information intégrant les principaux aspects du risque volcanique et permettant la création de cartes de risques est alors proposé. Ce système comprend un modèle, basé sur les automates cellulaires et intégrant le traitement d’images satellitaires. Il permet de simuler l'évolution d'une coulée ainsi que son débit. Ce système est alors intégré dans un Système d'Information Géographique. Il est validé sur les éruptions 2001, 2006 et 2007. Enfin, nous développons, pour l’enrichir, un modèle numérique pour le refroidissement d'une coulée de lave à l'aide des Smoothed Particle Hydrodynamics. Ce modèle, validé sur différents cas test, est appliqué au refroidissement d'un lac et d’une coulée de lave. Keywords : risque volcanique, automates cellulaires, système de veille, information élaborée, système d'information géographique, Smoothed Particle Hydrodynamics / Preventing volcanic risk is a major challenge, in particular when dealing with Mt Etna whose frequent eruptions regularly threaten Catane province. First, the physical elements necessary to understand the mechanism intervening in basaltic lava flow are exposed. Then, we develop an information system which deals with the main aspects of volcanic risk : lava flow evolution foresight and risk map design. This system is integrated in a geographical information system and is composed of both a model based on cellular automata permitting to simulate the evolution of a lava flow, and an infrared satellite image treatment module permitting to evaluate the lava flux rate. All the models and procedures developed were validated with the 2001, 2006 and 2007 eruptions. Lastly, to enhance the information system, we develop a digital model for lava flow cooling by means of Smoothed Particles Hydrodynamics. This model is validated by different case tests before being applied to the cooling of a lava lake

I detta arbete undersöktes processuell generering med tre algoritmer i syfte att skapa grottliknande banor och utvärdera kriterier baserat på eftertraktande egenskaper gällande tid, storlek, variation och pålitlighet. Algoritmerna är cellulär automat, random walk och Perlin noise. Flera olika hjälpfunktioner och algoritmer användes för utvärderingen av kriterierna. Syftet med arbetet var att ta reda på vilken av dessa algoritmer skulle passa bäst att användas i ett roguelikespel. Slutsatsen som drogs från undersökningen är att algoritmen random walk gav det bästa resultat gällande pålitlighet, variation och minst antal områden. Cellulär automat gav bäst resultat för genereringstid och minst antal golvytor. Perlin noise gav minst märkvärdigt resultat, men tillät relativt bättre kontroll över mängden golvytor än både cellulär automat och random walk. Överlag gav random walk det bästa resultat för att användas i syftet att skapa grottliknande banor för roguelikespel.

This master thesis deals with the realization of a simulator based on asynchronous cellular automata simulating delay insensitive circuits. In connection with nanotechnology, cellular automata have several interesting properties, such as self-replication, regular structure and high parallelism that make them very useful as models for some types of nanocomputers. This text describes the relationship between cellular automata and nanotechnology. Emphasis is given to the possibility of using asynchronous timing mode. Asynchronous cellular arrays based on asynchronous cellular automata could prove to be a suitable architecture for future nanocomputer, which was the reason for implementation of this simulator. The simulator's functionality was verified by experiments.

The thesis focuses on a new concept of cellular automata control based on instructions. The instruction can be understood as a rule that checks the states of cells in pre-defined areas in the cellular neighbourhood. If a given condition is satisfied, the state of the central cell is changed according to the definition of the instruction. Because it's possible to perform more instructions in one computational step, their sequence can be understood as a form of a short program. This concept can be extended with simple operations applied to the instruction's prescription during interpretation of the instructions - an example of such operation can be row shift or column shift. An advantage of the instruction-based approach lies in the search space reduction. In comparison with the table-based approach, it isn't necessary to search all the possible configurations of the cellular neighbouhood, but only several areas determined by the instructions. While the groups of the inspected cells in the cellular neighbourhood are designed manually on the basis of the analysis of the solved task, their sequence in the chromosome is optimized by genetic algorithm. The capability of the proposed method of cellular automata control is studied on these benchmark tasks - majority, synchronization, self-organization and the design of combinational circuits.

Ce projet de thèse, dans le cadre d’une collaboration entre le LIMOS et le LPC, s’inscrit dans une démarche de recherche permettant la mise en synergie des domaines de la biologie, de la physique et de l’informatique par la proposition d’une démarche de simulation permettant la réalisation d’expériences in silico. Pour cela, nous nous proposons de développer une plateforme logicielle dédiée à la modélisation multiéchelle des systèmes biologiques qui pourra par la suite être interfacée avec les outils de simulation de physique des particules. Nous proposons également un modèle individu-centré de cellule biologique paramétrable à l’aide de données obtenues d’expériences in vitro. Nous présentons l’élaboration de cette plateforme et une démarche de validation de ses fonctionnalités à travers l’implémentation de modèles d’automates cellulaires de la littérature. Nous présentons ensuite la construction du modèle de cellule biologique en prenant le temps d’expliquer comment est pris en compte le système biologique, comment nous le modélisons puis comment nous paramétrons le modèle. Nous modélisons les processus internes de la cellule, dont les caractéristiques sont liées à l’information génétique qu’elle porte. Ce modèle de cellule permet de reproduire le comportement d’une cellule isolée, et à partir de là, d’un ensemble de cellules via l'automate. Le modèle est ensuite utilisé pour retrouver les courbes de croissance d'une population de bactéries Escherichia coli. Des valeurs de données de fluxomique ont été exploitées et ont permis la reproduction in silico des expériences in vitro dont elles étaient issues. / This PhD thesis project is part of a research program in the fields of biology, physics and computer science aiming to propose a simulation approach for performing experiments in silico. For this, we propose to develop a software platform dedicated to multi-scale modeling of biological systems that can be combined with particle physics simulation tools. We also propose a general individual-based model of biological cell in which data obtained from in vitro experiments can be used. We present the development of this platform and the validation process of its functionalities through the implementation of cellular automata from the literature. We then present the design of the biological cell model by giving the hypothesis we made, how we model and how we parameterize the model. Starting from a simple biological system, bacteria, observed in liquid culture, our model uses a multi-scale middle-out approach. We focus on the cell and we model internal processes, assuming that all their properties come from genetic information carried out by the cell’s genome. This model allows to consider the cell behavior, and then to obtain the behavior of a cell population. Data from fluxomic experiments have been used in this model to parameterize the biochemical processes. The results we obtain allow us to consider the model as validated as simulation results match the experimental data.

La dispersion atmosphérique de substances dangereuses est un évènement susceptible d’entrainer de graves conséquences. Sa modélisation est primordiale pour anticiper des situations accidentelles. L’objectif de ce travail fut de développer un modèle opérationnel, à la fois rapide et précis, prenant en compte la dispersion en champ proche sur un site industriel. L’approche développée s’appuie sur des modèles issus de l’intelligence artificielle : les réseaux de neurones et les automates cellulaires. L’utilisation des réseaux de neurones requiert l’apprentissage d’une base de données de dispersion : des simulations CFD k-ϵ dans ce travail. Différents paramètres sont évalués lors de l’apprentissage : échantillonnage et architecture du réseau. Trois méthodologies sont développées :La première méthode permet d’estimer la dispersion continue en champ libre, par réseaux de neurones seuls.La deuxième méthode utilise le réseau de neurones en tant que règle de transition de l’automate cellulaire pour le suivi de l’évolution d’une bouffée en champ libre.La troisième méthode sépare la problématique : le calcul de l’écoulement est effectué par les réseaux de neurones alors que le calcul de la dispersion est réalisé par la résolution de l’équation d’advection diffusion pour le suivi de l’évolution d’un nuage autour d’un obstacle cylindrique. La simulation de cas tests non-appris avec des simulations CFD permet de valider les méthodes développées. Les temps de calcul mis en œuvre pour réaliser la dispersion sont en accord avec la cinétique d’une situation de crise. L’application à des données réelles doit être développée dans la perspective de rendre les modèles opérationnels. / Atmospheric dispersion of hazardous materials is an event that could lead to serious consequences. Atmospheric dispersion is studied in particular in this work. Modeling of atmospheric dispersion is an important tool to anticipate industrial accidents. The objective of this work was to develop a model that is both fast and accurate, considering the dispersion in the near field on an industrial site. The approach developed is based on models from artificial intelligence: neural networks and cellular automata. Using neural networks requires training a database typical of the phenomenon, CFD k-ϵ simulations in this work. Training the neural network is carried out by identifying the important parameters: database sampling and network architecture. Three methodologies are developed:The first method estimates the continuous dispersion in free field by neural networks.The second method uses the neural network as a transition rule of the cellular automaton to estimate puff evolution in the free field.The third method divides the problem: the flow calculation is performed by the neural network and the calculation of the dispersion is realized by solving the advection diffusion equation to estimate the evolution of a cloud around a cylindrical obstacle. For the three methods, assessment of the generalization capabilities of the neural network has been validated on a test database and on unlearned cases. A comparison between developed method and CFD simulations is done on unlearned cases in order to validate them. Simulations computing time are low according to crisis duration. Application to real data should be developed to make these models operational.

Unidades de conservação possuem o objetivo de preservar a natureza, evitando o desmatamento e promovendo a sustentabilidade do meio ambiente. Contudo, para que estas atendam aos propósitos para os quais foram criadas, sem acarretar prejuízos sociais ou conflitos com as populações locais, estudos aplicados interdisciplinares são essenciais, agregando conhecimento útil à gestão e ao planejamento das unidades de conservação. Sob a ótica da ciência da complexidade, o objetivo principal deste trabalho foi desenvolver modelos que auxiliassem na compreensão das mudanças no uso e cobertura da terra, realizassem simulações de cenários futuros, e permitissem observar os efeitos da implantação de políticas de preservação sobre a paisagem. Construímos modelos dinâmicos baseados em cadeias de Markov e autômatos celulares, aliados a técnicas de geoprocessamento. Os modelos foram aplicados a um estudo de caso, o Parque estadual do Itinguçu, ao longo de uma série temporal de materiais aerofotográficos de quase 50 anos (1962-2010). Os resultados dos modelos mostraram que a implantação da unidade de conservação foi essencial para barrar o desmatamento, mas que as práticas tradicionais de agricultura itinerante não estavam diretamente relacionadas à conversão da área de floresta, indicando que a incompatibilidade entre preservação e presença humana, muitas vezes usada como justificativa para a implantação de unidades de proteção integral, deve ser reavaliada sob outra perspectiva. Os resultados também apontaram para um desempenho satisfatório do modelo de Markov em projetar tendências, apesar de possuir certa aleatoriedade na alocação dos elementos no espaço. O incremento do autômato celular diminuiu tal aleatoriedade, mas não foi tão eficiente em reproduzir as tendências observadas nas matrizes de transição quanto o modelo de Markov. Concluímos que a metodologia aplicada no presente trabalho foi útil para compreendermos as mudanças na paisagem da área de estudo, e que a escolha do modelo (Markov ou Markov com autômato celular) deve ser feita com base em uma análise criteriosa caso a caso, em conformidade com as prioridades do estudo a ser realizado. Espera-se que esta pesquisa possa fomentar a discussão sobre o uso desta metodologia como uma ferramenta para planejamento e análise de políticas de conservação da natureza e gestão do território / Conservation units have the purpose to preserve the nature, avoiding the deforestation and promoting the environment sustainability. However, for these to be effective in that purpose, without causing social injuries or conflicts with the local population, interdisciplinary applied studies are essential and must be made by different areas of science, adding useful knowledge to the management of protected areas. Under the vision of the Complexity Science, the main goal of this research was to develop models that help in understanding the land use and cover changes, perform simulations of future scenarios, and allow observing the effects of the implementation of conservation policies on the landscape. We built Markov and cellular automata models, allied to the geoprocessing techniques. The models were applied to a case study, the Parque Estadual do Itinguçu, over a time series of aero photographic materials of almost 50 years (1962-2010). The results of the models showed that the implementation of the conservation unit was essential to stop the deforestation, but the traditional practices of shifting cultivation were not directly related to the conversion of forest area, indicating that the incompatibility between conservation and human presence, often used as justification for the implementation of some strict protection units, should be reviewed from a different perspective. The results also pointed to a satisfactory performance of the Markov model to project trends, despite having certain randomness in the allocation of elements in space. Add cellular automata to model decreased this randomness, but was not so effective in reproducing the observed trends in transition matrices than the Markov model. We concluded that the methodology applied in this study was useful for understanding the changes in the landscape of the study area, and that the choice of model (Markov or Markov with cellular automata) should be based on a careful analysis in accordance with the priorities of the study to be applied. We hope that this research can encourage the discussion of this methodology as a tool for analysis of conservation policies of nature and land management

Made available in DSpace on 2015-03-04T18:51:11Z (GMT). No. of bitstreams: 1 Dissertacao_LNCC_2009_Sicilia_Judice.pdf: 24029440 bytes, checksum: aa6b5db9b8745db2d37133d63a7521ce (MD5) Previous issue date: 2009-08-10 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Physically-based techniques for the animation of fluids (gas or liquids) have taken the attention of the computer graphics community. The traditional fluid animation methods rely on a top down viewpoint that uses 2D/3D mesh based approaches motivated by the Eulerian methods of Finite Element (FE) and Finite Difference (FD), in conjunction with Navier-Stokes equations of fluids. Alternatively, lattice methods comprised by the Lattice Gas Cellular Automata (LGCA) and Lattice Boltzmann (LBM) can be used. The basic idea behind these methods is that the macroscopic dynamics of a fluid is the result of the collective behavior of many microscopic particles. Such bottom-up approaches need low computational resources for both the memory allocation and the computation itself. In this work, we consider animation of fluids for computer graphics applications, using a LGCA method called FHP, and a LBM method called D2Q9, both bidimensional models. We propose 3D fluid animation techniques based on the FHP and D2Q9 as well as interpolation methods. Then, we present two animating frameworks based on the mentioned lattice methods, one for a real time implementation and the other for an off-line implementation. In the experimental results we emphasize the simplicity and power of the presented models when combined with efficient techniques for rendering and compare their efficiency. / Técnicas baseadas em física têm chamado a atenção da comunidade de computação gráfica, em especial para animação de fluidos (gás ou líquidos). As técnicas tradicionais para animação de fluidos são metodologias top-down baseadas em malhas 2D/3D, tais como Diferenças Finitas e Elementos Finitos, em conjunto com equações de fluidos Navier-Stokes. Entretanto, tais métodos têm um custo computacional alto. Uma alternativa é o uso de técnicas baseadas em Autômatos Celulares do tipo Lattice Gas (LGCA) e o Método de Lattice Boltzmann (LBM). A idéia básica desses métodos consiste em obter a dinâmica macroscópica de um fluido a partir do comportamento coletivo de diversas partículas microscópicas. Em geral, tais metodologias bottom-up são eficientes do ponto de vista computacional. Neste trabalho, são estudados os aspectos teóricos e práticos da animação computacional de fluidos bidimensionais para computação gráfica, usando um método LGCA chamado FHP, e um método LBM chamado D2Q9. É proposto um modelo de fluido 3D baseado nos modelos bidimensionais FHP e D2Q9, bem como em métodos de interpolação. Em seguida, são apresentadas duas aplicações para animação de fluidos através dos métodos mencionados, uma para execução em tempo real e outra para execução off-line. Nos resultados dos experimentos computacionais são enfatizados a simplicidade e o potencial dos modelos propostos quando combinados com técnicas eficientes de rendering.