Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/handle/123456789/17000
Title: Análise e comparação entre algoritmos de percolação
Authors: Silva, Isaac Dayan Bastos da
Keywords: Percolação;Complexidade de algoritmos;Algoritmos de percolação;Algoritmos de Ziff e Neuman;Algoritmo de Elias;Percolation;Algorithms complexity;Percolation algorithms;Newman and Ziff algorithm;Elias algorithm
Issue Date: 25-Jul-2008
Publisher: Universidade Federal do Rio Grande do Norte
Citation: SILVA, Isaac Dayan Bastos da. Análise e comparação entre algoritmos de percolação. 2008. 92 f. Dissertação (Mestrado em Probabilidade e Estatística; Modelagem Matemática) - Universidade Federal do Rio Grande do Norte, Natal, 2008.
Portuguese Abstract: 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
Abstract: In this work, we study and compare two percolation algorithms, one of then elaborated by Elias, and the other one by Newman and Ziff, using theorical tools of algorithms complexity and another algorithm that makes an experimental comparation. This work is divided in three chapters. The first one approaches some necessary definitions and theorems to a more formal mathematical study of percolation. The second presents technics that were used for the estimative calculation of the algorithms complexity, are they: worse case, better case e average case. We use the technique of the worse case to estimate the complexity of both algorithms and thus we can compare them. The last chapter shows several characteristics of each one of the algorithms and through the theoretical estimate of the complexity and the comparison between the execution time of the most important part of each one, we can compare these important algorithms that simulate the percolation.
URI: http://repositorio.ufrn.br:8080/jspui/handle/123456789/17000
Appears in Collections:PPGMAE - Mestrado em Matemática Aplicada e Estatística

Files in This Item:
File Description SizeFormat 
IsaacDBS.pdf526,7 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.