Please enable JavaScript.
Coggle requires JavaScript to display documents.
Olavo Rangel da Conceição - Coggle Diagram
Olavo Rangel da Conceição
Set
Coleção Não ordenada
Elementos do conjunto
Pode ser vazio
Definidos
Lista Explicita
Propriedade Especifica
Engloba Todos os Elementos do Conjunto
Operação dos Conjuntos
Checking Membership
União de Dois Conjuntos
Intersecção de Dois Conjuntos
Aplicação Informatica
Conjuntos que são Subconjuntos do Conjunto U
Se o Conjunto U tem n elementos
Qualquer outro subconjunto de U será menor ou igual a n
Bit Vector
Estrutura de Lista
Indicar Elementos do Conjunto
Aplicavel Em Conjuntos Finitos
Operações
Busca Determinado Item
Dicionário
Problema
Set Union Problem
Adição de Item
Exclusão de Item
Diferenças Entre Conjunto e Lista
Lista não pode Ter Elementos Identicos
Multiset
Conjunto é uma Coleção Não ordenada de Elementos
Algumas Vezes Vale a Pena Deixar o Conjunto Ordenado
Lista é Uma Coleção Ordenada
Space and Time Trade-Offs
Bastante Conhecido
Teoricos
Profissionais da Computação
Antes dos Computadores Eletrônicos
Pré-Computar Valores da Função
Armazenar Em Tabela
Util
Usado até Hoje
Desenvolvimento de Algoritmos
Input Enhancement
Counting Methods
Sorting
Prestructuring
Hashing
Indexing with B-Trees
Dynamic Programming
Registro de Solução
Overlapping de Subproblemas
1 more item...
Tempo e Espaço
Não precisam Competir entre Si
Solução Algoritmicas
Contempla os Dois Problemas
Compressão de Dados
Redução de Tamanho é a Meta
Não é Tecnica para Resolver outros Problemas
Hashing
Open Hashing
Chaves
Armazenada
Linked Lists
Anexadas as Células da Tabela Hash
Fazer uma Busca
Eficiência Depende do Tamanho da Linked List
Que Depende do Tamanho do Dicionario e da Tabela
Colocar Chave de Busca
Mesmo Procedimento
Criar Tabela
Ratio
Alfa = n/m
Load Factor
Importante
Boa Eficiência
Closed Hashing
Chaves Armazenadas
Hash Table
Linear Probing
Onde Ocorre Colisão
Verifica Próx Cell
Empty Cell
Nova Chave Instalada
Full Cell
Verificar o Próx
Fim
Busca Volta para o Inicio
1 more item...
Operação
Busca
Simples
Inserção
Eliminação
Complexa
Solução
Lazy Deletion
Cluster
Hash Table Ficando Cheia
Performance Deteriora
Sequência de Células
Contiguamente Ocupadas
Operação Dicionario
Menos Eficiente
Grandes Clusters
Aumenta Probabilidade de Colisões
Aliviar problema
Aliviar Problema
Double Hashing
Analise Matematica Dificil
Boa Implementação Hash
1 more item...
Desempenho Piora
1 more item...
Maneira Eficiente
Implementação Dicionarios
Registros
Vários Campos
Manter Tipo de Informação do Registro
Key
Distribuição de Chaves
Matriz Unidimensional
Hash Table
Computando
Chaves
Valor
Função Predefinida H
Hash Function
Hash Table Size Não Deve Ser Grande
Numero de Chaves
1 more item...
Distribuir Key
Mais Uniforme Possivel
Precisa ser Fácil de Computar
Atribui Numero entre 0 e m-1
Endereço Hash