Pesquisa em Memória Primária David Menotti Algoritmos e Estruturas de Dados I DECOM – UFOP

  • Published on
    17-Apr-2015

  • View
    103

  • Download
    1

Embed Size (px)

Transcript

<ul><li> Slide 1 </li> <li> Pesquisa em Memria Primria David Menotti Algoritmos e Estruturas de Dados I DECOM UFOP </li> <li> Slide 2 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa em Memria Primria Introduo - Conceitos Bsicos Pesquisa Sequencial Pesquisa Binria rvores de Pesquisa rvores Binrias de Pesquisa sem Balanceamento rvores Binrias de Pesquisa com Balanceamento rvores AVL rvores Digitais Transformao de Chave (Hashing) Listas Encadeadas, Endereamento Aberto, Hashing Perfeito </li> <li> Slide 3 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Introduo Conceitos Bsicos Estudo de como recuperar informao a partir de uma grande massa de informao previamente armazenada. A informao dividida em registros. Cada registro possui uma chave para ser usada na pesquisa. Objetivo da pesquisa: Encontrar uma ou mais ocorrncias de registros com chaves iguais chave de pesquisa. Pesquisa com sucesso X Pesquisa sem sucesso. </li> <li> Slide 4 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Introduo Conceitos Bsicos Tabelas Conjunto de registros ou arquivos TABELAS Tabela: associada a entidades de vida curta, criadas na memria interna durante a execuo de um programa. Arquivo: geralmente associado a entidades de vida mais longa, armazenadas em memria externa. Distino no rgida: tabela: arquivo de ndices arquivo: tabela de valores de funes. </li> <li> Slide 5 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Escolha do Mtodo de Pesquisa mais Adequado a uma Determinada Aplicao Depende principalmente: 1. Quantidade dos dados envolvidos. 2. Arquivo estar sujeito a inseres e retiradas freqentes. Se contedo do arquivo estvel importante minimizar o tempo de pesquisa, sem preocupao com o tempo necessrio para estruturar o arquivo </li> <li> Slide 6 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Algoritmos de Pesquisa Tipos Abstratos de Dados importante considerar os algoritmos de pesquisa como tipos abstratos de dados (TADs), com um conjunto de operaes associado a uma estrutura de dados, de tal forma que haja uma independncia de implementao para as operaes. Operaes mais comuns: 1. Inicializar a estrutura de dados. 2. Pesquisar um ou mais registros com determinada chave. 3. Inserir um novo registro. 4. Retirar um registro especfico. 5. Ordenar um arquivo para obter todos os registros em ordem de acordo com a chave. 6. Juntar dois arquivos para formar um arquivo maior. </li> <li> Slide 7 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Dicionrio Nome comumente utilizado para descrever uma estrutura de dados para pesquisa. Dicionrio um tipo abstrato de dados com as operaes: 1. Inicializa 2. Pesquisa 3. Insere 4. Retira Analogia com um dicionrio da lngua portuguesa: Chaves palavras Registros entradas associadas com *pronncia, definio, sinnimos, outras informaes </li> <li> Slide 8 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Sequencial Mtodo de pesquisa mais simples: a partir do primeiro registro, pesquise seqencialmente at encontrar a chave procurada; ento pare. Armazenamento de um conjunto de registros por meio do tipo estruturado arranjo: </li> <li> Slide 9 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Sequencial #define MAX 10 typedef long TipoChave; typedef struct { TipoChave Chave; /* outros componentes */ } Registro; typedef int Indice; typedef struct { Registro Item[MAX + 1]; Indice n; } Tabela; </li> <li> Slide 10 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Sequencial Implementao para as operaes Inicializa, Pesquisa : void Inicializa(Tabela *T) { T-&gt;n = 0; } int Pesquisa(TipoChave x, Tabela *T) { int i; T-&gt;Item[0].Chave = x; i = T-&gt;n; while (T-&gt;Item[i].Chave != x) i--; return i; } </li> <li> Slide 11 n++; T-&gt;Item[T-&gt;n] = Reg; }"&gt; </li><li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Sequencial Implementao para a operacao Insere: void Insere(Registro Reg, Tabela *T) { if (T-&gt;n == MAX) printf("Erro : tabela cheia\n"); else { T-&gt;n++; T-&gt;Item[T-&gt;n] = Reg; } </li> <li> Slide 12 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Sequencial Pesquisa retorna o ndice do registro que contm a chave x; Caso no esteja presente, o valor retornado zero. A implementao no suporta mais de um registro com uma mesma chave. Para aplicaes com esta caracterstica necessrio incluir um argumento a mais na funo Pesquisa para conter o ndice a partir do qual se quer pesquisar. </li> <li> Slide 13 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Sequencial Utilizao de um registro sentinela na posio zero do array: Garante que a pesquisa sempre termina: se o ndice retornado por Pesquisa for zero, a pesquisa foi sem sucesso. No necessrio testar se i &gt; 0, devido a isto: o anel interno da funo Pesquisa extremamente simples: o ndice i decrementado e a chave de pesquisa comparada com a chave que est no registro. isto faz com que esta tcnica seja conhecida como pesquisa seqencial rpida. </li> <li> Slide 14 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Sequencial Anlise: Pesquisa com sucesso: melhor caso : C(n) = 1 pior caso : C(n) = n caso mdio: C(n) = (n + 1) / 2 Pesquisa sem sucesso: C (n) = n + 1. O algoritmo de pesquisa sequencial a melhor escolha para o problema de pesquisa em tabelas com at 25 registros. </li> <li> Slide 15 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Binria Pesquisa em tabela pode ser mais eficiente Se registros forem mantidos em ordem Para saber se uma chave est presente na tabela 1. Compare a chave com o registro que est na posio do meio da tabela. 2. Se a chave menor ento o registro procurado est na primeira metade da tabela 3. Se a chave maior ento o registro procurado est na segunda metade da tabela. 4. Repita o processo at que a chave seja encontrada, ou fique apenas um registro cuja chave diferente da procurada, significando uma pesquisa sem sucesso. </li> <li> Slide 16 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Exemplo de Pesquisa Binria para a Chave G </li> <li> Slide 17 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Binria Indice Binaria(TipoChave x, Tabela *T) { Indice i, Esq, Dir; if (T-&gt;n == 0) return 0; else { Esq = 1; Dir = T-&gt;n; do { i = (Esq + Dir) / 2; if (x &gt; T-&gt;Item[i].Chave) Esq = i + 1; else Dir = i - 1; } while ( (x != T-&gt;Item[i].Chave) &amp;&amp; (Esq Item[i].Chave) return i; else return 0; } </li> <li> Slide 18 </li> <li> David Menotti Algoritmos e Estrutura de Dados I Pesquisa Binria Anlise A cada iterao do algoritmo, o tamanho da tabela dividido ao meio. Logo: o nmero de vezes que o tamanho da tabela dividido ao meio cerca de log n. Ressalva: o custo para manter a tabela ordenada alto: a cada insero na posio p da tabela implica no deslocamento dos registros a partir da posio p para as posies seguintes. Conseqentemente, a pesquisa binria no deve ser usada em aplicaes muito dinmicas. </li> </ul>

Recommended

View more >