Nota 10 - Semana 5_ Projeto e análise de algoritmos

Prévia do material em texto

Semana 5 - Atividade Avaliativa 
 
PERGUNTA 1 
1. A codificação de Huffman é um método eficiente de compressão de dados que utiliza 
uma tabela de frequência para construir uma árvore binária, atribuindo códigos 
binários a caracteres com base em suas frequências. A construção da tabela de 
frequência, a construção da árvore utilizando uma fila de prioridade, e a geração dos 
códigos binários são etapas essenciais do processo. A complexidade computacional 
da construção da árvore de Huffman é O(n log n), em que n é o número de 
caracteres únicos, o que torna o algoritmo eficiente para compressão rápida e eficaz. 
Analise o processo de construção da árvore de Huffman para os caracteres e 
frequências fornecidos: 
 A: 7 
 B: 3 
 C: 2 
 D: 6 
 E: 8 
 F: 1 
Agora, assinale a alternativa que apresenta a descrição correta em relação à 
frequência dos caracteres: 
 
a. A primeira combinação envolve C e F, formando um nó com frequência 3. A 
combinação seguinte junta este nó com D, resultando em um nó com 
frequência 9. O nó com frequência 9 é combinado com E, formando um nó 
com frequência 17. A árvore de Huffman é finalizada combinando todos os 
nós até restar apenas a raiz com a frequência total de 27. 
 
b. A primeira combinação envolve B e D, formando um nó com frequência 9. A 
seguinte junta este nó com E, resultando em um nó com frequência 17. O nó 
com frequência 17 é combinado com A, formando um nó com frequência 24. 
A árvore de Huffman é finalizada combinando todos os nós até restar a raiz 
com a frequência total de 27. 
 
c. A primeira combinação envolve C e F, formando um nó com frequência 3. A 
combinação seguinte junta este nó com B, resultando em um nó com 
frequência 6. O nó com frequência 6 é combinado com D, formando um nó 
com frequência 12. A árvore de Huffman é finalizada combinando todos os 
nós até restar apenas a raiz com a frequência total de 27. 
 
d. A primeira combinação envolve A e B, formando um nó com frequência 10. A 
seguinte junta este nó com C, resultando em um nó com frequência 12. O nó 
com frequência 12 é combinado com D, formando um nó com frequência 18. 
A árvore de Huffman é finalizada combinando todos os nós até restar a raiz 
com a frequência total de 27. 
 
e. A primeira combinação envolve C e F, formando um nó com frequência 3. A 
combinação seguinte junta este nó com B, resultando em um nó com 
frequência 6. O nó com frequência 6 é combinado com A, formando um nó 
com frequência 13. A árvore de Huffman é finalizada combinando todos os 
nós até restar apenas a raiz com a frequência total de 27. 
 
PERGUNTA 2 
1. A codificação de Huffman é uma técnica de compressão de dados sem perdas 
desenvolvida, ela gera códigos binários baseados na frequência de ocorrência dos 
caracteres, garantindo que os caracteres mais frequentes tenham códigos menores 
e os menos frequentes, códigos maiores. Dessa forma, avalie o texto com os 
caracteres e frequências fornecidos, determinando a validade e a relação entre elas. 
 A: 5 
 B: 9 
 C: 12 
 D: 13 
 E: 16 
 F: 45 
Com relação a esse contexto e sobre o conteúdo estudado, avalie as asserções a 
seguir e a relação proposta entre elas: 
I. A construção da árvore de Huffman começa combinando os caracteres A e B, 
resultando em um nó com frequência 14. 
PORQUE 
II. O próximo passo é combinar o nó resultante de A e B com o caractere C, formando 
um nó com frequência 26. 
A respeito dessas asserções, assinale a alternativa correta: 
 
 
 
a. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa 
da I. 
 
b. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I. 
 
c. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
 
d. As asserções I e II são falsas. 
 
e. A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
 
PERGUNTA 3 
1. Leia o trecho a seguir: 
Os algoritmos podem resolver problemas das mais diversas situações, o exemplo a 
seguir trata da alocação de um recurso para atividades programadas com tempo de 
início e fim, por exemplo, um equipamento que precisará realizar tarefas entre um 
tempo início e final. Considerando que para ordenação foi usado o MergeSort, a 
complexidade associada à linha 2 é [Preencher 1] e já para a linha 4 é [Preencher 
2], e considerando a complexidade de todo algoritmo tem-se [Preencher 3]. 
 
Linha 
 
Pseudocódigo 
 
1 
2 
 
3 
 
SelecionaAtividades (S, s, f, n) 
 Ordene as tarefas em ordem crescente do tempo de término 
 {r1’,r2,’,...rj,’...,rn’} , tal que f1≤ f2≤ ....≤ fn-1≤ fn 
 A = { r1’ } 
4 
5 
6 
7 
8 
9 
 
 
 
 
 
 
 
 k=1 
 para i de 2 até n faça 
 se si ≥ fk então 
 A = A U { ri’ } 
 k=i 
 retorna A 
 
 
 
 
 
 
 
 
Neste contexto, identifique os termos 
de [preencher1] [preencher2] e [preencher3] que são substituídos por: 
 
a. 1 – O(n2); 2 – O(1); 3 – O(n2). 
 
b. 1 – O(n); 2 – O(n); 3 – O(n). 
 
c. 1 – O(n.log n); 2 – O(1); 3 – O(n.log n). 
 
d. 1 – O(n.log n); 2 – O(n); 3 – O(n.log n). 
 
e. 1 – O(n.log n); 2 – O(n); 3 – O(n2). 
 
PERGUNTA 4 
1. A estratégia gulosa é uma abordagem para resolver problemas complexos de forma 
eficiente. Ela envolve a tomada de decisões em etapas, escolhendo em cada passo a 
opção que parece ser a melhor no momento. Essa abordagem depende de critérios 
específicos para cada problema e visa garantir que escolhas locais ótimas 
contribuam para a solução global. 
Diante disso, assinale a alternativa que apresenta a sequência dos passos principais 
na aplicação da estratégia gulosa. 
 
a. Selecionar o melhor candidato, definir um conjunto de candidatos, repetir o 
processo até alcançar a solução completa e verificar a viabilidade. 
 
b. Definir um conjunto de candidatos, verificar a viabilidade, selecionar o melhor 
candidato e repetir o processo até alcançar a solução completa. 
 
c. Definir um conjunto de candidatos, selecionar o melhor candidato, verificar a 
viabilidade e repetir o processo até alcançar a solução completa. 
 
d. Repetir o processo até alcançar a solução completa, definir um conjunto de 
candidatos, selecionar o melhor candidato e verificar a viabilidade. 
 
e. Verificar a viabilidade, definir um conjunto de candidatos, selecionar o melhor 
candidato e repetir o processo até alcançar a solução completa. 
 
PERGUNTA 5 
1. Um algoritmo é um conjunto de instruções que resolvem algum problema e a sua 
construção pode envolver algumas estratégias de projeto de algoritmos. Em um 
caixa eletrônico, o problema é fornecer o menor número de cédulas dentre as 
disponíveis, por exemplo de R$50, R$20 e R$10 reais. Diante de um valor, por 
exemplo, para sacar 190 reais, o algoritmo primeiro realiza divisão de um valor pela 
cédula de R$50, depois com o resto da divisão por 50, ele faz a divisão por R$20 e ao 
final ele faz a divisão por R$10. Desta forma, ele obtem ao final 3 cédulas de R$50, 2 
cédulas de R$20 e 1 cédula de R$10. 
Com base na descrição do algoritmo utilizado para fornecer o menor número de 
cédulas em um caixa eletrônico, assinale a alternativa correta que identifica a técnica 
de projeto de algoritmos aplicada nessa estratégia. 
 
a. Algoritmos recursivos 
 
b. Invariante de laço 
 
c. Algoritmos gulosos 
 
d. Divisão e conquista 
 
e. Programação dinâmica 
 
PERGUNTA 6 
1. A estrutura do algoritmo de Dijkstra envolve três etapas principais: inicialização, 
exploração e repetição. Na inicialização, a distância do nó inicial é definida como 
zero, enquanto todas as outras distâncias são definidas como infinito. Durante a 
exploração, o nó com a menor distância conhecida é selecionado, as distâncias de 
seus vizinhos são atualizadas e o nó é marcado como visitado. Esse processo é 
repetido até que todos os nós sejam visitados. O algoritmo utiliza uma estrutura de 
dados para atualizar e armazenar as distâncias mínimas dos nós visitados, 
garantindo a eficiência do processo.Com base no apresentado, assinale a alternativa que explica como a estrutura de 
dados utilizada no algoritmo de Dijkstra contribui para a eficiência do processo de 
encontrar o caminho mais curto: 
 
a. A estrutura de dados facilita a resolução de subproblemas independentes, que 
são combinados para formar a solução global. 
 
b. A estrutura de dados permite que o algoritmo considere todas as 
combinações possíveis de caminhos, garantindo a solução ótima. 
 
c. A estrutura de dados permite priorizar e selecionar rapidamente o nó com a 
menor distância, garantindo a eficiência do processo. 
 
d. A estrutura de dados permite retroceder e corrigir escolhas anteriores, 
assegurando que os caminhos mais curtos sejam encontrados. 
 
e. A estrutura de dados possibilita a atualização e o armazenamento eficientes 
das distâncias mínimas, reduzindo o tempo de processamento. 
 
PERGUNTA 7 
1. O algoritmo de Dijkstra é uma ferramenta essencial na teoria dos grafos, utilizada 
para determinar o caminho mais curto entre dois nós. Desenvolvido por Edsger 
Dijkstra em 1956, ele se destaca por sua eficiência e ampla aplicabilidade. O 
algoritmo de Dijkstra é projetado para encontrar o caminho mais curto em um grafo 
com arestas de pesos não negativos. Utilizado em diversos campos, como redes de 
telecomunicações e sistemas de navegação, esse algoritmo é fundamental para a 
resolução de problemas de roteamento e planejamento de rotas. 
Diante disso, assinale a alternativa que explica o processo passo a passo de como as 
distâncias são atualizadas: 
 
a. O algoritmo de Dijkstra utiliza heurísticas para escolher os nós a serem 
visitados, priorizando aqueles que parecem mais promissores para encontrar 
o caminho mais curto de maneira mais rápida e eficiente. 
 
b. O algoritmo de Dijkstra utiliza uma estrutura de dados eficiente para 
armazenar distâncias mínimas e atualiza essas distâncias repetidamente. Ele 
escolhe sempre o nó com a menor distância conhecida até que todos sejam 
visitados, garantindo que o caminho mais curto seja encontrado de forma 
sistemática. 
 
c. O algoritmo de Dijkstra retrocede e corrige escolhas feitas anteriormente para 
garantir que o caminho mais curto seja encontrado, assegurando que todas 
as possibilidades sejam verificadas e que a solução seja otimizada, 
proporcionando flexibilidade no processo de escolha. 
 
d. O algoritmo de Dijkstra considera todas as combinações possíveis de 
caminhos antes de determinar o mais curto, garantindo a solução mais 
eficiente e precisa para o grafo, assegurando a escolha ótima ao analisar todas 
as opções. 
 
e. O algoritmo de Dijkstra resolve subproblemas independentes e depois 
combina suas soluções para encontrar o caminho mais curto, permitindo uma 
abordagem modular que facilita a resolução do problema de forma eficiente 
e dividida em partes menores e manejáveis. 
 
PERGUNTA 8 
1. O mundo atual hoje fortemente relacionado com o trato de grande volume de 
informações e dados, seja em um comércio eletrônico, nos aplicativos de mensagens 
ou em soluções especializadas. Na Indústria por exemplo, existem sistemas que 
captam informações de equipamentos a cada segundo ou fração e isso gera um 
volume bem grande de informações que podem requerer soluções, por exemplo, 
para compactação destes dados. Imagine que um equipamento pode estar em três 
estados, “N” de operação normal, “D” de desligado ou “M” em manutenção. Na 
solução cada estado deste está representado por um caractere. Uma uma análise 
dos dados em certo período, percebeu-se que o estado “N” aparece 10 mil vezes, o 
estado “D” duas mil vezes e o estado “M” mil vezes. 
Nesta situação, considerando uma compactação por código de Huffman, calcule e 
assinale qual a redução correta no tamanho dos dados. 
 
a. 62% 
 
b. 78% 
 
c. 45% 
 
d. 92% 
 
e. 85%