Uma abordagem para avaliar o desempenho de algoritmos baseada em simulações automáticas de modelos de Petri coloridas hierárquicas

Among the various approaches established for analyzing the performance of algorithms in terms of runtime, one can highlight as examples, the asymptotic analysis, recurrence techniques, and probabilistic analysis. However, there are algorithms that present certain peculiarities, which make the use of these purely mathematical performance evaluation techniques inadequate or excessively difficult. This is the case of algorithms for which the runtime varies significantly for the same input data, due to its execution dynamics. The same happens in the case of distributed algorithms, where depending on the complexity of the distribution policy being used, the evaluation by means of analytical methods concerning the effect of a gradual increase in processors on runtime can become impractical. In situations such as these, in order to avoid the high mathematical complexity involved in the performance analysis, researchers have adopted alternatives based on empirical methods or visual modeling. However, both alternatives have drawbacks: in the case of empirical methods, they require the implementation of analyzed algorithms, which has a perverse effect especially in the case of distributed algorithms. This occurs, as they demand the acquisition beforehand of expensive multiprocessing hardware resources before knowing if the distribution proposal under investigation is in fact viable. On the other hand, those approaches based on visual models currently under use (based on graphs, automata and Unified Modeling Language) one notes that does not contain the necessary dynamic resources for dealing with the runtime evaluation of algorithms. In this scenario, the present study proposes a formal visual approach, in order to evaluate the algorithm runtime based on automatic simulations of Hierarchical Colored Petri Net models in the CPN Tools graphic environment. The proposed approach is validated through the calculation of the following parameters associated with the algorithms being used as a case study: the complexity function, real runtime, and in the case of distributed algorithms, speedup and efficiency. The cases studies were based on three relevant search algorithms used in the agents of the Artificial Intelligence, with the aim of defining the most appropriate actions that these agents need to execute in order to fulfil their objective, in an environment where the opponent tries to minimize their chances of success. The algorithms under consideration were the serial algorithms Minimax and Alpha-Beta; and the PVS distributed algorithm. The obtained results confirm the correction of the proposed approach.Tese (Doutorado)Dentre as várias abordagens consagradas para análise de desempenho de algoritmos em termos de tempo de execução, destacam-se, por exemplo, a análise assintótica, as técnicas de recorrências e a análise probabilística. Entretanto, há algoritmos que apresentam certas peculiaridades que tornam o uso dessas técnicas puramente matemáticas de avaliação de desempenho inadequadas ou excessivamente árduas. É o caso, por exemplo, de algoritmos cujo tempo de execução pode variar significativamente para um mesmo dado de entrada em função da dinâmica de execução. O mesmo acontece no caso de algoritmos distribuídos em que, dependendo da complexidade da política de distribuição utilizada, a avaliação por meio de métodos analíticos do efeito de um gradual incremento de processadores no seu tempo de execução pode tornar-se impraticável. Em situações como essas, a fim de evitar a alta complexidade matemática envolvida na análise de desempenho desses algoritmos, algumas alternativas baseadas em métodos empíricos ou em modelagem visual vêm sendo adotada pelos pesquisadores. Contudo, ambas alternativas apresentam inconvenientes: no caso dos métodos empíricos, eles requerem a implementação dos algoritmos analisados, o que tem um efeito perverso particularmente no caso dos algoritmos distribuídos, uma vez que eles demandam a aquisição prévia de recursos de hardware dispendiosos de multi-processamento antes mesmo de saber se a proposta de distribuição investigada, de fato, vale a pena. Já as abordagens baseadas em modelos visuais atualmente utilizadas (baseadas em grafos, autômatos e Unified Modeling Language - UML) não contam com os recursos dinâmicos necessários para lidar com a avaliação do tempo de execução dos algoritmos. Neste cenário, o presente trabalho propõe uma abordagem visual formal para avaliar o tempo de execução de algoritmos baseada em simulações automáticas de modelos de Redes de Petri Coloridas Hierárquicas (RdPCH) no ambiente gráfico CPN Tools. A abordagem proposta é validada por meio de cálculo dos seguintes parâmetros associados aos algoritmos usados como estudo de caso: a função de complexidade, o tempo de execução real e, no caso dos algoritmos distribuídos, o speedup e a eficiência. Foram usados como estudos de caso os seguintes três relevantes algoritmos de busca usados nos agentes da Inteligência Artificial com a finalidade de definir as ações mais apropriadas que tais agentes devem executar de modo a cumprir seu objetivo, com êxito, em um ambiente em que um oponente tenta minimizar suas chances de sucesso: os algoritmos seriais Minimax e Alpha-Beta; e o algoritmo distribuído PVS. Os resultados obtidos confirmam a correção da abordagem proposta