Dois problemas de busca

Carmo, Renato José da Silva

doi:10.11606/T.45.2005.tde-20210729-150217

Início

Servicios

Tesis Doctoral

DOI

https://doi.org/10.11606/T.45.2005.tde-20210729-150217

Documento

Tesis Doctoral

Autor

Carmo, Renato José da Silva (Catálogo USP)

Nombre completo

Renato José da Silva Carmo

Dirección Electrónica

Instituto/Escuela/Facultad

Instituto de Matemática e Estatística

Área de Conocimiento

Informática

Fecha de Defensa

2005-06-22

Publicación

São Paulo, 2005

Director

Kohayakawa, Yoshiharu (Catálogo USP)

Título en portugués

Dois problemas de busca

Palabras clave en portugués

Combinatória
Ordens Parciais

Resumen en portugués

Dois problemas de busca são estudados: o problema de busca num conjunto parcialmente ordenado e o problema de otimização de consultas em bases de dados com predicados caros. Provamos que o primeiro problema é NP-difícil e apresentamos algoritmos polinomiais que fornecem aproximações de maneira assintoticamente quase certa. Para o segundo problema cotas justas inferiores de desempenho são apresentadas para algoritmos determinísticos e aleatorizados, bem como algoritmos determinísticos e aleatorizados que atingem ou aproximam essas cotas. Diversas variantes do problema são consideradas.

Título en inglés

not available

Resumen en inglés

not available

ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.

CarmoRenatoJoseDaSilva.pdf (10.72 Mbytes)

Fecha de Publicación

2021-07-29

Trabajos derivados

ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.