Cellular automata constitues original computational methods, that found its application in many disciplines. The special class of cellular automata, so called lattice gas automata were succesfull in dealing with many challenges in hydrodynamic simulations, and they bootstrap one of the most perspective CFD methods, the Lattice Boltzmann models. In the theoretical part, we follow the evolution of the lattice gas automata, explore the theory behind them, and from their microdynamics, we derive the macroscopic equations. In the practical part, we implemented two distincet types of LGCA, the pair-interaction automata and FCHC. We applied them on the flow around obstacles of various shapes. The scientifically most relevant part concerns statistical properties of the turbulent flow simmulated by LGCA, but requires further research to conclude it. Powered by TCPDF (www.tcpdf.org)

Cellular automata constitutes a unique approach to the modeling of complex systems. The major phase of their development in continuum mechanics came in the late 80s, but the closer inspection of their macroscopic limit revealed that it does not accurately correspond to hydrodynamic equations. Besides the Lattice-Boltzmann model, various other approaches to improve LGCA have emerged. The main focus of our research is on the Pair-interaction cellular automaton. In this thesis, we propose the non-deterministic variant of this automaton, and we compare it with its predecessor on the simulations of the "exploding cube", Taylor- Green vortex and fully developed turbulence. The results for the non-deterministic automaton seem quiet reasonable, but derivation of the hydrodynamic equations is necessary to conclude in what extent it solves the problem with anisotropic viscosity.

Cell migration, the active translocation of cells is involved in various biological processes, e.g. development of tissues and organs, tumor invasion and wound healing. Cell migration behavior can be divided into two distinct classes: single cell migration and collective cell migration. Single cell migration describes the migration of cells without interaction with other cells in their environment. Collective cell migration is the joint, active movement of multiple cells, e.g. in the form of strands, cohorts or sheets which emerge as the result of individual cell-cell interactions. Collective cell migration can be observed during branching morphogenesis, vascular sprouting and embryogenesis. Experimental studies of single cell migration have been extensive. Collective cell migration is less well investigated due to more difficult experimental conditions than for single cell migration. Especially, experimentally identifying the impact of individual differences in cell phenotypes on individual cell migration behavior inside cell populations is challenging because the tracking of individual cell trajectories is required. In this thesis, a novel mathematical modeling approach, individual-based lattice-gas cellular automata (IB-LGCA), that allows to investigate the migratory behavior of individual cells inside migrating cell populations by enabling the tracking of individual cells is introduced. Additionally, stochastic differential equation (SDE) approximations of individual cell trajectories for IB-LGCA models are constructed. Such SDE approximations allow the analytical description of the trajectories of individual cells during single cell migration. For a complete analytical description of the trajectories of individual cell during collective cell migration the aforementioned SDE approximations alone are not sufficient. Analytical approximations of the time development of selected observables for the cell population have to be added. What observables have to be considered depends on the specific cell migration mechanisms that is to be modeled. Here, partial integro-differential equations (PIDE) that approximate the time evolution of the expected cell density distribution in IB-LGCA are constructed and coupled to SDE approximations of individual cell trajectories. Such coupled PIDE and SDE approximations provide an analytical description of the trajectories of individual cells in IB-LGCA with density-dependent cell-cell interactions. Finally, an IB-LGCA model and corresponding analytical approximations were applied to investigate the impact of changes in cell-cell and cell-ECM forces on the migration behavior of an individual, labeled cell inside a population of epithelial cells. Specifically, individual cell migration during the epithelial-mesenchymal transition (EMT) was considered. EMT is a change from epithelial to mesenchymal cell phenotype which is characterized by cells breaking adhesive bonds with surrounding epithelial cells and initiating individual migration along the extracellular matrix (ECM). During the EMT, a transition from collective to single cell migration occurs. EMT plays an important role during cancer progression, where it is believed to be linked to metastasis development. In the IB-LGCA model epithelial cells are characterized by balanced cell-cell and cell-ECM forces. The IB-LGCA model predicts that the balance between cell-cell and cell-ECM forces can be disturbed to some degree without being accompanied by a change in individual cell migration behavior. Only after the cell force balance has been strongly interrupted mesenchymal migration behavior is possible. The force threshold which separates epithelial and mesenchymal migration behavior in the IB-LGCA has been identified from the corresponding analytical approximation. The IB-LGCA model allows to obtain quantitative predictions about the role of cell forces during EMT which in the context of mathematical modeling of EMT is a novel approach.

Ce travail présente un modèle théorique de morphogenèse animale, sous la forme d’un système complexe émergeant de nombreux comportements, processus internes, expressions et interactions cellulaires. Son implémentation repose sur un automate cellulaire orienté système multi-agents avec un couplage énergico-génétique entre les dynamiques cellulaires et les ressources.Notre objectif est de proposer des outils permettant l’étude numérique du développement de tissus cellulaires à travers une approche hybride (discrète/continue et qualitative/quantitative) pour modéliser les aspects génétiques, énergétiques et comportementaux des cellules. La modélisation de ces aspects s’inspire des principes de la théorie de la viabilité et des données expérimentales sur les premiers stades de division de l’embryon du poisson-zèbre.La théorie de la viabilité appliquée à la morphogenèse pose cependant de nouveaux défis en informatique pour pouvoir implémenter des algorithmes dédiés aux dynamiques morphologiques. Le choix de données biologiques pertinentes à considérer dans le modèle à proposer, la conception d’un modèle basé sur une théorie nouvelle, l’implémentation d’algorithmes adaptés reposant sur des processeurs puissants et le choix d’expérimentations pour éprouver nos propositions sont les enjeux fondamentaux de ces travaux. Les hypothèses que nous proposons sont discutées au moyen d’expérimentations in silico qui ont porté principalement sur l’atteignabilité et la capturabilité de formes de tissus ; sur la viabilité de l’évolution d’un tissu pour un horizon de temps ; sur la mise en évidence de nouvelles propriétés de tissus et la simulation de mécanismes tissulaires essentiels pour leur contrôlabilité face à des perturbations ; sur de nouvelles méthodes de caractérisation de tissus pathologiques, etc. De telles propositions doivent venir en appoint aux expérimentations in vitro et in vivo et permettre à terme de mieux comprendre les mécanismes régissant le développement de tissus. Plus particulièrement, nous avons mis en évidence lors du calcul de noyaux de viabilité les relations de causalité ascendante reliant la maintenance des cellules en fonction des ressources énergétiques disponibles et la viabilité du tissu en croissance. La dynamique de chaque cellule est associée à sa constitution énergétique et génétique. Le modèle est paramétré à travers une interface permettant de prendre en compte le nombre de coeurs à solliciter pour la simulation afin d’exploiter la puissance de calcul offerte par les matériels multi-coeurs. / This work presents a theoretical model of animal morphogenesis, as a complex system from which emerge cellular behaviors, internal processes, interactions and expressions. Its implementation is based on a cellular automaton oriented multi-agent system with an energico-genetic coupling between the cellular dynamics and resources. Our main purpose is to provide tools for the numerical study of tissue development through a hybrid approach (discrete/continuous and qualitative/quantitative) that models genetic, behavioral and energetic aspects of cells. The modeling of these aspects is based on the principles of viability theory and on experimental data on the early stages of the zebrafish embryo division. The viability theory applied to the morphogenesis, however, raises new challenges in computer science to implement algorithms dedicated to morphological dynamics. The choice of relevant biological data to be considered in the model to propose, the design of a model based on a new theory, the implementation of suitable algorithms based on powerful processors and the choice of experiments to test our proposals are fundamental issues of this work. The assumptions we offer are discussed using in silico experiments that focused on the reachability and catchability of tissue forms ; on the viability of the evolution of a tissue for a time horizon ; on the discovery of new tissue properties and simulation of tissue mechanisms that are fondamental for their controllability face to disruptions ; on new pathological tissue characterization methods, etc. Such proposals must come extra to support experiments in vitro and in vivo and eventually allow a better understanding of the mechanisms governing the development of tissues.In particular, we have highlighted through the computing of viability kernels the bottom causal relationship between the maintenance of cells according to available energy resources and the viability of the tissue in growth. The model is set through an interface that takes into account the number of cores to solicit for simulation in order to exploit the computing power offered by multicore hardware.

We study cellular automata as discrete dynamical systems and in particular investigate under which conditions two cellular automata are topologically conjugate. Based on work of McKinsey, Tarski, Pierce and Head we introduce derivative algebras to study the topological structure of sofic shifts in dimension one. This allows us to classify periodic cellular automata on sofic shifts up to topological conjugacy based on the structure of their periodic points. We also get new conjugacy invariants in the general case. Based on a construction by Hanf and Halmos, we construct a pair of non-homeomorphic subshifts whose disjoint sums with themselves are homeomorphic. From this we can construct two cellular automata on homeomorphic state spaces for which all points have minimal period two, which are, however, not topologically conjugate. We apply our methods to classify the 256 elementary cellular automata with radius one over the binary alphabet up to topological conjugacy. By means of linear algebra over the field with two elements and identities between Fibonacci-polynomials we show that every conjugacy between rule 90 and rule 150 cannot have only a finite number of local rules. Finally, we look at the sequences of finite dynamical systems obtained by restricting cellular automata to spatially periodic points. If these sequences are termwise conjugate, we call the cellular automata conjugate on all tori. We then study the invariants under this notion of isomorphism. By means of an appropriately defined entropy, we can show that surjectivity is such an invariant.

Geospatial analysis involves application of statistical methods, algorithms and information retrieval techniques to geospatial data. It incorporates time into spatial databases and facilitates investigation of land cover (LC) dynamics through data, model, and analytics. LC dynamics induced by human and natural processes play a major role in global as well as regional scale patterns, which in turn influence weather and climate. Hence, understanding LC dynamics at the local / regional as well as at global levels is essential to evolve appropriate management strategies to mitigate the impacts of LC changes. This can be captured through the multi-resolution remote sensing (RS) data. However, with the advancements in sensor technologies, suitable algorithms and techniques are required for optimal integration of information from multi-resolution sensors which are cost effective while overcoming the possible data and methodological constraints. In this work, several per-pixel traditional and advanced classification techniques have been evaluated with the multi-resolution data along with the role of ancillary geographical data on the performance of classifiers. Techniques for linear and non-linear un-mixing, endmember variability and determination of spatial distribution of class components within a pixel have been applied and validated on multi-resolution data. Endmember estimation method is proposed and its performance is compared with manual, semi-automatic and fully automatic methods of endmember extraction. A novel technique - Hybrid Bayesian Classifier is developed for per pixel classification where the class prior probabilities are determined by un-mixing a low spatial-high spectral resolution multi-spectral data while posterior probabilities are determined from the training data obtained from ground, that are assigned to every pixel in a high spatial-low spectral resolution multi-spectral data in Bayesian classification. These techniques have been validated with multi-resolution data for various landscapes with varying altitudes. As a case study, spatial metrics and cellular automata based models applied for rapidly urbanising landscape with moderate altitude has been carried out.

L'objet de cette thèse est l'étude de l'auto-organisation dans les automates cellulaires unidimensionnels.Les automates cellulaires sont un système dynamique discret ainsi qu'un modèle de calcul massivement parallèle, ces deux aspects s'influençant mutuellement. L'auto-organisation est un phénomène où un comportement organisé est observé asymptotiquement, indépendamment de la configuration initiale. Typiquement, nous considérons que le point initial est tiré aléatoirement: étant donnée une mesure de probabilité décrivant une distribution de configurations initiales, nous étudions son évolution sous l'action de l'automate, le comportement asymptotique étant décrit par la(les) mesure(s) limite(s).Notre étude présente deux aspects. D'abord, nous caractérisons les mesures qui peuvent être atteintes à la limite par les automates cellulaires; ceci correspond aux différents comportements asymptotiques pouvant apparaître en simulation. Cette approche rejoint divers résultats récents caractérisant des paramètres de systèmes dynamiques par des conditions de calculabilité, utilisant des outils d'analyse calculable. Il s'agit également d'une description de la puissance de calcul des automates cellulaires sur les mesures.Ensuite, nous proposons des outils pour létude de l'auto-organisation dans des classes restreintes. Nous introduisons un cadre d'étude d'automates pouvant être vus comme un ensemble de particules en interaction, afin d'en déduire des propriétés sur leur comportement asymptotique. Une dernière direction de recherche concerne les automates convergeant vers la mesure uniforme sur une large classe de mesures initiales (phénomène de randomisation). / The subject of this thesis is the study of self-organization in one-dimensional cellular automata.Cellular automata are a discrete dynamical system as well as a massively parallel model of computation, both theseaspects influencing each other. Self-organisation is a phenomenon where an organised behaviour is observed asymptotically, regardless of the initial configuration. Typically, we consider that the initial point is sampled at random; that is, we consider a probability measure describing the distribution of theinitial configurations, and we study its evolution under the action of the automaton, the asymptoticbehaviour being described by the limit measure(s).Our work is two-sided. On the one hand, we characterise measures that can bereached as limit measures by cellular automata; this corresponds to the possible kinds of asymptoticbehaviours that can arise in simulations. This approach is similar to several recent results characterising someparameters of dynamical systems by computability conditions, using tools from computable analysis. Thisresult is also a description of the measure-theoretical computational power of cellular automata.On the other hand, we provided tools for the practical study of self-organization in restricted classes of cellularautomata. We introduced a frameworkfor cellular automata that can be seen as a set of interacting particles, in order todeduce properties concerning their asymptotic behaviour. Another ongoing research direction focus on cellular automata that converge to the uniform measurefor a wide class of initial measures (randomization phenomenon).

O processo de auto-organização da estrutura proteica a partir da cadeia de aminoácidos é conhecido como enovelamento. Apesar de conhecermos a estrutura tridimencional de muitas proteínas, para a maioria delas, não possuímos uma compreensão suficiente para descrever em detalhes como a estrutura se organiza a partir da sequência de aminoácidos. É bem conhecido que a formação de núcleos de estruturas locais, conhecida como estrutura secundária, apresenta papel fundamental no enovelamento final da proteína. Desta forma, o desenvolvimento de métodos que permitam não somente predizer a estrutura secundária adotada por um dado resíduo, mas também, a maneira como esse processo deve ocorrer ao longo do tempo é muito relevante em várias áreas da biologia estrutural. Neste trabalho, desenvolvemos dois métodos de predição de estruturas secundárias utilizando modelos com o potencial de fornecer informações mais detalhadas sobre o processo de predição. Um desses modelos foi construído utilizando autômatos celulares, um tipo de modelo dinâmico onde é possível obtermos informações espaciais e temporais. O outro modelo foi desenvolvido utilizando redes neurais residuais profundas. Com este modelo é possível extrair informações espaciais e probabilísticas de suas múltiplas camadas internas de convolução, o que parece refletir, em algum sentido, os estados de formação da estrutura secundária durante o enovelamento. A acurácia da predição obtida por esse modelo foi de ~78% para os resíduos que apresentaram consenso na estrutura atribuída pelos métodos DSSP, STRIDE, KAKSI e PROSS. Tal acurácia, apesar de inferior à obtida pelo PSIPRED, o qual utiliza matrizes PSSM como entrada, é superior à obtida por outros métodos que realizam a predição de estruturas secundárias diretamente a partir da sequência de aminoácidos. / The process of self-organization of the protein structure is known as folding. Although we know the structure of many proteins, for a majority of them, we do not have enough understanding to describe in details how the structure is organized from its amino acid sequence. In this work, we developed two methods for secondary structure prediction using models that have the potential to provide detailed information about the prediction process. One of these models was constructed using cellular automata, a type of dynamic model where it is possible to obtain spatial and temporal information. The other model was developed using deep residual neural networks. With this model it is possible to extract spatial and probabilistic information from its multiple internal layers of convolution. The accuracy of the prediction obtained by this model was ~ 78% for residues that showed consensus in the structure assigned by the DSSP, STRIDE, KAKSI and PROSS methods. Such value is higher than that obtained by other methods which perform the prediction of secondary structures from the amino acid sequence only.

Many diffusion processes in nature and society were found to be anomalous, in the sense of being fundamentally different from conventional Brownian motion. An important example is the migration of biological cells, which exhibits non-trivial temporal decay of velocity autocorrelation functions. This means that the corresponding dynamics is characterized by memory effects that slowly decay in time. Motivated by this we construct non-Markovian lattice-gas cellular automata models for moving agents with memory. For this purpose the reorientation probabilities are derived from velocity autocorrelation functions that are given a priori; in that respect our approach is “data-driven”. Particular examples we consider are velocity correlations that decay exponentially or as power laws, where the latter functions generate anomalous diffusion. The computational efficiency of cellular automata combined with our analytical results paves the way to explore the relevance of memory and anomalous diffusion for the dynamics of interacting cell populations, like confluent cell monolayers and cell clustering.

This thesis deals with a path planning using cellular automata algorithms in a rectangular grid environment. Theoretical part starts with an overview of commonly used approaches for path planning and later on focuses on existing cellular automata solutions and capabilities in detail. Implemented cellular automata algorithms and the commonly used path planning algorithms are together with a map generator described in the practical part. Conclusion of this thesis contains results completed in a special application.