Estruturas de dados cinéticas (2022)
- Authors:
- USP affiliated author: MARTINS, MARCOS SIOLIN - IME
- School: IME
- Subjects: DADOS CINÉTICOS; GEOMETRIA COMPUTACIONAL; ALGORITMOS
- Language: Português
- Abstract: Estruturas de dados cinéticas são um modelo proposto por Basch, Guibas e Hershberger para a resolução de problemas cinéticos de maneira eficiente. Problemas cinéticos são problemas em que os objetos envolvidos estão em movimento contínuo e desejamos saber um determinado atributo destes objetos no instante atual. Por exemplo, consultar qual o par de pontos mais próximo no momento, num conjunto de pontos em movimento. A interface proposta para as estruturas oferece suporte a três operações: consulta, que retorna o atributo mantido, avançar no tempo, que altera o instante atual para um dado instante no futuro, e alterar a trajetória de objetos, caracterizada pela alteração de uma função cujo nome é plano de vôo. O plano de vôo é necessário para manter o atributo desejado sobre os elementos: ele define a trajetória dos pontos ao longo do tempo e será utilizado para calcular os chamados certificados. Os certificados são objetos que garantem que a organização interna da estrutura está correta até um determinado instante, denominado prazo de validade do certificado. As estruturas serão orientadas a eventos, que são o vencimento de certificados. Os certificados serão mantidos numa fila de prioridades com o seu prazo de validade como prioridade. O vencimento de um certificado significa que a estrutura ficou inválida e é necessário realizar mudanças para que ela volte a se tornar válida, removendo os certificados vencidos e gerando novos certificados no processo. Com a inclusão da dimensão tempo, a forma tradicional de analisar algoritmos não é adequada para a análise dessas estruturas. Por isso, Basch, Guibas e Hershberger também propuseram outros quatro critérios com o intuito de determinar a eficiência de cada estrutura: responsividade, eficiência, localidade e compacidade.Neste trabalho, estudaremos quatro problemas: ordenação, máximo, par mais próximo e triangulação de Delaunay, todos num contexto cinético. Também estudaremos as respectivas estruturas utilizadas na solução de cada problema e discutiremos sobre os critérios de eficiência em cada uma delas. Para algumas das estruturas também discutiremos um cenário dinâmico-cinético, ou seja, consideraremos operações de inserção e remoção dentro de um contexto cinético.
- Imprenta:
-
ABNT
MARTINS, Marcos Siolin. Estruturas de dados cinéticas. 2022. Trabalho de Conclusão de Curso (Graduação) – Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2022. Disponível em: https://bdta.abcd.usp.br/directbitstream/373d5a7e-e91e-446f-8354-f7e9897317ef/3129770.pdf. Acesso em: 27 abr. 2024. -
APA
Martins, M. S. (2022). Estruturas de dados cinéticas (Trabalho de Conclusão de Curso (Graduação). Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo. Recuperado de https://bdta.abcd.usp.br/directbitstream/373d5a7e-e91e-446f-8354-f7e9897317ef/3129770.pdf -
NLM
Martins MS. Estruturas de dados cinéticas [Internet]. 2022 ;[citado 2024 abr. 27 ] Available from: https://bdta.abcd.usp.br/directbitstream/373d5a7e-e91e-446f-8354-f7e9897317ef/3129770.pdf -
Vancouver
Martins MS. Estruturas de dados cinéticas [Internet]. 2022 ;[citado 2024 abr. 27 ] Available from: https://bdta.abcd.usp.br/directbitstream/373d5a7e-e91e-446f-8354-f7e9897317ef/3129770.pdf
Download do texto completo
| Tipo | Nome | Link | |
|---|---|---|---|
 |
3129770.pdf | Direct link |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
