Trabalho Pratico Matematica Discreta UFMG - Implementacao de Fractais em C

Trabalho Prático UFMGICExDCC DCC216 Matemática Discreta Ciências Exatas Engenharias 1o Semestre 2023 Observações 1 Comece a fazer este trabalho imediatamente Você nunca terá tanto tempo para resolvêlo quanto agora 2 Data de entrega 31 de maio de 2023 até às 2359 horas ou antes 3 Submissão Faça a submissão deste trabalho no Moodle conforme instruções postadas lá 4 Plataforma computacional O seu trabalho deve ser executado em alguma máquina do ambiente computacional do Departamento de Ciência da Computação da UFMG onde os monitores irão avaliálo 5 Linguagem Você deve escrever o seu programa obrigatoriamente na linguagem de pro gramação C 6 Documentação Uma documentação que explique cada uma das cinco partes descritas neste docu mento Em particular descreva as fases de especicação projeto e implementação dos algoritmos deste TP Um arquivo leiametxt a ser incluído no arquivo zip como informações sobre o ambiente computacional para executar o seu TP bem como todas as instruções neces sárias 7 Testes O seu programa será avaliado conforme descrito no Moodle da disciplina MD o 20231 Trabalho Prático 1 Fractais O que são fractais Um fractal é uma forma ou padrão geométrico que exibe autosemelhança em diferentes escalas ou ampliações Em outras palavras ao ampliar um fractal você verá os mesmos padrões ou padrões semelhantes repetidos em escalas cada vez menores Os fractais são muitas vezes for mas complexas e irregulares que são criadas através de processos iterativos ou recursivos o que signica que a mesma fórmula matemática ou algoritmo é aplicado repetidamente para gerar a forma Os fractais são encontrados em muitos objetos naturais e articiais como ocos de neve lito rais raios e até tendências do mercado de ações Eles também têm sido usados em uma variedade de áreas incluindo matemática física ciência da computação arte e design Um exemplo famoso de fractal é o conjunto de Mandelbrot1 que é um conjunto de números complexos que é gerado por meio de um processo iterativo especíco e produz um padrão fractal surpreendentemente intrincado e detalhado Fractais que geram uma cadeia de polígonos simples Existem algoritmos fractais que geram uma cadeia de polígonos simples ou seja polígonos que não possuem cruzamentos ou interseções que serão o foco deste trabalho prático Por exemplo algoritmos nos chamados Lsistemas Sistema de Lindenmayer2 ou sistemas de reescrita de cadeias fractais determinísticos e fractais de movimento brownianos fractais aleatórios Os Lsistemas são um tipo especial de gramática de reescrita de strings Esses sistemas reescrevem uma determinada cadeia de caracteres ie strings que representam uma sequência de símbolos de acordo com uma gramática que é um conjunto de regras veja os exemplos abaixo Sistemas de reescrita de strings podem ser usados para gerar curvas fractais clássicas como o oco de neve clássico de von Koch e as curvas de preenchimento de espaço de Peano e Hilbert Esses fractais podem ser gerados fornecendo o axiomauma sequência de caracteres cada um com um signicado que é usado para iniciar a geração do fractal e um ângulo θ as regras de produçãoindicam como cada caractere do axioma pode ser substituído e o número de ciclos ou estágiosindicam o nível de recursividade Basicamente os caracteres símbolos que aparecem no axioma e nas regras de produção são F desenha uma linha para a frente na direção onde a caneta se encontra vire à direita em θ graus a direção da caneta vire à esquerda em θ graus a direção da caneta Para desenhar todos os fractais deste trabalho podemos imaginar que a caneta que fará o desenho está posicionada inicialmente sobre uma linha horizontal e está direcionada para a direita ou seja faz um ângulo de 0 com essa linha 1Veja em httpsptwikipediaorgwikiConjuntodeMandelbrot para mais informações 2Veja em httpsenwikipediaorgwikiLsystem e em httpswwwusergwdgdegroimpgrogra degrammarslsystemshtml para mais informações MD o 20231 Trabalho Prático 2 Exemplo de um desenho O fractal de oco de neve clássico de von Koch pode ser denido pelo seguinte Lsistema axioma valor de θ regras de produção e estágiosneste caso o valor será fornecido como uma entrada Axioma F θ π 3 Regra F FFFF O axioma indica a regra de geração do fractal Neste caso o axioma indica apenas um segmento desenhado na horizontal a partir de uma posição inicial O ângulo vale π 3 ou 60 que é o valor da rotação para a direita ou esquerda A regra mostra que a ocorrência do símbolo F deve ser substituída pelo sequência de símbolos FFFF na geração dos próximos estágios A Figura 1 ilustra os primeiros estágios do fractal de oco de neve clássico de von Koch A Figura 1a mostra o axioma desse fractal que se resume a aplicar a regra F Observe que o primeiro estágio recursivo é obtido aplicando a regra que diz que o símbolo F deve ser substituído pela sequência FFFF como ilustrado na Figura 1b Os outros estágios aplicam a mesma regra toda ocorrência de F deve ser substituída por FFFF Figura 1 Primeiros estágios do fractal de oco de neve clássico de von Koch O primeiro estágio do fractal de oco de neve clássico de von Koch que deve gerar o polígono denido pela sequência de símbolos FFFF é desenhado da seguinte forma a Inicialmente a caneta se encontra sobre uma linha horizontal e está direcionada para a direita como mencionado anteriormente b FFFF O primeiro símbolo é F e um segmento é desenhado nessa direção c FFFF O próximo símbolo 2o é e a caneta é girada de 60 para a esquerda MD o 20231 Trabalho Prático 3 d FFFF O próximo símbolo 3o é F e um segmento é desenhado nessa direção e FFFF Os próximos dois símbolos 4o e 5o são e a caneta é girada de 120 2 60 para a direita f FFFF O próximo símbolo 6o é F e um segmento é desenhado nessa direção g FFFF O próximo símbolo 7o é e a caneta é girada de 60 para a esquerda h FFFF O próximo e último símbolo 8o é F e um segmento é desenhado nessa direção A Tabela 1 mostra a sequência de caracteres string dos estágios iniciais do fractal de oco de neve clássico de von Koch Com os símbolos de cada sequência é possível desenhar esse estágio do fractal como ilustrado na Figura 1 Estágio Sequência de caracteres 1 FFFF 2 FFFFFFFFFFFFFFFF 3 FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFF 4 FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFFFFFFFF FFFFFFFFFFFFFFF Tabela 1 Sequência de caracteres string dos primeiros estágios do fractal de oco de neve clássico de von Koch MD o 20231 Trabalho Prático 4 O número total de segmentos F gerados em n etapas completas é F 4n A Tabela 2 lista a quantidade de segmentos e símbolos para os primeiros estágios do fractal de oco de neve clássico de von Koch n F Símbolos 1 4 8 2 16 36 3 64 145 4 256 585 Tabela 2 Quantidade de segmentos e símbolos para os primeiros estágios do fractal de oco de neve clássico de von Koch Exemplos de fractais que geram uma cadeia simples A seguir são apresentadas as denições de vários fractais que geram uma cadeia simples usando o Lsistema Veja a literatura para vários outros fractais como o ilustrado na Figura 2 Figura 2 Exemplo de outro fractal 1 Floco de neve clássico de von Koch Axioma F θ π 3 Regra F FFFF 2 Floco de neve onda quadrada de von Koch Veja Figura 3 Axioma F θ π 2 Regra F FFFFFFFF MD o 20231 Trabalho Prático 5 3 Floco de neve onda senoidal 1 de von Koch Veja Figura 4 Axioma F θ π 3 Regra F FFFFFF Figura 3 Dois primeiros estágios do fractal oco de neve onda quadrada de von Koch Figura 4 Dois primeiros estágios do fractal oco de neve onda senoidal 1 de von Koch 4 Floco de neve onda senoidal 2 de von Koch Veja Figura 5 Axioma F θ π 3 Regra F FFFFFFFF 5 Ilha de Koch Veja Figura 6 Axioma FFFF θ π 2 Regra F FFFFFFFFF MD o 20231 Trabalho Prático 6 Figura 5 Dois primeiros estágios do fractal oco de neve onda senoidal 2 de von Koch Figura 6 Dois primeiros estágios do fractal ilha de Koch 6 Preenchimento de espaço de Hilbert Veja Figura 7 Axioma X θ π 2 Regras X YFXFXFY Y XFYFYFX 7 Preenchimento de espaço de Peano Veja Figura 8 Axioma X θ π 2 Regras X XFYFXFYFXFYFXFYFX Y YFXFYFXFYFXFYFXFY No caso dos fractais preenchimento de espaço de Hilbert e de Peano temos os símbolos X e Y os quais são usados na denição recursiva No entanto ao nal do nésimo passo recursivo esses dois símbolos devem ser removidos e a sequência de caracteres resultante terá apenas os símbolos F e Por exemplo suponha que desejamos gerar a sequência de símbolos do primeiro estágio do fractal preenchimento do espaço de Peano Temos os seguintes passos 1 O axioma é denido pelo símbolo X MD o 20231 Trabalho Prático 7 Figura 7 Dois primeiros estágios do fractal espaço de Hilbert Figura 8 Dois primeiros estágios do fractal espaço de Peano 2 Substituímos o símbolo X pela regra correspondente para gerarmos o primeiro estágio desse fractal Assim temos XFYFXFYFXFYFXFYFX 3 Como desejamos gerar apenas a sequência de símbolos do primeiro estágio desse fractal o processo recursivo está nalizado e devemos eliminar todas as ocorrências dos símbolos X e Y Assim temos XFYFXFYFXFYFXFYFX sequência do primeiro estágio com os símbolos X e Y F F F F F F F F sequência após a eliminação dos símbolos X e Y FFFFFFFF sequência sem os espaços em branco não devem aparecer Observe que a sequência resultante FFFFFFFF desenha o primeiro estágio do fractal espaço de Peano como ilustrado na Figura 9 o qual possui oito símbolos F e um total de 12 símbolos MD o 20231 Trabalho Prático 8 Figura 9 Primeiro estágio do fractal espaço de Peano com os símbolos associados sendo que θ 90 O que deve ser feito Este TP é constituído de cinco partes como descrito abaixo Leia com atenção o que deve ser feito 1 Fazer três programas um para cada fractal como indicado a seguir i Um fractal dentre os seguintes Floco de neve onda quadrada de von Koch algs nº matrícula mod 4 0 Floco de neve onda senoidal 1 de von Koch algs nº matrícula mod 4 1 Floco de neve onda senoidal 2 de von Koch algs nº matrícula mod 4 2 Ilha de Koch algs nº matrícula mod 4 3 Para definir o fractal que você deve implementar pegue o seu número de matrícula 10 dígitos some esses algarismos e calcule o resto da divisão inteira por 4 O resto será um valor entre 0 e 3 que deve ser usado para identificar o fractal a ser implementado como definido acima Por exemplo para o nº de matrícula 2022012345 a soma dos algarismos vale 21 e o resto da divisão inteira por 4 é 1 Assim o fractal a ser implementado é o floco de neve onda senoidal 1 de von Koch ii Um fractal dentre os seguintes Preenchimento de espaço de Hilbert nº de matrícula par Preenchimento de espaço de Peano nº de matrícula ímpar Para o exemplo de nº de matrícula anterior o fractal a ser implementado é o preenchimento de espaço de Peano nº de matrícula ímpar iii Um fractal definido por você que gere uma cadeia de polígonos simples que tenha pelo menos duas regras como as curvas de preenchimento de espaço de Peano e Hilbert 2 Claramente há pelo menos duas estratégias para implementar esses fractais a Uma versão iterativa onde os caracteres de um estágio intermediário são gravados em um arquivo lidos e processados para gerar um outro arquivo para o próximo estágio até se chegar ao estágio desejado b Uma versão recursiva que gera os caracteres do estágio desejado Discuta essas duas estratégias e outras que você considerou analisando pontos positivos e negativos de cada uma 3 Para cada um dos fractais implementados apresente a equação de recorrência para calcular a quantidade de segmentos F gerados e a quantidade de símbolos existentes em cada estágio Para o fractal de oco de neve clássico de von Koch esses valores são apresentados na Tabela 2 mas não as equações de recorrência que levam a esses valores o que deve ser feito aqui Sugestão para os fractais das letras ii e iii acima para o caso da quantidade de símbolos tente fazer as equações de recorrência considerando tudo símbolos F X e Y e depois sem os símbolos F 4 Apresente a complexidade de seus algoritmos considerando a notação assintótica mais pre cisa possível 5 Investigue as opções de software preferencialmente grátis para desenhar os fractais gerados e discuta brevemente aqui Apresente uma gura com os primeiros quatro estágios de pelo menos o fractal que você propôs na letra iii acima Sugestão tente usar algum software para desenhar os fractais Entrada para o TP Será denida assim que o monitor da disciplina for alocado No entanto comece a fazer este trabalho imediatamente pois a solução não depende dessa entrada O formato da entrada será postado no Moodle da disciplina e avisado em sala de aula Saída do TP Idem MD o 20231 Trabalho Prático 10