17
5COP096 – Teoria da Computação Aula 8 – Pesquisa em Memória Primária 5COP096 Teoria da Computação Aula 8 Prof. Dr. Sylvio Barbon Junior Sylvio Barbon Jr – [email protected] 1

5COP096 Teoria da Computação - barbon.com.br · 5COP096 – Teoria da Computação Aula 8 – Pesquisa em Memória Primária Pesquisa em Memória Primária. - Trata sobre a recuperação

  • Upload
    vothuan

  • View
    215

  • Download
    0

Embed Size (px)

Citation preview

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

5COP096 Teoria da ComputaçãoTeoria da Computação

Aula 8

Prof. Dr. Sylvio Barbon Junior

Sylvio Barbon Jr – [email protected] 1

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Sumário

1) Introdução à Pesquisa em Memória Primária

2) Pesquisa Sequencial

3) Pesquisa Binária

4) Árvore de Pesquisa

5) Pesquisa Digital

Sylvio Barbon Jr – [email protected] 2

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa em Memória Primária.

- Trata sobre a recuperação de informação a partir de uma grande massa deinformação previamente armazenada.

- A informação é dividida em registros.

-Uma pesquisa é na realidade a busca por chaves iguais à chave de pesquisa.

3

-Uma pesquisa é na realidade a busca por chaves iguais à chave de pesquisa.Caso a pesquisa retorne outro registro, teremos sucesso na pesquisa, casocontrário insucesso.

-Existem diversos métodos de pesquisa, para a escolha deve-se observar:a) A quantidade de dados envolvidos;b) O arquivo está sujeito a inserções e retiradas freqüentes ou é estável.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa em Memória Primária.

-A operações para a realização de uma pesquisa em memória primária, são:1) Inicializar a estrutura de dados;

2) Pesquisar uma ou mais registros com determinada chave;

3) Inserir um novo registro;

4

3) Inserir um novo registro;

4) Retirar um registro específico;

5) Ordenar um arquivo para obter os registros de acordo com a chave;

6) Mesclar dois arquivos para formar um arquivo maior.

- Normalmente a estrutura de dados para pesquisa é o dicionário.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa Sequencial

- É o método mais simples, onde a partir do primeiro registro, deve-se varrersequencialmente até encontrar a chave procurada.

- Normalmente o registro apresenta, além da chave, uma série de informaçõesque não interferem no mecanismo de pesquisa.

5

- Essa implementação não permite mais de um registro com a mesma chave.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa Sequencial

- Essa solução é adequada para problemas de pesquisa em tabelas com 25registros ou menos.

Melhor caso C(n) = 1

6

Melhor caso C(n) = 1

Caso médio C(n) = (n +1) /2

Pior caso C(n) = n

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa Binária

- A pesquisa em uma tabela onde os registros estão em ordem pode ser muitomais rápida.

- A cada iteração do algoritmo, o tamanho da tabela é dividido ao meio. Aquantidade de vezes que a tabela é dividida ao meio é log n.

7

- O custo para manter a tabela ordenada é alto, onde cada inserção na posição pda tabela implica o deslocamento dos registros a partir da posição p para asseguintes. Assim, a pesquisa binária não é recomendada para aplicaçõesdinâmicas.

Melhor caso C(n) = O(1)

Caso médio C(n) = O(log n)

Pior caso C(n) = O(log n)

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Árvore de Pesquisa

- É a mais adequada quando deve-se considerar:1) Acessos diretos e sequenciais;2) Facilidade para inserir e retirar registros;3) Bom consumo de memória;4) Utilização de Memória Primária e Secundária.

8

Árvores Binárias de Pesquisa sem Balanceamento- Uma árvore binária tem em cada nó no máximo duas subárvores.

- Os nós podem ser:1) De grau zero: nó externo ou folha, não há subárvores.2) De grau um ou dois: nó interno, onde os registros com chaves

menores estão na subárvore a esquerda e todos os registros com chavesmaiores estão na subárvore a direita.

- A altura de um nó é o comprimento do caminho mais longo deste nó até umnó folha.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Árvore de Pesquisa

- Exemplo de árvore com altura 4.

9

- O número de comparações em uma pesquisa de sucesso é:

Melhor caso C(n) = O(1)

Caso médio C(n) = O(log n)

Pior caso C(n) = O(n)

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Árvore de Pesquisa

- Para uma árvore de pesquisa randômica é possível mostrar que o númeroesperado de comparações é 1,39 log n, 39% pior do que a árvorebalanceada.

-Árvores Binárias de Pesquisa com Balanceamento- Esta árvore apresenta uma distribuição uniforme das chaves, em que

10

- Esta árvore apresenta uma distribuição uniforme das chaves, em quecada chave é igualmente provável de ser encontrada.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Árvore de Pesquisa

- O custo para se manter uma árvore balanceada após cada inserção é muitoalto.

- Inúmeras técnicas foram desenvolvidas para resolver este problema:- Árvores B (1972), onde uma estrutura secundária é utilizada, onde cadanó tem 2 ou 3 subárvores.

11

nó tem 2 ou 3 subárvores.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Árvore de Pesquisa

- Árvores SBB (Symmetric Binary B-Trees)(1972) – é uma árvore bináriacom dois tipos de referências, chamadas verticais e horizontais.

12

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa Digital

-É baseada na representação de chaves como uma sequência de caracteresou dígitos.

-Entre as principais vantagens está a pesquisa com chaves grandes e detamanho variável.

13

Trie- É uma árvore M-ária cujos nós são vetores de M componentes com

campos correspondentes aos dígitos ou caracteres que formam as chaves.

- Cada nó do nível i representa o conjunto de todas as chaves quecomeçam com a mesma sequência de i dígitos ou caracteres.

- O formato das Tries são diferentes das árvores binárias comuns, nãodependem da ordem em que as chaves são inseridas e sim da estrutura edistribuição de seus bits.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa Digital

- Exemplo de Trie.

14

- O maior problema de uma Trie é a formação de um caminho muito longo emuma direção para chaves com grandes quantidades de bits em comum. Porexemplo quando duas chaves de 1024bits se diferem apenas no últimoelemento.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa Digital

Patrícia

- Practical Algorithm To Retrieve Information Coded In Alphanumeric.

- Foi criado em 1968 por Morrison em um trabalho para recuperarinformações de arquivos de texto de grande porte.

15

informações de arquivos de texto de grande porte.

- Soluciona o problema das Tries de caminhos de uma só direção, onde cadanó interno contém o índice do bit a ser testado para decidir que ramo tomar.

- Uma restrição dessas árvores é a necessidade de não haver um elementoque seja prefixo de outro, o que pode facilmente ser obtido se necessário.

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Pesquisa Digital

Patrícia

16

5COP096 – Teoria da ComputaçãoAula 8 – Pesquisa em Memória Primária

Referências

Ziviani, Nivio. Projeto de algoritmos: com implementações em Java e C. Thomson Learning, 2007.

Leiserson, Charles E., Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. Ed. Thomas H. Cormen. The MIT press, 2001.