Please enable JavaScript.

Coggle requires JavaScript to display documents.

M6 (Levitin) - Coggle Diagram

- - - - Input enhancement ("Otimização de entrada"), a qual se baseia em pré-processar as entradas de um problema e armazenar as informações obtidas para acelerar a sua solução em situações futuras
        
        Ex.: Métodos de contagem para ordenação e o algoritmo de Boyer-Moore para correspondência de strings
      - Prestructuring, a qual se baseia no uso de espaço extra para facilitar um acesso mais rápido ou flexível às informações, através de um pré-processamento que cria estruturas de acesso para serem usadas durante a solução do problema
        
        Ex.: Hashing e indexamento em Árvores B
      - Dynamic Programming ("Programação Dinâmica"), a qual se baseia no registro de soluções para subproblemas sobrepostos em uma tabela que é acessada durante a solução do problema
  - - - Hashing
        
        Se baseia na distribuição de elementos, caracterizados por "chaves", em uma array unidimensional chamada tabela hash
        
        Por meio de uma função hash, cada chave é associada a um endereço hash, que é um índice da tabela hash (inteiros de 0 a m-1, sendo m o tamanho da tabela). Cada endereço indica então uma partição do dicionário com um ou mais itens (dependendo da implementação do código)
        
        Como a função hash pode fornecer um mesmo endereço para chaves diferentes, situação chamada de "colisão", o algoritmo necessita de um mecanismo para solucionar esse tipo de problema.
        Dois algoritmos que apresentam mecanismos diferentes para lidar com colisões são:
        
        Open Hashing (ou Separate Chaining)
        
        As chaves são armazenadas em listas ligadas que estão anexadas a cada um dos índices da array
        
        1 more item...
        
        Inserção e remoção possuem eficiência θ(1) para um número de chaves próximo ao tamanho da tabela hash
        
        Closed Hashing (ou Open Addressing)
        
        Não faz uso de lista ligada, de maneira que cada endereço hash está relacionado exclusivamente
        a uma única chave (consequentemente, a tabela hash necessariamente precisa conter um número de índices maior ou igual ao número de chaves)
        
        1 more item...
        
        Enquanto a inserção é um procedimento direto, a remoção precisa se preocupar com o espaço vazio deixado, pois pode impedir que um elemento posicionado posteriormente, devido à uma situação de conflito, seja acessado. Uma solução é indicar com um caractere especial, após a remoção, que aquela determinada posição já esteve preenchida (o que é chamado lazy deletion)
        
        Uma de suas variações que ameniza o efeito de colisão é o double hashing o qual adiciona uma nova função hash para ser aplicada sobre a chave que entrou em conflito
        
        Uma saída para problemas decorrentes do preenchimento quase completo da tabela hash é o rehashing que realoca todos os itens para uma nova tabela hash maior
        
        Para verificar se um elemento pertence ao dicionário, a função hash é aplicada sobre sua chave e em seguida verifica-se, no endereço obtido, se já há registro dessa chave.
        
        Uma das vantagens desse método em relação às árvores de busca balanceadas é sua eficiência temporal de θ(1) para os casos médios, enquanto a sua concorrente realiza em θ((log(n))
        
        Uma das desvantagens desse método em relação às árvores de busca balanceadas é o fato de não preservar uma ordem entre os itens
- - - - Pode ser definido pela declaração direta de seus elementos, ou pelo estabelecimento de propriedades que caracterizam todos os seus elementos (e todos os elementos com essa característica pertencem a conujunto)
        
        Ex.: S = {2,4, 6} ou S = {2n | n é natural e 1 < n < 3}
      - As operações mais comuns realizadas com conjuntos são:
        
        Verificar o pertencimento de algum elemento
        
        Determinar a união entre conjuntos
        
        Determinar a interseção entre conujntos
      - Em geral, sua implementação como data structure é chamada de "Dicionário"
        
        Possui 2 tipos de implementação predominante:
        
        Como um subconjunto de um conjunto universo maior, indicando quais elementos desse universo pertencem ao subconjunto em questão
        
        Normalmente é usado um vetor binário para representar esse caso. Dessa maneira, os elementos do universo são posicionados em sequência e o vetor binário exprime quais elementos pertencem ao conjunto, indicando com o 1 se o elemento daquela posição pertence, ou 0 caso contrário
        
        É um método com boa eficiência temporal, mas em compensação com um relativo grande custo espacial para armazenar vetores como o mesmo tamanho de elementos do universo
        
        Ex.: Universo = {1, 2, 3, 4}, S = {2, 4} =>
        Vetor binário = (0101)
        
        Ambos requerem que os conjunto sejam finitos
        
        Como uma lista de elementos, em que não há elementos repetidos e a ordem dos elementos não importa, ou seja, modificar a ordem em que esses elementos estão dispostos não define um conjunto distinto
        
        Um conjunto do tipo multiset ou bag pode ter elementos repetidos
        
        As operações mais usuais são de busca, inserção e remoção