Algoritmos e Estruturas de Dados Aleatorizadas

Trabalho de Conclusão de Curso

Aluno: Pedro Teotonio de Sousa

Supervisor: Prof. José Coelho de Pina Junior


Resumo

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.

Monografia

A monografia está disponível aqui.

Motivação

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.

Proposta

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.

Estruturas

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.