Atividade Objetiva 2 - Estrutura de Dados - NOTA 1.0 de 1.0

Prévia do material em texto

Atividade 2
Iniciado: 30 ago em 10:18
Instruções do teste
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 ptsPergunta 1
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-
NOTA: 1.0 de 1.0
Há padrões bem definidos para escrever algoritmos. Os algoritmos sempre são
escritos para suportar um código de programação específico.
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.
Escrevemos algoritmos sempre passo a passo. A escrita de algoritmos é um
processo e é executado assim que o domínio do problema foi descoberto.
A eficiência de um algoritmo pode ser analisada somente após a implementação.
Esta é uma análise empírica de um algoritmo.
0,2 ptsPergunta 2
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 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 [...].
 
A+
A
A-
II, III e IV, apenas.
II e IV, apenas.
I e II, apenas.
I e III, apenas.
I e IV, apenas.
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.
 
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:
0,2 ptsPergunta 3
A+
A
A-
dos bancos de dados.
das colisões.
da função hash usada.
dos pares de valores-chave.
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.
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
A+
A
A-
https://wagnergaspar.com/o-que-e-e-como-funciona-a-estrutura-de-dados-tabela-hash/
da implementação de objeto.
0,2 ptsPergunta 4
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 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ãosendo 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
A+
A
A-
I e III, apenas.
I e II, apenas.
III, apenas.
II e III, apenas.
II, apenas.
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:
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
A+
A
A-
Salvo em 10:30 
I, III e IV, apenas.
III e IV, apenas.
I e II, apenas.
I, II e III, apenas.
II e IV, apenas.
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.
 
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:
Enviar teste
A+
A
A-
A+
A
A-