Solução numérica de descritores markovianos a partir de re-estruturações de termos tensoriais

Exportar este item:

Use este identificador para citar ou linkar para este item: https://tede2.pucrs.br/tede2/handle/tede/5091

Registro completo de metadados

Campo DC	Valor	Idioma
dc.creator	Czekster, Ricardo Melo	-
dc.creator.Lattes	http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4758052P1	por
dc.contributor.advisor1	Fernandes, Paulo Henrique Lemelle	-
dc.contributor.advisor1Lattes	http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4781822J3	por
dc.date.accessioned	2015-04-14T14:49:22Z	-
dc.date.available	2010-05-25	-
dc.date.issued	2010-03-29	-
dc.identifier.citation	CZEKSTER, Ricardo Melo. Solução numérica de descritores markovianos a partir de re-estruturações de termos tensoriais. 2010. 195 f. Tese (Doutorado em Ciência da Computação) - Pontifícia Universidade Católica do Rio Grande do Sul, Porto Alegre, 2010.	por
dc.identifier.uri	http://tede2.pucrs.br/tede2/handle/tede/5091	-
dc.description.resumo	Os formalismos estruturados foram definidos ao longo dos anos com o objetivo de aumentar o nível de abstração e oferecer uma alternativa de modelagem mais sofisticada do que a proporcionada pelas tradicionais Cadeias de Markov. Exemplos de formalismos estruturados que utilizam álgebra tensorial para o armazenamento de seus descritores são as Redes de Autômatos Estocásticos, as Redes de Petri Estocásticas Generalizadas Superpostas e as Álgebras de Processo. Tais descrições utilizam primitivas de modelagem entre seus componentes capturando sua semântica operacional e permitindo a sua análise ao retornarem índices quantitativos de desempenho quando são resolvidos numericamente. Os mecanismos atuais de solução usam propriedades da Álgebra Tensorial (clássica ou generalizada) para multiplicar termos tensoriais de eventos entre os estados dos modelos (i.e., um descritor Markoviano) por um vetor de probabilidade, que contém a solução estacionária ou transiente. Esta operação é chamada de Multiplicação Vetor-Descritor (MVD) e é realizada de três maneiras básicas: de forma esparsa (ineficiente em memória, eficiente em tempo), utilizando o Algoritmo Shuffle (eficiente em memória, ineficiente em tempo para algumas classes de modelos) ou através do Algoritmo Split, que é uma combinação das duas primeiras abordagens. A principal contribuição deste último foi a proposição de um método híbrido onde incrementa-se a memória (de forma razoável) para acelerar o cálculo efetuado por iteração. Entretanto, o principal desafio do Algoritmo Split é relativo à determinação de cortes de cada termo tensorial e em como re-estruturá-lo para reduzir o custo computacional por iteração, acelerando a convergência de modelos estruturados. Este trabalho aborda estes problemas, baseando-se em três eixos: i) na discussão das primitivas de modelagem para composição de sistemas através de formas mais abstratas de descrição, ii) nas diferentes formas de tratamento de termos tensoriais de descritores Markovianos para execução mais otimizada da MVD a partir de re-estruturações das ordens originais, e iii) na execução do Algoritmo Split com taxas constantes ou funcionais demonstrando os resultados obtidos para diversas classes de modelos. Para os casos observados, foi demonstrado através de experimentos que o melhor ganho, balanceando-se tempo e memória, é verificado quando as matrizes dos termos tensoriais são reordenadas, tratando as do tipo identidade na parte estruturada e avaliando-se os elementos funcionais uma única vez na parte esparsa. Ao avaliar as funções somente uma vez em todo o processo de MVD, converte-se os descritores generalizados para clássicos em tempo de execução e promove-se ganhos consideráveis em tempo para determinadas classes de modelos. Observou-se também que as atividades de sincronização ou comunicação entre os módulos ou partições envolvidas bem como o total de parâmetros das dependências funcionais realizam um papel crucial no desempenho obtido. A presente tese é finalizada identificando as classes de modelos mais adequadas para a utilização do Algoritmo Split, propondo formas de re-estruturação de descritores Markovianos que privilegiem a esparsidade e a existência de matrizes do tipo identidade para balancear os custos em memória e tempo de execução.	por
dc.description.provenance	Made available in DSpace on 2015-04-14T14:49:22Z (GMT). No. of bitstreams: 1 423499.pdf: 2268638 bytes, checksum: a9a287a49644290eaf88a8b8d38f9f10 (MD5) Previous issue date: 2010-03-29	eng
dc.format	application/pdf	por
dc.thumbnail.url	http://tede2.pucrs.br:80/tede2/retrieve/15006/423499.pdf.jpg	*
dc.language	por	por
dc.publisher	Pontifícia Universidade Católica do Rio Grande do Sul	por
dc.publisher.department	Faculdade de Informáca	por
dc.publisher.country	BR	por
dc.publisher.initials	PUCRS	por
dc.publisher.program	Programa de Pós-Graduação em Ciência da Computação	por
dc.rights	Acesso Aberto	por
dc.subject	INFORMÁTICA	por
dc.subject	SIMULAÇÃO E MODELAGEM EM COMPUTADORES	por
dc.subject	CADEIAS DE MARKOV - COMPUTAÇÃO	por
dc.subject	REDES DE AUTÔMATOS ESTOCÁSTICOS	por
dc.subject.cnpq	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO	por
dc.title	Solução numérica de descritores markovianos a partir de re-estruturações de termos tensoriais	por
dc.type	Tese	por
Aparece nas coleções:	Programa de Pós-Graduação em Ciência da Computação

Arquivos associados a este item:

Arquivo	Descrição	Tamanho	Formato
423499.pdf	Texto Completo	2,22 MB	Adobe PDF	Baixar/Abrir Pré-Visualizar ×

Mostrar registro simples do item Recomendar este item Visualizar estatísticas

PUCRS

Biblioteca Digital de Teses e Dissertações