Algoritmos e Estrutura de Dados - TA04

Prévia do material em texto

Algoritmos e 
Estrutura de dados 
Prof. Me. Wesley Viana
• Unidade de Ensino: 04
• Competência da Unidade: Algoritmos e Estrutura de dados 
• Resumo: Saber utilizar algoritmos e estrutura de dados na 
programação
• Palavras-chave: Linguagem de programação; Programação; 
Desenvolvimento; estrutura de dados ; Algoritmos.
• Título da Teleaula: Armazenamento associativo
• Teleaula nº: 04
Contextualização
• Definição e usos de Mapas de Armazenamento;
• Mapas com Lista;
• Mapas com Espelhamento.
Conceitos
Armazenamento 
associativo
Armazenamento associativo
Definição e Usos de Mapas de Armazenamento
As estruturas de Armazenamento Associativo permitem
armazenar elementos em estruturas como Listas ou Mapas com
Espalhamento sem depender da posição onde estão armazenados,
baseando-se apenas em seu valor
Armazenamento Associativo, uma estrutura que permite
criarmos um mapeamento entre o elemento que desejamos e uma
chave para identificá-lo.
Segundo Tenenbaum (2007), uma estrutura de dados precisa
dispor de implementações para gerenciar e controlar como o
armazenamento será atribuído a uma linguagem de programação.
Armazenamento associativo
Definição de Armazenamento Associativo
Segundo Goodrich e Tamassia (2013), o Armazenamento
Associativo é uma estrutura que permite o acesso aos seus elementos
com base apenas no seu valor, independentemente de sua posiçãona
estrutura. Em determinados casos, é utilizado apenas parte do valor do
elemento, conhecido como chave, em vez do valor do elemento
completo.
Armazenamento associativo
Definição de Armazenamento Associativo
Podemos visualizar um exemplo de tabela associativa de
Código Morse, onde um caractere representa uma sequência de sinais
curtos ou longos.
Armazenamento associativo
Definição de Armazenamento Associativo
A utilização de código de barras em produtos industrializados
é uma forma de criar associações entre o produto, o fabricante e a
empresa que vende determinado produto.
Armazenamento associativo
Motivação para Armazenamento Associativo
Para Goodrich e Tamassia (2013), a utilização de uma chave
em mapa permite armazenar e localizar elementos que possam ser
encontrados rapidamente. A motivação para as pesquisas é referente a
cada elemento que armazena informações adicionais úteis junto à
chave, mas que podem ser acessadas somente pela chave.
Imagine se cada pessoa fosse identificada apenas pelo nome,
como funcionariam os sistemas? E nos casos de nomes iguais? Para
isso, foi implantado o CPF (Cadastro de Pessoa Física), que permite
identificar uma pessoa apenas com um código de 11 (onze) dígitos.
Armazenamento associativo
Mapas Associativos
Segundo Pereira (2008), um mapa não pode ser definido por
fórmulas, diferentemente de como acontece com funções. Um
mapeamento é definido por meio de uma relação entre seus pares, que
nem sempre é baseada em questões lógicas ou matemáticas.
Os Mapas Associativos são estruturas de dados que permitem
implementar as seguintes funcionalidades:
• Adicionar uma associação.
• Verificar um valor de uma chave específica.
• Remover uma associação de uma chave específica.
• Verificar se existe uma associação para determinada chave.
• Informar a quantidade de associações na estrutura
Armazenamento associativo
Usos gerais para Armazenamento Associativo
Conforme Goodrich e Tamassia (2013), a utilização de
estruturas de Armazenamento Associativo está presente em todos os
tipos de sistemas, seja um simples sistema de cadastro de clientes de
uma pequena loja, seja um sistema de grande porte de uma empresa
multinacional.
Em um sistema de supermercado, o código de barras é a chave
de identificação de todas as informações dos produtos e, por meio do
leitor de código de barras, temos as informações, no caixa, da
descrição do produto, valor de venda e valor de imposto
Exercício 01:
Conceitos
Mapas com Lista
Armazenamento associativo
Mapas com Lista
A utilização de Mapas com Listas permite implementar o
armazenamento de informações de forma mais simples, facilitando a
busca mais rápida de informações.
Armazenamento associativo
Mapas com Lista
Desta forma, ao utilizar o mapeamento por meio de listas,
podemos otimizar o sistema para a consulta e o armazenamento de
informações associados a um índice.
Definição e exemplos de Mapas com Listas
O uso de um índice é como uma referência associada a uma
chave, utilizada para realizar a da otimização do desempenho e
permitindo uma localização mais rápida de um elemento quando
solicitado.
Armazenamento associativo
Podemos observar a coluna de índice que se refere aos
índices da Lista. A coluna de Elementos da Lista é formada por uma
estrutura de mapa, em que é associada uma chave a uma
informação.
Armazenamento associativo
Podemos utilizar como exemplo também a criação de um
sumário de um livro.
Armazenamento associativo
Antes de adicionar ou remover uma associação no Mapa, o
sistema deve verificar se a chave não pertence a alguma associação
da Lista ou se está associada a um valor. Para realizar essa
verificação, é necessário percorrer a Lista, pois o Mapa permite
apenas associações com chaves distintas.
Verificação da Existência de uma Chave em Mapeamento
com Listas
Para adicionar uma associação no Mapa, é necessário
verificar se a chave da nova associação não pertence a alguma
associação da Lista; para isso, precisamos verificar se a chave já
existe na estrutura.
Armazenamento associativo
Adicionar/remover associações dadas suas chaves em
mapeamento com listas
Como a estrutura de Mapa não pode permitir que duas
associações com a mesma chave sejam inseridas e com a realização
da verificação de existência de chave já realizada, podemos inserir
uma nova chave em nossa estrutura de Mapa.
Para remover uma associação, comparamos a chave
informada com as demais chaves das associações da Lista. Se acaso
a chave existir, será removida do mapeamento, deixando essa
posição disponível para uma eventual adição com essa chave.
Armazenamento associativo
Recuperar valores associados a chaves em mapeamento com
listas
A recuperação de valores associados a chaves em um
mapeamento com listas pode ser implementada de forma bem
simples, utilizando a mesma lógica de verificação de existência de
uma chave, alterando apenas o retorno da mensagem.
Outra forma de utilizarmos essa pesquisa de elementos em
um mapeamento é realizar a pesquisa por meio do código.
Exercício 02:
Exercício 03:
Conceitos
Mapas com 
Espalhamento
Mapas com Espalhamento
Mapas com Espalhamento
A utilização de Mapa com Espalhamento permite uma
associação entre chaves e valores mais rápida e, assim, quando
empregado em sistemas com muitas informações, possibilita a rápida
identificação dos elementos associados. Exemplo CPF.
A implementação de estrutura de dados do tipo Mapa,
utilizando Listas, pode ser menos eficiente quando o sistema possui
muitas informações, pois, em operações em que precisam ser
percorridas todas as associações e, conforme o número de
associações cresce, o tempo para percorrer a estrutura torna-se mais
demorado, interferindo no desempenho do sistema
Mapas com Espalhamento
Definição e exemplos de Mapas com Espalhamento
Para Tenenbaum (1995), da mesma forma que podemos
utilizar a técnica de Espalhamento para melhorar o desempenho da
estrutura de dados para acesso rápido às informações, podemos
utilizar a técnica de Espalhamento associada aos Mapas para suprir
essa necessidade de melhora nos acessos.
O Mapa com Espalhamento tem como características:
• os elementos não são ordenados;
• rápida busca/inserção de dados;
• permite inserir valores e chaves nulas
Mapas com Espalhamento
O Mapa com Espalhamento permite gerenciar uma sequência
de elementos como uma Tabela de Espalhamento, com cada entrada
de tabela armazenando uma lista de nós vinculados e cada nó
armazenando um elemento. Um elemento consiste em uma chave,
para poder ordenar a sequênciae um valor mapeado.
Mapas com Espalhamento
A utilização do Mapa com Espalhamento é muito comum
quando se trabalha com valores “nomeados”, ou seja, não importa a
posição do elemento, mas o valor da sua chave.
Mapa com Espalhamento é utilizado com muita frequência
no sistema de parametrização de métodos, ou seja, um sistema que
tenha um método que pode receber um número diversificado de
parâmetros com grande quantidade de nomes distintos.
Verificação da existência de uma Chave em Mapas com
Espalhamento
Segundo Goodrich (2013), como estamos utilizando a técnica
de Espalhamento para verificar a existência de uma chave no Mapa,
precisamos calcular o índice da Tabela e procurá-lo na Lista
correspondente.
Mapas com Espalhamento
Adicionar/remover associações dadas suas Chaves em
Mapas com Espalhamento
Para Goodrich (2013), ao adicionar uma nova associação,
pode ser que a chave já exista no Mapa. Neste caso, vamos retirar a
associação antiga antes de colocar a nova. Isso deve ser feito porque
o Mapa não permite chaves repetidas.
Já a remoção de uma associação é um procedimento
simples: apenas calculamos o índice e procuramos a chave na tabela
correspondente e, ao encontrarmos a chave, removemos a
associação.
Mapas com Espalhamento
Recuperar valores associados a chaves em Mapas com
Espalhamento
Conforme Goodrich (2013), o principal objetivo do Mapa com
Espalhamento é oferecer uma forma rápida de acessar o valor de
uma chave desejada e, assim, ter um desempenho da estrutura
maior que o das demais estruturas.
Recuperar as informações associadas à chave desejada,
como realizar uma pesquisa no sistema para saber quais os dados de
endereço de uma pessoa, consultando-os pela chave, que pode ser
seu nome ou seu CPF.
Mapas com Espalhamento
Recuperar valores associados a chaves em Mapas com
Espalhamento
Os Armazenamentos Associativos com Espalhamento são
otimizados para as operações de pesquisa, inserção e remoção e são
muito eficientes quando usados com uma Função de Espalhamento
bem projetada, executando-as em um tempo que é, em média,
constante e não depende do número de elementos. Uma Função de
Espalhamento bem projetada realiza uma distribuição
uniforme de valores e minimiza o número de colisões, e, no pior
caso, com a pior Função de Espalhamento possível, o número de
operações será proporcional ao número de elementos na sequência
de elementos
Mapas com Espalhamento
Exercício 04:
Recapitulando
Recapitulando
• Definição e Usos de Tabela de Espelhamento;
• Operações em tabelas de Espelhamento;
• Otimização de tabelas de Espelhamento.