53
edits
Changes
→Computações e Explorações
== Computações e Explorações ==
1. Mostre todas as árvores com seis vértices. '''''Solução'''''
Para resolver esse problema nós usamos uma definição recursiva de árvores. Sabemos que um gráfo vazio é uma árvore, e que um grafo com apenas um vértice é uma árvore. Podemos então construir árvores mais largas a partir dessas árvores menores se pegarmos cada vértice e formarmos uma nova árvore adicionando uma folha conectada a esse vértice.
Então, nós devemos criar um procedure em Maple chamado ExtendTree, que pega um conjunto de árvores com n vértices e adiciona uma nova aresta a cada árvore, retornando o conjunto resultante de árvores com n+1 vértices. A implementação em Maple é a seguinte:
</pre>
2. Construa uma codificação de Huffman para as letras da língua inglesa baseada na frequência de sua ocorrência em textos comuns em inglês.
'''''Solução'''''
Esse problema pode ser quebrado em dois problemas menores. O primeiro problema é determinar como coletar a frequência de ocorrência para cada letra da língua inglesa. O segundo é como construir uma codificação de Huffman baseado nessa frequência de ocorrencia.
Para determinar a frequência de ocorrência das letras inglesas em certos contextos, nós podemos rodar esse programa em largas amostras de inputs. Podemos simplesmente extender nosso alfabeto e incluir pontuação e qualquer outro carácter especial que seja usado no conjunto dos caracteres. Vocè irá encontrar uma distribuição um pouco diferente para tipos diferentes de conteúdo, como literatura, correspondencia, programas de computador, e-mail etc. Vale notar que muitos livros sobre Criptografia contêm frequências de caracteres em inglês e muitas outras linguagens. Além disso, esse código pode ser usado para contar a frequência de ocorrência de qualquer conjunto de caracteres, como ASCII, francês, espanhol etc.
3. Compute o número de diferentes árvores de extensão de K_n para n = 1, 2, 3, 4, 5, 6. Conjecture uma fórmula para o número de tais árvores de extensão sempre que n for um inteiro positivo. '''''Solução'''''
Esse problema pode ser resolvido facilmente usando o comando counttrees do Maple, que retorna o número de árvores de extensão únicas de um grafo não-dirigido. Então, para determinar o número de árvores de extensão únicas em K_n, n = 1..6, podemos executar as seguintes declarações em Maple.
Deixamos para o leitor a conjectura da forma. Uma dica útil é para procurar por uma fórmula de forma n^{f(n)}, onde f(n) é uma simples função em termos de n.
4. Compute the number of different ways n queens can be arranged on an n \times n chessboard so that no two queens can attack each other for all positive integers n not exceeding 10. '''''Solução'''''
Esse problema pode ser resolvido alterando o procedure NQueens que foi implementado nesse capítulo. Especificamente, quando uma solução é determinada, ao invés de sair do procedura, nós simplesmentes fazemos backtrack nessa solução e continuamos, até todos os caminhos possíveis terem sido examinados. Assim, o procedura vai sair apenas quando todas as soluções tiverem sido testadas. Deixamos para o leitor alterar o procedure NQueens e conjecturar a fórmula para o número de soluções em termos de n para o problema das n-rainhas.
5. Desenhe a árvore de jogo completa para damas em um tabuleiro 4x4. '''''Solução'''''
Iremos oferecer uma solução parcial para esse problema; o leitor deve completar a solução. Especificamente, iremos criar um procedure em Maple chamado MovePiece que irá determinar todas as possíveis combinações de movimento dada uma peça específica que deve ser movida para algum espaço. Quando esse procedure for criado, o leitor deve determinar como representar essas posições no tabuleiro como vértices e arestas, como determinar o próximo nível da árvore jogo e se é necessária alguma condição de parada.