53
edits
Changes
→Computações e Explorações
== Computações e Explorações ==
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>
ExtendTree:=proc(Trees::set)
local i, j, S, t, num_vertices, X;
S:={};
</pre>
Entra num laço sobre todas as árvores em dado conjunto
<pre>
for i to nops(Trees) do
T := Trees[i];
</pre>
Adiciona novo vértice
<pre>
num_vertices:=nops(vertices(T));
addvertex(num_vertices+1, T);
</pre>
Para cada vértice, adicione uma nova aresta folha.
<pre>
for v in vertices(T) do
new(X[i][v]);
X[i][v]:=duplicate(T);
addedge([v , num_vertices+1], X[i][v]);
S:=S union X[i][v];
od;
od;
S;
end:
</pre>
Iremos agora ilustrar como formar todas as árvores com 4 vértices, e deixar a determinação de todas as árvores de tamanho mais largo serem determinadas pelo leitor:
<pre>
new(StartingTree):
addvertex(1, StartingTree):
X:=ExtendTree(ExtendTree(ExtendTree(StartingTree))):
draw(Tree(1),X[1]);
draw(Tree(1), X[2]):
draw(Tree(1),X[3]):
draw(Tree(1), X[4]):
draw(Tree(1),X[5]):
draw(Tree(1), X[6]):
</pre>
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.
Nós já criamos o procedure de Huffman em Maple que pode ser usado para determinar a codificação de Huffman correta dada a frequência de ocorrencia de caractéres em inglês. Consequentemente, nós resolvemos o segundo problema.
Para resolver o primeiro problema, nós podemos usar o Maple para analisar uma string de texto e conta o número de ocorrencia de cada letra do alfabeto inglês. Especificamente, podemos usar strings em Maple da seguinte maneira. Suponha que nós temos uma passagem de texto que está em minúsculo e não tem pontuação. como:
<pre>
input_text:=
`the quick brown fox sat down and had lunch with me`;
</pre>
Então, podemos inicializar a tabela indexada com cada carácter da língua inglesa, e então analisar input_text e contar as ocorrências de cada carácter.
Inicialização
<pre>
alphabet:=`a bcdefghijklmnopqrstuvwxyz`;
for i from 1 to length(alphabet) do
freq[substring(alphabet, i..i)]:=0;
od:
</pre>
Conta a ocorrência de cada carácter
<pre>
for i from 1 to length(input_text) do
freq[substring(input_text, i..i)] :=
freq[substring(input_text, i..i)] + 1;
od:
freq[a];
freq[e];
freq[q];
</pre>
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.
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.
<pre>
counttrees(complete(1));
counttrees(complete(2));
counttrees(complete(3));
counttrees(complete(4));
counttrees(complete(5));
counttrees(complete(6));
</pre>
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.
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.
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.
A implementação de MovePiece é bastante direta: examinamos cada peça que pode ser movida, e então determinamos se podemos mover a peça para frente e para esquerda ou direita, dependendo da posição atual da peça no tabuleiro e se há uma peça ocupando a possivelmente nova posição. Além disso, nós vamos determinar se uma peça pode pular e capturar uma peça de um oponente, dependendo do espaço do tabuleiro e a posição do oponente. Adicionalmente, nós vamos examinar ser a peça é rei, nesse caso, a peça pode mover tanto para frente como para trás no tabuleiro.
Agora damos uma implementação em Maple de MovePIece. Comentários em linha são dados para facilitar o entendimento do código.
<pre>
MovePiece:=proc(A::matrix, piece::integer)
local i, j, k, cur_column, is_king, S, Temp, direction;
</pre>
Inicialize os valores, dependendo do valor da peça
<pre>
S:=[];
if piece = 1 then direction:=-1;
else direction:=1; fi;
</pre>
Examine todas as posições possíveis no tabuleiro
<pre>
for i from 1 to 4 do
for j from 1 to 4 do
</pre>
Se tivermos achado um peça, determine se é ou não o rei.
<pre>
if abs(A[i,j])=piece then
if A[i,j] < 0 then is_king:=1;
else is_king:=0; fi;
</pre>
Se a peça é um rei, então examine as direções pra frente e pra trás
<pre>
for k from 0 to is_king do
if k>0 then direction:=-1*direction; fi;
</pre>
Examine possíveis novas posições para ver se elas ainda estão no tabuleiro
<pre>
if i+direction >= 1 and i+direction <= 4 then
for cur_column from -1 to 1 by 2 do
if j-cur_column >=1 and j-cur_column<=4 then
</pre>
Determine se a posição está livre
<pre>
if A[i+direction, j-cur_column] = 0 then
</pre>
Mova uma única posição
<pre>
Temp:=copy(A);
Temp[i,j]:=0;
Temp[i+direction, j-cur_column]:=piece;
S:=[op(S), copy(Temp)];
elif abs(abs(A[i+direction,j-cur_column])
-piece)=1 then
</pre>
Nós podemos ser capazes de pular uma peça
<pre>
if (i+2*direction >=1 and
i+2*direction<=4) and
(j-2*cur_column >=1 and
j-2*cur_column<=4) then
</pre>
Pule uma peça
<pre>
if A[i+2*direction, j-2*cur_column]
= 0 then
Temp:=copy(A);
Temp[i,j]:=0;
Temp[i+direction, j-cur_column]:=0;
Temp[i+2*direction, j-2*cur_column]
:=piece;
S:=[op(S), copy(Temp)];
fi;
fi;
fi;
fi;
od;
fi;
od;
if is_king=1 then direction:=-1*direction; fi;
fi;
od;
od;
</pre>
Procura por reis
<pre>
for i from 1 to nops(S) do
for j from 1 to 4 do
if S[i][1,j] = 1 then S[i][1,j]:=-1 fi;
if S[i][4,j] = 2 then S[i][4,j]:=-2 fi;
od;
od;
</pre>
Retorna lista de novas combinações do tabuleiro
<pre>
S;
end:
</pre>
Para examinar esse procedure, nós vamos criar uma combinação inicial no tabuleiro, chamada A, usando a função matriz do Maple.
<pre>
A:=linalg[matrix](4, 4,
[[2,0,2,0],[0,0,0,0],[0,0,0,0],[0,1,0,1]]);
</pre>