Análise e comparação entre algoritmos de percolação

AUTOR(ES)
DATA DE PUBLICAÇÃO

2008

RESUMO

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

ASSUNTO(S)

percolation algoritmo de elias algoritmos de ziff e neuman matematica aplicada algoritmos de percolação elias algorithm algorithms complexity newman and ziff algorithm percolação complexidade de algoritmos percolation algorithms

Documentos Relacionados