Trabalho de Conclusão de Curso
Aluno: Pedro Teotonio de Sousa
Supervisor: Prof. José Coelho de Pina Junior
Aleatorização, por meio sequências de números pseudoaleatórios, é utilizada na prática para manter certas propriedades em estruturas de dados, auxiliar em coleta de amostras, em aplicações visuais, jogos e muitas outras coisas. Esse texto apresenta como essas sequências são geradas na prática, assim como alguns algoritmos e estruturas de dados que os utilizam, muitas vezes melhorando sua complexidade de tempo e espaço e simplificando seu código.
Aleatoriedade tem se mostrado uma aliada muito útil na solução de problemas, muitos dos quais reconhecidamente difíceis.
Frequentemente as estruturas e dados mais concisas, eficientes ou simples possuem um componente aleatório na sua lógica, já que esse componente permite que a organização da estrutura seja engenhosamente estregue "ao acaso".
Nesse TCC pretendo apresentar diversas estruturas de dados que utilizam essa aleatoriedade, mostrando suas aplicações e funcionamento.
Apresentar cada uma dessas estruturas de dados envolve vasculhar um pouco a fim de desvendar os seus aspectos interessantes, encontrar suas aplicações e compreender as razões de seus sucessos. Tudo isso deverá estar estruturado na monografia.
Já iniciei meus estudos e escrita sobre algumas das estruturas que pretendo apresentar, tais como treaps, skip lists e filtros de Bloom. Meu plano é continuar explorando essa área durante os dois semestres, escrevendo a monografia e selecionando as estruturas que serão apresentadas.
O Filtro de Bloom utiliza múltiplas funções de hash para verificar se um elemento é membro de um conjunto. Diferente de outras estruturas que conseguem realizar a mesma tarefa, o filtro de Bloom utiliza poucos bits por elemento, com o custo da possibilidade de falsos positivos.
A Skip list utiliza vários níveis de listas ligadas ordenadas, onde quais elementos aparecem em quais níveis é decidido com a ajuda de um gerador de números aleatórios. Essa estrutura permite realizar buscas e inserções em tempo esperado logarítmico. Modificações simples permitem que a skip list realize acesso aleatório e inserção em uma posição, ambos em tempo esperado logarítmico.
A Treap (tree + heap) é uma árvore de busca binária que se mantém balanceada utilizando um heap com prioridades geradas aleatoriamente. Sendo uma árvore de busca binária com distribuição similar a uma árvore binária aleatória, a treap tem tempo esperado logarítmico para busca e inserção.