Orientador : Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-18T08:17:24Z (GMT). No. of bitstreams: 1 Saip_HerbertAlexanderBaier_M.pdf: 3945244 bytes, checksum: af2897a4f350aea0252f42478c71f837 (MD5) Previous issue date: 1993 / Resumo: O problema de emparelhamentos em grafos consiste em determinar um conjunto M de arestas do grafo, onde as arestas são disjuntas nos vértices. Em particular, estamos interessados em determinar emparelhamentos máximos, ou seja, de cardinalidade máxima. Existem muitas variações em torno do tema, o grafo pode ser: bipartido ou não, ponderado ou não. Neste trabalho apresentamos as principais técnicas para se projetar os algoritmos mais eficientes que resolvem o problema de emparelhamentos máximos, ponderados ou não, em grafos bipartidos. Também descrevemos os principais algoritmos, seqüenciais e paralelos, que resolvem este problema. O Capítulo 2 apresenta os principais algoritmos para resolver o problema em grafos bipartidos não ponderados: o algoritmo de Hopcroft e Karp, o algoritmo paralelo de Kim e Chwa e o algoritmo paralelo de Goldberg, Plotkin e Vaidya. O Capítulo 3 apresenta os principais algoritmos para resolver o problema em grafos bipartidos ponderados: o algoritmo de Edmonds e Karp, o algoritmo com escalonamento de Gabow, o algoritmo com escalonamento e aproximação de Gabow e Tarjan, o algoritmo paralelo de Goldberg, Plotkin e Vaidya e o algoritmo paralelo de Gabow e Tarjan. O Apêndice A contém uma tabela dos principais algoritmos para resolver o problema no caso em que os grafos não são bipartidos / Abstract: The matching problem in graphs consists in determining a vertex disjoint set M of edges of the graph. In particular, we are interested in finding maximum matchings, that is, matchings of maximum cardinality. There are many variations around this problem, the graph can be: bipartite or general, weighted or not. In this work we present the main techniques to design the most efficient algorithms that solve the problem of maximum matching, weighted or not, in bipartite graphs. We also describe the main algorithms, sequential and parallel, to solve this problem. Chapter 2 contains the most important algorithms to solve the problem for non weighted bipartite graphs, namely, the algorithm of Hopcroft and Karp, the parallel algorithm of Kim and Chwa, and the parallel algorithm of Goldberg, Plotkin and Vaidya. Chapter 3 contains the most important algorithms to solve the problem for weighted bipartite graphs, namely, the algorithm of Edmonds and Katp, the scaling algorithm of Gabow, the scaling and approximation algorithm of Gabow and Tarjan, the parallel algorithm of Goldberg, Plotkin and Vaidya and the parallel algorithm of Gabow and Tarjan. In Appendix A it is given a table which describes briefly the most important algorithms for solving the general problem, in which the graph is not bipartite / Mestrado / Mestre em Ciência da Computação

Orientador : Roberto de Alencar Lotufo / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-01T04:56:56Z (GMT). No. of bitstreams: 1 Silva_WellingtonDioliceFelixda_D.pdf: 935006 bytes, checksum: 11b650203be2a75c0752f563a298638b (MD5) Previous issue date: 2001 / Doutorado

Orientadores: Leo Pini Magalhães, Alberto Barbosa Raposo / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T04:02:08Z (GMT). No. of bitstreams: 1 Cruz_AdailtonJoseAlvesda_D.pdf: 2075694 bytes, checksum: 3f08ec5e5787a8b5f92fc0b7990a402c (MD5) Previous issue date: 2004 / Resumo: Um dos desafios relacionados à coordenação em ambientes computacionais é a geração de estruturas para equacionar possíveis conflitos decorrentes de relacionamentos de dependências entre as atividades deste ambiente. Este trabalho apresenta uma metodologia para automatizar a geração de mecanismos de coordenação em ambientes computacionais. Estes mecanismos são gerados a partir dos comportamentos temporais especificados para as atividades executadas no ambiente. Permite-se especificar comportamentos temporais alternativos e atividades alternativas, os quais podem ser selecionados em tempo de processamento mudando assim as relações temporais entre as atividades e/ou as atividades que participam destes comportamentos. O algoritmo proposto para este fim implementa uma política de coordenação global permitindo-se que a execução de uma atividade aconteça somente quando não violar qualquer restrição temporal do ambiente. A identificação e modelagem das restrições temporais que cada atividade deve atender resultam no mecanismo de coordenação, obtido em tempo linear no número de atividades. Exploram-se as capacidades de encapsulamento e compactação das redes de Petri coloridas na modelagem dos mecanismos de coordenação sem vincular o uso da metodologia a um conhecimento prévio deste sistema formal (redes de Petri coloridas) / Abstract: One of the challenges related to the coordination of computational environments is the generation of structures to address possible conflicts related to dependences among the activities of these environments. This work presents a methodology to automate the generation of coordination mechanisms for computational environments. These mechanisms are generated from the temporal behaviors specified for the activities executed in the environment. It is possible to specify alternative temporal behaviors and alternative activities, which can be selected in processing time changing temporal relationships among the activities and/or the activities that participate in these behaviors. The algorithm proposed for this implements a global coordination policy, allowing that the execution of an activity only occurs when this doesn't violate any temporal restriction of the environment. The identification and modeling of the temporal restrictions that each activity should satisfy result in the coordination mechanism, obtained in linear time in the number of activities. The modular and compacting capacities of colored Petri nets are explored in the modeling of the coordination mechanisms without connecting the use of the methodology to a previous knowledge of this formal system (colored Petri nets) / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

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.

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

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.

Orientador: Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-14T01:00:50Z (GMT). No. of bitstreams: 1 Silva_LeilaMacieldeAlmeidae_M.pdf: 2512572 bytes, checksum: bac1797d1e4cff92457eeaac832615b5 (MD5) Previous issue date: 1991 / Resumo: Neste trabalho é desenvolvido o estudo de fluxos inteiros em grafos, especificamente as Conjeturas de Tutte sobre a existência de k-fluxos (k = 3,4,5) que generalizam teoremas sobre coloração de grafos planares. A dissertação consiste de cinco capítulos. O capítulo 1 apresenta as Conjeturas de Tutte, além de um breve histórico sobre coloração de grafos. O capítulo 2 apresenta relações entre colorações de grafos planares, fluxos inteiros e fluxos modulares. O capítulo 3 apresenta configurações redutíveis, ou seja, subgrafos que não ocorrem em contra-exemplos mínimos para as Conjeturas de Tutte. O capítulo 4 apresenta os seguintes resultados conhecidos sobre a Conjetura dos 5-' fluxos: teorema dos 8-fluxos (Jaeger), teorema dos 6-fluxos (Seymour) e teorema dos 5-fluxos para grafos em superfícies de gênus baixo (Younger Moller-Carstens Drinkmann). O capítulo 5 apresenta os seguintcs resultados conhecidos sobre a Conjetura dos 3-fiuxos: teorema dos 4-fluxos (Jaeger) e teorema dos 3-fiuxos para grafos planares (Grotzsch; Grünbaum-Aksionov; Steinberg- Younger). / Abstract: A study of integer flows in graphs is developed, specifically on Tutte's Conjectures on the existence of k-flows (k = 3,4,5) that generalize theorems about planar graph colourings. This work consists of five chapters. The first chapter presents Tutte's Conjectures and a brief historical review of graph colouring. Chapter 2 presents relations among planar graph colouring, integer flows and modular flows. Chapter 3 presents reducible configurations, that is, subgraphs that do not occur in minimal counter-examples for Tutte's Conjectures. Chapters 4 presents well ' known results on the 5-flow Conjecture: Jaeger's 8-flow theorem, Seymour's 6flow theorem and the 5-flow theorem for graphs embedded on surfaces of low genus (Younger; Mõller-Carstens-Dririkmalin). Chapter 5 presents well known results on the 3-fiow Conjecture: Jaeger's 4-flow theorem and the 3-flow theorem for planar graphs (Grõtzsch; Grünbaum-Aksionov, Steinberg-Younger). / Mestrado / Mestre em Ciência da Computação

Orientador : Claudio L. Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-15T05:25:59Z (GMT). No. of bitstreams: 1 MendoncaNeto_CandidoFerreiraXavierde_M.pdf: 1216674 bytes, checksum: 8e85895a8cb7f162a8e6807b1c063822 (MD5) Previous issue date: 1987 / Resumo: O primeiro capítulo introduz a noção de grafos perfeitos e as antigas conjeturas de Berge. A primeira delas, demontrada por Lovász, consta do capítulo 1 com o nome de Teorema dos Grafos Perfeitos. O segundo capítulo apresenta propriedades fundamentais dos grafos críticos (i. é, imperfeitos minimais) e os chamados grafos particionáveis. O capítulo termina com a apresentação dos grafos de cliques máximos de Tucker. O terceiro e último capítulo apresenta uma variada coleção de classes de grafos perfeitos. Foi consegui da uma tênue unificação de algumas dessas classes. O apêndice considera a segunda conjetura, a chamada conjetura "forte", e apresenta um resumo de algumas classes para as quais a conjetura vale / Abstract: The first chapter introduces the notion of perfect graphs and Berge's old conjecture, proved by Lovász, appears in chapter 1 under the name or Perfect Graphs Theorem. The second chapter presents fundamental properties of critical graphs (i. e., minimal imperfect graphs) and the so-called partitionable graphs. The chapter concludes with a presentation of Tucker's maximum clique graphs. The third and the last chapter presents a broad colection or classes of perfect graphs. The chapter presents a weak unification or these classes. The appendix analyzes the second conjecture, the so-called "strong" conjecture, and presents a survey of some classes over which this conjecture holds / Mestrado / Mestre em Ciência da Computação

Orientador: Armando Freitas da Rocha / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-07-18T11:20:45Z (GMT). No. of bitstreams: 1 Sato_AdemarTakashi_M.pdf: 3266616 bytes, checksum: b3d9f01577317b8eff12b4ed7e347d93 (MD5) Previous issue date: 1992 / Resumo: O trabalho apresenta a proposta de um Sistema Inteligente para Elaborar um Projeto de Perfuração de um Poço de Petróleo, que engloba o tratamento da base de dados, grafo de conhecimento para a escolha de poços de correlação, e recomendações para o posicionamento das sapatas com um grafo de conhecimento. Para tanto foram utilizadas diversas teorias e técnicas dentro da Inteligência Artificial. A aquisição do conhecimento de textos em linguagem natural, para a organização da base de dados utilizada, foi feita em um programa computacional, baseada em Redes Neurais Nebulosas e aprendizado evolutivo. A estruturação em relatórios que sintetizam um aglomerado de informações da base de dados, compreende a noção de programação orientada por objetos, e a construção de diversos grafos de conhecimento. A explicitação do conhecimento dos especialistas em Grafos de Conhecimento, que se baseiam em Redes Neurais Nebulosas, mostram-se adequados, devido a facilidade de se visualizar o problema em questão, e também. da facilidade de se efetuar a manutenção (aprendizado evol utivo) de eventuais correções / Abstract: The work presents a proposal of a Well Drilling Project Expert System, which includes database treatment, knowledge graph for correlation well choice, and recommendations for positioning casing shoes with a knowledge graph. Accordingly several Artificial Intelligence theories and techniques were used. A fuzzy neural net based and self leaming computer program was used for natural language text based knowledge acquisition. Structuring reports that summarize several database information involves an object oriented programming approach and several knowledge graphs. The experts knowledge explicitation through fuzzy neural nets based knowledge graphs are well-suited for modelling the problem in question and easing life cycle system maintenance through self learning techniques / Mestrado / Mestre em Engenharia de Petróleo