[TESE DE DOUTORADO] Uma Abordagem para Avaliar o Desempenho de Algoritmos Baseada em Simulações Automáticas de Modelos de Redes de Petri Coloridas Hierárquicas

Local: 
Sala 1B132, Bloco 1B, Campus Santa Mônica
Data de Defesa: 
03/03/2017 - 14:00
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.ª Márcia Aparecida Fernandes - FACOM/UFU
Prof. Dr. José Reinaldo Silva - EP/USP
Prof. Dr. João Manuel Portela Gama - Universidade do Porto - Portugal

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 apresen-
tam 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 (aqui denominados algoritmos com
comportamento não-preditivo).  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 analisa-
dos, 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, por
exemplo,  dos  algoritmos  com  comportamento  não-preditivo.   Neste  cenário,  o  presente
trabalho propõe uma abordagem visual formal para avaliar o tempo de execução de al-
goritmos  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 é vali-
dada 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 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 minimi-
zar suas chances de sucesso:  os algoritmos seriais Minimax e Alpha-Beta (esse último,
com comportamento não-preditivo); e o algoritmo distribuído PVS. Os resultados obtidos
confirmam a correção da abordagem proposta.