Neste trabalho estudamos um pouco de Teoria dos Grafos, abordando diversas definições e teoremas interessantes. Apresentamos o Teorema das Quatro Cores, desde o surgimento do problema com Francis Guthrie. Analisamos a demonstração do teorema realizada por Alfred Bray Kempe e sua refutação através do contraexemplo de Percy John Heawood. Analisamos também a demonstração do Teorema das Cinco Cores de Percy John Heawood. Porém, apresentamos a primeira demonstração válida do Teorema das Quatro Cores, como sua particularidade de ter sido feita com o auxílio de um computador. O trabalho é concluído com uma análise sobre os benefícios que o conhecimento de Teoria dos Grafos pode render aos alunos do Ensino Básico, e como professor o pode trabalhar este assunto em sala de aula, inclusive abordando o problema de coloração de mapas. / In this paper we study Graph Theory, addressing various definitions and interesting theorems. We present the Four Color Theorem, since the origin of the problem with Francis Guthrie. We analyze the proof of the theorem presented by Alfred Bray Kempe, and its refutation by Percy John Heawood counter-example. We also analyze the Percy John Heawood demonstration of the Five Color Theorem. Finally, we present the first valid proof of the Four Colors Theorem, with its peculiarity of having been done with the aid of a computer. We conclude with an analysis of the beneficial that the knowledge of Graph Theory can render students of Basic Education, and how a teacher can work this topic in the classroom, including addressing the problem of map coloring.

O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma análise dos algoritmos exatos e de aproximação para resolver o problema. Também implementa alguns desses algoritmos e compara seus desempenhos. / The directed multicut problem is a classical problem in combinatorial optimization. It is NP-hard even for very simple families of instances. This work makes an analysis of the exact and approximation algorithms for the problem. It also implements some of these algorithms and compares their performances.

Submitted by Setor de Tratamento da Informa??o - BC/PUCRS (tede2@pucrs.br) on 2015-06-19T11:11:46Z No. of bitstreams: 1 470809 - Texto Completo.pdf: 6861498 bytes, checksum: 8ff1a79ef3ddb913c671a8d1f821428d (MD5) / Made available in DSpace on 2015-06-19T11:11:46Z (GMT). No. of bitstreams: 1 470809 - Texto Completo.pdf: 6861498 bytes, checksum: 8ff1a79ef3ddb913c671a8d1f821428d (MD5) Previous issue date: 2015-01-26 / With the use of resting state functional magnetic resonance imaging (rs-FMRI) we can analyze the functional connectivity between different brain areas. However, recent studies show that this connectivity undergoes fluctuations over time (also known as dynamic Resting State). In this study, the analysis of Graph Theoretical (GT) metrics will be used to assess the variability of the correlation between these areas, through a windowing technique. For this study, we used images of 15 patients with ADHD that underwent a clinical treatment with the medication (Ritalin?). Images were taken before treatment (Visit 1 - PRE) and after 6 months of treatment (Visit 2 - POST). We determined the GT metrics for windows between 75 and 150s generated from the correlation between the various groups after applying a mask that divided the brain into 190 regions. The results showed statistically significant differences between visits for the metric of the characteristic path length. Were also generated graphs that show the fluctuations of each of the metrics. GT analysis identified an increase in the average value of the characteristic path length after drug treatment for most patients. However, some patients behaved differently and therefore results are not conclusive. Furthermore, it was observed that there is a dependence of GT metrics based on the size of the window. Conclusion show that based on the analysis of the dynamics of the brain network by the GT metrics show to be an auxiliary tool in the diagnosis of ADHD, but still requires further studies to test the viability of this tool as a diagnostic test in neuroimaging. / Atrav?s da Resson?ncia Magn?tica Funcional no estado de repouso (RMf-er) podemos analisar a conectividade funcional entre as diversas ?reas do c?rebro. Entretanto, estudos recentes mostram que a correla??o desta conectividade sofre flutua??es ao longo do tempo (Dynamic Resting State). No presente trabalho, foi feita uma an?lise por interm?dio de m?tricas da Teoria dos Grafos da variabilidade da correla??o entre as ?reas cerebrais atrav?s de t?cnicas de janelamento. Para este estudo, foram utilizadas imagens de 15 pacientes com transtorno de d?ficit de aten??o com hiperatividade (TDAH) e que passaram por um tratamento cl?nico com o uso do medicamento (Ritalina?). As imagens de resson?ncia foram adquiridas antes do pr?-tratamento (Visita 1 - PR?) e ap?s 6 meses de tratamento (Visita 2 ? P?S). Foram desenvolvidas m?tricas de Teoria dos Grafos (TG) para janelas entre 75 e 150s geradas a partir da correla??o entre as diversas regi?es, ap?s aplicar uma m?scara que dividiu o c?rebro em 190 ?reas. Os resultados encontrados apresentaram dados estatisticamente relevantes para a m?trica do comprimento do caminho caracter?stico. Foram gerados tamb?m gr?ficos que apresentam as flutua??es de cada uma das m?tricas. Na an?lise dos gr?ficos foi poss?vel identificar um aumento do valor m?dio do comprimento do caminho caracter?stico ap?s o tratamento com o f?rmaco para a maioria dos pacientes. Entretanto, alguns pacientes tiveram comportamento oposto, n?o sendo portanto conclusivo. Al?m disso, observou-se que existe uma depend?ncia das m?tricas de TG para a janela adotada. Concluiu-se, baseado nos dados encontrados, que a an?lise da din?mica da rede cerebral pela m?trica dos grafos ? uma ferramenta auxiliar para o entendimento do comportamento funcional do c?rebro e dos dist?rbios, mas que ainda requer mais estudos para que venha a ser adotada como apoio ao diagn?stico em neuroimagem.

Ontologias são especificações formais e explícitas usadas para descrever entidades de um domínio e seus relacionamentos. Estatísticas recentes do projeto Linked Open Data (LOD) indicam a existência de milhares de ontologias heterogêneas publicadas na nuvem do LOD, impondo um desafio para a integração de ontologias. Um passo fundamental na integração é o emparelhamento, processo que obtém elementos correspondentes entre ontologias heterogêneas. Visando superar o desafio de efetuar o emparelhamento em larga escala, desenvolveu-se uma estratégia baseada em clusterização das ontologias, a qual particiona as ontologias em subontologias, clusteriza as subontologias e restringe o processo de emparelhamento aos elementos de um mesmo cluster. Porém, observa-se que as soluções do estado da arte necessitam explorar mais os múltiplos aspectos que as subontologias possuem. As clusterizações de cada aspecto podem ser combinadas, por meio de um consenso. Cluster Ensembles é uma técnica que permite obter esse consenso. Além disso, estudos comparativos indicaram que o uso de Cluster Ensembles Bayesianos (CEB) resulta em uma clusterização de maior acurácia do que a obtida por outras técnicas de Cluster Ensembles. Um dos principais objetivos deste trabalho foi desenvolver uma nova metodologia de emparelhamento de ontologias baseada em clusterização consensual de múltiplos aspectos de comunidades, de forma a estruturar um arcabouço metodológico, por meio do qual diferentes técnicas e aspectos podem ser incorporados e testados. De acordo com a metodologia desenvolvida neste trabalho, inicialmente aplicaram-se técnicas de Detecção de Comunidades para particionar as ontologias. Em seguida, consideraram-se os seguintes aspectos das comunidades obtidas: terminológico, estrutural e extensional. Fez-se, separadamente, a clusterização das comunidades segundo cada aspecto e aplicaram-se diferentes técnicas de clusterização consensual para obter um consenso entre as clusterizações de cada aspecto: CEB, técnicas baseadas em similaridades e técnicas baseadas em métodos diretos. Para os diferentes consensos, o processo de emparelhamento foi feito apenas entre elementos das ontologias que pertencessem a um mesmo cluster consensual. As soluções consensuais destacaram-se nos estudos de caso efetuados quanto à precisão e cobertura dos alinhamentos, enquanto a solução baseada no aspecto terminológico destacou-se quanto ao valor de F-measure. A principal contribuição deste trabalho relaciona-se à metodologia desenvolvida, que constitui um arcabouço metodológico, por meio do qual diferentes aspectos e técnicas podem ser incorporados e testados quanto ao seu desempenho de clusterização e de alinhamento de ontologias. / Ontologies are formal and explicit specifications used to describe entities of a domain and its relationships. Recent statistics of the Linked Open Data (LOD) project indicate the existence of thousands of heterogeneous ontologies in the LOD cloud, posing a challenge to ontology integration. A fundamental step in integration is matching, a process that finds correspondent elements between heterogeneous ontologies. Aiming to overcome the challenge of large-scale ontology matching, researchers developed a strategy based on clustering, which divides ontologies into subontologies, clusters subontologies and restricts the matching process to elements of the same cluster. However, state-of-the-art solutions need to explore more the multiple aspects that subontologies have. Clustering solutions of each aspect can be combined, by means of a consensus. Cluster Ensembles is a technique that allows obtaining this consensus. Besides, comparative studies indicated that Bayesian Cluster Ensembles has higher clustering accuracy than other Cluster Ensembles techniques. One of the main goals of this work was to develop a new methodology for ontology matching based on consensus clustering of multiple aspects of communities, structuring a methodological framework that enables the use and tests of different techniques and aspects. According to the methodology adopted in this work, initially, Community Detection techniques were applied to partition the ontologies. In the sequence, the following aspects of the communities were considered: terminological, structural and extensional. Clustering according to each aspect was performed separately and different consensus clustering techniques were applied to obtain a consensus among clustering solutions of each aspect: Bayesian Cluster Ensembles, techniques based on similarities and techniques based on direct methods. For the different consensuses, matching was done only between elements of the two ontologies that belonged to the same consensual cluster. For the case studies applied in this work, the consensual solutions were a standout in precision and recall, while the terminological-based solution was a standout in F-measure. The main contribution of this work is related to the developed methodology, which constitutes a methodological framework, through which different aspects and techniques can be incorporated and tested concerning their ontology clustering and alignment performance.

Orientador: Maria do Socorro Nogueira Rangel / Banca: Samuel Jurkiewicz / Banca: Cleonice Fátima Bracciali / Resumo: O objetivo desse trabalho é apresentar o problema de coloração em grafos sob diferentes perspectivas. Caracterizamos o polinômio cromático de um grafo e enunciamos algumas de suas propriedades. Apresentamos duas formulações matemáticas para o problema de coloração de vértices e um método de solução para cada formulação. Apresentamos e discutimos propostas de atividades para o desenvolvimento de uma Oficina de Coloração para alunos do Ensino Médio e Fundamental. / Abstract: In this work the graph coloring problem was presented under di erent perspectives. We define the chromatic polynomials of a graph and describe some of its properties. Furthermore, two solution methods for the vertex coloring problem, through integer programming formulation, has been presented. We propose and discuss some activities for the development of a Workshop for students of secondary school. / Mestre

A capacidade das células para responder corretamente a sinais externos e perceber mudanças no seu microambiente é a base do desenvolvimento, reparação de tecidos e de imunidade, bem como a homeostase do tecido normal. Transdução de sinal é o principal meio pelo qual as células respondem a sinais externos de seu ambiente e coordenam alterações celulares complexas. O estudo das vias de sinalização molecular permite-nos tentar compreender o funcionamento dessas transduções de sinais e, consequentemente, as respostas celulares a estímulos externos. Uma abordagem adequada para tais estudos é o uso de modelos matemáticos para simular a cinética das reações químicas que descrevem uma dada via de sinalização, o que nos permite gerar predições testáveis de processos celulares. Construir modelos cinéticos preditivos de vias de sinalização molecular através de dados de alto rendimento produzidos utilizando técnicas ômicas (i.e., genômica, transcriptômica, (fosfo-)proteômica) constitui um dos atuais desafios enfrentados pelos pesquisadores na área de Biologia Molecular. Recentemente, para lidar com este desafio, o arcabouço de e-Science SigNetSim foi introduzido pelo Grupo de Biologia Computacional e de Bioinformática do Instituto Butantan. Esse arcabouço permite fazer a descrição de vias de sinalização molecular através da descrição da estrutura de um modelo através de um conjunto de reações químicas, que por sua vez é mapeado para um sistema de Equações Diferencias Ordinárias (EDOs), numericamente simuladas e avaliadas. Todavia, modificações na estrutura das vias precisam ser feitas manualmente, o qual restringe severamente o número de estruturas da via que precisam ser testadas, especialmente no caso de modelos grandes. Portanto, diante desse panorama, este trabalho propõe o desenvolvimento de um método para modificar vias de sinalização molecular. Esse método se baseia no uso de bancos de dados de interatomas para fornecer um conjunto de espécies químicas candidatas para serem incluídas na via de sinalização. Um componente integrado ao arcabouço SigNetSim capaz de testar diferentes hipóteses de modificação de vias foi desenvolvido neste projeto utilizando a metodologia de heurística incremental. Para avaliar a eficiência do componente implementado, utilizamos como estudo de caso um modelo de vias sinalização de MAPKs e PI3K/Akt para realizar testes experimentais e analisar os resultados obtidos. / The ability of cells to respond correctly external signals and to perceive changes in their microenvironment is the basis for development, tissue repair and immunity as well as normal tissue homeostasis. Signal transduction is the primary means by which cells respond to external signals from their environment and coordinate complex cellular changes. The study of molecular signaling pathways allows us to understand the operation of each process of cellular signal transduction. The use of mathematical models to simulate the kinetics of chemical reactions that describe a given signaling pathway, allow us to generate testable predictions of the cell processos. To Build Kinetic predictive models to molecular signaling pathways through massive data omics produced using modern techniques, Genomics, transcriptomics, (Phospho) proteomics, is one of the current challenges faced by researchers in the field of molecular biology. Recently, the \\textit SigNetSim e-Science was introduced by the Biological Computacional and Bioinformatical Group from the Butantan Institute to face this challenge. This \\textit makes the description of molecular signaling pathways through a set of chemical reactions, which are mapped into a system of ordinary differential equations, this system will be numerically simulated and evaluated . However, changes in the structure of the pathways need to be updated manually presented in this work, which severely restricts the number of track structures that need to be tested, especially for the large models. Therefore, given this background, we present the method to modify the molecular signaling pathways. This method relies on the use of interactome database to provide a set of chemical species candidates to be included in the signaling pathway. An component integrated to SigNetSim framework able to test different hypotheses of pathways modification was developed in this project using the incremental heuristic methodology. To evaluate the implemented component, we used the MAPKs and PI3K/Akt pathways model as case study, in order to perform experimental tests and to analyze the obtained results.

Submitted by Denize Lourenço (biblicfp@cfp.ufcg.edu.br) on 2018-01-02T13:56:35Z No. of bitstreams: 1 EPITÁCIO SILVA LOPES - DISSERTAÇÃO PROFLETRAS 2016.pdf: 1320308 bytes, checksum: b62d818b4bc33dbceef15819251da066 (MD5) / Made available in DSpace on 2018-01-02T13:56:35Z (GMT). No. of bitstreams: 1 EPITÁCIO SILVA LOPES - DISSERTAÇÃO PROFLETRAS 2016.pdf: 1320308 bytes, checksum: b62d818b4bc33dbceef15819251da066 (MD5) Previous issue date: 2016-11-17 / A sintaxe constitui um campo de estudo que diz respeito à combinação entre as palavras para a construção da frase. O ensino de sintaxe da língua portuguesa é inerente à capacidade de compreensão e elaboração de textos orais e escritos, embora encontre dificuldades no ensino atual. A partir disso, foi realizada uma pesquisa sobre as principais correntes da sintaxe, a disposição dos componentes sintáticos nos livros didáticos com o objetivo geral de propor estratégias de utilização de múltiplos usos da Teoria dos Grafos no ensino de sintaxe com o período simples no 8º ano do Ensino Fundamental. Alguns estudiosos vêm apresentando propostas para a melhoria desse estudo a partir dessa modalidade de ensino. Para compreender o ensino de sintaxe, de acordo com as diretrizes dos Parâmetros Curriculares Nacionais (PCN), a teoria em voga sobre os tipos de sintaxe e a forma como esta está presente nas escolas, observa-se um distanciamento entre o que se propõe pelas teorias e o que é vivenciado nas salas de aula através do livro didático, disseminando a ideia de que aprender sintaxe é difícil. A Teoria dos Grafos, método que permite ao aluno visualizar a estrutura da frase, compreender a sua organização e auxiliar como um facilitador para a sua produção, melhorando o processo comunicativo tanto no aspecto da escrita como da oralidade, colabora para melhor assimilação do conteúdo ensinado. Trata-se de uma pesquisa baseada em estudos bibliográficos com fins de reflexão sobre o ensino do componente sintático presente no livro didático adotado pela escola, visto de forma fragmentada e isolada, o que justifica propor meios para melhoria do ensino e compreensão da sintaxe, fundamentada, principalmente, nas produções de Borba (1979), Franchi (2013), Borgatto (2012), Cereja (2015), para construção de um guia didático que aborda o ensino de sintaxe com a Teoria dos Grafos. / La sintaxis es un campo Lingüística Área de estudio que está relacionada con la combinación de las palabras para la construcción de la frase. La sintaxis de la educación de la lengua portuguesa es inherente a lo que se dice a la capacidad de comprensión y la preparación de textos orales y escritos, aunque tienen dificultades en los problemas educativos actuales. De esto, se realizó un estudio de las principales corrientes de la sintaxis, con el objetivo general de la propuesta de los múltiples usos de la Teoría de Grafos en la sintaxis simplemente periodo en el octavo grado de la escuela primaria la enseñanza. Algunos estudiosos han presentado propuestas para la mejora de este estudio de este tipo de educación. Para entender la sintaxis de la educación, de acuerdo con las directrices de los Parámetros Curriculares Nacionales (PCN) y la teoría en boga en los tipos de sintaxis y la forma en que esto está presente en las escuelas, hay una brecha entre lo que se propone teorías y lo que se vive en las aulas a través de los libros de texto, la difusión de la idea de que es difícil aprender la sintaxis. La teoría de grafos, método que permite a los estudiantes a visualizar la estructura de la oración, para comprender su organización y ayudar como facilitador para su producción, mejorando el proceso de comunicación, tanto en el aspecto de la escritura como la oralidad, contribuye a una mejor asimilación de los contenidos impartidos. Esta es una encuesta sobre la base de los estudios publicados con fines de reflexión sobre la enseñanza de componente sintáctico presente en el libro de texto adoptado por la escuela, como una forma fragmentada y aislada, lo que explica proponer formas de mejorar la enseñanza y la comprensión de la sintaxis, basadas, principalmente, en Borba productions (1979), Franchi (2013), Borgatto (2012), Cereja (2015), para la construcción de una guía didáctica que se ocupa de la sintaxis de la enseñanza con la Teoría de Grafos.

A teoria dos grafos é uma ferramenta matemática muito utilizada na resolução de problemas algorítmicos e computacionais em que se quer modelar conjuntos de elementos e relações entre estes elementos. Sistemas naturais e tecnológicos de diversos domínios podem ser representados matematicamente por grafos que possuem propriedades estatísticas bem conhecidas, sendo uma destas propriedades a distribuição de graus dos vértices do grafo seguindo a lei de potência (power law). Exemplos destes grafos, conhecidos como grafos power law são a internet, World-Wide Web, as redes sociais, redes biológicas. No contexto de problemas algorítmicos em grafos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos que pertencem à classe NP-Difícil (ou NP-Hard), mais especificamente no problema de cobertura por vértices. Neste trabalho será estudado experimentalmente o comportamento de um algoritmo baseado em uma estratégia gulosa para o problema de cobertura de vértices e compararemos com outro algoritmo de aproximação e com a solução exponencial ótima. Em particular esta solução será aplicada e analisada em redes complexas. / Graph theory is a mathematical tool used in solving many algorithmic and computational problems in that both sets of model elements and relationships between these elements. Most natural and technological systems can be mathematically modeled by graph having many well known properties, in particular the power law distribution of the vertex degree sequence. Examples of such graphs, called power law graphs are the Internet, World-Wide Web, social networks, biological networks. In the context of algorithmic problems on graphs, we are interested in problems in class NP-Hard, more specifically in the vertex cover problem. This work will be studied experimentally the behavior of an algorithm based on a greedy strategy for the vertex cover problem and compare with other approximation algorithms and with the exponential optimal solution. In particular this solution will be applied and analyzed in complex networks.

A crescente demanda por produtos de melhor qualidade, diferenciados e com custos competitivos tem forçado as manufaturas a se tornarem flexíveis, capacitando-as a responder às mudanças impostas pelo mercado. A flexibilidade permite que as empresas alcancem a customização desejada através da capacitação do sistema de responder e atuar em tempo real, mesmo em um ambiente de incertezas. Para atuar em tempo real, os sistemas de manufatura precisam de representações eficientes dos planos de produção. Muitas vezes, a atuação em tempo real torna-se inviável devido ao crescimento exponencial no número de planos de produção para cada máquina ou operação adicionada ao sistema. Uma possível solução para este problema é uso de representações adequadas para o espaço de estados. A escolha de uma representação adequada para o espaço de estados influencia na capacidade de reposta em tempo real, pois determina o desempenho computacional do sistema através da utilidade e eficiência dos algoritmos desenvolvidos, tornando possível explorar problemas clássicos de flexibilidade, tais como, seqüenciamento, otimização, etc. Entretanto, a geração de uma representação que trabalhe com o espaço de estados completo de uma manufatura é considerada um problema não polinomial (NP). Esta particularidade dificulta o desenvolvimento de algoritmos que trabalhem com uma manufatura flexível. Assim, a geração de uma representação, que trabalhe com pouca memória computacional e permita o desenvolvimento de heurísticas eficientes, é um importante desafio para uma avaliação efetiva da flexibilidade. Este trabalho objetiva o desenvolvimento de uma representação para o espaço de estados de uma manufatura com flexibilidade de seqüência. Na construção desta representação são aplicadas técnicas de modelagem baseadas na teoria dos grafos e nos princípios de álgebra booleana. Inicialmente, os grafos são utilizados para representar todas as seqüências de operações de uma manufatura, posteriormente estas seqüências são convertidas em formas normais disjuntivas (FND). Por fim, é apresentada uma possível aplicação da representação na FND em modelos de programação linear.

Submitted by Henrique Teixeira (henrique.oliv@gmail.com) on 2016-03-16T02:51:18Z No. of bitstreams: 1 Dissertacao.pdf: 1894861 bytes, checksum: af73e440cc555c69c32dbb74b4ba3f59 (MD5) / Approved for entry into archive by Renata de Souza Nascimento (renata.souza@fgv.br) on 2016-03-16T21:49:10Z (GMT) No. of bitstreams: 1 Dissertacao.pdf: 1894861 bytes, checksum: af73e440cc555c69c32dbb74b4ba3f59 (MD5) / Made available in DSpace on 2016-03-17T11:42:41Z (GMT). No. of bitstreams: 1 Dissertacao.pdf: 1894861 bytes, checksum: af73e440cc555c69c32dbb74b4ba3f59 (MD5) Previous issue date: 2016-02-18 / Starting from the idea that economic systems fall into complexity theory, where its many agents interact with each other without a central control and that these interactions are able to change the future behavior of the agents and the entire system, similar to a chaotic system we increase the model of Russo et al. (2014) to carry out three experiments focusing on the interaction between Banks and Firms in an artificial economy. The first experiment is relative to Relationship Banking where, according to the literature, the interaction over time between Banks and Firms are able to produce mutual benefits, mainly due to reduction of the information asymmetry between them. The following experiment is related to information heterogeneity in the credit market, where the larger the bank, the higher their visibility in the credit market, increasing the number of consult for new loans. Finally, the third experiment is about the effects on the credit market of the heterogeneity of prices that Firms faces in the goods market. / Partindo da ideia de que os sistemas econômicos se enquadram na teoria da complexidade, onde seus inúmeros agentes interagem entre si sem um controle central e que essas interações são capazes de alterar o comportamento futuro dos agentes e de todo o sistema, semelhante a um sistema caótico, incrementamos o modelo de Russo et al. (2014) para a realização de três experimentos com foco na interação entre bancos e empresas em uma economia artificial. O primeiro experimento diz respeito a Relationship Banking onde, segundo a literatura, a interação ao longo do tempo entre bancos e empresas é capaz de produzir benefícios mútuos, principalmente devido a redução da assimetria de informação entre eles. O experimento seguinte está relacionado a assimetria de informação no mercado de crédito, onde quanto maior o banco, maior sua visibilidade no mercado de crédito, elevando na mesma proporção as consultar para novos emprestimos. Por fim, o terceiro experimento é relativo aos efeitos no mercado de crédito da heterogeneidade de preços que as empresas se deparam no mercado de bens