No description available.

On s'intéresse dans ce travail aux automates cellulaires unidimensionnels qui ont été largement étudiés mais où il reste beaucoup à faire. La théorie spectrale des automates cellulaires a notamment été peu abordée à l'exception de quelques résultats indirects. On cherche a mieux comprendre les cadres topologiques et ergodiques en étudiant l'existence de valeurs propres en particulier celles irrationnelles c'est à dire de la forme e^{2Iπα} où α est un irrationnel et I la racine carrée de l'unité. Cette question ne semble pas avoir été abordée jusqu'à présent. Dans le cadre topologique les résultats sur l'équicontinuité de Kůrka et Blanchard et Tisseur permettent de déduire directement que tout automate cellulaire équicontinu possède des valeurs propres topologiques rationnelles. La densité des points périodiques pour le décalage empêche l'existence de valeurs propres topologiques irrationnelles. La densité des points périodiques pour l'automate cellulaire semble être liée à la question des valeurs propres. Dans le cadre topologique, si l'automate cellulaire possède des points d'équicontinuité sans être équicontinu, la densité des points périodiques a comme conséquence le fait que le spectre représente l'ensemble des racines rationnelles de l'unité c'est à dire tous les nombres de la forme e^{2Iπα} avec α∈Q .Dans le cadre mesuré, la question devient plus difficile, on s'intéresse à la dynamique des automates cellulaires surjectifs pour lesquels la mesure uniforme est invariante en vertu du théorème de Hedlund. La plupart des résultats obtenus demeurent valable dans un cadre plus large. Nous commençons par montrer que les automates cellulaires ayant des points d'équicontinuité ne possèdent pas de valeurs propres mesurables irrationnelles. Ce résultat se généralise aux automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman. Nous démontrons finalement que les automates cellulaires possédant des points μ-équicontinu selon la définition de Gilman possèdent des valeurs propres rationnelles / We investigate properties of one-dimensional cellular automata. This category of cellular automata has been widely studied but many questions are still open. Among them the spectral theory of unidimensional cellular automata is an open field with few indirect results. We want a better understanding of both ergodic and topological aspect by investigating the existence of eigenvalues of cellular automata, in particular irrational ones, i.e., those of the form e^{2Iπα} where α is irrationnal and I the complex root of -1. The last question seems not to have been studied yet.In the topological field the results of Kůrka & Blanchard and Tisseur about equicontinuous cellular automata have as direct consequence that any equicontinuous CA has rational eigenvalues. Density of shift periodic points leads to the impossibility for CA to have topological irrational eigenvalues. The density of periodic points of cellular automata seems to be related with the question of eignevalues. If the CA has equicontinuity points without being equicontinuous, the density of periodic points implies the fact that the spectrum contains all rational roots of the unity, i.e., all numbers of the form e^{2Iπα} with α∈Q .In the measurable field the question becomes harder. We assume that the cellular automaton is surjective, which implies that the uniform measure is invariant. Most results are still available in more general conditions. We first prove that cellular automata with equicontinuity points never have irrational measurable eigenvalues. This result is then generalized to cellular automata with μ-equicontinuous points according to Gilman's classification. We also prove that cellular automata with μ-equicontinuous points have rational eigenvalues

Durant cette thèse, nous abordons le problème de la fouille exhaustive de motifs pour un cas particulier de graphes : les grilles. Ces grilles peuvent être utilisées pour modéliser des objets ayant une structure régulière. Ces structures sont naturellement présentes dans de nombreux jeux de plateaux (les dames, les échecs ou le go par exemple) ou encore dans les modélisations d’écosystèmes utilisant des automates cellulaires. On les retrouve également à un plus bas niveau dans les images, qui sont des grilles 2D de pixels ou encore les vidéos, qui sont des grilles spatio-temporelles 2D+t de pixels. Au cours de cette thèse, nous avons proposé un nouvel algorithme de fouille de motifs fréquents dédié aux grilles spatio-temporelles, GriMA. L’usage des grilles régulières permet à notre algorithme de réduire la complexité des tests d’isomorphismes. Ces tests sont souvent utilisés par les algorithmes génériques de fouilles de graphes mais ayant une complexité importante, cela limite leur usage sur des données réelles. Deux applications ont été proposées pour évaluer notre algorithme : la classification d’images pour la fouille de grilles 2D et la prédiction d’automates cellulaires pour la fouille de grilles 2D+t. / During this thesis, we consider the exhaustive graph mining problem for a special kind of graphs : the grids. Theses grids can be used to model objects that present a regular structure. These structures are naturally present in multiple board games (checkers, chess or go for instance) or in ecosystems models using cellular automata. It is also possible to find this structure in a lower level in images, which are 2D grids of pixels, or even in videos, which are 2D+t spatio-temporal grids of pixels. In this thesis, we proposed a new algorithm to find frequent patterns dedicated to spatio-temporal grids, GriMA. Use of regular grids allow our algorithm to reduce the complexity of the isomorphisms test. These tests are often use by generic graph mining algorithm but because of their complexity, they are rarely used on real data. Two applications were proposed to evaluate our algorithm: image classification for 2D grids mining and prediction of cellular automata for 2D+t grids mining.

Nesta tese, é discutida a possibilidade de se representar as variações sistêmicas das transições do uso e ocupação do solo, nos períodos compreendidos entre antes e após a construção dos equipamentos públicos denominados de centros educacionais unificados (CEUs). Foram elaborados modelos dinâmicos de simulação, baseados no paradigma de autômatos celulares, e aplicados na área de influência de 10 unidades deste equipamento, observando-se um raio de influência de 2 km. As unidades foram implantadas, em sua maioria, na periferia do município de São Paulo, Brasil. A pesquisa foi feita entre os anos 2000 e 2010, recorte temporal de maior implantação das estruturas, sendo que o recorte abrange as fases de projeto e apresenta avaliações das unidades implantadas. Para a parametrização das simulações de transição do uso e ocupação do solo urbano, foi utilizado o método bayesiano de pesos de evidência. Os resultados foram conclusivos sobre a relação dos centros educacionais unificados com a modificação de padrões e tendências de variação do uso e ocupação do solo no entorno das unidades estudadas. Houve um aumento de 35% nas probabilidades de transição entre as diferentes classes de uso do solo, indicando uma maior dinâmica de modificações após a construção dos centros educacionais unificados. Ainda no período posterior à implantação desta infraestrutura, foi identificada uma intensificação nas transições entre as classes de uso residencial, áreas urbanas vagas e assentamentos urbanos precários, em processos formais e informais de expansão urbana que estão diretamente relacionados com a condição inicial de uso e ocupação do entorno de cada unidade. Foi possível constatar uma explícita diferenciação espacial do processo de urbanização na área de influência de várias unidades, com a análise contínua da formação das manchas de transição das classes de uso em relação às faixas de distância aos CEUs. Nas unidades construídas em áreas com maior vulnerabilidade e precariedade das ocupações, a expansão urbana tende a ser informal e a ultrapassar os limites imobiliários formais, como no caso do CEU Paz, que concentrou o crescimento dos assentamentos urbanos precários nas áreas íngremes e mais próximas à Serra da Cantareira, em uma taxa anual 27% maior no período pós-implantação. A análise da variação da tendência de uso e ocupação entre os períodos de análise possibilitou comparar todas as unidades estudadas, demonstrando que não existe um caráter regional no padrão de modificação, mas sim uma grande heterogeneidade na organização espacial, em conformidade com os padrões da periferia de São Paulo. Por fim, foi possível observar que nem todas as classes de uso sofreram alteração na tendência entre os períodos, fato que confirma que a influência dos CEUs pode variar conforme o contexto de implantação. / In this thesis, a proposal for modelling land use dynamics is conceived, comprising periods immediately before and after the implementation of the so-called unified educational centers (or centros educacionais unificados - CEUs, in Portuguese). Cellular automaton-based models were applied to assess the influence of CEUs in land use change within circular catchment areas of a two-kilometer radius surrounding them. Most of these social infrastructure equipments were implemented at the periphery of São Paulo city, Brazil. The research was carried out between 2000 and 2010, period of intensive implementation of such social equipments. This time span covers the project phases and presents evaluations of the implemented units. For discretizing continuous variables and running the simulations, we used the Bayesian weights of evidence method. The results were conclusive on the relation between the unified educational centers with changes in land use variation patterns and trends around the studied units. There was a 35% increase in the possibilities of transition among the different land use classes, indicating a greater dynamic of change after the unified educational centers construction. Also, in the period after the implementation of this infrastructure, it was identified an intensification in the transitions among the classes of formal residential use, vacant urban plots and informal urban settlements, in formal and informal processes of urban expansion that are directly related to the initial condition of use and occupation found in the surroundings of each unit. It was possible to observe an explicit spatial differentiation of the urbanization process in the catchment area of several units, by means of the continuous analysis of the land use patches formation in relation to the distance ranges to CEUs. In the units built in areas with greater vulnerability and precarious occupations, urban expansion tends to be informal and invade the formal occupation limits, as in the case of CEU Paz, which concentrated the growth of precarious urban settlements in steep areascloser to the Cantareira Ridge, at a 27% higher yearly rate in the second period, i.e. after the CEU Paz construction. The trend variation analysis between the periods made it possible to compare all the studied units, demonstrating that there is no regional character in the modification pattern, but rather a great heterogeneity in the spatial organization, in accordance with patterns found at the periphery of São Paulo. Finally, it was possible to observe that not all land use classes suffered transition trend changes between the periods, confirming that the influence of the unified educational centers may vary according to the local context.

Os padrões espaciais das alterações da cobertura da terra podem ser analisados a partir de modelagens da sua dinâmica espacial. Essas modelagens são capazes de descrever possíveis fatores responsáveis pelas mudanças territoriais, bem como viabilizar a estimativa de impactos futuros sobre o ambiente simulado. Considerando as pressões do setor de infraestrutura portuária sobre as configurações da forma de uso e planejamento do espaço na região portuária da Baixada Santista, tais como o aporte por áreas de retroporto, o armazenamento e o transporte de cargas, este estudo buscou desenvolver modelos dinâmicos da paisagem e investigar a relação entre as alterações na cobertura da terra e a infraestrutura de transportes na região portuária da Baixada Santista. A partir de produtos de sensoriamento remoto e da metodologia de modelagem dinâmica espacial baseada em autômatos celulares, foram gerados mapas simulados e cenários de prognósticos, com e sem projetos de expansão portuária para o ano de 2024. Os mapas simulados do ano de 1995 e 2005 foram semelhantes aos mapeamentos temáticos de cobertura da terra reais e apresentaram boa avaliação. Importante ressaltar que, apenas o mapa simulado de 2013 não previu as novas instalações portuárias, mesmo com a simulação rodando com a variável de novos empreendimentos operacionais em curto intervalo de tempo. O modelo estacionário em 2024 mostrou a expansão de áreas construídas em substituição, sobretudo, às áreas de campo. Não houve expansão de novas manchas de áreas construídas e isso condiz com a tendência de expansão de áreas urbanas seguindo as áreas já consolidadas e com infraestrutura implantada. Com relação à geração de modelos com os projetos de expansão portuária, tem-se a implantação de diversos empreendimentos ocupando parte da margem esquerda do estuário e áreas de retroporto próximas do arco viário da Baixada Santista. / Spatial patterns of change in land cover can be analyzed with spatial dynamic models. This modeling can indicate the driving factors of territorial changes as well as assess future impacts over the simulated environment. Considering the pressures of the port infrastructure sector over the land use and physical planning in the region of Baixada Santista, such as the demand for backport areas as well as for loads storage and transport, this study aims to develop dynamic models of the landscape and investigate the relationship between land cover change and the transport infrastructure in the port area of Santos. With the aid of remote sensing products and cellular automata based models, simulated maps of past landscapes and maps of future landscape scenarios were generated, both considering and disregarding port expansion projects for the year 2024.The simulated landscape maps of 1995 and 2005 were similar to the real ones, and hence, presented high fitness indices. It is important to mention that only the simulated map of 2013, could not foresee the new port facilities, even when the runs took into account the variables associated with the new operational ventures in a short period of time. The stationary model showed an expansion of built-up areas, mainly replacing former field areas. There was no occurrence of new patches of built-up areas and this trend is consistent with the expansion of urban areas nearby the already consolidated and established areas disposing of infrastructure facilities. Regarding the generation of future simulated scenarios taking into account the port expansion projects, they could well reproduce the implementation of several projects along part of the left bank of the estuary and nearby areas of the road ring of Baixada Santista.

Dans cette thèse, nous étudions la robustesse dans le contexte de la modélisation de systèmes complexes par les automates cellulaires. En effet, si l'on cherche à reproduire un comportement émergent à partir d'un modèle d'automate cellulaire, il nous semble nécessaire de se demander si les comportements observés sont bien le résultat d'interactions entre entités constituantes, ou bien s'ils dépendent d'une définition particulière du modèle. Nous allons ainsi être amenés à considérer la robustesse du modèle, à savoir la résistance de son comportement à de petites variations sur les attributs de sa définition. Dans un premier temps, nous montrons la pertinence de cette approche en considérant plusieurs définitions possibles d'une perturbation de la mise à jour globale et en les appliquant à une classe simple et représentative de modèles d'automates cellulaires, les Automates Cellulaires Elémentaires. Nous observons que, malgré le fait que nos perturbations soient proches et qu'une majorité des modèles considérés ne change pas de comportement, quelques cas particuliers montrent des changements qualitatifs du comportement que nous étudions plus en détail. Dans un second temps, nous appliquons cette approche en nous penchant sur un modèle particulier d'automate cellulaire, qui simule le phénomène de formation d'essaim à partir d'un modèle évolué d'automate cellulaire, le gaz sur réseau. Nous explorons la robustesse du comportement du modèle en considérant la perturbation de deux attributs du modèle, la forme de la grille cellulaire et la mise à jour globale, et en tirons les conclusions sur la relation entre l'observation du comportement et la définition précise du modèle / In this thesis, we study the role of robustness in the context of the modelling of complex systems by cellular automata. Indeed, if we consider a cellular automaton which aims at reproducing an emergent behaviour from a similar structure, we want to determine whether its observed dynamics are the result of the interaction of entities, or whether it depends a precise definition of the model. We thus consider the model's robustness, that is, the resistance of the behaviour to small perturbations on the model features. First, we show the relevance of this approach by considering several definitions of a perturbation of the global updating and by applying them to a simple and representative class of cellular automata, the Elementary Cellular Automata. We observe that, despite the fact that most models show little or no change between the different perturbations, some particular cases show qualitative changes that we study in detail. Second, we apply this approach to a particular model of cellular automata, which simulates a swarming behaviour based on a lattice-gas model. We then explore the model robustness by considering the pertubations of two of the model's attributes, the lattice shape and the global updating, and discuss the relationship between the observation of the behaviour and the precise definitions of the model

Die Anwendung von Methodiken und Technologien aus dem Bereich der Softwaretechnik auf den Bereich der Umweltmodellierung ist eine gemeinhin akzeptierte Vorgehensweise. Im Rahmen der "modellgetriebenen Entwicklung"(MDE, model-driven engineering) werden Technologien entwickelt, die darauf abzielen, Softwaresysteme vorwiegend auf Basis von im Vergleich zu Programmquelltexten relativ abstrakten Modellen zu entwickeln. Ein wesentlicher Bestandteil von MDE sind Techniken zur effizienten Entwicklung von "domänenspezifischen Sprachen"( DSL, domain-specific language), die auf Sprachmetamodellen beruhen. Die vorliegende Arbeit zeigt, wie modellgetriebene Entwicklung, und insbesondere die metamodellbasierte Beschreibung von DSLs, darüber hinaus Aspekte der Pragmatik unterstützen kann, deren Relevanz im erkenntnistheoretischen und kognitiven Hintergrund wissenschaftlichen Forschens begründet wird. Hierzu wird vor dem Hintergrund der Erkenntnisse des "modellbasierten Forschens"(model-based science und model-based reasoning) gezeigt, wie insbesondere durch Metamodelle beschriebene DSLs Möglichkeiten bieten, entsprechende pragmatische Aspekte besonders zu berücksichtigen, indem sie als Werkzeug zur Erkenntnisgewinnung aufgefasst werden. Dies ist v.a. im Kontext großer Unsicherheiten, wie sie für weite Teile der Umweltmodellierung charakterisierend sind, von grundsätzlicher Bedeutung. Die Formulierung eines sprachzentrierten Ansatzes (LCA, language-centered approach) für die Werkzeugunterstützung konkretisiert die genannten Aspekte und bildet die Basis für eine beispielhafte Implementierung eines Werkzeuges mit einer DSL für die Beschreibung von Zellulären Automaten (ZA) für die Umweltmodellierung. Anwendungsfälle belegen die Verwendbarkeit von ECAL und der entsprechenden metamodellbasierten Werkzeugimplementierung. / The application of methods and technologies of software engineering to environmental modeling and simulation (EMS) is common, since both areas share basic issues of software development and digital simulation. Recent developments within the context of "Model-driven Engineering" (MDE) aim at supporting the development of software systems at the base of relatively abstract models as opposed to programming language code. A basic ingredient of MDE is the development of methods that allow the efficient development of "domain-specific languages" (DSL), in particular at the base of language metamodels. This thesis shows how MDE and language metamodeling in particular, may support pragmatic aspects that reflect epistemic and cognitive aspects of scientific investigations. For this, DSLs and language metamodeling in particular are set into the context of "model-based science" and "model-based reasoning". It is shown that the specific properties of metamodel-based DSLs may be used to support those properties, in particular transparency, which are of particular relevance against the background of uncertainty, that is a characterizing property of EMS. The findings are the base for the formulation of an corresponding specific metamodel- based approach for the provision of modeling tools for EMS (Language-centered Approach, LCA), which has been implemented (modeling tool ECA-EMS), including a new DSL for CA modeling for EMS (ECAL). At the base of this implementation, the applicability of this approach is shown.

O autômato celular Game of LIFE (GL) exibe comportamento coletivo não-trivial (Classe IV de Wolfram) a partir de regras locais simples. Na década de 1990, conjecturou-se que o autômato seria um exemplo de sistema não-conservativo com criticalidade auto-organizada. Nesse trabalho refutamos essa conjectura verificando que o regime transiente para estados absorventes não escala de forma correta para redes grandes. Usando uma aproximação de campo médio com considerações sobre interfaces para a rede quadrada, definimos um parâmetro de controle sigma0 relacionado com a razão de ramificação da interface da fase absorvente. A partir da análise de um grande número de autômatos celulares (6144), encontramos uma transição de fase descontínua no espaço de regras dos autômatos celulares totalistas. Também encontramos que o GL é um autômato celular quasi-crítico, com sigma0=1.006, ou seja, o GL equivale a um processo de nucleação quasi-crítico. Mostramos que essa quasi-criticalidade é resultado da coexistência e competição entre a fase viva e a fase morta: embora o LIFE esteja destinado à extinção (ao estado absorvente morto), o decaimento é adiado devido a um forte ralentamento crítico. / The cellular automaton Game of LIFE exhibits non-trivial collective behavior (Wolfram Class IV) from local simple rules. In the 1990s, it was conjectured that the automaton would be an example of self-organized criticality in non-conservative systems. In this work we refute this conjecture by verifying that the transient regime to absorbing states does not scale for large lattice sizes. By using a mean-field approximation with considerations about interfaces in square lattices, we define a control parameter sigma0 related to the interfacial absorbing phase branching rate. From the analysis of a large number of cellular automata (6144), we find a discontinuous phase transition in the cellular automata rule space. We also find that LIFE is a quasi-critical cellular automaton, with sigma0=1.006, that is, LIFE is a quasi-critical nucleation process. It is shown that this quasi-criticality is a result of coexistence and competition between the living and dead phases: although LIFE is destined to extinction (to the dead absorbing state), this decay is delayed due to a strong critical slowing down.

O objetivo deste trabalho é identificar regiões urbanas homogêneas por meio da aplicação de duas vertentes da análise espacial: a estatística espacial e uma estratégia de modelagem espacial baseada na comparação de informações oriundas de diferentes entidades espaciais, em níveis diversos de informação. Um método baseado em fluxos de viagens seria a melhor alternativa para o problema em questão, mas não há dados disponíveis para sua aplicação no Brasil. Em virtude disso, o método aqui apresentado identifica regiões que podem ser consideradas como uniformes em relação a uma variável a partir de técnicas de análise exploratória de dados espaciais, como por exemplo, o gráfico e o mapa de Moran. Em um estudo de caso para o estado de São Paulo, analisando-se as distribuições espaciais dos valores da densidade populacional por meio de sua representação em mapas temáticos classificados segundo os quadrantes do gráfico de Moran (ou box map), esse indicador permite caracterizar razoavelmente bem as regiões urbanas homogêneas existentes (inclusive as oficiais). Entretanto, ao tentar representar o seu comportamento em uma análise temporal por meio de modelos, o indicador populacional não foi capaz de descrever esse comportamento e, conseqüentemente, não serviu para elaborar estratégias de previsão para o futuro. Por outro lado, ao combinar essas informações com um indicador que representa a oferta de transportes, os resultados obtidos permitiram observar o alto desempenho dos modelos, dada a forte influência recíproca entre uso e ocupação do solo e oferta de transportes. Ao permitir a identificação de padrões e a projeção de tendências, este tipo de análise pode ser útil para o planejamento urbano e regional, tanto no contexto estudado como em uma visão mais abrangente. / The objective of this work is to identify homogeneous urban regions through the application of two branches of spatial analysis: spatial statistics and a modeling strategy based on the comparison of information from different spatial entities and at distinct levels. A commuting-based approach would be the best alternative in that case, but there is no data available for its application in Brazil. Thus, the method presented here identifies uniform regions regarding a particular variable through exploratory spatial data analysis techniques, such as the Moran scatter plot and box maps. In a case study carried out in the state of São Paulo, in which the spatial distribution of the values of population density was analyzed through the representation in box maps, a reasonable identification of the existing homogeneous urban regions (including the official ones) was performed. However, the models based only on the population density distribution did not perform well for analyses through time and therefore they were not adequate for forecasting strategies. In contrast, when combining population density information with an indicator of transportation supply the performance of the models was noticeably improved, what was likely caused by the strong reciprocal influence between land use and transportation supply. As a conclusion, the method developed in this work shall be useful for urban and regional planning at different scales, given its potential for patterns recognition and trends forecasting.

Este trabalho aborda a utilização do método de Lattice Boltzmann como ferramenta de simulação para a área de dinâmica de fluidos. Além disso, apresenta o programa LBSim desenvolvido durante o período de pesquisa, construído para ser flexível e extensível (através do emprego de técnicas de orientação a objetos) e com uma interface gráfica mais amigável do que outros projetos semelhantes. Como resultado deste trabalho, o software LBSim implementa uma série de módulos diferentes que utilizam o método de Lattice Boltzmann como base, permitindo a simulação de casos monofásico, multifásico, multicomponente, com suporte à gravidade, meios porosos, difusão, transferência de calor e paredes deslizantes. / This work approaches the use of the Lattice Boltzmann method as a simulation tool for the fluid dynamics area. Beyond that, it presents the LBSim software, developed during the period of the research and built to be flexible and extensible (through the application of techniques of the object oriented paradigm) and with a graphical interface more friendly than other similar projects. As a result of this work, the LBSim software implements a series of different modules that uses the Lattice Boltzmann method as a base, allowing the simulations of the following cases: monophase, multiphase, multicomponent, with support of gravity, porous media, diffusion, heat transfer and moving walls.