A2 Estrutura de Dados

Prévia do material em texto

Atividade 2
Entrega 22 de out de 2023 em 23:59 Pontos 1 Perguntas 5
Disponível 14 de ago de 2023 em 0:00 - 22 de out de 2023 em 23:59
Limite de tempo Nenhum Tentativas permitidas 2
Instruções
Este teste não está mais disponível, pois o curso foi concluído.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 18 minutos 0,8 de 1
Pontuação desta tentativa: 0,8 de 1
Enviado 12 de out de 2023 em 10:27
Esta tentativa levou 18 minutos.
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
0,2 / 0,2 ptsPergunta 1
Leia o texto a seguir:
O que é uma Tabela Hash?
Uma tabela hash, tabela de dispersão ou ainda tabela de
espalhamento, é uma estrutura de dados utilizada para tornar o
processo de busca mais eficiente. Assim, esta estrutura de dados é
muito utilizada não para inserções ou remoções, mas quando há a
necessidade de realizar muitas buscas e com rápido tempo de
resposta.
A+
A
A-
https://famonline.instructure.com/courses/31357/quizzes/158714/history?version=1
Imagine um vetor, estrutura de dados homogênea [...]. Para descobrir
se um dado elemento está ou não no vetor precisamos percorrer todo
o vetor procurando pelo elemento. Isso pode ser muito demorado
dependendo da quantidade de buscas necessárias e principalmente do
tamanho do vetor.
Em uma tabela hash é possível acessar diretamente a posição da
tabela onde o elemento deve estar caso ele exista, tornando o
processo de busca muito mais eficiente.
Como implementar uma tabela hash?
Uma tabela hash pode ser implementada de diferentes formas [...]
usando vetor e lista encadeada.
Fonte: GASPAR, W. O que é e como funciona a estrutura de dados
Tabela Hash? Wagner Gaspar, 30 ago. 2021. Disponível em:
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-
de-dados-tabela-hash/ (https://wagnergaspar.com/o-que-e-e-como-
funciona-a-estrutura-de-dados-tabela-hash/) . Acesso em: 27 set. 2022.
Hashing é uma técnica ou processo de mapeamento de chaves e
valores na tabela de hash usando uma função de hash. Isso é feito
para acesso mais rápido aos elementos. A eficiência do mapeamento
depende da eficiência
 da implementação de objeto. 
 das colisões. 
 dos pares de valores-chave. 
 dos bancos de dados. 
 da função hash usada. Correto!Correto!
A alternativa está correta, pois a eficiência do mapeamento 
depende da eficiência da função hash usada. Uma função de 
hash pega um grupo de caracteres (chaves) e o mapeia para um 
valor de um determinado comprimento (valor de hash ou hash).
A+
A
A-
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
A alternativa está correta, pois a eficiência do mapeamento
depende da eficiência da função hash usada. Uma função de
hash pega um grupo de caracteres (chaves) e o mapeia para
um valor de um determinado comprimento (valor de hash ou
hash).
0,2 / 0,2 ptsPergunta 2
Leia o trecho abaixo:
Um algoritmo é projetado em função de tipos abstratos de dados. Para
implementá-los em uma linguagem de programação é necessário
representá-los de alguma maneira nessa linguagem, utilizando tipos e
operações suportadas pelo computador. Na representação do tipo
abstrato de dados, emprega-se uma estrutura de dados. É durante o
processo de implementação que a estrutura de armazenamento dos
valores é especificada e os algoritmos que desempenharão o papel
das funções (operações) são projetados. Uma estrutura de dados é um
meio para armazenar e organizar dados com o objetivo de facilitar o
acesso e as modificações. As estruturas diferem umas das outras pela
disposição ou manipulação de seus dados, de modo que não se pode
separar as estruturas de dados e os algoritmos associados a elas.
Todos os problemas a serem resolvidos por algoritmos possuem dados
que precisam ser armazenados, e o são em estruturas, de acordo com
o contexto do problema. A escolha de um algoritmo para resolver um
problema depende também do tipo de estrutura utilizada para
armazenamento dos dados. Assim, uma estrutura é escolhida de
acordo com as operações que podem ser realizadas sobre ela e com o
custo de cada uma dessas operações.
Fonte: ASCENCIO, A. F. G.; ARAÚJO, G. S. Estrutura de Dados:
algoritmos, análise da complexidade e implementações em Java e
C/C++. São Paulo: Contentus, 2010.
Considerando as informações apresentadas, assinale a opção correta.
A+
A
A-
 
A eficiência de um algoritmo pode ser analisada somente após a
implementação. Esta é uma análise empírica de um algoritmo.
 
Os algoritmos são criados dependentes das linguagens subjacentes,
um algoritmo pode ser implementado em uma linguagem de
programação.
 
Projetamos um algoritmo para obter a solução de um determinado
problema. Um problema pode ser resolvido de mais de uma maneira.
Correto!Correto!
Esta alternativa é correta, pois projetamos um algoritmo para
obter a solução de um determinado problema. Um problema pode
ser resolvido de mais de uma maneira. Assim, muitos algoritmos
de solução podem ser derivados para um determinado problema.
O próximo passo é analisar os algoritmos de solução propostos e
implementar a solução mais adequada.
 
Escrevemos algoritmos sempre passo a passo. A escrita de algoritmos
é um processo e é executado assim que o domínio do problema foi
descoberto.
 
Há padrões bem definidos para escrever algoritmos. Os algoritmos
sempre são escritos para suportar um código de programação
específico.
0,2 / 0,2 ptsPergunta 3
Leia o texto a seguir:
Um exemplo de função hash pode ser aquele que leva em
consideração o resto de uma divisão para definir a posição na estrutura
de dados. Porém uma função hash não apresenta uma fórmula
A+
A
A-
definida, e deve ser projetada levando-se em consideração o tamanho
do conjunto de dados, seu comportamento e os tipos de dados-chave
utilizados. As funções hash são o cerne na construção das tabelas
hashing, e o desenvolvimento de uma boa função de hash é essencial
para que o armazenamento dos dados, a busca e o tratamento de
colisões [...] ocorram de forma mais eficiente possível. Uma boa função
hash, em suma, deve ser:
Fácil de ser calculada. De nada valeria termos uma função com
cálculos tão complexos e lentos que todo o tempo que seria ganho
no acesso a informação com complexidade 0(1), seria perdido
calculando uma custosa função de hash;
Capaz de distribuir palavras-chave o mais uniforme possível;
Capaz de minimizar colisões. Os dados devem ser inseridos de
uma forma que as colisões sejam as mínimas possíveis, reduzindo
o tempo gasto resolvendo colisões e também reavendo os dados;
Capaz de resolver qualquer colisão que ocorrer.
Fonte: BORIN, Vinicius Pozzobon. Estrutura de dados. São Paulo:
Contentus, 2020.
Considerando as informações, avalie as afirmações a seguir:
I. Uma vantagem da sondagem linear é a tendência de agrupamento,
ou seja, os itens ficam agrupados na tabela. Isso terá um impacto em
outros itens que estão sendo inseridos.
II. Se a função hash for perfeita, as colisões nunca ocorrerão. No
entanto, como isso geralmente não é possível, a resolução de colisões
se torna uma parte muito importante do hash.
III. Uma maneira de lidar com o agrupamento é estender a técnica de
sondagem linear para que, em vez de procurar sequencialmente o
próximo slot aberto, pulemos slots.
É correto o que se afirma em:
A+
A
A-
 II, apenas. 
 II e III, apenas. Correto!Correto!
A alternativa está correta.
A afirmação I está incorreta, pois uma desvantagem da sondagem
linear é a tendência de agrupamento, ou seja, os itens ficam
agrupados na tabela. Isso significa que, se ocorrerem muitas
colisõesno mesmo valor de hash, vários slots circundantes serão
preenchidos pela resolução de sondagem linear. Isso terá um
impacto em outros itens que estão sendo inseridos.
A afirmação II está correta, pois quando dois itens fazem hash
para o mesmo slot, devemos ter um método sistemático para
colocar o segundo item na tabela de hash. Este processo é
chamado de resolução de colisão. Se a função hash for perfeita,
as colisões nunca ocorrerão. No entanto, como isso geralmente
não é possível, a resolução de colisões se torna uma parte muito
importante do hash.
A afirmação III está correta, pois uma maneira de lidar com o
agrupamento é estender a técnica de sondagem linear para que,
em vez de procurar sequencialmente o próximo slot aberto,
pulemos slots, distribuindo assim de maneira mais uniforme os
itens que causaram colisões. Isso reduzirá potencialmente o
clustering que ocorre.
 III, apenas. 
 I e III, apenas. 
 I e II, apenas. 
0,2 / 0,2 ptsPergunta 4
Leia o texto a seguir:
Uma tabela hashing é uma generalização de um vetor com m
posições. Cada posição na tabela representa um endereço. Os
A+
A
A-
elementos a serem armazenados nela possuem um valor-chave que é
utilizado para calcular o endereço na tabela onde serão alocados.
Dado um conjunto C de chaves a serem armazenadas na tabela
hashing, uma tabela de tamanho m, com endereços variando de 0 a m-
1 e dado um elemento x ∈ C , existe uma função de espalhamento ou
dispersão (ou função de hashing) que calcula o endereço (ou índice)
onde x será armazenado. A função de espalhamento tem o objetivo de
reduzir o espaço de endereços para armazenar os elementos de C. Em
vez de ICI endereços, tem-se o espaço de m endereços.
A maioria das funções de hashing assume que os elementos-chave
são números naturais. Mas é possível encontrar casos em que strings
são os elementos-chave. Nesses casos, utiliza-se como número
natural a soma dos códigos ASCII de cada caractere da string.
Um dos métodos para criar funções de hashing é o método da divisão.
Uma chave x é mapeada em um dos m endereços da tabela hashing
calculando o resto da divisão de x por m , ou seja, a função de hashing
é dada por h(x) = x mod m . Por exemplo, em uma tabela hashing com
tamanho m = 8, a chave x = 100 seria armazenada no endereço 4 [...].
Fonte: ASCENCIO, A. F. G.; ARAÚJO, G. S. Estrutura de Dados:
algoritmos, análise da complexidade e implementações em Java e
C/C++. São Paulo: Contentus, 2010.
Um paradigma muito comum no processamento de dados envolve o
armazenamento de informações em uma tabela e, posteriormente, a
recuperação das informações ali armazenadas.
Considerando as informações, avalie afirmações abaixo:
I. A ideia essencial por trás de uma tabela de dispersão é que todas as
informações sejam armazenadas em um array de tamanho fixo.
II. No dia a dia da aplicação de funções hash, na estrutura de dados,
podemos esperar que as chaves sejam sempre números inteiros.
A+
A
A-
III. Um método alternativo de lidar com colisões que elimina totalmente
a necessidade de links e encadeamento é chamado de endereçamento
aberto.
IV. Funções de criptografia simétrica são muito mais rápidas do que
funções hash computacionais.
É correto o que se afirma em:
 I e IV, apenas. 
 I e II, apenas. 
 II e IV, apenas. 
 I e III, apenas. Correto!Correto!
A alternativa está correta.
A afirmação I está correta, pois a ideia essencial por trás de uma
tabela de dispersão é que todas as informações sejam
armazenadas em um array de tamanho fixo. O hashing é usado
para identificar a posição onde um item deve ser armazenado.
A afirmação II está incorreta, pois na realidade, não podemos
esperar que as chaves sejam sempre números inteiros.
Dependendo da aplicação, as chaves podem ser letras, cadeias
de caracteres ou até mesmo estruturas de dados mais complexas.
A afirmação III está correta, pois um método alternativo de lidar
com colisões que elimina totalmente a necessidade de links e
encadeamento é chamado de endereçamento aberto. A ideia
básica é definir uma sequência de sondagem para cada chave
que, quando seguida, sempre leva à chave em questão.
A afirmação IV está incorreta, pois funções hash computacionais
são muito mais rápidas do que funções de criptografia simétrica.
Esses são aspectos relacionados à eficiência da operação hash.
 II, III e IV, apenas. 
A+
A
A-
0 / 0,2 ptsPergunta 5
Leia o texto a seguir:
Adotar números primos, especialmente aqueles não muito próximos
aos valores de potência de 2, tende a ser uma boa escolha para o
tamanho do vetor com palavras-chaves alfanuméricas. Por exemplo,
suponhamos que temos 2000 conjuntos de caracteres para serem
colocadas em uma tabela hashing. Por projeto, definiu-se que realizar
uma busca, em média, em até três posições antes de encontrar um
espaço vazio é considerado aceitável. Se fizermos . Para o
valor de m podemos adotar um número primo não muito próximo de
um múltiplo de 2. Podemos usar o valor 701. Nossa função hash
resultante seria h(k) = k MOD 701.
Por fim, quando trabalhamos com valores-chave sendo conjuntos de
caracteres, devemos tomar cuidado com palavras que contenham as
mesmas letras, mas em ordens diferentes (anagrama). Por exemplo,
uma palavra-chave com quatro caracteres chamada ROMA poderá
gerar o mesmo resultado que uma palavra-chave chamada AMOR,
pois os caracteres são os mesmos rearranjados de outra maneira.
Uma função de hash deve ser cuidadosamente definida para tratar
este tipo de problema, caso ele venha a ser recorrente; caso contrário,
teremos excessivas colisões [...]
Fonte: BORIN, Vinicius Pozzobon. Estrutura de dados. São Paulo:
Contentus, 2020.
Considerando as informações, avalie as afirmações abaixo:
I. Os algoritmos de hash fornecem a camada extra de proteção
necessária para proteger a transmissão de uma mensagem ao seu
destinatário.
A+
A
A-
II. Os algoritmos de hash são frequentemente usados para impedir que
terceiros interceptem mensagens digitais.
III. Uma colisão de hash ocorre quando um algoritmo de hash produz o
mesmo valor de hash para dois valores de entradas diferentes.
IV. A melhor prática é usar os algoritmos de hash tradicionais para
autorizar que invasores façam engenharia reversa dos valores de hash
originais.
É correto o que se afirma em:
 II e IV, apenas. 
 I e II, apenas. 
 I, II e III, apenas. esposta corretaesposta correta
 III e IV, apenas. ocê respondeuocê respondeu
A+
A
A-
A alternativa está incorreta.
A afirmação I está correta, pois os algoritmos de hash fornecem a
camada extra de proteção necessária para proteger a
transmissão de uma mensagem ao seu destinatário. Na ciência
da computação, o hashing é uma prática comum usada para
diversos fins, incluindo criptografia, indexação de dados e
compactação de dados.
A afirmação II está correta, pois os algoritmos de hash são
frequentemente usados para impedir que terceiros interceptem
mensagens digitais. Tanto o hash quanto a criptografia protegem
os dados transformando-os em um formato seguro. No entanto,
enquanto a criptografia usa um processo chamado criptografia, o
hashing usa uma fórmula matemática chamada função hash para
truncar um valor em outro.
A afirmação III está correta, pois uma colisão de hash ocorre
quando um algoritmo de hash produz o mesmo valor de hash
para dois valores de entradas diferentes. Se colisões ocorrerem,
os hackers podem enganar o computador para dar-lhes acesso
erroneamente sempre que fizerem login com uma senha próxima
o suficiente da senha original para produzir o mesmo hash.
A afirmação IV está incorreta, pois a melhor abordagem é usar os
algoritmos de hash mais recentes para impedir que invasores
façam engenharia reversa dos valores de hash originais.
Idealmente, uma boa função de hash deve processar o valor de
entrada rapidamente, minimizando a possibilidade de colisão.
 I, III e IV, apenas. 
Pontuação do teste: 0,8 de 1
A+
A
A-