Eduardo Laber
Universidade Federal do Rio de Janeiro
Sexta-feira, 24 de novembro de 2000 às 14 horas
Sala 144, Bloco B, IME-USP
Resumo:
Seja A[1:n] um vetor ordenado. Se o custo para testar cada posição deste vetor é uniforme, então a busca binaria é a melhor estratégia possível, tanto no caso médio quanto no pior caso. Entretanto, se os custos de acesso não são uniformes, então a melhor estratégia de busca não é necessariamente a busca binária. O melhor algoritmo conhecido para construir a estratégia que minimiza o custo médio de busca requer O(n3) passos e espaço quadrático. As mesmas complexidades valem para o melhor algoritmo conhecido que minimiza o custo máximo de busca.
Nesta palestra, mostramos algoritmos que executam em tempo linear e constroem estratégias de busca cujos custos estão no máximo a um fator (2+\epsilon+o(1)) do custo da estratégia ótima, para todo \epsilon >0. Estes problemas surgem no processamento de consultas em bases textuais distribuídas.