XINFORMAÇÕES SOBRE DIREITOS AUTORAIS
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital
Título: ALGORITMOS APROXIMATIVOS PARA O PROBLEMA DE ATRIBUIÇÃO DE HOTLINKS E PARA BUSCA BINÁRIA EM ÁRVORES Autor: MARCO SERPA MOLINARO
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
EDUARDO SANY LABER - ORIENTADOR
Nº do Conteudo: 11879
Catalogação: 07/07/2008 Idioma(s): INGLÊS - ESTADOS UNIDOS
Tipo: TEXTO Subtipo: TESE trabalho premiado
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11879@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11879@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.11879
Resumo:
Título: ALGORITMOS APROXIMATIVOS PARA O PROBLEMA DE ATRIBUIÇÃO DE HOTLINKS E PARA BUSCA BINÁRIA EM ÁRVORES Autor: MARCO SERPA MOLINARO
Nº do Conteudo: 11879
Catalogação: 07/07/2008 Idioma(s): INGLÊS - ESTADOS UNIDOS
Tipo: TEXTO Subtipo: TESE trabalho premiado
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
Referência [pt]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11879@1
Referência [en]: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=11879@2
Referência DOI: https://doi.org/10.17771/PUCRio.acad.11879
Resumo:
Neste trabalho, apresentamos algoritmos aproximativos para
dois problemas de otimização em árvores. Na primeira parte,
consideramos o Problema de Atribuição de k-Hotlinks. Seja G=
(V,E) um grafo direcionado acíclico representando um web
site, onde nós correspondem a páginas e arcos correspondem
a hyperlinks. Nesse contexto, hotlink são definidos como
atalhos (novos arcos) adicionados às páginas de G de modo a
reduzir o tempo gasto pelos usuários para alcançarem as
informações desejadas. Neste trabalho consideramos o
problema onde G é uma árvore enraizada e o objetivo é
minimizar o tempo médio gasto pelos usuários atribuindo no
máximo k hotlinks a cada nó. Para a versão mais estudada
desse problema onde no máximo um hotlink pode ser atribuído
a cada nó, provamos a existência de um FPTAS. Isso
representa uma significante melhora em relação ao algoritmo
com aproximação constante obtido recentemente em [Jacobs,
WADS 2007]. Além disso, desenvolvemos o primeiro algoritmo
com aproximação constante para a versão mais geral onde k
hotlinks podem ser atribuídos a cada nó. Na segunda parte
deste trabalho, consideramos o problema de computar
estratégias eficientes para realizar buscas em árvores.
Como uma generalização da tradicional busca binária em
listas ordenadas, suponha que se deseja encontrar um nó
específico (porém desconhecido) de uma árvore realizando
consultas em seus arcos, onde cada consulta indica a
extremidade do arco mais próxima ao nó desejado. Dada a
probabilidade de cada nó ser aquele procurado, o objetivo é
computar uma estratégia de busca que minimize o número
esperado de consultas. Aplicações práticas desse problema
incluem sincronização de file systems e testes de software.
Apresentamos um algoritmo linear que obtém a primeira
aproximação constante para esse problema. Isso representa
uma melhora significativa em relação à O(log n)-aproximação
anterior.