(Universidade Federal do Rio Grande do Norte, 2008-07-25) Silva, Isaac Dayan Bastos da; Pereira, Marcelo Gomes; Freitas, Joaquim Elias de; ; http://lattes.cnpq.br/6051109030233375; ; http://lattes.cnpq.br/8115277730238592; ; Medino, Ary Vasconcelos; ; http://lattes.cnpq.br/7296244207920172
Nesta dissertação estudamos e comparamos dois algoritmos de percolação, um elaborado por Elias e o outro por Newman e Ziff, utilizando ferramentas teóricas da complexidade de algoritmos e um algoritmo que efetuou uma comparação experimental. Dividimos este trabalho em três capítulos. O primeiro aborda algumas definições e teoremas necessários a um estudo matemático mais formal da percolação. O segundo apresenta técnicas utilizadas para o cálculo estimativo de complexidade de algoritmos, sejam elas: pior caso, melhor caso e caso médio. Utilizamos a técnica do pior caso para estimar a complexidade de ambos algoritmos e assim podermos compará-los. O último capítulo mostra diversas características de cada um dos algoritmos e através da estima- tiva teórica da complexidade e da comparação entre os tempos de execução da parte mais importante de cada um, conseguimos comparar esses importantes algoritmos que simulam a percolação
