Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa mental 7 - Daniel Nascimento - Coggle Diagram

- - - - As operações de conjunto mais importantes são: verificar a adesão de um determinado item a um determinado conjunto; encontrar a união de dois conjuntos, que compreende todos os elementos de um ou de ambos; e encontrar a intersecção de dois conjuntos, que compreende todos os elementos comuns nos conjuntos.
        
        Os conjuntos podem ser implementados em aplicações de computador de duas maneiras. O primeiro considera apenas conjuntos que são subconjuntos de algum grande conjunto U, denominado conjunto universal. Se o conjunto U tem n elementos, então qualquer subconjunto S de U pode ser representado por uma sequência de bits de tamanho n, chamada vetor de bits, em que o i-ésimo elemento é 1 se e somente se o i-ésimo elemento de U estiver incluído no conjunto S .
        
        Assim, para continuar com nosso exemplo, se U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, então S = {2, 3, 5, 7} é representado pela sequência de bits 011010100. Esta forma de representar conjuntos torna possível implementar as operações de conjunto padrão muito rapidamente, mas à custa de potencialmente utilizar uma grande quantidade de armazenamento.
        
        A segunda e mais comum maneira de representar um conjunto para fins computacionais é usar a estrutura de lista para indicar os elementos do conjunto. É claro que esta opção também é viável apenas para conjuntos finitos;
        
        conjunto não pode conter elementos idênticos; uma lista pode. Este requisito de exclusividade às vezes é contornado pela introdução de um multiset, ou bolsa, uma coleção não ordenada de itens que não são necessariamente distintos.
        
        um conjunto é uma coleção não ordenada de itens; portanto, alterar a ordem dos seus elementos não altera o conjunto. Uma lista, definida como uma coleção ordenada de itens, é exatamente o oposto.
        
        1 more item...
- - - - Há mais uma técnica de projeto de algoritmo relacionada à ideia de compensação espaço-por-tempo: programação dinâmica. Esta estratégia baseia-se no registo de soluções para subproblemas sobrepostos de um determinado problema numa tabela a partir da qual é obtida uma solução para o problema em questão.
        
        tempo e espaço – não precisam competir entre si em todas as situações de projeto. Na verdade, eles podem se alinhar para trazer uma solução algorítmica que minimize tanto o tempo de execução quanto o espaço consumido
        
        Tal situação surge, em particular, quando um algoritmo utiliza uma estrutura de dados com espaço eficiente para representar a entrada de um problema, o que leva, por sua vez, a um algoritmo mais rápido.
        
        a eficiência temporal dos dois principais algoritmos de travessia - pesquisa em profundidade e pesquisa em largura - depende da estrutura de dados usada para representar os gráficos: é (n2) para a representação da matriz de adjacência e ( n + m) para a representação da lista de adjacências, onde n e m são os números de vértices e arestas, respectivamente.
        
        Se os gráficos de entrada forem esparsos, ou seja, tiverem poucas arestas em relação a
        o número de vértices (digamos, m ∈ O(n)), a representação da lista de adjacências pode muito bem ser mais eficiente tanto do ponto de vista do espaço quanto do tempo de execução.
        
        A mesma situação surge na manipulação de matrizes e polinômios esparsos: se a porcentagem de zeros em tais objetos for suficientemente alta, podemos economizar espaço e tempo ignorando os zeros na representação e no processamento dos objetos.
        
        1 more item...
  - - - Os elementos deste conjunto podem ser de natureza arbitrária: números, caracteres de algum alfabeto, cadeias de caracteres e assim por diante.
        
        Hashing é baseado na ideia de distribuição de chaves entre um array unidimensional H[0..m − 1] chamado tabela hash. A distribuição é feita calculando, para cada uma das chaves, o valor de alguma função predefinida h chamada função hash.
        
        Se as chaves são letras de algum alfabeto, podemos primeiro atribuir a uma letra sua posição no alfabeto, denotada aqui por ord(K), e então aplicar o mesmo tipo de uma função usada para números inteiros.
    - - O tamanho de uma tabela hash não deve ser excessivamente grande comparado ao número de chaves, mas deve ser suficiente para não comprometer a eficiência do tempo de implementação (veja abaixo).
        
        Uma função hash precisa distribuir chaves entre as células da tabela hash da maneira mais uniforme possível. (Este requisito torna desejável, para a maioria das aplicações, ter uma função hash dependente de todos os bits de uma chave, e não apenas de alguns deles.)
        
        Uma função hash deve ser fácil de calcular.
    - - Hashing fechado (endereçamento aberto)
        
        No hashing fechado, todas as chaves são armazenadas na própria tabela hash sem o uso de listas vinculadas.
        
        Isto implica que o tamanho da tabela m deve ser pelo menos tão grande quanto o número de chaves n.
        
        <<<< A mais simples – chamada sondagem linear
        
        Verifica a célula seguinte àquela onde ocorre a colisão. Se essa célula estiver vazia, a nova chave será instalada ali; se a próxima célula já estiver ocupada, é verificada a disponibilidade do sucessor imediato daquela célula, e assim por diante.
        
        Observe que se o final da tabela hash for atingido, a pesquisa será quebrada no início da tabela; ou seja, é tratado como uma matriz circular.
        
        Embora as operações de pesquisa e inserção sejam simples para esta versão de hashing, a exclusão não é.
        
        “exclusão lenta”.
        
        2 more items...
        
        comparando as principais propriedades do hashing com árvores de busca balanceadas
        
        Seu principal concorrente na implementação de dicionários. Eficiência de tempo assintótica Com hashing, pesquisa, inserção e exclusão podem ser implementadas para levar (1) tempo em média, mas (n) tempo no pior caso, muito improvável. Para árvores de busca balanceadas, as eficiências médias de tempo são (log n) tanto para o caso médio quanto para o pior caso.
        
        Preservação de ordenação Ao contrário das árvores de busca balanceadas, o hashing não pressupõe a existência de ordenação de chave e geralmente não a preserva. Isso torna o hash menos adequado para aplicativos que precisam iterar sobre as chaves ou exigem consultas de intervalo, como contar o número de chaves entre alguns limites inferior e superior.
        
        Hash tornou-se uma técnica padrão para armazenar uma tabela de símbolos – uma tabela de símbolos de um programa de computador gerados durante a compilação.
        
        O hash é bastante útil para aplicações de IA, como verificar se as posições geradas por um programa de computador para jogar xadrez já foram consideradas. Com algumas modificações, também provou ser útil para armazenar dicionários muito grandes em discos; esta variação de hash é chamada de hash extensível.
        
        1 more item...
      - hash aberto, as chaves são armazenadas em listas vinculadas anexadas às células de uma tabela hash. Cada lista contém todas as chaves com hash para sua célula.
        
        a eficiência da pesquisa depende do comprimento das listas encadeadas, que, por sua vez, dependem do tamanho do dicionário e da tabela, bem como da qualidade
        
        Em geral, a eficiência da pesquisa depende do comprimento das listas encadeadas, que, por sua vez, dependem do tamanho do dicionário e da tabela, bem como a qualidade a eficiência da pesquisa depende do comprimento das listas encadeadas, que, por sua vez , depende do tamanho do dicionário e da tabela, bem como da qualidade da função hash.
        
        Se a função hash distribuir n chaves entre m células da tabela hash de maneira aproximadamente uniforme, cada lista terá cerca de n/m chaves. A razão α = n/m, chamada de fator de carga da tabela hash, desempenha um papel crucial na eficiência do hash.
        
        Em particular, o número médio de ponteiros (elos de cadeia) inspecionados em buscas bem-sucedidas, S, e buscas malsucedidas, U, acaba sendo respectivamente, sob as suposições padrão de busca por um elemento selecionado aleatoriamente e uma função hash distribuindo chaves uniformemente entre as células da tabela.
        
        Normalmente, queremos que o fator de carga não esteja longe de 1. Tê-lo muito pequeno implicaria em muitas listas vazias e, portanto, no uso ineficiente do espaço;
        
        1 more item...
- - - - compressão de dados, a redução de tamanho é o objetivo e não uma técnica para resolver outro problema.
        
        Dicionário é um tipo de dado abstrato, ou seja, um conjunto com as operações de busca (pesquisa), inserção e exclusão definidas em seus elementos.
        
        Na pior das hipóteses, todas as chaves poderiam ser criptografadas na mesma célula da tabela hash.
        
        hash aberto, as chaves são armazenadas em listas vinculadas anexadas às células de uma tabela hash. Cada lista contém todas as chaves com hash para sua célula.
        
        a eficiência da pesquisa depende do comprimento das listas encadeadas, que, por sua vez, dependem do tamanho do dicionário e da tabela, bem como da qualidade
        
        No hashing fechado, todas as chaves são armazenadas na própria tabela hash sem o uso de listas vinculadas.