62ª Reunião Anual da SBPC

A. Ciências Exatas e da Terra - 5. Matemática - 4. Matemática Aplicada

ANÁLISE E COMPARAÇÃO ENTRE ALGORITMOS DE PERCOLAÇÃO

Isaac Dayan Bastos da Silva 1 Marcelo Gomes Pereira 2 Joaquim Elias de Freitas 2 Antônio Carlos Fonseca Pontes 1 Antônio Carlos Fonseca Pontes Júnior 1

1. CCET,Universidade Federal do Acre/UFAC 2. CCET, Universidade Federal do Rio Grande do Norte/UFRN

INTRODUÇÃO:

Na atualidade, existem muitos trabalhos científicos que utilizam a percolação para modelar diversos problemas, muitas vezes, de difícil solução e que são resolvidos apenas de forma aproximada com a ajuda de computadores. Este trabalho tem como principal finalidade a comparação, utilizando métodos computacionais e teóricos, entre dois algoritmos que simulam o processo de percolação. Um deles foi elaborado por Joaquim Elias de Freitas e o outro por Mark E. J. Newman e Robert M. Ziff, um independente do outro, ambos com muitas diferenças, porém com o mesmo objetivo: modelagem computacional da percolação. Podemos destacar como objetivo secundário o estudo desses algoritmos para utilização dos conhecimentos adquiridos em futuras aplicações práticas, possivelmente em outras áreas do conhecimento.

METODOLOGIA:

O objetivo central deste artigo é efetuar uma comparação entre os algoritmos de Elias (chamaremos de algoritmo A) e de Ziff e Newman (chamaremos de algoritmo B). Para isso utilizamos duas técnicas: Cálculo da complexidade teórica (utilizando a notação de pior caso) da parte mais importante de cada um deles e utilização de um algoritmo mesclando os códigos dos dois para fazer a comparação entre as complexidades temporais desses algoritmos de forma experimental. Estudamos o código de cada algoritmo para conhecer de forma mais completa as rotinas e a forma como cada um deles simula a percolação. Após isso, modificamos os algoritmos para que eles utilizassem as mesmas ferramentas e fossem diferenciados apenas na parte essencial e crítica para o cálculo da complexidade que é a formação dos aglomerados.

RESULTADOS:

A partir do algoritmo resultante da modificação dos algoritmos A e B calculamos o tempo gasto pelo algoritmo de Ziff, que foi de 201,422s enquanto que o de Elias foi de 287,347s (diferença de 85,925s) para 100 execuções com lado da malha igual a 2048 (4.194.304 de sítios). Executamos o algoritmo que efetuou essas medições em um computador com a seguinte configuração: processador AMD Athlon(tm) 64 3800+ 2,4GHz e 512MB de memória RAM. Na estimativa teórica da complexidade os dois algoritmos apresentaram complexidades iguais a O(n). Isso nos diz que a função custo de cada algoritmo possui, no máximo, um comportamento linear e em um ambiente computacional ambos os algoritmos se comportariam de maneira equivalente, o que privilegia o algoritmo A, pois o mesmo possui uma estrutura que consegue efetuar a percolação em casos mais gerais que o algoritmo B. Na comparação experimental do tempo, o algoritmo de Ziff é ligeiramente mais rápido como podemos perceber na pequena diferença de tempo (85,925s) ao executarmos os algoritmos como lado L = 2048.

CONCLUSÃO:

Neste trabalho, foram estudados e comparados dois algoritmos que simulam o processo da percolação. Para isso, utilizamos não só conhecimentos de percolação, como também ferramentas da teoria de complexidade de algoritmos que possibilitaram a obtenção do resultado pretendido nesse estudo. Utilizamos duas técnicas para efetuarmos a comparação: construímos um algoritmo que possibilitasse a comparação do tempo de execução dos algoritmos em estudo que foram executados 100 vezes cada um e a partir do tempo total calculamos o tempo médio; a outra foi a utilização da técnica do pior caso para obtermos uma estimativa teórica do comportamento computacional de cada um deles.

Palavras-chave: percolação, complexidade de algoritmos, algoritmos de percolação.