Modelagem e Análise de Algoritmos Baseadas em Redes de Petri Coloridas e Hierárquicas

Local: 
Sala 1B132
Banca examinadora: 
Prof.ª Dr.ª Rita Maria da Silva Julia (orientadora) - FACOM/UFU
Prof. Dr. Stéphane Julia (coorientador) - FACOM/UFU
Prof. Dr. Carlos Roberto Lopes - FACOM/UFU
Prof. Dr. José Reinaldo Silva - Escola Politénica/USP

Este trabalho apresenta uma nova metodologia experimental que visa permitir a realização da modelagem e análise da performance de algoritmos recursivos estruturalmente complexos, os quais podem apresentar políticas de controle de fluxo de dados preditivas e/ou não-preditivas. A ferramenta utilizada para modelar os algoritmos foi a Rede de Petri Colorida e Hierárquica e para realizar a análise dos mesmos usou-se o ambiente CPN Tools. Como estudo de caso, foram escolhidos os algoritmos de busca serial Minimax e a versão fail-soft do Alpha-Beta combinado com Tabela de Transposição e Aprofundamento Iterativo. A metodologia proposta neste trabalho, é composta por cinco métodos. O primeiro método, consiste na modelagem da estrutura do algoritmo de busca serial Alpha-Beta usando uma Rede de Petri Colorida e Hierárquica e na simulação da evolução dinâmica do modelo por meio do CPN Tools, com o intuito de emular o comportamento recursivo existente. O segundo método, está baseado na modelagem da estrutura do algoritmo de busca Minimax associando-se o tempo ao modelo, de modo que, ao simulá-lo, faz-se uma avaliação da função de complexidade de tempo de execução do algoritmo e, posteriormente, uma comparação com resultados obtidos na teoria. Já o terceiro método, unifica as ideias utilizadas nos dois primeiros métodos para modelar o algoritmo Alpha-Beta e avaliar os seus tempos de execução por meio de simulações de cenários. Adicionalmente, o comportamento não-preditivo existente no referido algoritmo é considerado na sua modelagem. Para o quarto método, no sentido de apontar os pontos positivos e negativos da proposta desta pesquisa, é feito um comparativo dos resultados obtidos experimentalmente com os resultados apresentados em outras metodologias existentes na literatura. Por fim, o quinto método apresenta uma proposta de paralelização do algoritmo AlphaBeta com base nas simulações realizadas no seu modelo obtido, de modo a propiciar uma melhoria no tempo de execução desse algoritmo. Nesta pesquisa, os resultados parciais relacionados às três primeiras etapas mostram que a metodologia se apresenta de forma eficaz. De forma sucinta, observou-se que foi possível modelar a estrutura e as políticas de controle dos dois algoritmos escolhidos. Características como, comportamento recursivo e iterativo, controle não-preditivo do fluxos de dados e restrições de tempo foram modeladas com êxito de modo a permitir que se fizesse a simulação de diversos cenários e a obtenção de resultados consistentes. Os resultados obtidos nos experimentos até o momento, culminaram na publicação de um artigo em uma conferência com qualis B1 e na submissão de outros dois artigos em conferências com qualis A2 e B1.