Algoritmos Gulosos (Códigos de Huffman)
Vou postar aqui algumas soluções do capitulo 16 do livro “Algoritmos - Teoria e Prática” do Thomas H. Cormem. Acabei de fazer uma prova de Analise de AlgorÃtmos na faculdade, e na preparação para a prova resolvi estes exercÃcios. Portanto, vou ajudar aqueles que irão precisar destes no futuro.
Questão 16.3-2 - Enunciado: O que é um código de Huffman ótimo para o conjunto de freqüências a seguir, baseado nos primeiros 8 números de Fibonacci?
a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21
Você pode generalizar sua resposta para encontrar o código ótimo quando as freqüências forem os n primeiros números de Fibonacci?
RESPOSTA: Seguindo o Algoritmo de Huffman, chega-se à construção da seguinte árvore:
Percorrendo essa árvore a partir da raiz é possÃvel saber qual o código binário ótimo para cada letra, de acordo com sua freqüência:
h - 0
g - 10
f - 110
e - 1110
d - 11110
c - 111110
b - 1111110
a - 1111111
0 - caminho esquerdo da árvore (nesta implementação)
1 - caminho direito da árvore (nesta implementação)
Algoritmo de Huffman
Huffman(C)
1 n := |C|
2 Q := C
3 for i:=1 to n-1 do
4 alocar um nó z
5 esquerda[z] := x := EXTRACT-MIN(Q)
6 direita[z] := y := EXTRACT-MIN(Q)
7 f[z] := f[x] + f[y]
8 INSERT(Q,z)
9 return EXTrACT-MIN(Q) // Retornar a raiz da árvore.Artigos relacionados:
Comentários
Leave a Reply
- Celular / PDAs
- Certificações
- Cinema
- Curiosidades
- Games
- Google Word
- Humor
- i-doser
- Informática
- Mundo
- Mundo Gospel
- MySpace
- Pensamentos
- projetos
- Saúde
- Séries
- Skype
- Viagens
Podcast Feeds
