53
edits
Changes
Jump to navigation
Jump to search
no edit summary
</pre>
Se você preferir, pode substituir o teste cycle base test nesse procedure por um que verifica se o número de arestas é um a menos que o número de vértices.
Agora estamos prontos para usar o procedure IsTree para determinar se alguns grafos são árvores;
</pre>
Agora apresentaremos um procedure que encontra todos os descendentes, ancestrais e irmãos de um vértice particular em uma árvore com raiz. Esse procedure, chamado Family, pode ser descrito usando o seguinte pseudo-códigopseudocódigo:
1. Para encontrar todos os ancestrais, usamos o comando ancestor do Maple até que não hajam mais ancestrais (ex: quando atingimos o vértice raiz).
=== Codificação de Huffman ===
A codificação de Huffman é um método para construir um código prefixo eficiente para um conjunto de caractéres. Ele é baseado num Nesse algoritmo ganancioso, onde em cada passo os vértices com menos peso são examinados. A codificação de Huffman pode produzir códigos de prefixo em condições óptimasideais. O seguinte pseudo-código pseudocódigo descreve um algoritmo para codificação de Huffman. (Para uma discussão mais completa sobre a codificação de Huffman, veja Cormen, Leiserson, e Rivest, Introduction to Algorithms, MIT Press, 1989.)
Comece criando uma lista ordenada de elementos a serem codificados, onde a ordenação é com respeito a frequência de ocorrência desses elementos. Considere cada elemento da lista como um vértice com peso igual a sua frequência de ocorrência.
Os pesos adicionados aos vértices aqui representam o número que desse vértice em termos de seu pai. Por exemplo, d é o terceiro filho de a. Como nas seções anteriores, tais pesos poderiam ser usados para ordenação, apesar de que em fato, a ordenação por baixo é simplesmente alfabético nos nomes dos vértices.
Primeiro implementamos o algaritmo de percurso em pré-ordem. Esse visita a raiz e então cada sub-árvore da esquerda a direita em uma maneira de percurso em pré-ordem. Em forma de pseudo-códigopseudocódigo, o algoritmo para pré-ordem é:
1. Visite a raiz de T. Ponha o atua vértice para ser a raiz.
2. Considere os filhos do vértice atual como raízes das árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita. Repita o passo (1) em cada sub-árvore em ordem.
Como pode ser visto no passo (2) do pseudo-código pseudocódigo acima, esse algoritmo é recursivo. Nós providenciamos a seguinte implementação em Maple:
<pre>
</pre>
Nós implementamos o percurso em ordem de maneira similar. Simplesmente alteramos a sequência na qual os vértices são visitados. Especificamente, olhamos na sub-árvore mais a esquerda dos vértices, seguida pela raiz, seguida pela sub-árvore mais a direita dos vértices. Em pseudo-códigopseudocódigo, temos:
1. Se a árvore T tem apenas um vértice, r então visite r
</pre>
O percurso final que devemos implementar é em pós-ordem. Percurso em pós-ordem é similar ao percurso em pré-ordem, exceto que visitamos a raiz após visitar cada sub-árvore. Segue o pseudo-códigopseudocódigo:
1. Considere os filhos da raiz as sub-árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita.
O resultado é uma lista aninhada de listas, com cada lista representando uma operação binária.
Agora estamos prontos para construir uma árvore binária representando tal expressão. O algoritmo necessário em pseudo-código pseudocódigo é:
1. Se houver uma expressão algébrica isolada (como um nome ou número), a árvore consiste de um vértice isolado.
A raiz da árvore é manipulada de maneira especial. Recomputando a raiz da árvore é estranho e caro, então nós simplesmente pedimos a cada árvore que se lembre sua própria raiz. Isso feito por declarações de tarefa como T(Root) := LocL;.
O procedure Unique é novamente usado para se assegurar que cada instancia de vértice tem nome único, mesmo que pareça igual a outro. Em todos os outros aspectos, a implementação é quase exatamente como descrito no pseudo-códigopseudocódigo.
Para testar esse procedure, use-o para construir uma expressão árvore para a expressão anterior Expr1.
=== Bubble Sort ===
Para começar, nós iremos examinar a implementação do bubble sort. A razão pelo qual o bubble sort foi dado o nome "bubble" (bolha) é que o menor da lista "borbulha" em direção a frente da lista, se movendo um passo mais próximo a sua posições após cada iteração. O pseudo-códigopseudocódigo, que é destacado na página 575 do texto, é como o seguinte:
1. Recebe como entrada uma lista, L, de n elementos.
=== Merge Sort ===
Nós iremos agora implementar o merge sort em Maple. Nós também iremos usar Maple para estudar a complexidade desse algoritmo. O algoritmo de merge sort pode ser implementado como um procedure recursivo. A idéia básica da tarefa de aplicar merge sort numa é de dividir a lista em duas de tamanhos iguais ou quase iguais, ordenando cada sub-lista usando o algoritmo merge sort, e no final juntando as listas resultantes. Isso pode ser descrito no seguinte pseudo-códigopseudocódigo:
1. Dada uma lista de elementos, se o tamanho da lista é 1, retorne essa lista.
</pre>
Agora nós damos o pseudo-código pseudocódigo para o algoritmo merge sort:
A descrição do algoritmo merge sort que nós iremos usar é baseada na definição recursiva. Em pseudocódigo:
Essa seção explica como usar o Maple para construir árvores de extensão (spanning trees) para grafos e como usar árvores de extensão para resolver muitos tipos diferentes de problema. Árvores de extensão já foram usadas no capítulo 7; elas tem uma grande quantidade de aplicações. Em particular, nós iremos mostrar como usar o Maple para formar as árvores de extensão usando dois algoritmos: depth-first search e breadth-first search. Então nós iremos mostrar como usar o Maple para fazer backtracking, uma ténica baseada em depth-first search usada para resolver vários problemas.
Para começar, nós iremos discutir como implementar o algoritmo de depth-first search no Maple. Como o nome do algoritmo (busca em profundidade, em português) sugere, os vértices são visitados em ordem de crescimento de profundidade da árvore de extensão. O pseudo-código pseudocódigo é:
1. Dado um grafo G, e uma raiz vértice v, considere o primeiro vizinho de v, chamado w. Adicione aresta(v, w) a árvore de extensão.
</pre>
Tendo implementado o algoritmo de árvore de extensão de depth-first search, agora nós podemos modificar levemente o código Maple e conseguir uma árvore de extensão com breadth-first search. Especificamente, o algoritmo de breadth-first search opera examinando todos os vértices da atual profundidade do grafo antes de se mover para baixo, no próximo nível do grafo. Antes de implementar esse algoritmo, nós damos uma descrição em pseudo-código pseudocódigo do algoritmo.
1. Dado um grafo G, e uma raiz vértice v, identifique os vizinhos de v. Chame esse vizinho de conjunto N_1.
Backtracking é um método que pode ser usado para achar soluções para problemas que poderiam ser impráticos de se resolver usando técnicas de busca excessiva, O backtracking é baseado na busca sistemática pela solução de um problema usando uma árvore de decisão. Aqui nós mostramos comos usar backtracking para reslver vários problemas diferentes, incluindo pintar um grafo, resolver o problema das n-rainhas de posicionar n rainhas em um tabuleiro de xadrez nXn de maneira que uma rainha não possa atacar a outra, e também o problema do subconjunto da soma, que consiste em encontrar um subconjunto de um conjunto de inteiros cuja soma é dado inteiro.
O primeiro problemas nós iremos atacar através de um procedure de backtracking é o de colorir um grafo usando n cores, onde n é um inteiro positivo. Dado um grafo, nós tentaremos colorir ele usando n cores de uma maneira gananciosa. No entanto, quando nós atingimos uma coloração que não nos permite colorir um vértice adicional propriamente, nós usamos backtrack, mudando a cor de um vértice anteriormente colorido e tentando novamente. Aqui está o pseudo-código pseudocódigo para nosso procedure BackColor que executa essa coloração baseado em backtracking. Aqui nós ordenamos as cores como color1, color2, ..., colorn:
1. Ordene os vértices do grafo G como v_1, v_2, ..., v_m.
7. Para quando tivermos colorido todos os vértices, ou usado todas as colorações possíveis.
Uma implementação desse pseudo-código pseudocódigo no seguinte algoritmo Maple, chamado BackColor:
<pre>
