Hipergrafos de Dijkstra: Reconhecimento e Isomorfismo

• Ano de defesa: 2024
• Autor(a) principal: Cavadas, Leonardo de Almeida
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade do Estado do Rio de Janeiro; Centro de Tecnologia e Ciências::Instituto de Matemática e Estatística; Brasil; UERJ; Programa de Pós-Graduação em Ciências Computacionais
• Palavras-chave em Português: Hipergrafos; Hipergrafos de fluxo redutível; Programação paralela e estruturada; Isomorfismo; Hypergraphs; Reducible flow hypergraphs; Parallel and structured programming; Isomorphism; CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
• Link de acesso: http://www.bdtd.uerj.br/handle/1/23354

Um programa de computador frequentemente pode ter seu fluxo de controle representado por meio de grafos direcionados. Dijkstra apresentou os conceitos da programação sequencial estruturada como aquela que não contém a estrutura GO TO. Hetch e Ullman apresentaram os grafos direcionados de fluxo redutível, onde os grafos direcionados associados a um programa sequencial formam uma subclasse própria da classe dos grafos de fluxo redutível e esses grafos direcionados podem representar o fluxo de execução de um programa sequencial estruturado como descrito por Dijkstra. Dijkstra também estabeleceu o conceito de programação estruturada paralela introduzindo o comando PAR- BEGIN/PAREND. Bento et al. caracterizaram a classe dos grafos de Dijkstra os quais correspondem a grafos de fluxo de programas escritos usando programação sequencial estruturada, conforme descrito por Dijkstra. Bento et al. provaram que o reconhecimento desses grafos é linear, bem como a checagem do isomorfismo entre grafos dessa classe. Guedes e Markenzon introduziram o conceito de hipergrafos de fluxo redutível que estende, naturalmente, a classe dos grafos de fluxo redutível. A classe dos hipergrafos de fluxo redutíveis é uma superclasse própria da classe dos grafos de fluxo de programas paralelos estruturados. Nessa dissertação definimos os hipergrafos direcionados de Dijkstra como a classe que caracteriza os grafos de fluxo de programas paralelos estruturados que têm a estrutura paralela PARBEGIN/PAREND. Provamos que o reconhecimento desses hipergrafos é linear, bem como a checagem do isomorfismo entre hipergrafos dessa classe.