Please enable JavaScript.
Coggle requires JavaScript to display documents.
Conjuntos, Técnicas, Hashing, Dicionários, Input Enhancement,…
Conjuntos
Operações
Verificar pertinência de um item.
União de conjuntos.
Interseção de conjuntos.
Implementações
Vetor de bits.
Lista estruturada.
Coleções não ordenadas de elementos distintos.
Podem ser definidos explicitamente ou por propriedades.
Técnicas
Programação Dinâmica
Registra soluções de subproblemas sobrepostos em uma tabela
Evita cálculos redundantes
Reduz tempo de execução do problema
Pré-cálculo de valores de função
Tabelas matemáticas
Algoritmos de contagem para ordenação
Hashing
Indexação com B-trees
Hashing
Tipos de Funções de Hash
Para números não negativos
h(K) = K mod m
Para caracteres
h(K) = ord(K) mod m
Para cadeias de caracteres
h(K) = ((∑ ord(ci)) mod m)
Opção melhorada
h(K) = ((h * C + ord(ci)) mod m)
Hashing Aberto
Chaves armazenadas em listas ligadas nas células da tabela de hash
Busca envolve calcular o hash da chave e percorrer a lista ligada
Eficiência depende do tamanho das listas
Fator de carga: razão entre o número de chaves e o tamanho da tabela
Hashing Fechado
Chaves armazenadas diretamente na tabela de hash
Colisões resolvidas através de sondagem sequencial
Busca envolve calcular o hash e comparar com as chaves nas células
Clusters: sequências contíguas de células ocupadas
Requisitos das Funções de Hash
Tamanho adequado da tabela
Distribuição uniforme das chaves na tabela
Cálculo fácil da função de hash
Aplicações do Hashing
Tabelas de símbolos em programas de computador
Aplicações de IA
Armazenamento de grandes dicionários em discos
Dicionários
Operações
Buscar item
Adicionar item
Excluir item
Implementações
Arrays
Hashing
Árvores de busca balanceadas
Armazenam pares chave-valor
Input Enhancement
Pré-processar dados de entrada
Armazenar informações adicionais
Reduzir tempo de computação
Preestruturação
Utilizar espaço extra para acesso mais rápido
Processamento prévio antes de resolver o problema
Estruturar dados para facilitar o acesso
Set Union Problem
Particionar dinamicamente um conjunto em subconjuntos
Operações de união e busca
Tipos de Dados Abstratos
Conjuntos e dicionários são exemplos de ADTs
Representam objetos abstratos e operações relacionadas