Algoritmos e Novos Limites para Busca em Conjuntos Parcialmente Ordenados
Autores
1996 |
Leonardo Gomes Holanda
|
854,257,855
|
1997 |
854,257,855
|
|
1998 |
Eduardo Laber
(Co-orientador) |
854,257,855
|
Informações:
Publicações do PESC
Algoritmos e Novos Limites para Busca em Conjuntos Parcialmente Ordenados
Leonardo Gomes Holanda
Junho/2001
Orientadores: | Celina M. Herrera de Figueiredo
Eduardo Laber | |
|
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.
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.