Dada uma tabela de frequências (símbolo ? frequência) obtida por amostragem, elabore um algoritmo em…

Questão

Dada uma tabela de frequências (símbolo ? frequência) obtida por amostragem, elabore um algoritmo em pseudocódigo que construa a árvore de Huffman e gere os códigos binários para cada símbolo. Explique os passos e a complexidade temporal.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: 1. Para cada símbolo s com frequência f: criar nó(s,f) e inserir em fila de prioridade mínima (heap) por f. 2. Enquanto heap.size > 1: a = heap.pop(); b = heap.pop(); criar nó p com freq = a.freq+b.freq e filhos a,b; heap.push(p). 3. Raiz = heap.pop(). 4. Fazer travessia DFS da raiz, acumulando '0' à esquerda e '1' à direita para obter código de cada símbolo. Complexidade: construir heap inicial O(n); cada extração/insersão é O(log n) e ocorre O(n) vezes ? O(n log n).

Explicação

O algoritmo apresentado utiliza uma fila de prioridade para construir a árvore de Huffman, garantindo que os símbolos com menor frequência sejam combinados primeiro, o que é essencial para a eficiência da codificação. A complexidade temporal é bem justificada, pois a construção inicial do heap é linear, enquanto as operações de extração e inserção, que ocorrem durante a formação da árvore, são logarítmicas em relação ao número de símbolos. Assim, a análise da complexidade total resulta em O(n log n), refletindo o desempenho esperado do algoritmo.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que, a partir de uma amostra de dados numéricos (lista), construa uma tabela de…
• Escreva um algoritmo em pseudocódigo que, dado um vetor de respostas categóricas de uma pesquisa amostral, construa uma…
• Descreva um algoritmo em pseudocódigo que, dada uma lista de valores numéricos de uma amostra, construa a tabela de…
• Proponha um pseudocódigo que, dado um vetor de números inteiros obtido de uma amostra, construa uma tabela de…
• Você recebeu uma amostra de valores numéricos coletados por pesquisa (lista A). Elabore um algoritmo em pseudocódigo…
• Descreva, em pseudocódigo, um algoritmo que receba uma amostra de idades de estudantes, construa uma tabela de…

Todas as questões de Leitura e interpretação de tabelas e gráficos (de colunas ou barras simples ou múltiplas) referentes a variáveis categóricas e variáveis numéricas