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

• Processo: 16/11275-9
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de julho de 2016
• Data de Término da vigência: 31 de dezembro de 2016
• Área de 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
• Palavra(s)-Chave do Pesquisador: Ancestral Comum de Maior Profundidade (ou Lowest Common Ancestor) | Árvore de Feinwick (ou Binary Indexed Tree) | Árvore de Segmentos (ou Segment Tree) | Consulta em intervalos (ou Range queries) | Análise de Algoritmos e 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.