Algoritmos e Novos Limites para Busca em Conjuntos Parcialmente Ordenados

Autores

1996
Leonardo Gomes Holanda
854,257,855
1997
Celina Miraglia Herrera de Figueiredo
(Orientador)
854,257,855
1998
Eduardo Laber
(Co-orientador)
854,257,855

Informações:

Publicações do PESC

Título
Algoritmos e Novos Limites para Busca em Conjuntos Parcialmente Ordenados
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
25/6/2001
Resumo
PESC: Resumo de Dissertação de Mestrado Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)

Algoritmos e Novos Limites para Busca em Conjuntos Parcialmente Ordenados

Leonardo Gomes Holanda

Junho/2001
Orientadores: Celina M. Herrera de Figueiredo
Eduardo Laber 		 

 
Programa: Engenharia de Sistemas e Computação

      Neste trabalho, apresentamos um algoritmo 2-aproximativo de complexidade O(nlogn) para o problema de determinar uma estratégia de busca que minimiza a quantidade de testes para encontrar um elemento em um conjunto parcialmente ordenado que possui forma de uma árvore com n nós. Mostramos ainda que (d + 1) logn testes são suficientes para encontrar um nó em um conjunto parcialmente ordenado que possui forma de árvore, onde d é o maior entre os graus dos nós desta árvore.
      Utilizamos uma abordagem indutiva para analisar o custo de um dos protocolos de Adler e Maggs [FOCS'98] para o problema de comunicação em canais assimétricos, e concluímos que o limite superior para o custo deste protocolo está apenas a 1.09 do limite inferior, melhorando o resultado anterior de 1.71 mostrado por eles. Também notamos que podemos gerar uma distribuição cujo custo do protocolo é exatamente o valor deste limite encontrado. Mostramos ainda a relação do problema de comunicação em canais assimétricos com o problema de busca em árvores.

Abstract
PESC: Master's Degree Abstract Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)

Algorithms and New Bounds for the Partially Ordered sets Search Problem

Leonardo Gomes Holanda

June/2001
Advisor:Celina M. Herrera de Figueiredo
Eduardo Laber 		 
Department: Systems Engineering and Computer Science

      In this work, we present an approximation algorithm of complexity O(nlogn) for the problem of determinin a search strategy that minimizes the amount of tests to find an element in a tree-like partially ordered set with n nodes. We also show that (d + 1) logn tests are enough to find a node in a tree-like partially ordered set, where d is the greatest degree of the nodes in this tree.
      We use an inductive approach to analyze the cost of one of the Adler and Maggs protocols [FOCS'98] for the problem of communication in asymmetric channels, and conclude that the upper bound for the cost of this protocol is only the 1.09 of the lower bound, improving the previous result of 1.71 shown by them. Also we notice that we can generate a distribution whose cost of the protocol is accurately the same value of this new upper bound.
      We still show to the relation of the problem of communication in asymmetric channels with the problem of search in trees.

Arquivo
Topo