Dois problemas de busca (2005)
- Authors:
- Autor USP: CARMO, RENATO JOSÉ DA SILVA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: COMBINATÓRIA; ORDENS PARCIAIS
- Language: Português
- Abstract: 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.
- Imprenta:
- Data da defesa: 22.06.2005
-
ABNT
CARMO, Renato José da Silva. Dois problemas de busca. 2005. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2005. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-150217/. Acesso em: 19 set. 2024. -
APA
Carmo, R. J. da S. (2005). Dois problemas de busca (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-150217/ -
NLM
Carmo RJ da S. Dois problemas de busca [Internet]. 2005 ;[citado 2024 set. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-150217/ -
Vancouver
Carmo RJ da S. Dois problemas de busca [Internet]. 2005 ;[citado 2024 set. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-150217/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
