Trabalho Prático - Matemática Discreta - 2023-1

Trabalho Prático UFMG/ICEx/DCC 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 23:59 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 leiame.txt, 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 2023/1 Trabalho Prático 1 Fractais O que são fractais? Um fractal é uma forma ou padrão geométrico que exibe auto-semelhanç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 L-sistemas (Sistema de Lindenmayer)2 ou sistemas de reescrita de cadeias (fractais determinísticos) e fractais de movimento brownianos (fractais aleatórios). Os L-sistemas são um tipo especial de gramática de reescrita de strings. Esses sistemas reescrevem uma determinada cadeia de caracteres, i.e., 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 https://pt.wikipedia.org/wiki/Conjunto_de_Mandelbrot para mais informações 2Veja em https://en.wikipedia.org/wiki/L-system e em https://wwwuser.gwdg.de/~groimp/grogra. de/grammars/lsystems.html para mais informações MD o 2023/1 Trabalho Prático 2 Exemplo de um desenho O fractal de oco de neve clássico de von Koch pode ser denido pelo seguinte L-sistema (axioma, valor de θ, regras de produção e estágiosneste caso, o valor será fornecido como uma entrada): Axioma: F θ = π 3 Regra: F → F-F++F-F 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 F-F++F-F 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 1(a) 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 F-F++F-F, como ilustrado na Figura 1(b). Os outros estágios aplicam a mesma regra: toda ocorrência de F deve ser substituída por F-F++F-F. 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 F-F++F-F, é desenhado da seguinte forma: (a) Inicialmente, a caneta se encontra sobre uma linha horizontal e está direcionada para a direita, como mencionado anteriormente. (b) F-F++F-F O primeiro símbolo é F e um segmento é desenhado nessa direção. (c) F-F++F-F O próximo símbolo (2o) é - e a caneta é girada de 60◦ para a esquerda. MD o 2023/1 Trabalho Prático 3 (d) F-F++F-F O próximo símbolo (3o) é F e um segmento é desenhado nessa direção. (e) F-F++F-F Os próximos dois símbolos (4o e 5o) são + e a caneta é girada de 120◦ (2 × 60◦) para a direita. (f) F-F++F-F O próximo símbolo (6o) é F e um segmento é desenhado nessa direção. (g) F-F++F-F O próximo símbolo (7o) é - e a caneta é girada de 60◦ para a esquerda. (h) F-F++F-F 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 F-F++F-F 2 F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F 3 F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++ F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F -F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F 4 F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++ F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F -F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F+ +F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F+ +F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F ++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F- F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F- F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F -F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F- F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F -F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F -F++F-F-F-F++F-F++F-F++F-F-F-F++F-F Tabela 1: Sequência de caracteres (string) dos primeiros estágios do fractal de oco de neve clássico de von Koch MD o 2023/1 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 L-sistema. 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 → F-F++F-F 2. Floco de neve onda quadrada de von Koch Veja Figura 3. Axioma: F θ = π 2 Regra: F → F-F+F+FF-F-F+F MD o 2023/1 Trabalho Prático 5 3. Floco de neve onda senoidal 1 de von Koch Veja Figura 4. Axioma: F θ = π 3 Regra: F → F++FF--F+F 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 → F-F+F+FF-F-F+F 5. Ilha de Koch Veja Figura 6. Axioma: F+F+F+F θ = π 2 Regra: F → F+F-F-FFF+F+F-F MD o 2023/1 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 → -YF+XFX+FY- Y → +XF-YFY-FX+ 7. Preenchimento de espaço de Peano Veja Figura 8. Axioma: X θ = π 2 Regras: X → XFYFX+F+YFXFY-F-XFYFX Y → YFXFY-F-XFYFX+F+YFXFY 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 2023/1 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 XFYFX+F+YFXFY-F-XFYFX 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 XFYFX+F+YFXFY-F-XFYFX: 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 FF+F+FF-F-FF : sequência sem os espaços em branco (não devem aparecer) Observe que a sequência resultante (FF+F+FF-F-FF) 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 2023/1 Trabalho Prático 8 Posicao inicial ,.. F EF + da “caneta” EF EF EF - + F F F 1 Posicao final ~ ~ da “caneta” Figura 9: Primeiro estagio do fractal espago de Peano com os simbolos associados, sendo que § = 90° O que deve ser feito? Este TP é constitufdo de cinco partes, como descrito abaixo. Leia com atencgao o que deve ser feito. 1. Fazer trés programas, um para cada fractal como indicado a seguir: (i) Um fractal dentre os seguintes: e Floco de neve onda quadrada de von Koch (5 algs. n° matricula mod 4 = 0) e Floco de neve onda senoidal 1 de von Koch (-algs. n° matricula mod 4 = 1) e Floco de neve onda senoidal 2 de von Koch (}¢ algs. n2 matricula mod 4 = 2) e Ilha de Koch (> algs. n° matricula mod 4 = 3) Para definir o fractal que vocé deve implementar, pegue 0 seu nimero de matricula (10 digitos), some esses algarismos e calcule o resto da diviséo inteira por 4. O resto sera 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 matricula 2022012345, a soma dos algarismos vale 21 e o resto da divisao 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: e Preenchimento de espaco de Hilbert (n° de matricula par) e Preenchimento de espaco de Peano (n° de matricula impar) Para o exemplo de n° de matricula anterior, o fractal a ser implementado é o preen- chimento de espago de Peano (n° de matricula impar). (iii) Um fractal definido por vocé que gere uma cadeia de poligonos simples que tenha pelo menos duas regras como as curvas de preenchimento de espacgo de Peano e Hilbert. 2. Claramente ha pelo menos duas estratégias para implementar esses fractais: (a) Uma versao iterativa onde os caracteres de um estagio intermedidrio so gravados em um arquivo, lidos e processados para gerar um outro arquivo para 0 proximo estagio, até se chegar ao estagio desejado. (b) Uma versao recursiva que gera os caracteres do estagio desejado. Discuta essas duas estratégias e outras que vocé considerou, analisando pontos positivos e negativos de cada uma. MD *¢ 2023/1 TRABALHO PRATICO 9 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 2023/1 Trabalho Prático 10 Entradas e sa´ıdas para o Trabalho Pr´atico Aline Reis Abril 2023 As entradas para o trabalho pr´atico para cada fractal est˜ao definidas abaixo: linha 1: N´umero do fractal correspondente. linha 2: Axioma linha 3: ˆAngulo dado em graus. linha 4: Regra. 1 Floco de neve onda quadrada de von Koch linha 1: 2 linha 2: F linha 3: 90 linha 4: F-F+F+FF-F-F+F 2 Floco de neve onda senoidal 1 de von Koch linha 1: 3 linha 2: F linha 3: 60 linha 4: F-F++FF–F+F 3 Floco de neve onda senoidal 2 de von Koch linha 1: 4 linha 2: F linha 3: 60 linha 4: F-F+F+FF-F-F+F 4 Ilha de Koch linha 1: 5 linha 2: F+F+F+F linha 3: 90 linha 4: F+F-F-FFF+F+F-F 1 5 Preenchimento de espa¸co de Hilbert linha 1: 6 linha 2:X linha 3: 90 linha 4: X → −Y F + XFX + FY − Y → +XF − Y FY − FX+ 6 Preenchimento de espa¸co de Peano linha 1: 7 linha 2: X linha 3: 90 linha 2: X → XFY FX + F + Y FXFY F − F − XFY FX Y → Y FXFY − F − XFY FX + F + Y FXFY Lembrando que as entradas devem ser lidas via teclado. 7 Sa´ıdas As sa´ıdas devem consistir dos est´agios e da sequencias de caracteres de cada est´agio em um arquivo, e as imagens somente do fractal do item (iii) em cada estagio. Ou seja para cada est´agio, ´e necess´ario gerar uma imagem do fractal do item (iii). 2 Documentação de Projeto Problema do Caracol Noroeste Ester Sara Assis Silva Introdução: O Problema do Caracol Nordeste, exposto e exemplificado no arquivo de instruções do trabalho, pode ser resolvido por diferentes estratégias com diferentes custos computacionais. Para esse projeto, foi escolhido implementar um programa com custo , obtendo fórmulas para as coordenadas x e y de Θ(1) acordo com alguns critérios analisados de n. Fases do Projeto e Implementação: Segmentação da Análise: A primeira fase do projeto se baseia em segmentar espaços de análise de acordo com o problema, baseando-se em estruturas comuns. Analisando a tabela dada, uma segmentação clara que pode ser feita é a análise separada das coordenadas x e y, justamente para localização de cada uma por uma fórmula separada. Depois, outra segmentação que pode ser feita está indicada abaixo: Essa ilustração define os pontos dos conjuntos {4, 8, 12, …}, {2, 6, 10, …}, {3, 7, 11, …} e {1, 5, 9, …} em análises separadas, baseando-se no fato que um ponto desse conjunto sempre tem propriedades semelhantes aos pontos do mesmo conjunto. Ex.: Todos os pontos do conjunto identificado pelo número 3, por estarem em cima do eixo y, possuem coordenada x = 0. Busca de padrões nos números dos conjuntos: Tendo as segmentações definidas, a segunda fase consistiu na análise das sequências definidas no primeiro passo. a) Para o conjunto 1: Além de serem pares, percebe-se que todos os seus elementos são múltiplos de 4. b) Para o conjunto 2: Englobam os números pares, exceto aqueles que são múltiplos de 4. c) Para o conjunto 3: Englobam números ímpares, sendo que a soma desses ao número 1 gera pares múltiplos de 4. d) Para o conjunto 4: Além de ímpares, percebe-se que a soma de seus números ao número 1 gera pares não múltiplos de 4. Com isso, obtemos a estrutura inicial do programa, transformando cada um dos conjuntos em condicionais, de forma a encaixar o número n em um deles. Busca de padrões para as coordenadas do conjunto 1: Analisando o gráfico, percebemos que para esse conjunto, a coordenada x será sempre metade do número que representa o ponto e a coordenada y será sempre 0, uma vez que todos esses pontos estarão em cima do eixo x. Então podemos definir no código que: Busca de padrões para as coordenadas do conjunto 2: Para o conjunto 2, a relação da coordenada y se mantém, ou seja, uma vez que os pontos estão sempre no eixo x, y sempre é 0. Para a relação x, menos explícita que as demais, devemos implementar a fórmula . No − 2 − 2 · 𝑛 − 2 4 código, teremos: Busca de padrões para as coordenadas do conjunto 3: Para o conjunto 3, a relação da coordenada x, seguimos a mesma lógica usada para delimitar as coordenadas de y nos exemplos anteriores, ou seja, uma vez que os pontos estão sempre no eixo y, x sempre é 0. Para a relação y, devemos implementar a fórmula . No código, teremos: − 2 − 2 · (𝑛+1) − 2 4 Busca de padrões para as coordenadas do conjunto 4: Para o conjunto 4, analisando a marcação do gŕafico, temos que a coordenada x é sempre -1. Para a relação y, devemos implementar a fórmula . A implementação da última parte do código 𝑛 · 𝑛−1 2 é: Discussão e conclusão: A solução implementada, apesar de possuir baixo custo assintótico, com , exige do Θ(1) programador deduzir fórmulas e analisar uma alta quantidade de dados para se certificar de que a sequência selecionada é válida para o restante do problema. Com isso, temos um gasto manual de tempo e a necessidade da habilidade de gerar fórmulas a partir de sequências. Considerando essas observações, pensando em grandes projetos de estrutura de dados, onde as segmentações de análises podem atingir números muito altos, ou aqueles que envolvem números maiores e fórmulas complexas, a solução demonstrada, apesar de possuir baixo custo computacional, exigiria alto custo manual, deixando de ser bem aproveitada.