Made available in DSpace on 2016-08-29T15:33:12Z (GMT). No. of bitstreams: 1 tese_3542_.pdf: 1219514 bytes, checksum: 46e780a84760376a53aff9fb5e279285 (MD5) Previous issue date: 2010-08-23 / Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram presentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura.

Made available in DSpace on 2016-08-29T15:33:15Z (GMT). No. of bitstreams: 1 tese_4174_.pdf: 432544 bytes, checksum: 56e998c1c8c4b2e3ad13cf3720cfbe5f (MD5) Previous issue date: 2011-08-29 / A Teoria Espectral de Grafos (TEG) busca analisar propriedades dos grafos através de matrizes representativas de grafos e seus espectros. De uma propriedade proveniente da TEG, a autocentralidade, surge um importante invariante para o Problema de Isomorfismo de Grafos: se dois grafos são isomorfos então eles possuem autocentralidades proporcionais. Porém, esta propriedade não pode ser usada diretamente para resolução do Problema de Isomorfismo de Grafos Regulares (PIGR), pois todo grafo regular possui autocentralidades iguais. Este trabalho apresenta uma estratégia para resolver o PIGR através do uso das autocentralidades para podar a árvore de busca e restringir as possibilidades de mapeamento.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2015-05-20T18:18:24Z No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-05-20T19:03:59Z (GMT) No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Made available in DSpace on 2015-05-20T19:03:59Z (GMT). No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) Previous issue date: 2015 / Este trabalho explora a informação estrutural de relações entre variáveis binárias em problemas de Programação Inteira por meio de grafos de conflitos. Tal estrutura possui um papel fundamental na construção de métodos exatos e heurísticos de resolução. Nesse sentido, o presente trabalho propõe e desenvolve técnicas baseadas na análise de grafos de conflitos para obtenção de soluções factíveis e limites duais fortes para problemas de Programação Inteira. Foram desenvolvidas otimizações nas técnicas de detecção de conflitos, que permitiram a construção rápida de grafos densos mediante a análise de restrições. A obtenção de limites duais fortes para programas inteiros é realizada por uma rotina desenvolvida para geração de desigualdades válidas. Essa rotina é responsável por gerar cortes de clique e ciclo ímpar e inseri-los na relaxação linear, reforçando os limites duais e acelerando a convergência para a solução ótima. Para obter soluções factíveis para programas binários foi desenvolvido um resolvedor heurístico, que utiliza as relações lógicas entre variáveis para construir uma solução inicial e melhorá-la por meio de uma busca local. A busca local executa uma cadeia de movimentos a cada iteração, que permite corrigir a infactibilidade de uma solução ou, até mesmo, saltar de uma solução factível para outra. Considerando a produção de limites duais fortes, os resultados obtidos pela rotina de geração de desigualdades desenvolvida mostraram uma convergência mais rápida em relação à rotina de separação de cortes do resolvedor COINOR Branch-and-Cut. Em relação à obtenção de factibilidade, o resolvedor heurístico foi apto a gerar soluções para um número significativo de problemas de Programação Inteira Binária, considerando tempos restritos de execução. _________________________________________________________________________________ / ABSTRACT: This work explores the structural information of relations between binary variables in Integer Programming problems using conflict graphs. Such structure has a fundamental role in the construction of exact and heuristic solving methods. In this sense, the present work proposes and develops techniques based on the analysis of conflict graphs to obtain feasible solutions and strong dual bounds for Integer Programming problems. Optimizations were developed in the conflict detection techniques that allowed the fast construction of dense graphs through the constraints analysis. The obtaining of strong dual bounds for integer programs is performed by a routine developed for the generation of valid inequalities. This routine is responsible for generating clique and odd hole cuts and insert them into the linear relaxation, strengthening the dual bounds and accelerating the convergence to the optimal solution. To obtain feasible solutions for binary programs it was developed a heuristic solver, which uses the logical relations between variables to build an initial solution and improve it through a local search. Local search performs chains of movements at each iteration, which allows to fix infeasibilities of a solution or even jump from a feasible solution to another. Considering the production of strong dual bounds, the results obtained by the developed routine for generating inequalities showed a faster convergence compared with the cut separation routine of COIN-OR Branch-and-Cut solver. Regarding the production of feasible solutions, the heuristic solver was able to generate solutions to a significant number of Integer Binary Programming problems considering restricted runtimes.

Resumo: Buscas em grafos é uma das ferramentas mais simples e mais utilizadas para algoritmos em grafos. Um algoritmo de busca examina os vértices e as arestas de um grafo a partir de um vértice inicial e, sistematicamente visita um novo vértice por iterativa travessias em arestas incidentes a um vértice anteriormente já visitado. A ordem em que esses vértices são visitados definem uma enumeração desses vértices em um dado grafo. Na literatura disponível, poucos resultados teóricos são conhecidos sobre uma enumeração que pode ser gerada por um algoritmo de busca específico, embora buscas como em Largura e em Profundidade sejam algoritmos tradicionais e bem conhecidos na literatura atual. ecentemente, dois novos algoritmos, Busca em Largura Lexicográfica e a Busca da Cardinalidade Máxima, têm sido aplicados em uma grande variedade de problemas e, além desses, outras estratégias também são conhecidas, como a Busca em Profundidade Lexicográfica, da Vizinhança Maximal e do Rótulo Maximal, usadas para o reconhecimento de certas classes de grafos, por exemplo. Muito dos resultados obtidos nas aplicações desses algoritmos de busca dependem da simples caracterização da numeração que estes algoritmos podem computar. Neste trabalho, generalizamos o conceito de busca orientada por aresta para o caso de hipermultigrafo, apresentaremos características das enumerações e por fim provaremos que essas enumerações caracterizam um algoritmo de busca.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Diversos projetos nacionais e internacionais, como o dados.gov.br e o Linking Open Data, foram desenvolvidos com a finalidade de fomentar a criaÃÃo da Web de dados, que surge como uma nova abordagem para efetivamente publicar, recuperar e descrever dados distribuÃdos na Web. Diante desse cenÃrio, tais projetos enfrentam o desafio de criar e manter os dados estruturados que seguem os princÃpios do Linked Data, descritos no modelo de dados RDF e representados por ontologias. Esse desafio envolve outras tarefas complexas, tais como: reusar o vocabulÃrio das ontologias largamente utilizadas na elaboraÃÃo de novas ontologias (com a finalidade de promover a interoperabilidade e a integraÃÃo entre as aplicaÃÃes) e permitir a detecÃÃo de inconsistÃncias entre os termos de uma determinada ontologia. Com o objetivo de propor uma soluÃÃo para esse desafio, o problema de gerenciamento de ontologias foi abordado nesta dissertaÃÃo. Na literatura, existe uma grande variedade de trabalhos disponÃveis com diferentes enfoques e processos que propÃem o gerenciamento de ontologias. Entretanto, poucos trabalhos preocupam-se em auxiliar o especialista do domÃnio na elaboraÃÃo de uma ontologia que representa um entendimento correto sobre a semÃntica das ontologias envolvidas, visto que, para isso faz-se necessÃrio considerar as restriÃÃes lÃgicas das ontologias originais e propagÃ-las para as novas ontologias. AlÃm disso, foi percebido que, nos trabalhos anteriores, existe a necessidade de utilizar vÃrias ferramentas durante o processo de gerenciamento de ontologias, o que aumenta o esforÃo manual a ser despendido pelo especialista do domÃnio na elaboraÃÃo de novas ontologias. Sendo assim, a fim de oferecer algumas funcionalidades diferenciadas e de modo integrado ao gerenciamento de ontologias, foi desenvolvido um protÃtipo, denominado OntologyManagementTool. O protÃtipo desenvolvido considera as ontologias nÃo apenas como vocabulÃrio, mas como teorias lÃgicas, isto Ã, leva em conta tambÃm o seu conjunto de restriÃÃes. Cada ontologia manipulada à primeiramente normalizada para atender ao formalismo da LÃgica Descritiva, com um nÃmero especÃfico de restriÃÃes. Posteriormente, essa ontologia à transformada em um grafo de restriÃÃes, e assim, à possÃvel gerenciÃ-la a partir de um conjunto de operaÃÃes algÃbricas sobre o grafo. Destacam-se as seguintes operaÃÃes: uniÃo, interseÃÃo, diferenÃa eprojeÃÃo. ApÃs a execuÃÃo de cada uma dessas operaÃÃes, à possÃvel obter uma nova ontologia, bem como, o mapeamento entre as ontologias envolvidas. O trabalho proposto teve a sua aplicabilidade comprovada a partir de experimentos executados em ontologias descrevendo fontes de dados reais. Os resultados obtidos mostraram que a complexidade para gerar o grafo de restriÃÃes à linear em relaÃÃo ao nÃmero de restriÃÃes das ontologias; jà a complexidade do processamento das operaÃÃes algÃbricas (interseÃÃo, diferenÃa e projeÃÃo) à quadrÃtica em relaÃÃo ao nÃmero de vÃrtices do grafo de restriÃÃes, sendo importante evidenciar que o fator determinante para obtenÃÃo dessa complexidade à o procedimento escolhido para lidar com as restriÃÃes de inclusÃo, denominado fecho transitivo.

Submitted by Luiz Felipe Barbosa (luiz.fbabreu2@ufpe.br) on 2015-03-10T16:48:03Z No. of bitstreams: 2 DISSERTAÇÃO Paulo Orlando Vieira de Queiroz Sousa.pdf: 5635716 bytes, checksum: b2b109c6c80d0e60009d8dc1ced7fe08 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-11T17:34:13Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Paulo Orlando Vieira de Queiroz Sousa.pdf: 5635716 bytes, checksum: b2b109c6c80d0e60009d8dc1ced7fe08 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-02-20 / Uma ontologia é uma especificação formal explícita de uma conceituação compartilhada, que permite armazenar um conjunto de termos organizados hierarquicamente para descrever ou representar um conhecimento em um domínio. Ontologias são usadas em diversas áreas, tais como: Inteligência Artificial, com a taxonomia da lógica descritiva; Integração de Dados, para representar esquemas de bases de dados; Web Semântica, para produzir padrões de informação e repositórios semânticos; entre outras. O desenvolvimento de ontologias complexas têm motivado pesquisas para facilitar o entendimento e reuso de ontologias. A sumarização de ontologias é uma abordagem com o intuito de melhorar o entendimento de uma ontologia, produzindo um resumo da mesma. A abordagem inclui meios para identificar as partes mais importantes de uma ontologia e produzir uma versão resumida da ontologia original para um usuário ou uma atividade em particular. A produção de resumos possibilita visualizar as informações mais importantes de uma ontologia sem um conhecimento prévio da mesma. O objetivo principal desta dissertação é propor um método, baseado em medidas de centralidade de grafos e parâmetros definidos pelo usuário, para produzir uma versão resumida de uma ontologia. Neste método, a ontologia é representada em uma estrutura de grafo, na qual os vértices são representados por conceitos e as arestas por relacionamentos hierárquicos e propriedades entre conceitos. As medidas de centralidade, na ontologia representada em grafo, definem a relevância dos conceitos para produção do resumo. O método oferece um algoritmo parametrizável, capaz de produzir uma subontologia da ontologia original, que atenda aos parâmetros definidos pelo usuário e contenha os conceitos mais relevantes. Uma ferramenta para realizar a sumarização de ontologias foi desenvolvida de acordo com o método definido. Experimentos comparativos entre resumos gerados pela ferramenta com resumos produzidos por ferramentas semelhantes ou manualmente gerados por especialistas são apresentados, alcançando resultados comparativos próximos a 79,50%.

Orientador : Mario Jino / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-13T23:27:16Z (GMT). No. of bitstreams: 1 Carnassale_Mauro_M.pdf: 4907860 bytes, checksum: 9ae042cdd1fd83ffb5b10d25f8855a73 (MD5) Previous issue date: 1991 / Resumo: Grafos de programa têm sido utilizados há muito tempo e, apesar de serem um conceito tradicional, sua aplicabilidade atual é grande e crescente. Muitas ferramentas e alguns ambientes utilizam-se dessa representação da estrutura lógica do Programa para atingirem seus objetivos. O propósito deste trabalho é apresentar a arquitetura, aspectos fundamentais de implementação e principais aplicações de uma ferramenta que produz o grafo de programa a partir de programas escritos em diversas linguagens procedimentais. Os Programas são t raduzidos para uma linguagem intermediária, denominada LI, a partir da qual obtêm-se o grafo de programa e outros produtos relevantes. A ferramenta tambem aceita programas escritos diretament e em LI. Sua finalidade principal é apoiar outras ferramentas ou aplicações que se utilizam do grafo de programa / Abstract; Not informed. / Mestrado / Mestre em Engenharia Elétrica

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2007. / Submitted by Luis Felipe Souza (luis_felas@globo.com) on 2009-01-09T13:17:21Z No. of bitstreams: 1 Dissertacao_2007_JorgeSchtoltz.pdf: 2102171 bytes, checksum: a4bba0ce43d48ec2f9d4854022bc8eb4 (MD5) / Approved for entry into archive by Georgia Fernandes(georgia@bce.unb.br) on 2009-03-04T14:38:24Z (GMT) No. of bitstreams: 1 Dissertacao_2007_JorgeSchtoltz.pdf: 2102171 bytes, checksum: a4bba0ce43d48ec2f9d4854022bc8eb4 (MD5) / Made available in DSpace on 2009-03-04T14:38:24Z (GMT). No. of bitstreams: 1 Dissertacao_2007_JorgeSchtoltz.pdf: 2102171 bytes, checksum: a4bba0ce43d48ec2f9d4854022bc8eb4 (MD5) / O escalonamento estático de um programa, representado por um grafo dirigido acíclico de tarefas, em um ambiente multiprocessado, tem o objetivo de minimizar o tempo de conclusão do programa. Apesar das pesquisas nesta área terem obtido heurísticas eficientes, encontrar um escalonamento ótimo é um problema NP - Completo. Clusters de workstations podem ser utilizados no processamento paralelo de programas e devido à complexidade de integração entre os programas, o monitoramento e a simulação são efetuados através de ferramentas que gerenciam o cluster e a execução dos programas paralelos. Dentre as ferramentas analisadas, o PM2P, será utilizado como base de estudo devido ao conhecimento da ferramenta. O objetivo deste trabalho é o desenvolvimento e implementação na ferramenta citada um monitoramento periódico para verificar a disponibilidade das máquinas do cluster e re-escalonar os programas se houver necessidade ou ganho de desempenho. Para testar este monitoramento foram implementados, devido à carência de algoritmos na ferramenta, três algoritmos estáticos voltados para o escalonamento de tarefas que possam ser representados por um GDA (Grafo Dirigido Acíclico). Estes algoritmos funcionam de forma similar, gerando uma lista em ordem topológica das tarefas e àquelas pertencentes ao mesmo nível, portanto, concorrentes entre si, são ordenadas pelo maior ou menor tempo de execução. As tarefas são distribuídas de acordo com a disponibilidade das máquinas no cluster e o objetivo do algoritmo de escalonamento é manter o makespan gerado igual ao tempo do caminho crítico do grafo. Os resultados dos testes, as conclusões sobre o monitoramento e re-escalonamento serão demonstradas através de tabelas e mapas de Gantt para facilitar a visualização e o entendimento. Foram testados conjuntos de tarefas distintas que representam aplicações exemplo. Foi observado que aplicações rápidas, que finalizam sua execução concomitante ou logo após o tempo gasto para verificar a disponibilidade das máquinas no cluster, o monitoramento e o reescalonamento não são necessários e neste caso é recomendável o reinício da aplicação. Ao contrário, aplicações que demandam mais tempo para sua execução, o monitoramento e o re-início de algum programa no caso de indisponibilidade de uma máquina são importantes, uma vez que a aplicação continua sua execução com a nova arquitetura de máquinas, a partir do ponto de detecção da falha. Apesar do custo adicional para execução da atividade, conclui-se que há vantagens em se ter um cluster monitorado quando da execução dos programas paralelos utilizando a biblioteca MPI. ______________________________________________________________________________________________________ ABSTRACT / Static scheduling of a program represented by a directed acyclic graph task on a multiprocessor environment to minimize the program completion time is the goal. It is a wellknown problem of concurrent processing. Although the researches in this area already have reached heuristic efficient to find an optimal scheduling is a NP-Complete problem. The Cluster of Workstations can be used to the parallel processing of programs and due to the program interaction complexity, the monitoring and the simulation are made through frameworks that manage the cluster and the parallel program execution. Among the frameworks analyzed, the framework PM2P, will be used as the base study. The objective of this work is the development and implements a periodic monitoring to verify the machines availability at the cluster and rescheduling the programs whether is necessary or to improve the performance. It has been implemented, to test this periodic monitoring due to the framework algorithms lack new three static algorithms toward the scheduling of programs of tasks that could be represented by DAG (Directed Acyclic Graph). These three algorithms working in a similar way, each one create a topological order list of the tasks and they scheduling the tasks that belongs at the same level of the graph and ordering these tasks by the bigger or smaller execution time criteria. The tasks are sorted and distributed through the cluster machines in accordance with the availability of them. The scheduling goal is getting the graph makespan like the critical path time. The tests results, monitoring conclusions and the scheduling algorithms proposals will be demonstrated with tables and Gantt charts to a best exhibition and comprehension. The tests were over sets of different tasks that representing some real application. It was observed that applications with small execution time finish their at the same time or as soon as the framework check the cluster machines availability. In these cases are not necessary to rescheduling the applications and is recommended restart them. By the other hand, applications with big execution time, the programs monitoring and the restart of some program is important if any machine become unavailability. So, the application continues this execution at the restart point using the other workstations. Nevertheless the additional monitoring overhead, the conclusions show that exist advantages of monitoring the cluster when are executing a parallel programs using the MPI library with a big execution time.

Submitted by Marcos Samuel (msamjunior@gmail.com) on 2016-06-07T14:47:24Z No. of bitstreams: 1 Dissertacao Diogo.pdf: 861905 bytes, checksum: 035f09262025273ab8457d6f1200e5de (MD5) / Approved for entry into archive by Alda Lima da Silva (sivalda@ufba.br) on 2016-06-13T16:57:36Z (GMT) No. of bitstreams: 1 Dissertacao Diogo.pdf: 861905 bytes, checksum: 035f09262025273ab8457d6f1200e5de (MD5) / Made available in DSpace on 2016-06-13T16:57:36Z (GMT). No. of bitstreams: 1 Dissertacao Diogo.pdf: 861905 bytes, checksum: 035f09262025273ab8457d6f1200e5de (MD5) / O objetivo desta dissertação é estudar e apresentar alguns resultados em Percolação homogênea de elos para grafos hipercúbicos. O resultado principal deste trabalho é a diferenciabilidade contínua de k(p), o número médio de aglomerados por vértice no grafo. Para obtermos este resultado, serão utilizados argumentos em áreas distintas da Matemática, principalmente em Probabilidade, Combinatória e Teoria dos Grafos.

Resumo: Um dos problemas chave dos sistemas autômatos é o problema de alcançabilidade. A resolução deste mediante o grafo de alcançabilidade gera, sobretudo em sistemas do mundo real, o problema de explosão de estados. McMillan [12] propôs uma técnica chamada de unfolding – desdobramento – que gera uma nova rede, de complexidade menor que a do grafo de alcançabilidade, que contém o conjunto de estados alcançaveis, o que permite evitar a explosão de estados de sistemas modelados com redes de Petri. Esta técnica tem várias implementações, a maioria limitada para redes de Petri seguras, sendo que no contexto dos sistemas do mundo real, geralmente trabalha-se com um número limitado de recursos, frequentemente superior a uma unidade. Por esta razão, é importante disporse de uma implementação da técnica de desdobramento, mas para redes de Petri k-limitadas, que permitem modelar sistemas com um número limitado de recursos. Neste trabalho serão apresentados, além de conceitos importantes de redes de Petri e do processo de desdobramento, uma proposta de desdobramento para redes de Petri k-limitadas. Para a implementação foi escolhida uma das ferramentas de mais destaque na técnica de desdobramento. Após um estudo aprofundado desta ferramenta, ela foi modificada de forma a incorporar o desdobramento de redes k-limitadas. A proposta e a implementação foram validadas a partir de um estudo de caso. São apresentados e discutidos os resultados obtidos, as limitações da proposta e possíveis trabalhos futuros neste campo de pesquisa.