Computação8º anoBNCC EF08CO03Difícil⏱ longo

Projete um algoritmo em pseudocódigo que recebe um conjunto de símbolos com suas frequências (variável 'freq')…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF08CO03

Utilizar algoritmos clássicos de manipulação sobre listas.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Projete um algoritmo em pseudocódigo que recebe um conjunto de símbolos com suas frequências (variável 'freq') e gera uma codificação de prefixo mínima (variável 'codigo'), explicando como o algoritmo escolhe códigos mais curtos para símbolos mais frequentes.

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

Resposta esperada

Entrada: lista de pares (símbolo, freq). 1. Criar uma fila de prioridade Q onde each nó contém (símbolo ou subárvore, frequência); ordenar por frequência crescente. 2. Enquanto Q tiver mais de um nó: a) Remover os dois nós de menor frequência n1 e n2. b) Criar um novo nó pai p com frequência = n1.freq + n2.freq e filhos n1 (esquerdo) e n2 (direito). c) Inserir p em Q. 3. O nó restante em Q é a raiz da árvore de codificação. 4. Percorrer a árvore da raiz até as folhas: atribuir '0' para ramificação à esquerda e '1' para à direita; o código de cada símbolo é a sequência de bits do caminho raiz?folha. Justificação do método: ao combinar iterativamente os símbolos de menor frequência, o algoritmo minimiza a soma ponderada dos comprimentos dos códigos (custo esperado), atribuindo códigos mais curtos aos símbolos mais frequentes. Complexidade típica: O(n log n) devido às operações na fila de prioridade (n = número de símbolos). Este procedimento corresponde ao método padrão de construção de codificações prefixas ótimas (Huffman).

Explicação

O algoritmo apresentado utiliza a técnica de Huffman, que é eficaz para gerar codificações de prefixo mínimas ao priorizar a combinação de símbolos menos frequentes. Isso resulta em códigos mais curtos para símbolos com maior frequência, minimizando a soma ponderada dos comprimentos dos códigos. A complexidade O(n log n) reflete a eficiência do método ao lidar com a fila de prioridade durante a construção da árvore de codificação.

Raio-X da questão

Dificuldade Difícil

Bloom Analisar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

codificação de prefixo

📌 Objetivo

avaliacao

🧱 Pré-requisitos

codificação de prefixo · algoritmos e pseudocódigo

📚 Reveja

Revisar algoritmos de codificação e suas aplicações em compressão de dados.

⚠️ Erro mais comum

O aluno pode confundir a lógica de codificação de prefixo com outros métodos de compressão, não priorizando a frequência dos símbolos.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

abstrato

Questões parecidas com resolução

Todas as questões de Programação - Algoritmos clássicos

🔎 Procurar outra questão

Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.

Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog