Trabalho Final Matematica Discreta Automato Celular 2022-2

1 TRABALHO FINAL DE MATEMÁTICA DISCRETA 20222 Esse trabalho final consiste em implementar um autômato celular conforme descrito nos trabalhos de Conway 0X Nas questões de implementação deverão ser realizados testes com diferentes valores dos parâmetros Além disso a linguagem de implementação deverá ser CC ou Java ou Python e não poderão ser utilizadas bibliotecas prontas Trabalhos que forem implementados em outras linguagens terão nota atribuída como zero Bibliotecas gráficas para plotagem dos gráficos são permitidas podendo ser usado o Excel Java Python ou outra biblioteca gráfica Entrega Código fonte do trabalho e o relatório contendo no máximo 5 páginas O arquivo a ser enviado deverá ser no formato ZIP com nome dado NOMESOBRENOMEALUNO1NOMESOBRENOMEALUNO2ZIP Data de entrega 18012023 até às 2359h após esse horário a nota será automaticamente zero O trabalho pode ser realizado em DUPLA Referência 0X httpwwwconwaylifecomwiki 1 Hunter DJ Fundamentos da Matemática Discreta LTC 2011 2 Hoekstra AG et al Simulating Complex Systems by Cellular Automata Springer 2010 3 httpwwwconwaylifecomwikiMainPage Descrição das Questões Autômatos celulares são estruturas discretas formadas por uma rede de células que possuem seus estados alterados num tempo discreto de acordo com seu estado anterior e o estado de suas células vizinhas Algumas características importantes e comuns a todos os autômatos celulares são Estados discretos cada célula pode estar em um dos finitos estados Homogeneidade as regras são iguais para todas as células Interações locais o estado de uma célula depende apenas das células mais próximas vizinhas Processo dinâmico a cada instante de tempo as células podem sofrer uma atualização de estado Matematicamente um autômato celular é definido por uma 5tupla de elementos ARSS0 V F onde R é a grade de células pode ser 1D 2D 3D S é o conjunto de estados de uma célula ci S0 é o estado inicial do sistema V é conjunto vizinhança define quem são os vizinhos de cada célula F é a função de transição regras de governam a evolução do sistema no tempo O Jogo da Vida The Game of Life é um algoritmo de simulação de um sistema dinâmico criado pelo matemático britânico John Horton Conway em 1970 O algoritmo não possui entradas ie só depende do seu estado inicial Um exemplo pode ser visto em httpswwwyoutubecomwatchvC2vgICfQawEt281s O Jogo da Vida é o primeiro exemplo desenvolvido de um autômato celular O interesse teórico pelo Jogo da Vida se deve ao fato de que o algoritmo é uma Máquina Universal de Turing ou seja qualquer problema computável pode ser computado pelo Jogo da Vida 2 Especificamente o Universo do Jogo da Vida consiste de um grid malha bidimensional de células quadradas Cada célula pode se encontrar em dois estados viva ou morta Cada célula interage com oito células vizinhas horizontais verticais e diagonais Resumidamente as regras do jogo são 1 Uma célula viva com menos do que 2 células vizinhas vivas deve morrer na próxima geração devido à superpopulação 2 Uma célula viva com 2 ou 3 células vizinhas vivas permanece viva na próxima geração 3 Uma célula viva com mais de 3 vizinhos morre na próxima geração devido à superpopulação 4 Uma célula morta com exatamente 3 células vizinhas vivas se torna viva na próxima geração devido à reprodução As regras descritas acima correspondem ao Jogo da Vida padrão Tais regras são usualmente resumidas através dos símbolos B3S23 Born 3 Stays alive 2 and 3 Várias outras regras já foram testadas como por exemplo B6S16 B36S23 B3S236 B3S2367 etc Em particular a regra B36S23 Born 3 and 6 Stays alive 2 and 3 é conhecida como High Life Dependendo da regra utilizada e da inicialização padrões de evolução surpreendentes podem ser observados Estes padrões possuem categorias como por exemplo Still lifes padrões estáticos Oscillators padrões que se repetem indefinidamente Spaceships padrões que se assemelham a naves espaciais Guns padrões estacionários que emitem naves espaciais Methuselah padrão que demora muito tempo para estabilizar Vários outros padrões são possíveis Verifique referência 3 A Figura 1 ilustra alguns exemplos de padrões Figura 1 Alguns exemplos de padrões 3 Tarefas 1 Descreva como uma 5tupla o problema do Jogo da Vida 2 Implementar o Jogo da Vida utilizando as regras B3S23 e B3S236 3 O usuário do programa deve poder selecionar qual a regra desejada 4 A regra B3S23 deve ser testado com os seguintes padrões a Glider pequena nave espacial Verifique em httpwwwconwaylifecomwikiGlider b Pulsar oscilador com período 3 Verifique em httpwwwconwaylifecomwikiPulsar c Gosper Glider Gun criado por Bill Gosper este é um padrão que produz um glider na 15a geração um outro na 30a e assim por diante Verifique em httpwwwconwaylife comwikiGosperglidergun 4 A regra B3236 deve ser testado com os seguintes padrões a The Replicator este padrão faz cópias dele mesmo ao longo de uma linha diagonal A primeira cópia surge após 12 gerações e produz duas cópias mais após 24 gerações e assim por diante Verifique em httpwwwconwaylifecomwikiHighLife Figura 2 The Replicator b The Bomber este padrão é uma nave espacial baseada no comportamento do Replicator Pode ser iniciado colocando um padrão do tipo Blinker no caminho do Replicator Verifique em httpwwwconwaylifecomwikiHighLife Figura 3 The Bomber 4 5 O usuário deve poder selecionar qual o padrão de entrada estado inicial Por exemplo pode ser definido no programa principal matrizes correspondendo a cada padrão de entrada 6 Pesquisa outras aplicações de Autômatos Celulares AC e descreva a definição matemática do AC para a aplicação