Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 6 - Coggle Diagram
Mapa Mental 6
Capítulo 1: "
Introdution
".
Seção 1.4: "
Fundamental Data Structures
".
Tópico: "
Sets and Dictionaries
".
Conjunto
: coleção não ordenada e possivelmente vazia de itens distintos, estes chamados de elementos.
Pode ser definido por:
Explícita listagem de seus elementos.
Especificando uma propriedade à qual todos os elementos do conjunto devem satisfazer.
Operações importantes:
Encontrar a união de dois conjuntos.
Encontrar a interseção de dois conjuntos.
Existem duas maneiras de implementar conjuntos em aplicativos de computadores.
2 more items...
Averiguar a associação de um determinado item em um determinado conjunto.
Dictionaries
: é a estrutura de dados que implementa as três operações mais utilizadas para um conjunto ou multiconjunto, que são:
Adicionar um item novo.
Deletar um item da coleção.
As algumas maneiras existentes para implementar um dicionário variam de um uso não sofisticado de
arrays
a técnicas muito mais sofisticadas, como
hashing
e árvores de busca balanceadas.
Alguns aplicativos de computação exigem uma partição dinâmica de um conjunto de \(n\) elementos em uma coleção de subconjuntos disjuntos.
A coleção é inicializada como uma coleção de \(n\) subconjuntos unitários e depois é submetida a uma sequência de operações mescladas de união e busca.
Procurar por um item dado.
Capítulo 7: "
Space and Time Trade-Offs
".
Os computadores humanos, antes do advento dos computadores eletrônicos, sobrecarregavam as bibliotecas com grandes volumes de tabelas matemáticas de cálculos que eles realizavam previamente e armazenavam as respostas.
Mesmo com os computadores eletrônicos isso não sendo mais muito necessário, essa ideia se tornou bastante útil no desenvolvimento de algoritmos para outros problemas
A ideia é pré-processar a entrada do problema e armazenar as informações adicionais obtidas para acelerar a resolução do problema depois.
Essa abordagem é chamada de
aprimoramento de entrada
.
Alguns algoritmos baseados nessa abordagem:
Métodos de contagem para ordenamento.
Algoritmo de
Boyer-Moore
para correspondência de
strings
.
Outra abordagem, chamada
pré-estruturação
, usa espaço extra para facilitar o acesso mais rápido e/ou flexível aos dados.
Algum processamento é feito antes que um problema em questão seja resolvido.
Ao contrário do aprimoramento de entrada, essa abordagem lida com a estruturação de acesso.
Essa abordagem pode ser ilustrada por:
Hashing
.
Indexando com árvores B.
Existe ainda outra técnica de projeto de algoritmo relacionada à ideia de compensação de espaço por tempo, chamada
programação dinâmica
.
Essa estratégia é baseada em registrar em uma tabela soluções para subproblemas sobrepostos de um dado problema, e a partir dessa tabela a solução do problema em questão é obtida.
Esclarecimentos acerca da interação entre espaço e tempo no projeto de algoritmos:
O tempo e o espaço não devem concorrer entre si sempre, eles podem se alinhar e resultar em uma solução algorítmica tanto com um tempo de execução menor quanto como consumindo menos espaço.
Não se pode discutir a compensação de espaço por tempo sem mencionar a área extremamente importante da compactação de dados.
Seção 7.4: "
Hashing
".
O caso mais importante da utilização de dicionários é para registros de informações, os quais contêm vários campos, cada um responsável por armazenar um tipo particular de informação acerca da entidade que o registro representa.
Dentre esses campos, geralmente existe um chamado de
chave
, que é usado para identificar a entidade representada pelo registro. É assumido que aqui será implementado um dicionário com \(n\) registros com chaves \(K_1,K_2,...,K_n\).
Hashing
é baseado na ideia de distribuir as chaves em um
array
\(H[0..m-1]\) unidimensional, chamado de
hash table
.
A distribuição é feita computando para cada chave o valor de uma função pré-definida chamada
hash function
.
Essa função atribui para uma chave um inteiro entre \(0\) e \(m-1\), chamado de
hash address
.
5 more items...