Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/448
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorPagliosa, Paulo Aristarco-
dc.contributor.authorDantas, Bianca de Almeida-
dc.date.accessioned2011-09-01T13:49:23Z-
dc.date.available2011-09-01T13:49:23Z-
dc.date.issued2006-
dc.identifier.urihttps://repositorio.ufms.br/handle/123456789/448-
dc.description.abstractO objetivo principal deste trabalho consistiu em estudar e detalhar o algoritmo paralelo PRAM para computar a extensão linear de um digrafo acíclico planar, devido a Kao e Klein [KAO93]. Para digrafos acíclicos gerais, a obtenção de uma extensão linear não é simples. Kao e Klein mostraram que no modelo PRAM ela só pode ser obtida por meio da computação do fecho transitivo do digrafo. Para a classe dos digrafos acíclicos planares, Kao e Klein apresentam um algoritmo paralelo PRAM para computar a extensão linear sem a necessidade de computar o fecho transitivo do digrafo. Esse algoritmo, entretanto, utiliza uma série de estruturas e definições próprias de teoria dos grafos, além de outros algoritmos para resolver problemas chaves em digrafos. Dentre estes, o principal algoritmo estudado foi o algoritmo paralelo PRAM para obtenção de árvores geradoras em digrafos fortemente conexos, denominado algoritmo do CD-PAR, devido a Kao e Shannon [KAO89]. Kao e Klein mostraram que, partindo do resultado do algoritmo do CD-PAR, pode-se obter uma decomposição em orelhas de digrafos acíclicos planares e, a partir desta, alcançar a extensão linear. Essa relação entre árvores geradoras e decomposição em orelhas é a base para o entendimento do algoritmo de extensão linear proposto por Kao e Klein e amplamente discutida neste trabalho.pt_BR
dc.description.abstractThis work main objective was to study and to detail a PRAM parallel algorithm to compute topological ordering of a planar acyclic digraph, proposed by Kao and Klein. It is not trivial to obtain a topological ordering of general acyclic digraphs. Kao and Klein showed that this ordering can only be achieved computing the digraph transitive closure. Concerning to planar acyclic digraphs, Kao and Klein proposed a PRAM parallel algorithm for computing topological ordering without computing the digraph transitive closure. However this algorithm uses a sort of data structures and definitions from Graph Theory, beyond other algorithms for solving some graph related key problems. Among these algorithms, we focused on a PRAM parallel algorithm for obtaining spanning trees in strongly connected digraphs. This algorithm was proposed by Kao and Shannon and is named CD-PAIR algorithm. Kao and Klein showed that, based on this algorithm result, it is possible to obtain an ear decomposition of planar acyclic digraphs and, further achieve a topological ordering. This relation between spanning trees and ear decomposition is the most important concept for the total comprehension of the Kao and Klein's topological ordering algorithm widely discussed on this work.pt_BR
dc.language.isoporpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectProgramação Paralelapt_BR
dc.subjectProgramação Orientada a Objetospt_BR
dc.subjectMétodo dos Elementos Finitospt_BR
dc.subjectAlgoritmos Úteis e Específicos-
dc.titleUm Framework para Análise Seqüencial e em Paralelo de Sólidos Elásticos pelo Método dos Elementos Finitospt_BR
dc.typeDissertaçãopt_BR
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Bianca de Almeida Dantas.pdf856,2 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.