Spelling suggestions: "subject:"[een] CELLULAR AUTOMATA"" "subject:"[enn] CELLULAR AUTOMATA""
181 |
Computational Explorations of Creativity and Innovation in DesignSosa Medina, Ricardo January 2005 (has links)
This thesis addresses creativity in design as a property of systems rather than an attribute of isolated individuals. It focuses on the dynamics between generative and evaluative or ascriptive processes. This is in distinction to conventional approaches to the study of creativity which tend to concentrate on the isolated characteristics of person, process and product. Whilst previous research has advanced insights on potentially creative behaviour and on the general dynamics of innovation in groups, little is known about their interaction. A systems view of creativity in design is adopted in our work to broaden the focus of inquiry to incorporate the link between individual and collective change. The work presented in this thesis investigates the relation between creativity and innovation in computational models of design as a social construct. The aim is to define and implement in computer simulations the different actors and components of a system and the rules that may determine their behaviour and interaction. This allows the systematic study of their likely characteristics and effects when the system is run over simulated time. By manipulating the experimental variables of the system at initial time the experimenter is able to extract patterns from the observed results over time and build an understanding of the different types of determinants of creative design. The experiments and findings presented in this thesis relate to artificial societies composed by software agents and the social structures that emerge from their interaction. Inasmuch as these systems aim to capture some aspects of design activity, understanding them is likely to contribute to the understanding of the target system. The first part of this thesis formulates a series of initial computational explorations on cellular automata of social influence and change agency. This simple modelling framework illustrates a number of factors that facilitate change. The potential for a designer to trigger cycles of collective change is demonstrated to depend on the combination of individual and external or situational characteristics. A more comprehensive simulation framework is then introduced to explore the link between designers and their societies based on a systems model of creativity that includes social and epistemological components. In this framework a number of independent variables are set for experimentation including characteristics of individuals, fields, and domains. The effects of these individual and situational parameters are observed in experimental settings. Aspects of relevance in the definition of creativity included in these studies comprise the role of opinion leaders as gatekeepers of the domain, the effects of social organisation, the consequences of public and private access to domain knowledge by designers, and the relation between imitative behaviour and innovation. A number of factors in a social system are identified that contribute to the emergence of phenomena that are normally associated to creativity and innovation in design. At the individual level the role of differences of abilities, persistence, opportunities, imitative behaviour, peer influence, and design strategies are discussed. At the field level determinants under inspection include group structure, social mobility and organisation, emergence of opinion leaders, established rules and norms, and distribution of adoption and quality assessments. Lastly, domain aspects that influence the interaction between designers and their social groups include the generation and access to knowledge, activities of gatekeeping, domain size and distribution, and artefact structure and representation. These insights are discussed in view of current findings and relevant modelling approaches in the literature. Whilst a number of assumptions and results are validated, others contribute to ongoing debates and suggest specific mechanisms and parameters for future experimentation. The thesis concludes by characterising this approach to the study of creativity in design as an alternative �in silico� method of inquiry that enables simulation with phenomena not amenable to direct manipulation. Lines of development for future work are advanced which promise to contribute to the experimental study of the social dimensions of design.
|
182 |
Emergence and evolution of computational habitats /Tulai, Alexander F. January 1900 (has links)
Thesis (Ph. D.)--Carleton University, 2004. / Includes bibliographical references (p. 189-201) and index. Also available in electronic format on the Internet.
|
183 |
Automates cellulaires pour la modélisation et le contrôle en épidémiologie / Cellular automata for modeling and control in epidemiologyCisse, Baki 08 June 2015 (has links)
Ce travail de thèse traite de la modélisation et du contrôle des maladies infectieuses à l’aide des automates cellulaires. Nous nous sommes d’abord focalisés sur l’étude d’un modèle de type SEIR. Nous avons pu monter d’une part qu’un voisinage fixe pouvait entrainer une sous-évaluation de l’incidence et de la prévalence et d’autre part que sa structure a un impact direct sur la structure de la distribution de la maladie. Nous nous sommes intéressés également la propagation des maladies vectorielles à travers un modèle de type SIRS-SI multi-hôtes dans un environnement hétérogène.Les hôtes y étaient caractérisés par leur niveau de compétence et l’environnement par la variation du taux de reproduction et de mortalité. Son application à la maladie de Chagas, nous a permis de montrer que l’hétérogénéité de l’habitat et la diversité des hôtes contribuaient à faire baisser l’infection. Cependant l’un des principaux résultats de notre travail à été la formulation du nombre de reproduction spatiale grâce à deux matrices qui représentent les coefficients d’interactions entre les différentes cellules du réseau. / This PhD thesis considers the general problem of epidemiological modelling and control using cellular automata approach.We first focused on the study of the SEIR model. On the one hand, we have shown that the traditionnal neighborhood contribute to underestimate the incidence and prevalence of infection disease. On the other hand, it appeared that the spatial distribution of the cells in the lattice have a real impact on the disease spreading. The second study concerns the transmission of the vector-borne disease in heterogeneous landscape with host community. We considered a SIRS-SI with various level of competence at witch the environnment heterogeneity has been characterized by the variation of the birth flow and the death rate. We simulated the Chagas disease spreading and shown that the heterogeneity of habitat and host diversity contribute to decrease the infection. One of the most important results of our work, was the proposition of the spatial reproduction number expression based on two matrices that represent the interaction factors between the cells in the lattice.
|
184 |
Approches informatique et mathématique des dynamiques causales de graphes / Algorithmical and mathematical approaches of causal graph dynamicsMartiel, Simon 06 July 2015 (has links)
Le modèle des automates cellulaires constitue un des modèles le mieux établi de physique discrète sur espace euclidien. Ils implantent trois symétries fondamentales de la physique: la causalité, l'homogénéité et la densité finie de l'information. Bien que l'origine des automates cellulaires provienne de la physique, leur utilisation est très répandue comme modèles de calcul distribué dans l'espace (machines auto-réplicantes, problèmes de synchronisation,...), ou bien comme modèles de systèmes multi-agents (congestion du trafic routier, études démographiques,...). Bien qu'ils soient parmi les modèles de calcul distribué les plus étudiés, la rigidité de leur structure interdit toute extension triviale vers un modèle de topologie variant dans le temps, qui se trouve être un prérequis fondamental à la modélisation de certains phénomènes biologiques, sociaux ou physiques, comme par exemple la discrétisation de la relativité générale. Les dynamiques causales de graphes généralisent les automates cellulaires aux graphes arbitraires de degré borné et pouvant varier dans le temps. Dans cette thèse, nous nous attacherons à généraliser certains des résultats fondamentaux de la théorie des automates cellulaires. En munissant nos graphes d'une métrique compacte, nous présenterons deux approches différentes du modèle. Une première approche axiomatique basée sur les notions de continuité et d'invariance par translation, et une deuxième approche constructive, où une règle locale est appliquée en parallèle et de manière synchrone sur l'ensemble des sommets du graphe. / Cellular Automata constitute one of the most established model of discrete physical transformations that accounts for euclidean space. They implement three fundamental symmetries of physics: causality, homogeneity and finite density of information. Even though their origins lies in physics, they are widely used to model spatially distributed computation (self-replicating machines, synchronization problems,...), as well as a great variety of multi-agents phenomena (traffic jams, demographics,...). While being one of the most studied model of distributed computation, their rigidity forbids any trivial extension toward time-varying topology, which is a fundamental requirement when it comes to modelling phenomena in biology, sociology or physics: for instance when looking for a discrete formulation of general relativity. Causal graph dynamics generalize cellular automata to arbitrary, bounded degree, time-varying graphs. In this work, we generalize the fundamental structure results of cellular automata for this type of transformations. We endow our graphs with a compact metric space structure, and follow two approaches. An axiomatic approach based on the notions of continuity and shift-invariance, and a constructive approach, where a local rule is applied synchronously on every vertex of the graph. Compactness allows us to show the equivalence of these two definitions, extending the famous result of Curtis-Hedlund-Lyndon’s theorem. Another physics-inspired symmetry is then added to the model, namely reversibility.
|
185 |
Cenários de mudanças climáticas usando modelagem dinâmica na Bacia do Alto Taquari. / Climate Change Scenarios using Dynamic Modelling in Upper Taquari Basin.Leila Sheila Silva Lisboa 17 September 2008 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A região Centro-Oeste do Brasil tornou-se nos últimos 40 anos grande produtora de grãos e carne bovina. As condições edafoclimáticas, o sistema de manejo do solo e o descumprimento de leis ambientais trouxeram conseqüências drásticas à região como o agravamento do processo hídrico erosivo, principalmente na Bacia do Alto Taquari (BAT). Cerca de 90% da BAT localiza-se na porção norte do estado de Mato Grosso do Sul (MS), porém os efeitos do transporte de sedimentos e volume de água são refletidos a jusante dos rios, na Bacia do Pantanal. Utilizando-se pressupostos do Painel Intergovernamental de Mudanças Climáticas (IPCC) foram estabelecidos cenários de mudanças climáticas na Bacia do Alto Taquari, visando identificar áreas com maior vulnerabilidade ao processo erosivo em função de pressões de uso da terra. Usando a modelagem dinâmica no TerraME (Environment Modeling) foram gerados cenários topopluviais até 2100, considerando-se para a temperatura do ar média anual um aumento de 1C, em cenário otimista e, em pessimista, elevações térmicas de 3C. Para a precipitação pluvial média anual um cenário foi com aumento de 15% e outro com reduções de 15%. Os dados foram espacializados no ArcGis 9.2 e exportados para o TerraView 3.2, criando-se espaços celulares e integrando-se com as informações do modelo digital do terreno do Shuttle Radar Topography Mission (SRTM) para geração dos mapas topoclimáticos e simulações de cenários no TerraMe. Os resultados apontam que 85% da área da BAT nas condições atuais as temperaturas médias variam entre 23,6 a 25,7C. As simulações térmicas no cenário otimista indicam que em 40 anos as temperaturas tendem a superar o maior limite térmico médio nas áreas ao longo do rio Taquari, no sentido Oeste-Leste. Esses valores evidenciam elevações nas taxas evapotranspiratórias de matas ciliares, indicando reduções na vazão do Taquari. Em cenário pessimista essas temperaturas antecipam sua ocorrência, em um prazo de 20 anos. Os cenários com acréscimo de 15% na precipitação pluvial mostram aumentos no volume de água precipitada na parte norte da Bacia, região mais vulnerável aos problemas de erosão hídrica. Cenários do regime térmico-hídrico apontam áreas mais sensíveis às mudanças climáticas na parte oeste da BAT e impactos ambientais também na Bacia do Pantanal. Conclui-se que o TerraME é indicado para gerar cenários de mudanças climáticas em bacias hidrográficas. / Due to agriculture frontier advance in Centre-Western Brazil in the last 40 years, the region became a major grain and meat producer. Soil and Climate particular characteristics, associated to soil management system brought drastic environmental consequences, such as erosion process, mainly in Upper Taquari Basin (UTB). Approximately 86% of UTB is located in North of Mato Grosso do Sul, however the sediment transport effects are reflected downstream, at Pantanal Basin. This study aimed at modeling meteorological variables and simulating climate change scenarios applying dynamic modeling techniques coupled to geoprocessing tools in UTB in order to support land use planning in the region. IPCC assumptions were adopted to simulate two termopluvial scenarios until 2100 applying TerraME (Modelling Environment) tool. An optimistic scenario considers that yearly average air temperature would be increased by 1C, while pessimistic scenario points out 3C as average temperature elevation. Regarding to annual pluvial precipitation means, an optimistic scenario forecasts 15% of precipitation increment. Reductions of 15% in precipitation are waited in pessimistic foreseen. Isolines spatial distribution was calculated using DEM (Digital Elevation Model) based on SRTM (Shuttle Radar Topography Mission). Scenarios generate different spatial topoclimate patterns in the basin. Prevalent mean temperatures currently vary from 23.6 to 25.7C. After 100 years in simulation, optimistic scenario shows a displacement to thermal range from 22.1 to 23.0C. In the next 40 years, on areas along Taquari river basin, from West to East direction, temperatures will overcome current mean superior thermal limit for the region of UTB, i.e., evapotranspiration rates in riparian zone are likely to increase. This indicates a trend to reduction in stream discharges. In the pessimistic scenarios, these temperatures will be anticipated in 20 years. Scenario with 15% higher pluvial precipitation shows that north part of UTB will receive larger rainfall volumes, what should make erosion problem worse. These scenarios demonstrate spatial-temporal dynamic model potential. Among studied climate variables, air temperature is the most sensitive to express climate change effects in Upper Taquari Basin.
|
186 |
Modélisation cellulaire et simulation physique : contribution à l'analyse de la dynamique de population des insectes ravageurs / Cell Modeling and physical Simulation : contribution to the analysis of population dynamics of insect pestsTraore, Mahamadou 09 March 2018 (has links)
Les insectes ravageurs constituent depuis longtemps une menace sérieuse pour l’agriculture dans plusieurs régions du monde. En particulier, les criquets pèlerins (Schistocerca Gregaria) sont les plus redoutés à cause des dégâts colossaux qu’ils peuvent infliger à une large variété de cultures. Ces derniers, dans leur milieu de reproduction et un ensemble de paramètres climatiques, peuvent être assimilés à un système biophysique. Un système biophysique associe plusieurs composants caractérisés par leur complexité propre et celle de leurs interactions. Par exemple la pluie apporte de l’humidité et le développement du couvert végétal qui sont critiques dans la dynamique de population du criquet pèlerin. Ces systèmes biophysiques peuvent être contrôlés par divers moyens, dont un réseau de surveillance couplant des capteurs sans fil. L’intégration des systèmes biophysiques et des réseaux d’observation peut être un des faits majeurs de cette décennie. Elle permet un échange entre les processus cycliques physiques et les systèmes d’information. Ces derniers permettent de collecter et de traiter les données de terrain et peuvent aussi agir sur le système physique par le biais de boucles rétro-actives. Cette intégration a été possible grâce aux avancées technologiques notées dans les domaines de la micro électronique et de la transmission sans fil. On la trouve dans des domaines émergents tels que l’agriculture fine. Cette thèse est consacrée à la modélisation cellulaire et à la simulation de systèmes physiques. Pour cela, un échantillonnage spatial et temporel d’une zone de reproduction des criquets pèlerins a été réalisé à l’aide d’outils spécifiques avec différentes résolutions, dans le but de générer les systèmes cellulaires. Ces systèmes cellulaires contiennent des informations telles que le vent, la température, l’humidité relative et la pluviométrie. L’échantillonnage spatial permet une représentation de migration et l’échantillonnage temporel permet de suivre l’évolution locale des individus dans une cellule.Les systèmes cellulaires sont transcrits en réseaux de processus communicant et évoluent de manière synchrone afin de reproduire et de simuler le phénomène de migration intercellulaire et le cycle de vie du criquet pèlerin dans une cellule. La construction de ces systèmes a été explorée en profondeur, en faisant varier leur contexte géographique, les critères de classification, la dimension des cellules, la connectivité entre les processus, les comportements collectifs. L’exploration a porté sur la génération de codes parallèles et les performances à l’exécution, essentiellement pour le cas des processus légers.Ce travail a abouti à la production de deux simulateurs paramétriques, le premier est destiné à la dynamique de population des criquets pèlerins en vue d’évaluer l’état de la situation acridienne par un couplage entre les réseaux de surveillance synchrones et les systèmes biophysiques. Le second permet de planifier le déploiement de réseaux de capteurs sans fil dans une zone afin de déterminer l’emplacement des capteurs. / Insect pests have long been a serious threat to agriculture in many parts of the world. In particular, desert locusts (Schistocerca Gregaria) are the most feared because of the colossal damage they can inflict on a wide variety of crops.The latter, in their breeding environment and a set of climatic parameters, can be assimilated to a biophysical system. A biophysical system associates several components characterized by their own complexity and that of their interactions. For example, rain brings moisture and canopy development that is critical in Desert Locust population dynamics. These biophysical systems can be controlled by various means, including a monitoring network coupling wireless sensors. The integration of biophysical systems and observation networks can be one of the major events of this decade. It allows an exchange between physical cyclical processes and information systems. These can collect and process field data and can also act on the physical system through feedback loops. This integration has been made possible thanks to technological advances noted in the fields of microelectronics and wireless transmission. It is found in emerging fields such as fine agriculture. This thesis is devoted to cellular modeling and simulation of physical systems. For this, a spatial and temporal sampling of a Desert Locust breeding area was carried out using specific tools with different resolutions, in order to generate the cellular systems. These cellular systems contain information such as wind, temperature, relative humidity and rainfall. Spatial sampling allows a migration representation and temporal sampling can track the local evolution of individuals in a cell.Cellular systems are transcribed into communicating process networks and evolve synchronously to reproduce and simulate the phenomenon of intercellular migration and the life cycle of the Desert Locust in a cell. The construction of these systems has been explored in depth, making vary their geographical context, the criteria for classification, the cells, connectivity between processes, collective behaviors.Exploration has focused on the generation of parallel codes and performance at the execution, mainly for the case of lite processes.This work has led to the production of two parametric simulators, the first of which is aimed at Desert Locust population dynamics with a view to assessing the state of the locust situation through coupling between synchronous monitoring networks and biophysical systems. The second allows you to plan the deployment of wireless sensor networks in an area to determine the location of the sensors.
|
187 |
Cenários de mudanças climáticas usando modelagem dinâmica na Bacia do Alto Taquari. / Climate Change Scenarios using Dynamic Modelling in Upper Taquari Basin.Leila Sheila Silva Lisboa 17 September 2008 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A região Centro-Oeste do Brasil tornou-se nos últimos 40 anos grande produtora de grãos e carne bovina. As condições edafoclimáticas, o sistema de manejo do solo e o descumprimento de leis ambientais trouxeram conseqüências drásticas à região como o agravamento do processo hídrico erosivo, principalmente na Bacia do Alto Taquari (BAT). Cerca de 90% da BAT localiza-se na porção norte do estado de Mato Grosso do Sul (MS), porém os efeitos do transporte de sedimentos e volume de água são refletidos a jusante dos rios, na Bacia do Pantanal. Utilizando-se pressupostos do Painel Intergovernamental de Mudanças Climáticas (IPCC) foram estabelecidos cenários de mudanças climáticas na Bacia do Alto Taquari, visando identificar áreas com maior vulnerabilidade ao processo erosivo em função de pressões de uso da terra. Usando a modelagem dinâmica no TerraME (Environment Modeling) foram gerados cenários topopluviais até 2100, considerando-se para a temperatura do ar média anual um aumento de 1C, em cenário otimista e, em pessimista, elevações térmicas de 3C. Para a precipitação pluvial média anual um cenário foi com aumento de 15% e outro com reduções de 15%. Os dados foram espacializados no ArcGis 9.2 e exportados para o TerraView 3.2, criando-se espaços celulares e integrando-se com as informações do modelo digital do terreno do Shuttle Radar Topography Mission (SRTM) para geração dos mapas topoclimáticos e simulações de cenários no TerraMe. Os resultados apontam que 85% da área da BAT nas condições atuais as temperaturas médias variam entre 23,6 a 25,7C. As simulações térmicas no cenário otimista indicam que em 40 anos as temperaturas tendem a superar o maior limite térmico médio nas áreas ao longo do rio Taquari, no sentido Oeste-Leste. Esses valores evidenciam elevações nas taxas evapotranspiratórias de matas ciliares, indicando reduções na vazão do Taquari. Em cenário pessimista essas temperaturas antecipam sua ocorrência, em um prazo de 20 anos. Os cenários com acréscimo de 15% na precipitação pluvial mostram aumentos no volume de água precipitada na parte norte da Bacia, região mais vulnerável aos problemas de erosão hídrica. Cenários do regime térmico-hídrico apontam áreas mais sensíveis às mudanças climáticas na parte oeste da BAT e impactos ambientais também na Bacia do Pantanal. Conclui-se que o TerraME é indicado para gerar cenários de mudanças climáticas em bacias hidrográficas. / Due to agriculture frontier advance in Centre-Western Brazil in the last 40 years, the region became a major grain and meat producer. Soil and Climate particular characteristics, associated to soil management system brought drastic environmental consequences, such as erosion process, mainly in Upper Taquari Basin (UTB). Approximately 86% of UTB is located in North of Mato Grosso do Sul, however the sediment transport effects are reflected downstream, at Pantanal Basin. This study aimed at modeling meteorological variables and simulating climate change scenarios applying dynamic modeling techniques coupled to geoprocessing tools in UTB in order to support land use planning in the region. IPCC assumptions were adopted to simulate two termopluvial scenarios until 2100 applying TerraME (Modelling Environment) tool. An optimistic scenario considers that yearly average air temperature would be increased by 1C, while pessimistic scenario points out 3C as average temperature elevation. Regarding to annual pluvial precipitation means, an optimistic scenario forecasts 15% of precipitation increment. Reductions of 15% in precipitation are waited in pessimistic foreseen. Isolines spatial distribution was calculated using DEM (Digital Elevation Model) based on SRTM (Shuttle Radar Topography Mission). Scenarios generate different spatial topoclimate patterns in the basin. Prevalent mean temperatures currently vary from 23.6 to 25.7C. After 100 years in simulation, optimistic scenario shows a displacement to thermal range from 22.1 to 23.0C. In the next 40 years, on areas along Taquari river basin, from West to East direction, temperatures will overcome current mean superior thermal limit for the region of UTB, i.e., evapotranspiration rates in riparian zone are likely to increase. This indicates a trend to reduction in stream discharges. In the pessimistic scenarios, these temperatures will be anticipated in 20 years. Scenario with 15% higher pluvial precipitation shows that north part of UTB will receive larger rainfall volumes, what should make erosion problem worse. These scenarios demonstrate spatial-temporal dynamic model potential. Among studied climate variables, air temperature is the most sensitive to express climate change effects in Upper Taquari Basin.
|
188 |
Dinâmica de populações: um estudo a partir de autômatos celulares probabilísticos / Population dynamics: a study from cell probabilistic automataKelly Cristina de Carvalho 16 February 2005 (has links)
Apresentamos dois autômatos celulares com regras de interação locais que permitem descrever a dinâmica de população de um sistema predador-presa. Os modelos são definidos sobre uma rede regular quadrada e se diferenciam pelo caráter isotrópico ou anisotrópico da interação entre os sítios. A cada sítio é associada uma variável estocástica, que pode assumir três estados - vazio, presa ou predador. A dinâmica de competição entre espécies animais que nos interessa é a mesma descrita pelo modelo de Lotka-Volterra no qual as populações de presas e predadores oscilam temporalmente. Nosso objetivo é a análise dessas oscilações, como se comportam com o aumento da rede e se permanecem estáveis. Para a obtenção das séries temporais realizamos simulações de Monte Carlo. Para o autômato definido sobre o espaço isotrópico, também realizamos análise de campo médio dinâmico. Os resultados indicam que a oscilação é um efeito local (não sobrevive em sistemas infinitos), e é mais significativo devido à migração das espécies pelos subsistemas. O estudo da anisotropia revela alguns padrões espaciais organizados e que as oscilações são menos intensas do que no caso isotrópico e como consequência a fase ativa é mais abrangente. / We present two cellular automata with local interaction rules which allow us to describe the dynamical population of a predator-prey system. The models are defined on a regular square lattice and are distinguished by the isotropic or anisotropic character of the interaction between sites. To each site a stochastic variable is associated, which can assume three states- void, prey or predator. The competition dynamics between animal species which interest us is the same described by the Lotka-Volterra model in which the populations of preys and predators oscillate in time. Our aim is the analysis of these oscillations, how they behave with an increasing lattice and if they remain stable. In order to obtain temporal series we perform Monte Carlo simulations. For the automaton defined on isotropic space, dynamical mean field analysis was also performed. Results indicate that the oscillation is a local effect ( vanishing in infinite systems), and is more significant due to migration of species through the subsystems. The study of anisotropy reveals some organized spatial patterns and that oscillations are less intense than in the isotropic case and as a consequence the active phase is more comprehensive.
|
189 |
Autômatos celulares caóticos aplicados na Criptografia e Criptoanálise / Chaotic cellular automata applied to Cryptography and CryptanalysisMarina Jeaneth Machicao Justo 24 July 2013 (has links)
A teoria do caos estuda o tipo de comportamento, aparentemente aleatório, que apresentam alguns sistemas complexos sensíveis à perturbação dos seus parâmetros, como por exemplo sistemas dinâmicos, fractais, autômatos celulares, entre outros. Os autômatos celulares (ACs) são sistemas dinâmicos discretos que podem apresentar comportamentos caóticos a partir de regras simples. Os ACs tem sido empregados em diversas aplicações principalmente em simulações, mas também tem contribuído no reconhecimento de padrões, processamento de imagens e na Criptografia. A necessidade em transmitir informação de forma mais segura vem crescendo com a necessidade por novos algoritmos criptográficos. Paralelamente, os criptoanalistas vem progredindo constantemente na quebra e na procura de vulnerabilidades destes algoritmos, sendo necessaria a incursão de novas abordagens para atender estes desafios. Neste trabalho é proposto o desenvolvimento e avaliação de algoritmos criptográficos, assim como um novo método de criptoanálise, motivados pela adequação dos ACs caóticos com os princípios de confusão e difusão da Criptografia, seguindo critérios apropriados para a boa construção destes algoritmos, que são sintetizados em três partes: (i) Na proposta do algoritmo de cifra criptográfico baseado no AC caótico, foi sugerida uma estratégia de seleção de ACs em base a combinação de vários critérios como o expoente de Lyapunov, a entropia e a distância de Hamming; visando selecionar um AC apropriado para a geração de números pseudo-aleatórios usados no processo de encriptação/decriptação do algoritmo, o qual é validado por diversos testes de aleatoriedade. (ii) Foi proposto o algoritmo de hash criptográfico baseado numa abordagem híbrida dos ACs e as redes complexas, visando a construção de um algoritmo flexível e de bom desempenho. Os resultados alcançados por ambos os algoritmos criptográficos mostraram-se relevantes quando comparados com o estado da arte, com boas qualidades de segurança e um grande potencial para ser aplicados em problemas reais. (iii) Na proposta do método de criptoanálise foi sugerido traçar equivalências entre os sistemas criptográficos e os ACs caóticos visando explorar e analisar seu comportamento dinâmico, por meio da adaptação do algoritmo do expoente de Lyapunov dos ACs, cujos resultados permitiram encontrar padrões característicos nos modos de operação criptográficos. Os resultados obtidos mostraram que a abordagem dos ACs caóticos para desenvolver os algoritmos pode ser bastante útil em aplicações de Criptografia e Criptoanálise. / Chaos theory studies the apparently random behaviour from some complex systems with highly sensitive to the initial conditions, such as dynamical systems, fractals, cellular automata, among others. Cellular automata (CA) are discrete dynamical systems that may exhibit chaotic behaviour from simple rules. CA have been employed in many multidisciplinary applications, most of them in simulations systems, including pattern recognition, image processing and Cryptography. Nowadays, the development of new cryptographic algorithms is required in order to fulfil the increasing demand for secure transmission of confidential information. These algorithms are intensively analyzed, most of them broken by the cryptanalyst community. We proposed to develop two cryptographic algorithms: a block cipher and a hash function based on chaotic CA and its corresponding evaluation. We also proposed a new cryptanalysis methodology motivated by the strong relationship between the chaotic properties of CA and the cryptographic principles of confusion and diffusion, by following appropriate criteria to the proper design of these algorithms, which are summarized into three parts: (i) To proposed the block cipher proposed it was suggested a methodology to select a suitable CA to Cryptography by means of compounded measures such as the Lyapunov exponent, entropy and Hamming distance. Moreover, this selected CA is employed to generate pseudo-random numbers, which are further used in the encryption/decryption of the proposed block cipher and validated under several randomness tests. The results obtained by this cryptographic algorithm achieved similar and even higher performance when compared to others found in literature. (ii) The cryptographic hash function was developed using an hybrid approach of CA and complex networks, in order to build a flexible algorithm with acceptable performance when compared to conventional hash functions. In general, the results obtained from both cryptographic algorithms showed good security qualities and great potential to be applied in real problems. (iii) To proposed the cryptanalysis methodology it was suggested to draw parallels between cryptographic systems and CA, in order to explore and analise their dynamic behaviour. Hence, upon drawing such parallels, we have a means to adapt the Lyapunov exponent algorithm conceived in the framework of CA. Unexpectedly, the results obtained allow to discriminate among cryptographic modes of operation, which provides significant contributions to the field. Finally, we proved that the chaotic cellular automata approach can be quite useful in applications cryptography and cryptanalysis.
|
190 |
Eficácia e comportamento do tempo de imunidade em um modelo de descontaminação de reticulados por autômatos celularesNogueira, Marcelo Arbori 12 December 2013 (has links)
Made available in DSpace on 2016-03-15T19:37:48Z (GMT). No. of bitstreams: 1
Marcelo Arbori Nogueira.pdf: 904606 bytes, checksum: 186b7d2c9f1c91d2dc019d673ecdf983 (MD5)
Previous issue date: 2013-12-12 / Cellular automata are models where, out of the application of a local rule to the cells of their regular lattice, global behaviour emerges. Depending on the rule applied, the emergent behaviour may be interpreted as a computation, or used to simulate
various types of phenomena, such as physical, biological or social. Cellular automata can be used to simulate population growth, spread of disease, tumor growth, decontamination, among other applications. This paper seeks to expand the theoretical limits on the process of decontamination of a two-dimensional lattice using cellular automata, as established by Daadaa (2012). Here we relax premises assumed therein and seek a better understanding of the characteristics of the rules involved as well as of the behaviour of the immunity time of the decontaminated cells. In order to do so, but since the initial conditions correspond to a very large space, massively parallel programming was employed using GPU, which allowed to evaluate a large number of possibilities. It was possible to identify two decontamination rules linked to each type of neighborhood studied (von Neumann and Moore), that generalise previous rules
defined in the work we relied upon. In experiments made with the new rules, their superior efficacy became apparent for random initial conditions; it was also possible to assertain their effectiveness for uniform distribution of states. The general rules allow we developed allowed for a better understanding of the
immunity time required to decontaminate a lattice. It was observed that the ratio between the immunity time and the lattice size is not linear, as suggested by Daadaa. / Autômatos celulares são modelos onde, a partir da aplicação de regras locais às células de seu reticulado, emerge um comportamento global. Dependendo da regra aplicada o comportamento emergente pode ser entendido como uma computação, ou utilizado para simular fenômenos físicos, biológicos, sociais, etc. Pode-se usar autômatos celulares para simular crescimento populacional, propagação de doenças,
crescimento de tumores, descontaminação, entre outras aplicações. O presente trabalho procura expandir limites teóricos a respeito do processo de descontaminação de reticulados bidimensionais por autômatos celulares, apresentado por Daadaa (2012). Flexibiliza-se aqui premissas lá assumidas e procura-se uma melhor compreensão sobre as características das regras envolvidas bem como do comportamento do tempo de imunidade de células recuperadas. Para tanto, uma vez que as possíveis condições iniciais configuram um espaço muito grande, foi empregada programação massivamente paralela utilizando GPU,
permitindo avaliar um grande número de possibilidades. Foi possível identificar duas regras de descontaminação, específicas para cada tipo de vizinhança estudada (vizinhanças de von Neumann e de Moore), que generalizam as regras anteriormente definidas no mesmo contexto do trabalho aqui tratado. Nos experimentos realizados, foi possível comparar a eficácia das regras propostas com as que lhes deram origem, e ficou evidente a eficácia superior das novas regras para condições iniciais aleatória; também foi possível constatar a eficácia das regras para distribuições uniformes de estados. As regras gerais desenvolvidas permitiram melhor compreensão do tempo de
imunidade necessário para descontaminar um reticulado. Foi possível observar que a relação do tempo de imunidade com o tamanho do reticulado não é linear como sugerido no trabalho de Daadaa.
|
Page generated in 0.0728 seconds