Use este identificador para citar ou linkar para este item: https://repositorio.ufrn.br/jspui/handle/123456789/17000
Título: Análise e comparação entre algoritmos de percolação
Autor(es): Silva, Isaac Dayan Bastos da
Palavras-chave: 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
Data do documento: 25-Jul-2008
Editor: Universidade Federal do Rio Grande do Norte
Citação: 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.
Resumo: 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.
metadata.dc.description.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
URI: http://repositorio.ufrn.br:8080/jspui/handle/123456789/17000
Aparece nas coleções:PPGMAE - Mestrado em Matemática Aplicada e Estatística

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
IsaacDBS.pdf526,7 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.