Busca avançada
Ano de início
Entree

Range-Queries: algoritmos, estruturas de dados e aplicações

Processo: 16/11275-9
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de julho de 2016
Vigência (Término): 31 de dezembro de 2016
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Candida Nunes da Silva
Beneficiário:Lucas Sampaio da Rocha
Instituição-sede: Centro de Ciências em Gestão e Tecnologia (CCGT). Universidade Federal de São Carlos (UFSCAR). Campus de Sorocaba. Sorocaba , SP, Brasil
Assunto(s):Algoritmos   Estruturas de dados

Resumo

Este projeto propõe um estudo sobre o problema de \emph{range queries} (consultas em intervalos), comumente abreviado como RSQ (\textsl{Range Sum Query}) ou RMQ (\textsl{Range Min Query}), e sobre diversas variações do problema. Será feita uma análise comparativa de vários algoritmos e estruturas de dados que podem ser usados para resolver cada variação do problema, na qual serão comparados aspectos teóricos como complexidade assintótica e aspectos práticos como tempo de execução de cada algoritmo para diferentes famílias de entradas. Neste projeto também serão apresentadas algumas aplicações clássicas deste problema que motivam o estudo do mesmo, como uma redução do problema do menor ancestral comum (LCA, em inglês \textsl{lowest common ancestor}) para o RMQ.