Spelling suggestions: "subject:"[een] CELLULAR AUTOMATA"" "subject:"[enn] CELLULAR AUTOMATA""
241 |
Explorando a noção de reversibilidade parcial de autômatos celulares elementares em reticulados cíclicosFreitas, Rodrigo da Silva 12 August 2010 (has links)
Made available in DSpace on 2016-03-15T19:37:32Z (GMT). No. of bitstreams: 1
Rodrigo da Silva Freitas.pdf: 462625 bytes, checksum: 0a15a8db6ef05a12c27f5668822ef98c (MD5)
Previous issue date: 2010-08-12 / Fundo Mackenzie de Pesquisa / Cellular automata have been studied as computer models in many different forms. Several of its properties have been widely explored, among which reversibility stands out. This property is able to provide a cellular automaton the possibility of having their temporal evolution regenerated backward in time, regardless of its initial configuration, through an inverse cellular automaton. Reversibility is such a well characterized concept that many fundamental results associated with it have been obtained, such as the development of algorithms to enumerate all reversible one-dimensional cellular automata
and the undecidability of this property for cellular automata in dimensions larger than 1. The driving force for the present research is to introduce a new concept involving the reversibility ability of a cellular automaton, the concept of partial reversibility, which is analysed herein according to the pre-images of all initial configurations of a rule, up to a certain length. This new concept may be useful for evolutionary searches for reversible cellular automata, to allow the use of cellular automata in tasks related somehow to the reversibility degree of a rule, or in applications where reversible rules are demonstrably employed, such as in cryptography. To that end, some parameters presumably related to reversibility are studied and compared, and empirical measures (lexicographical and numerical) are addressed. The results involving these empirical measures, showed that is possible to refer to a more partially reversible rule than another, besides revealing properties, apparently unknown so far, involving the pre-images of elementary rules. / Os autômatos celulares têm sido estudados como modelos computacionais de diversas formas. Diversas de suas propriedades têm sido amplamente exploradas, entre elas destacando-se a reversibilidade. Esta propriedade é capaz de fornecer a um autômato celular a possibilidade de ter sua evolução temporal refeita para trás no tempo, independentemente de sua configuração inicial, através de um autômato celular inverso. A reversibilidade é um conceito tão bem caracterizado que muitos resultados fundamentais associados a ela têm sido obtidos, tais como o desenvolvimento de algoritmos para enumerar todos os autômatos celulares unidimensionais reversíveis e a indecidibilidade desta propriedade para autômatos celulares com dimensão maior que 1. A ideia principal deste trabalho é introduzir um novo conceito envolvendo a capacidade de reversibilidade de um autômato celular, o conceito de reversibilidade parcial, que é analisado com base nas pré- imagens de todas configurações iniciais de uma regra, até um determinado tamanho de reticulado. Este novo conceito pode ser útil em buscas evolutivas de autômatos celulares reversíveis, a fim de permitir a utilização de autômatos celulares em tarefas associadas de alguma forma ao grau de reversibilidade de uma regra, ou ainda, em aplicações onde
as regras reversíveis são comprovadamente empregadas, tal como em criptografia. Para tanto, alguns parâmetros supostamente relacionados à reversibilidade são estudados e
comparados, e medidas empíricas (lexicográficas e numéricas) são abordadas. Os resultados obtidos envolvendo essas medidas empíricas mostraram que é possível referir-se a uma regra mais parcialmente reversível do que outra, além de revelar propriedades, até então desconhecidas, envolvendo as pré-imagens das regras elementares.
|
242 |
Representação ternária em algoritmos evolutivos para a obtenção de autômatos celulares bináriosInterciso, Mateus 23 August 2011 (has links)
Made available in DSpace on 2016-03-15T19:37:38Z (GMT). No. of bitstreams: 1
Mateus Interciso.pdf: 1720671 bytes, checksum: aa67cff2cc9f7abe5fb3b48bead6b38d (MD5)
Previous issue date: 2011-08-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos (AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.
|
243 |
Representação ternária em algoritmos evolutivos para a obtenção de autômatos celulares bináriosInterciso, Mateus 23 September 2011 (has links)
Made available in DSpace on 2016-03-15T19:37:41Z (GMT). No. of bitstreams: 1
Mateus Interciso.pdf: 1732926 bytes, checksum: f29787f421b0b5f1d6dedd2c1eb4e0fc (MD5)
Previous issue date: 2011-09-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos(AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.
|
244 |
Ordenação com autômatos celulares unidimensionaisCarvalho, Carlos Eduardo Profeta de 04 March 2015 (has links)
Made available in DSpace on 2016-03-15T19:37:56Z (GMT). No. of bitstreams: 1
CARLOS EDUARDO PROFETA DE CARVALHO.pdf: 1714302 bytes, checksum: 9f543bb164424f04ade23ddc5bedeb07 (MD5)
Previous issue date: 2015-03-04 / Cellular automata are discrete complex systems and also fully distributed computational
systems, with arbitrarily simple local processing. One of computations that can be made
with cellular automata is sorting of numerical sequences. Sorting is a quite relevant topic
and widely used in computing, as one of its fundamental processes. This research aimed
at the development of sorting algorithms based on one-dimensional cellular automata.
Two new versions with range 1 and 3 have been proposed, inspired by the characteristics
of existing studies in the literature. In the analysis carried out, the proposed cellular
automata have advantages over the approaches that originated them. / Autômatos celulares são sistemas complexos discretos e também sistemas computacionais
totalmente distribuídos, com processamento local arbitrariamente simples. Uma das
computações que se pode realizar com autômatos celulares é a ordenação de sequências
numéricas. A ordenação é um tema bastante relevante e utilizado amplamente na computação, como um de seus processos fundamentais. A presente pesquisa visou o desenvolvimento
de algoritmos de ordenação baseados em autômatos celulares unidimensionais.
Foram propostas duas novas versões, de raios 1 e 3, inspirados por características de trabalhos
existentes na literatura. Em análise realizada, os autômatos celulares propostos
apresentam vantagens com relação às abordagens que lhes deram origem.
|
245 |
A dinâmica da percepção de qualidade em serviços estéticos sob uma perspectiva diádicaZimbres, Rubens de Almeida 02 June 2009 (has links)
Made available in DSpace on 2016-03-15T19:31:19Z (GMT). No. of bitstreams: 1
Rubens de Almeida Zimbres.pdf: 953627 bytes, checksum: 788a11f034cfb7d55e50c105894ec1f3 (MD5)
Previous issue date: 2009-06-02 / Wolfram Research, Inc. / The main goal of this thesis was to verify the influence of clients and providers role clarity in quality perception of esthetic services. Starting from a dyadic perspective, we studied how interactions during service cycle clarify roles of its participants, generating cognitive and emotional involvement, thus influencing quality perception and behavioral intentions. We did a quali-quantitative research, and had developed a scale for measuring the constructs. We evaluated psychometric properties of the scale and results suggest that relationships proposed and the scale for measuring constructs are valid. Results also show that there are perception discrepancies related to quality criteria among clients and providers. The use of control variables allowed to understand better clients and providers idiosyncrasies. After data analysis, we developed an artificial society based in cellular automata concept. Simulation results allowed to understand information diffusion in the social network and may be useful for service cycle management and development of Marketing strategies based in market segmentation. / A presente tese teve como objetivo verificar a influência da clareza do papel de clientes e provedores de serviços estéticos na percepção de qualidade dos mesmos. Partindo de uma perspectiva diádica, estudou-se como as interações durante o ciclo de serviço esclarecem os papéis dos participantes do mesmo, gerando envolvimento cognitivo e emocional, e influenciando assim a percepção de qualidade de serviço e as intenções comportamentais. Foi realizada uma pesquisa quali-quantitativa longitudinal, onde foram desenvolvidas escalas para mensuração dos construtos estudados. Foram avaliadas as propriedades psicométricas da
escala desenvolvida e os resultados sugerem que as relações propostas e a escala desenvolvida apresentam validade. Os resultados também mostram que existem discrepâncias de percepção com relação aos critérios de qualidade entre clientes e provedores e o uso de variáveis de controle permitiu aprofundar o conhecimento das idiossincrasias de clientes e provedores. Após a análise dos dados, procedeu-se à construção de uma sociedade artificial baseada no conceito de autômatos celulares. Os resultados da simulação permitiram entender melhor a dinâmica de evolução de opiniões na rede social estudada, podendo ser úteis para gestão do ciclo de serviço e desenvolvimento de estratégias de Marketing baseadas em segmentação de mercado.
|
246 |
Desenvolvimento de um simulador computacional de dinâmica de fluidos utilizando o método de Lattice Boltzmann. / Development of a computational simulator fo fluid dynamica using the Lattice Boltzmann method.Fabio Sussumu Komori 23 May 2012 (has links)
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.
|
247 |
Modèles physiques et perception, contributions à l'analyse du milieu sonore urbain / Physical models and perception, contributions to sound analysis in urban environmentKeita, Eloi Bandia 02 July 2015 (has links)
L’intégration du monde physique et des systèmes d’information est l’un des faits majeurs de la récente décennie. Cette intégration est rendue possible par les systèmes de communication, en particulier les systèmes sans fil, et par les recherches à l’interface physique dans le domaine des capteurs.L’usage de cette interface peut se concevoir de manière locale, par exemple le contrôle d’un objet, ou une aide dirigée vers une personne. Cette interface peut aussi exister au niveau distribué, en permettant la synthèse d’informations éparses et des prises de décisions concernant par exemple des économies de ressources : éteindre l’éclairage d’une rue, guider vers une place de parking libre.Les réseaux de capteurs sans fil contribuent à cette seconde catégorie et cette thèse s’est consacrée à la simulation de la propagation d’informations sonores en milieu urbain, avec une caractérisation distribuée.Le support décisif pour cette simulation est la représentation cellulaire de la ville et de ses zones : rues, jardins, rocades, bâtiments, rivières. Cette représentation cellulaire est produite par l’analyse d’imagesgéo-localisées et peut être complétée par la consultation de bases de données, pour l’élévation, par exemple. La représentation cellulaire est ensuite transformée en systèmes de processus interconnectés, à même de reproduire quantité de comportements collectifs, physiques ou numériques. / Physical world and information systems unification is a major achievement during this last decade. Communication systems, especially wireless technology, and research in physical sensors field have taken a major part in this integration.The interface between the physical word and a computer can be used in two ways. First, from a local perspective, where such a system can control for instance a single object or provide a personal assistance.Moreover, in a distributed system, this interface collects and analyses sparse data to make decisions, for instance about resource savings: to turn off streetlights, to guide to a parking spot.Wireless sensor networks are part of this second category. Thus, this thesis is focused on sound propagation simulation in urban environment, in a distributed manner.The key point of this work is a cellular representation of the city in order to model streets, gardens, ring roads, buildings, and rivers. Georeferenced image analysis, complemented by database consultation, for example to retrieve elevation data, generates this cellular model. Then, this model is converted into a system made of interconnected processes, that can reproduce many collective behaviors, whether physical or digital.We have developed a cellular automata that models sound propagation, including reflection and refraction, working on a graphics accelerator. Finally, we have produced a coupling method between observation systems by sensor networks and physical systems.
|
248 |
Portfolio of original compositions : dynamic audio composition via space and motion in virtual and augmented environmentsPecino Rodriguez, Jose Ignacio January 2015 (has links)
Electroacoustic music is often regarded as not being sufficiently accessible to the general public because of its sound-based abstract quality and the complexity of its language. Live electronic music introduces the figure of the performer as a gestural bodily agent that re-enables our multimodal perception of sound and seems to alleviate the accessibility dilemma. However, live electronic music generally lacks the level of detail found in studio-based fixed media works, and it can hardly be transferred outside the concert hall situation (e.g. as a video recording) without losing most of its fresh, dynamic and unpredictable nature. Recent developments in 3D simulation environments and game audio technologies suggest that alternative approaches to music composition and distribution are possible, presenting an opportunity to address some of these issues. In particular, this Portfolio of Compositions proposes the use of real and virtual space as a new medium for the creation and organisation of sound events via computer-simulated audio-sources. In such a context, the role of the performer is sometimes assumed by the listener itself, through the operation of an interactive-adaptive system, or it is otherwise replaced by a set of automated but flexible procedures. Although all of these works are sonic centric in nature, they often present a visual component that reinforces the multimodal perception of meaningful musical structures, either as real space locations for sonic navigation (locative audio), or live visualisations of physically-informed gestural agents in 3D virtual environments. Consequently, this thesis draws on general game-audio concepts and terminology, such as procedural sound, non-linearity, and generative music; but it also embraces game development tools (game engines) as a new methodological and technological approach to electroacoustic music composition. In such context, space and the real-time generation, control, and manipulation of assets combine to play an important role in broadening the routes of musical expression and the accessibility of the musical language. The portfolio consists of six original compositions. Three of these works–Swirls, Alice - Elegy to the Memory of an Unfortunate Lady, and Alcazabilla–are interactive in nature and they required the creation of custom software solutions (e.g. SonicMaps) in order to deal with open-form musical structures. The last three pieces–Singularity, Apollonian Gasket, and Boids–are based on fractal or emergent behaviour models and algorithms, and they propose a non-interactive linear organisation of sound materials via real-time manipulation of non-conventional 3D virtual instruments. These original instrumental models exhibit strong spatial and kinematic qualities with an abstract and minimal visual representation, resulting in an extremely efficient way to build spatialisation patterns, texture, and musical gesture, while preserving the sonic-centric essence of the pieces.
|
249 |
Spatially explicit modeling on networks: understanding patterns & describing processes / Modelagem espacialmente explícita em redes: compreendendo padrões e descrevendo processosMiranda, Gisele Helena Barboni 28 May 2019 (has links)
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.
|
250 |
Recent advances in regional controllability of cellular automata / Nouvelles avancées en contrôlabilité régionale des automates cellulairesDridi, Sara 29 November 2019 (has links)
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.
|
Page generated in 0.0367 seconds