Sistemas Dinâmicos Discretos de Ordem Superior PDF

SISTEMAS DINÂMICOS DISCRETOS DE ORDEM SUPERIOR Arnaldo Abrantes | Paulo Vieira | Carlos Júnior 2023 AUTÓMATOS CELULARES Sistema dinâmico no qual um grande número de variáveis discretas estão dispostas num array ou grelha Actualizado a cada passo temporal atravé...

SISTEMAS DINÂMICOS DISCRETOS DE ORDEM SUPERIOR Arnaldo Abrantes | Paulo Vieira | Carlos Júnior 2023 AUTÓMATOS CELULARES Sistema dinâmico no qual um grande número de variáveis discretas estão dispostas num array ou grelha Actualizado a cada passo temporal através de uma regra determinística Evolução depende de interacções locais ACs são modelos discretos, no espaço e no tempo Cada célula é uma máquina de estados (implementando um conjunto de regras de transição) que produz o próximo estado da célula, tendo como entradas os estados das células numa dada vizinhança local setembro de 24 2 EVOLUÇÃO NO TEMPO DOS ACS Nos ACs o estado actual determina completamente o próximo estado não é necessário ter memória de nenhum estado anterior ao actual Uma vez que as regras e os estados são locais, qualquer padrão global que eventualmente apareça, é necessariamente emergente setembro de 24 3 AUTÓMATOS CELULARES: BREVE HISTÓRIA 1940s – Modelos inventados por John von Neumann por sugestão de Stanislaw Ulam (o objectivo inicial era estudar o processo de reprodução) 1969 – Konrad Zuse publica um artigo onde defende que “As leis físicas do Universo são discretas” 1970s – Os ACs ganham popularidade com o Jogo da Vida de Conway setembro de 24 4 AUTÓMATOS CELULARES: BREVE HISTÓRIA 1983 – Stephen Wolfram publica o primeiro de um conjunto de artigos em que investiga de forma sistemática as propriedades dos ACs 2002 – É publicado o livro de Wolfram, “A New Kind of Science” setembro de 24 5 APLICAÇÕES: CIÊNCIA, TECNOLOGIA, ARTE Autómatos celulares podem ser usados para modelar sistemas complexos usando regras simples Características principais: Divide o espaço do problema em células Cada célula pode estar num dos vários possíveis estados As células são afectadas pelas vizinhas de acordo com regras Em cada geração, todas as células são afectadas simultaneamente As regras são reaplicadas repetidamente em cada uma das muitas gerações 6 UTILIDADE Modelar fenómenos físicos e biológicos, e.g.: Sistemas mecânicos estatísticos Conjuntos químicos autocatalíticos – hodgepodge machine Regulação genética Organismos multicelulares Colónias e superorganismos Bandos e rebanhos – optimização da segurança Ecossistemas Economias e sociedade – competição VS cooperação [Flake, 1998 pp. 251-255] setembro de 24 7 NOTAÇÃO – CASO 1D E 2D Cada célula possui um conjunto de propriedades que podem variar ao longo do tempo (variáveis) Aos valores das variáveis duma célula dá-se a designação de estado da célula O estado global (ou configuração) do AC é definido pelo conjunto dos estados de todas as células e representa-se usualmente na forma de um vector ou de uma matriz Símbolo Significado t Tempo t Passo temporal, normalmente 1 ai(t) Estado da célula i no instante t (caso 1D) aij(t) Estado da célula na posição (i,j) no instante t (caso 2D) setembro de 24 A(t) Estado global do AC no instante t 8 CÉLULA E ESTADO Célula Uma célula é o elemento básico do AC; Uma célula funciona como um elemento de memória que armaneza um estado. Estado A célula i no instante t está num dos k estados do conjunto S Frequentemente o conjunto é binário, S = 0,1 Por vezes é ternário, S = 0,1,2 etc. 9 GRELHA E VIZINHANÇA Uma grelha é um array de células (1D, 2D, 3D) que define a organização espacial das mesmas célula 1D 0 0 2 1 2 0 1 0 0 0 2 0 0 A “vermelho” está a 2D (Autómatos de Pixels) vizinhança da célula 0 1 1 1 2 “verde” 1 0 1 1 0 0 2 2 0 2 1 0 2 1 2 3D (Autómatos de Voxels) 10 VIZINHANÇA A vizinhança de uma célula consiste nas células em seu redor A vizinhança de uma célula é constituída por n células ela própria mais as células adjacentes a que está ligada Exemplos (vizinhança de Moore): Numa grelha 1D, n = 2r + 1, r = “raio” Em 2D, n = (2r + 1)2 Em 3D, n = (2r + 1)3 A interacção é local! Significa que não é permitida qualquer acção-à- distância Podem existir várias definições para vizinhança 11 VIZINHANÇAS MAIS USUAIS – CASO 2D Moore r=1 r=2 von Neumann Outras 12 ACTUALIZAÇÃO SÍNCRONA EM TEMPO DISCRETO t=1 t=2 Os estados das células são actualizados, em simultâneo, em instantes discretos de tempo 13 CONDIÇÕES FRONTEIRA Grelha infinita/adaptativa A grelha cresce à medida que o padrão se propaga; Grelha finita Fronteira rígida (hard) – as células nas extremidades da grelha têm um estado fixo (usualmente 0); Fronteira suave (soft) – condições fronteira periódicas (wrap) Caso 1D – forma-se um anel; Caso 2D – forma-se um toróide; Caso 1D – 4 hipóteses: a) array infinito; b) array finito, fronteira FIXA; c) array finito, fronteira REFLECTIVA; d) array finito, fronteira PERIÓDICA. 14 REGRAS DE TRANSIÇÃO As regras de transição determinam qual o próximo estado das células definem máquinas de estados As regras de transição dependem da geometria da grelha, da vizinhança e do estado Tipicamente as regras são uniformes (i.e., são iguais em toda a parte da grelha) – ACs homogéneos 15 REPRESENTAÇÃO EM TABELA ai-1(t) ai(t) ai+1(t) ai(t+1) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 ai (t + 1) = ai −1 (t )  ai (t )  ai +1 (t ) 16 REPRESENTAÇÃO GRÁFICA ai-1 ai ai+1 t n = 3 (raio unitário) t+1 k = 2 (binário) Exemplo (igual ao da tabela anterior): Dimensão da regra: 23=8 Número possível de regras: 28=256 17 EXEMPLO: CASO 1D Questão: Para um autómato celular com k estados e vizinhança de von Neumann com raio r (n = 2r + 1), quantas regras diferentes são possiveis? Resposta: O número de configurações possíveis para a vizinhança é igual a #V = k(2r + 1) No caso em que k = 2, r = 1, tem-se #V = 8 possíveis configurações. O número de regras diferentes que se podem definir é dado por k#V Para o caso anterior, tem-se portanto um total de 28 = 256 diferentes regras. 18 ENUMERAÇÃO DAS 256 REGRAS Neste caso é possível enumerar as regras de forma exaustiva 19 OUTRO EXEMPLO 1D: CASO INTRACTÁVEL k = 10 (cada célula pode tomar um de 10 estados) r = 2 (a vizinhança é constituída por 5, 2r + 1, células) Existem pois 105 diferentes configurações para a vizinhança (ou seja, uma regra pode ser representada por uma tabela com 100.000 entradas) Ou seja, neste caso podem ser definidas 10100000 regras diferentes! 20 ILUSTRAÇÃO: CASO 2D Tabela com regra de transição: t Centro Cima Direita Baixo Esq. Estado (t + 1) t+1 … … … … … … 21 EXEMPLO: CASO 2D Questão: Para um AC binário (k = 2) e vizinhança de Moore, com raio 1(ou seja, n = (2r + 1)2 = 9), quantas regras diferentes podem ser definidas? Resposta: Existem 29 = 512 diferentes configurações para a vizinhança e portanto uma tabela com uma regra específica de transição terá 512 entradas; O número de regras diferentes que se podem definir é portanto 2512, um número verdadeiramente gigantesco! 22 CONFIGURAÇÃO INICIAL A configuração inicial estabelece o estado inicial de todas as células do autómato celular; É muito importante especificar claramente a configuração inicial para se proceder à correcta definição do autómato celular. 23 AUTÓMATOS CELULARES ELEMENTARES Dois estados possíveis por célula (k = 2) e vizinhança da célula definida pelas duas células adjacentes (r = 1); A célula e as suas vizinhas formam uma vizinhança de 3 células e portanto existem 8 possíveis padrões para a vizinhança e um total de 256 regras possíveis; Estes 256 ACs são geralmente referidos usando a notação de Wolfram: um número que expresso em binário nos dá directamente a tabela da regra. 111 0 011 1 Exemplo: regra 30 (24 + 23 + 22 + 21) 110 0 010 1 101 0 001 1 100 1 000 0 24 EXEMPLO: REGRA 30 t= 0 t= 1 t= 8 25 EXEMPLOS: ACS ELEMENTARES Regra 30 Regra 110 Regra determinística capaz de Nem totalmente periódico nem produzir padrões aleatórios totalmente aleatório 26 DIAGRAMAS ESPAÇO-TEMPO DE 32 ACS ELEMENTARES 27 TAXONOMIA DOS ACS ELEMENTARES Classe I – Ponto fixo (Constante) Tende a ficar num único estado Exemplos: Regra 250 Classe II – Ciclo limite (Repetições) Formam-se estruturas periódicas Exemplos: Regra 90 Classe III – Caótico (Pseudo-aleatório) Formam-se padrões aperiódicos (caóticos) Exemplos: Regra 30 Classe IV – Estruturados (Complexos) Formam-se padrões complexos (movem-se no espaço-tempo) Exemplo: Regra 110 28 AUTÓMATOS CELULARES TOTALÍSTICOS Num autómato celular totalístico, o estado seguinte de uma célula é função da soma dos valor da célula em questão com os valores das suas células vizinhas; Exemplo: (AC 1D, r=1, k=3) Tabela com regra de transição: ai-1(t)+ai(t)+ai+1(t) ai(t+1) 0 0 1 2 2 1 3 0 4 2 5 0 6 2 29 ACS TOTALÍSTICOS – REGRAS DE TRANSIÇÃO Questão: Qual a dimensão da tabela de regra para um AC 1D totalístico? E quantas regras diferentes (ACs) podem ser definidos? Resposta: A soma pode tomar todos os valores de 0 até n(k-1), ou seja tem-se n(k-1)+1 diferentes valores para a soma que é a dimensão da tabela que define a regra; O número de regras diferentes é dado portanto por kn(k-1)+1 30 AC TOTALÍSTICO: EXEMPLO Questão: Comparar as dimensões das tabelas de regras e o número possível de regras um AC totalístico e um AC elementar, tratando-se em ambos os casos de um AC 1D, ternário (k=3) e com raio unitário (n=3). Resposta: No caso do AC totalístico, tem-se que as tabelas de regras têm 7 entradas, havendo 37=2187 possíveis regras; No caso do AC elementar tem-se que as tabelas de regras têm 33=27 entradas, havendo 327 possíveis regras (cerca de 8 milhões de milhões). 31 AUTÓMATOS CELULARES TOTALÍSTICOS EXTERNOS Num autómato celular totalístico externo, o estado seguinte de uma célula depende do seu estado actual e da soma dos valores das células vizinhas. Questão: Qual a dimensão da tabela de regra de um AC totalístico externo 2D, binário, com r=1? Quantas regras diferentes se podem construir? Resposta: A soma externa pode variar entre 0 e 8 (ou seja, 9 valores). Podemos ter pois 18 configurações diferentes Tem-se 218 diferentes regras (Nota: o Jogo da Vida é uma destas 262144 regras) 32 EXERCÍCIO PRÁTICO setembro de 24 MSSN - Geração Procedimental de Conteúdos 33 O JOGO DA VIDA Soma externa aij(t) aij(t+1) 0 0 0 O Jogo da Vida é um dos 262144 possíveis ACs 0 1 0 totalísticos externos, 2D, binários, com raio 1 1 0 1 0 0 unitário. 2 0 0 A tabela ao lado descreve a regra do Jogo da Vida 2 1 1 3 0 1 O mesmo modelo descrito em termos de uma 3 1 1 máquina de estados: 4 4 0 1 0 0 5 0 0 5 1 0 6 0 0 Soma = 3 6 1 0 1 7 0 0 7 1 0 Soma 2,3 8 0 0 8 1 0 0 34 O JOGO DA VIDA – JOHN CONWAY O Jogo da Vida é um autómato celular imaginado pelo matemático britânico John Conway em 1970 e tornado popular por Martin Gardner O “jogo” era originalmente jogado com peças num tabuleiro de Go 35 JOGO DA VIDA #n = 3 #n / si,t 0 1 1 3 0 0 Morre de “asfixia” 0 36 JOGO DA VIDA Essencialmente um autómato celular, 2D, totalístico externo, binário (k=2) e r=1 (n=9) Regras da Vida: O próximo estado de cada célula depende do seu estado actual e da soma do estado das 8 vizinhas; #n = 3 #n / si,t 0 1 1 3 0 0 Morre de “asfixia” 0 37 VIDA PARADA Padrões estáveis e imutáveis 38 OSCILADORES Padrões periódicos 39 NAVES Padrões em movimento 40 GLIDER O padrão mais pequeno que se move repetidamente sobre a grelha Após 4 gerações o padrão original reproduz-se uma célula a baixo e uma célula à direita 41 O PENTOMINÓ-R Os pentominós (5 células vivas adjacentes) são relativamente pouco interessantes (morrem rapidamente ou convergem para uma forma de “vida parada”), excepto o pentominó-r que se vai “reproduzindo” em múltiplas formas dando origem, ao fim de cerca de 1000 iterações, a uma “população” de 6 gliders, 8 blocks, 4 beehives, 4 blinkers, 1 ship, 1 boat, 1 loaf, etc. pentominó-r 42 AUTÓMATOS CELULARES CONTÍNUOS Um AC contínuo é totalmente análogo aos ACs que temos vindo a estudar, excepto no facto dos estados não serem valores discretos mas sim valores contínuos; Ao contrário dos ACs binários, ternários, etc., cada célula num AC contínuo pode, idealmente, estar num número infinito de estados – na prática, o número de estados é limitado pela precisão numérica usada pelo computador. Exemplo (AC totalístico, contínuo, 1D, raio unitário): O estado seguinte é calculado extraindo a parte fraccionária do valor que se obtém somando os estados da vizinhança com uma dada constante  i +1  ai (t + 1) = frac   a n (t ) + Const.   n =i −1  43 EXEMPLO 44 AUTÓMATOS CELULARES ESTOCÁSTICOS Ao contrário dos autómatos celulares determinísticos, o comportamento de um AC estocástico é regido por regras probabilísticas; Os ACs estocásticos são modelos de sistemas “com ruído” nos quais os processos não funcionam exactamente sempre da mesma forma, que é o que acontece frequentemente em sistemas naturais; O comportamento destes ACs tende a ser muito rico e complexo, formando-se frequentemente estruturas exibindo auto-semelhança e comportamento caótico; Têm capacidade de imitar muitos fenómenos encontrados na natureza (crescimento de cristais, turbulência, etc.) 45 EXEMPLO AC 1D, estocástico, binário (k=2) e r = 1 Tabela de transição: ai-1(t) ai(t) ai+1(t) P(ai(t+1)=1) 0 0 0 0.00 0 0 1 0.50 0 1 0 0.50 0 1 1 0.50 1 0 0 0.66 1 0 1 0.50 1 1 0 0.50 1 1 1 0.00 46 AC ESTOCÁSTICO: FOGO NA FLORESTA 47 MODELO DE INCÊNDIO NA FLORESTA O modelo é um AC estocástico, 2D, onde cada célula pode estar num dos seguintes 3 estados: Estado 0 – Clareira; Estado 1 – Árvore; Estado 2 – Árvore a arder. O estado de cada célula evolui de acordo com as seguintes regras: Uma clareira (estado 0) passa a árvore (estado 1) com probabilidade p; Uma árvore (estado 1) passa a árvore a arder (estado 2): Com probabilidade f se não tiver na vizinhança árvores a arder (f representa a probabilidade de um relâmpago); Com probabilidade 1-g se tiver na vizinhança uma ou mais árvores a arder (g representa a probabilidade da árvore resistir ao fogo); Uma árvore a arder (estado 2) passa a clareira (estado 0) com probabilidade 1 48 REPRESENTAÇÃO EM MÁQUINA DE ESTADOS Parâmetros do modelo: p – probabilidade de crescer uma árvore numa clareira; f – probabilidade de cair um raio numa árvore e incendiá-la; g – probabilidade de uma árvore não arder, tendo árvore(s) vizinha(s) a arder. p 0 1 (m, n)  Vij : amn = 2 amn  2, (m, n) Vij 1-g f 1 2 49 SIMULAÇÃO - NETLOGO Início Os primeiros focos de incêndio O fogo alastra A florestação e o incêndio 50 OS FOGOS E A DENSIDADE DA FLORESTA Densidade inicial: 5% Taxa de crescimento da floresta (p): 1.5% Probabilidade de relâmpago (f): 0.001% Probabilidade de imunidade (g): 2% 51 DESAFIO AGREGAÇÃO DE DIFUSÃO LIMITADA (DLA) setembro de 24 52 AGREGAÇÃO DE DIFUSÃO LIMITADA Encontra-se em: Crescimento de cristais Recifes de coral Outros sistemas naturais setembro de 24 53 AGREGAÇÃO DE DIFUSÃO LIMITADA Aleatoriedade e auto-semelhança não são mutuamente exclusivos Partículas semente (seed) movem-se num meio com movimento Browniano Mantém-se em movimento enquanto não tocar num objecto estacionário À medida que o processo avança, partículas acumulam-se numa estrutura em crescimento setembro de 24 54 IMPLEMENTAÇÃO DLA setembro de 24 55