Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-16T02:00:59Z (GMT). No. of bitstreams: 1 Taube_JaimedeMattos_M.pdf: 1255661 bytes, checksum: ff5047b766e8267439eee9debee809b1 (MD5) Previous issue date: 1992 / Resumo: Nesta dissertação é feito um estudo problema do carteiro chinês: as diferentes apresentações, formulações e métodos de resolução. Foi feita uma implementação do método de resolução do problema definido em redes não orientadas que utiliza a teoria de emparelhamento. Finalmente, é feito o estudo de um problema de distribuição de jornal. / Abstract: Not informed. / Mestrado / Mestre em Matemática Aplicada

Orientador : Tomasz Kowaltowski / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-17T01:31:31Z (GMT). No. of bitstreams: 1 BreternitzJunior_Mauricio_M.pdf: 1239855 bytes, checksum: d471fe519d92ebf63f59d23b8a867ce4 (MD5) Previous issue date: 1984 / Resumo: Este trabalho descreve a implementação de um mecanismo de alocação de registradores em programas estruturados, através da técnica de coloração de grafos sugerida por Chai tin.. O problema da coloração é resolvido colorindo-se individualmente uma série de sub~grafos do grafo de interferências global, escolhidos de acordo com a estrutura do programa. Técnicas de análise de fluxo são utilizadas para construir os grafos de interferência / Abstract: Not informed / Mestrado / Mestre em Matemática

Um emparelhamento em um grafo é um conjunto de arestas duas a duas não adjacentes. Dado um grafo G com pesos em suas arestas, o problema do emparelhamento de peso é máximo é encontrar um emparelhamento cuja soma dos pesos de suas arestas é máxima. Neste trabalho estudamos diferentes soluções para esse problema. Estudamos algoritmos combinatórios que resolvem o problema no caso em que G é bipartido e no caso geral. O algoritmo de Edmonds é um algoritmo polinomial cuja complexidade de tempo é O(n^4), onde n é o número de vértices do grafo G. Discutimos nesse trabalho nossa implementação desse algoritmo. Num trabalho de 1985, Grötschel e Holland propuseram o uso de ferramentas de programação linear para resolver o mesmo problema. O método chamado de planos-de-corte baseia-se em um resultado de Padberg e Rao de que o problema da separação associado ao poliedro dos emparelhamentos pode ser resolvido em tempo polinomial. Neste trabalho fizemos implementações dos dois métodos e os utilizamos para resolver diversos tipos de instâncias do problema. Nossa conclusão é que o método poliédrico, apesar de utilizar ferramentas genéricas, é bastante eficiente na prática. / A matching in a graph G is a set of pairwise disjoint edges of G. Given a graph G with edge weights, we define the maximum weight matching problem as that of finding a matching which maximizes the sum of its weights. In this thesis we study different solutions to this problem. We studied combinatorial algorithms that solve this problem in the case where G is bipartite and also in the general case. Edmonds algorithm [Edm65a] is a polynomial time algorithm with complexity O(n4 ), where n is the number of vertices in the graph G. We discuss in this document our implementation of this algorithm. In a paper from 1985, Gr tschel & Holland [GH85] discussed the use of linear programming o tools for solving the maximum weight matching problem. This so called cut-plane method relies on a result by Padberg & Rao [PR82] that proves that the separation problem associated with matching polyhedron is solvable in polinomial time. In this work we implemented both methods and used then to solve different instances of the problem. Our conclusion is that the polyhedral method, although using generical tools is very efficient in practice.

Submitted by Leonardo Rodrigues Mattos da Costa (leorodrigues.ence@gmail.com) on 2016-08-24T13:13:57Z No. of bitstreams: 1 algoritmos-geneticos-aplicados (1).pdf: 3144047 bytes, checksum: 998963b49b6ea865ce1cbaecc897ea61 (MD5) / Approved for entry into archive by Janete de Oliveira Feitosa (janete.feitosa@fgv.br) on 2016-08-29T13:58:24Z (GMT) No. of bitstreams: 1 algoritmos-geneticos-aplicados (1).pdf: 3144047 bytes, checksum: 998963b49b6ea865ce1cbaecc897ea61 (MD5) / Approved for entry into archive by Marcia Bacha (marcia.bacha@fgv.br) on 2016-09-05T13:48:39Z (GMT) No. of bitstreams: 1 algoritmos-geneticos-aplicados (1).pdf: 3144047 bytes, checksum: 998963b49b6ea865ce1cbaecc897ea61 (MD5) / Made available in DSpace on 2016-09-05T13:49:02Z (GMT). No. of bitstreams: 1 algoritmos-geneticos-aplicados (1).pdf: 3144047 bytes, checksum: 998963b49b6ea865ce1cbaecc897ea61 (MD5) Previous issue date: 2016-03-31 / Concerns about the spread of disease affect both the population in their daily life and public health policy in Brazil and worldwide. The Brazilian Ministry of Health estimates that 2.5 billion people across the globe live in regions where dengue fever is an endemic disease, and approximately 50 million people are infected each year. In Brazil, new disease outbreaks occur every 3 to 5 years, generally associated with the introduction of a new serotype in the country. The last outbreak occurred in 2013 with the introduction of the so-called type-4 dengue virus. Surveillance of mosquito reproduction and infestation includes, among other methods, the use of “ovitraps” – traps where mosquitoes lay their eggs, which are considered one the best alternatives for detecting dengue and yellow fever outbreaks. The aim of this study is to reduce the sample size of the system for capturing dengue mosquito eggs used by the city of Rio de Janeiro. With this, it will be possible to increase the frequency of data collection from a monthly to a weekly basis without increasing costs, while maintaining the quality of estimates obtained from the sample. The sampling grid reduction problem is associated with a combinatorial optimization problem belonging to the NP class where, given a sample of size , a subset of elements of size * needs to be found such that the estimation error is less a preset limit. From this definition, it is possible to turn the sample reduction problem into a case of the 0/1 knapsack problem. Using this association, this paper proposes objective functions that incorporate spatio-temporal dependence effects as well as an approach using biased random-key genetic algorithms / A preocupação com a disseminação de doenças é presente tanto no dia-a-dia da população quanto nas pautas governamentais de saúde pública de cidades em todo o Brasil e no mundo. Segundo dados da Organização Mundial da Saúde, é estimado que no mundo, 2.5 bilhões de pessoas morem em regiões onde a Dengue é endêmica, sendo que aproximadamente 50 milhões de pessoas são infectadas anualmente. No Brasil, em particular, foram registrados ciclos de 3 a 5 anos para um novo surto da doença, geralmente associados à entrada de um novo sorotipo no país, sendo a última epidemia registrada em 2013, com a entrada da chamada ``Dengue do tipo 4''. Dentre as diversas formas de monitoramento da reprodução e infestação do mosquito, o uso das chamadas ``Ovitrampas'', armadilha nas quais os mosquitos depositam seus ovos, vem sendo apontado como uma das melhores alternativas para detecção de surtos de Dengue e Febre Amarela, \cite{marques1993comparative,chadee1990metodos}. O objetivo principal deste estudo é a redução do tamanho da amostra do sistema de captura de ovos de mosquito da dengue, realizado pela prefeitura do Rio de Janeiro, viabilizando um aumento na frequência da coleta de dados, antes mensal, para uma frequência semanal, sem impactar nos custos do projeto e preservando a qualidade das estimativas obtidas a partir da amostra. O problema de redução da malha amostral está associado a um problema de otimização combinatória que pertence à classe NP, onde, dada uma amostra de tamanho $n$, desejamos encontrar um subconjunto de elementos amostrais de tamanho $n^{*}$ tal que o erro de estimação seja menor que um limite pré-estabelecido. A partir dessa definição, é possível estabelecer a correspondência do problema de redução amostral com o \textit{Problema da mochila 0-1}. Utilizando esta associação, serão propostas funções objetivo onde são incorporados efeitos de dependência espaço-temporal, além de uma abordagem heurística baseada nos Algoritmos Genéticos de Chaves Aleatórias Viciadas.

Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-16T18:39:44Z (GMT). No. of bitstreams: 1 Domingues_DeborahPereira_M.pdf: 925996 bytes, checksum: 6a430acfaa4475e03a36ee7e09bbf42a (MD5) Previous issue date: 2010 / Resumo: Neste trabalho estudamos dois importantes tópicos em combinatória. O primeiro deles é o Teorema Enumerativo de Pólya. No capítulo 2 é dada uma demonstração deste teorema usando o Teorema de Burnside. Também neste capítulo, encontram-se algumas de suas diversas aplicações. O segundo tópico trata de Teoria de Partições. Esta dissertação aborda alguns objetos de estudo desta área. O primeiro objeto é o método de Partition Analisys, usado para achar funções geradoras de vários tipos de interessantes funções de partição. Ainda relacionado a funções geradoras, o capítulo 3 aborda um pouco sobre q-séries. O segundo objeto é o método gráfico, que utiliza a representação gráfica de Ferrers para uma partição. Ainda neste capítulo, são usados os conceitos de quadrado de Durfee e símbolo de Frobenius para provar algumas identidades. / Abstract: This paper presents two important topics in combinatorics. The first one is the Pólya Enumeration Theorem. In chapter 2 is given a demonstration of this theorem by Burnside's Theorem. Also in this chapter are some of their various applications. The second topic deals with the Theory of Partition. This dissertation addresses some aspects of the study on this area. The first is Partition Analysis, this method is used to find the generating functions of various kinds of interesting partition functions. In the third chapter we deal with q-series which is also related to generating functions. The second is the graphical method, which uses a Ferrers's graphical representation of a partition. In addition, we use the concepts of Durfee square and Frobenius's symbol to prove some identities. / Mestrado / Mestre em Matemática

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-17T07:58:08Z (GMT). No. of bitstreams: 1 Porto_ClaudiaAkemiFurushima_M.pdf: 1805902 bytes, checksum: 15341772d15a37d8642fa403d27fbd6a (MD5) Previous issue date: 2010 / Resumo: O resumo poderá ser visualizado no texto completo da tese digital / Abstract: The abstract is available with the full electronic digital document / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

DANTAS, Allberson Bruno de Oliveira. Uma Interface de Programação Distribuída para Aplicações em Otimização Combinatória. 2011. 79 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Programa de Pós-Graduaçõa em Ciência da Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T16:25:19Z No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T16:27:03Z (GMT) No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) / Made available in DSpace on 2016-05-24T16:27:03Z (GMT). No. of bitstreams: 1 2011_dis_abodantas.pdf: 805347 bytes, checksum: c9671608a7d738f843239856e546e201 (MD5) Previous issue date: 2011 / This work was motivated by the need of exploiting the potential of distributed paralelism in combinatorial optimization applications. propose a distributed programming interface, To achieve this goal, we in which we cherish two main requirements: e ciency and reuse. The rst stems from the need of HPC (High applications require maximum possible performance. Performance Computing) Therefore, we specify our interface as an extension of the MPI library, which is assumed to be e cient for distributed applications. The reuse requirement must make compatible two important features: asynchronism and collective operations. Asynchronism must be present at our interface, once most of combinatorial optimization applications have an asynchronous nature. Collective operations are features that should be available in the interface, so that they can be used by applications in their execution. In order reach the reuse requirement, we based this interface on the Event- and Pulse-driven Models of Distributed Computing, once they are asynchronous and allow the incorporation of collective operations. We implemented partially the interface de ned in this work. In order to validate the use of the inteface by combinatorial optimization applications, we selected two applications and implemented them using our interface. They are the Branch-and-Bound technique and the Maximum Stable Set Problem (MSSP). We also provide some experimental results. / Este trabalho foi motivado pela necessidade da exploração do potencial do paralelismo distribuído em aplicações em Otimização Combinatória. Para tanto, propomos uma interface de programação distribuída, na qual prezamos dois requisitos principais: eficiência e reuso. O primeiro advém da necessidade de aplicações de CAD exigirem máximo desempenho possível. Assim sendo, especificamos esta interface como uma extensão da biblioteca MPI, a qual é assumida como eficiente para aplicações distribuídas. O requisito reuso deve tornar compatíveis duas características importantes: assincronismo e operações coletivas. O assincronismo deve estar presente na interface, uma vez que as aplicações em Otimização Combinatória, em sua maioria, possuem uma natureza assíncrona. Operações coletivas são funcionalidades que devem estar disponíveis na interface, de modo que possam ser utilizadas por aplicações em suas execuções. Tendo em vista atender o requisito reuso, baseamos esta interface nos Modelos de Computação Distribuída Dirigidos por Eventos e por Pulsos, pois os mesmos são assíncronos e permitem a incorporação de operações coletivas. Implementamos parcialmente a inteface definida neste trabalho. Tendo em vista validar uso desta inteface por aplicações em Otimização Combinatória, selecionamos duas aplicações e as implementamos utilizando a interface. São elas a técnica Branch-and-Bound e o Problema do Conjunto Independente Máximo (CIM). Fornecemos também alguns resultados experimentais.

Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T04:32:08Z (GMT). No. of bitstreams: 1 BrasilJunior_NelsonGomes_M.pdf: 980636 bytes, checksum: dd8d61baeb633d5f598abc3523def800 (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, estudamos a sequência dos Números de Catalan, uma sequência que aparece como solução de vários problemas de contagem envolvendo árvores, palavras, grafos e outras estruturas combinatórias. Atualmente, são conhecidas cerca de 200 interpretações combinatórias distintas para os Números de Catalan, o que motiva o estudo de relações entre estas interpretações, isto é, entre conjuntos cuja cardinalidade é dada pelos termos desta sequência. O principal objetivo do nosso trabalho é, portanto, mostrar bijeções entre esses conjuntos. No início do texto fazemos uma pequena introdução histórica aos números de Catalan, assim como definimos algumas formas de representar a sequência estudada. Depois mostramos algumas bijeções clássicas entre conjuntos contados pela sequência de Catalan. Além disso, apresentamos outras bijeções entre conjuntos envolvendo diversos objetos combinatórios. No total, são exibidas 29 bijeções / Abstract: In this work, we study the sequence of Catalan Numbers, which appears as a solution of many counting problems involving trees, words, graphs and other combinatorial structures. Nowadays, about 200 different combinatorial interpretations of the Catalan Numbers are known and that motivates the study between them, i. e., the study between sets whose cardinality is given by the terms of this sequence. The main objective of our work is therefore to show bijections between these sets. In the beginning, we make a short historical introduction of the Catalan Numbers and define some ways to represent the sequence. After that, we show some classical bijections between sets counted by the Catalan Numbers. Additionally, we exhibit other bijections between sets involving several combinatorial objects. Altogether, 29 bijections are presented / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

O princípio das gavetas de Dirichlet é um resultado matemático baseado numa proposição relativamente simples: se desejamos distribuir N +1 objetos em N gavetas, necessariamente alguma das gavetas conterá pelo menos 2 objetos. Apesar de parecer pouco relevante, devido a sua obviedade, esse teorema constitui uma ferramenta bastante importante na prova de outros resultados matemáticos. O presente trabalho, demonstra o Princípio das Gavetas em duas versões, uma mais simples e a outra mais geral, exibe algumas aplicações que evidenciam a sua importância como ferramenta de prova, e ao mesmo tempo, utiliza da sua simplicidade para motivar o estudo do próprio resultado assim como o de outros conceitos matemáticos. O banco de questões separado por níveis de dificuldade e o plano de aula têm o propósito de subsidiar o trabalho do professor no desenvolvimento desse interessante resultado matemático. / The Dirichlets drawers principle is a mathematical result based on a relatively simple proposition: if we wish to distribute N+1 objects in N drawers, necessarily some of the drawers will contain at least 2 objects. Although it seems insignificant due to its obviousness, this result is a very important tool in proving other mathematical results. The present work proves the Dirichlets principle, also know as pigeonhole principle in two versions, one simpler and the other more general, exibits some applications that show its importance as a tool of proof, and at the same time uses its simplicity to motivate the study of the own result as well as other mathematical concepts. The set of problems separated by difficulty levels and the lesson plan are intended to subsidize the teachers work in the development of this interesting mathematical result.

Nesta tese estudamos dois problemas em digrafos: um problema de empacotamento e um problema de contagem. Estudamos o problema de empacotamento máximo de arborescências no digrafo aleatório D(n,p), onde cada possvel arco é inserido aleatoriamente ao acaso com probabilidade p = p(n). Denote por (D(n,p)) o maior inteiro possvel 0 tal que, para todo 0 l , temos ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}| Provamos que a quantidade máxima de arborescências em D(n,p) é (D(n,p)) assintoticamente quase certamente. Nós também mostramos estimativas justas para (D(n, p)) para todo p [0, 1]. As principais ferramentas que utilizamos são relacionadas a propriedades de expansão do D(n, p), o comportamento do grau de entrada do digrafo aleatório e um resultado clássico de Frank que serve como ligação entre subpartições em digrafos e a quantidade de arborescências. Para o problema de contagem, estudamos a densidade de subtorneios fortemente conexos com 5 vértices em torneios grandes. Determinamos a densidade assintótica máxima para 5 torneios bem como as famlias assintóticas extremais de cada torneios. Como subproduto deste trabalho caracterizamos torneios que são blow-ups recursivos de um circuito orientado com 3 vértices como torneios que probem torneios especficos de tamanho 5. Como principal ferramenta para esse problema utilizados a teoria de álgebra de flags e configurações combinatórias obtidas através do método semidefinido. / In this thesis we study two problems dealing with digraphs: a packing problem and a counting problem. We study the problem of packing the maximum number of arborescences in the random digraph D(n,p), where each possible arc is included uniformly at random with probability p = p(n). Let (D(n,p)) denote the largest integer 0 such that, for all 0 l , we have ^(l-1)_i=0 (l-i)|{v in d^in(v) = i}|. We show that the maximum number of arc-disjoint arborescences in D(n, p) is (D(n, p)) asymptotically almost surely. We also give tight estimates for (D(n, p)) for every p [0, 1]. The main tools that we used were expansion properties of random digraphs, the behavior of in-degree of random digraphs and a classic result by Frank relating subpartitions and number of arborescences. For the counting problem, we study the density of fixed strongly connected subtournaments on 5 vertices in large tournaments. We determine the maximum density asymptotically for five tournaments as well as unique extremal sequences for each tournament. As a byproduct of this study we also characterize tournaments that are recursive blow-ups of a 3-cycle as tournaments that avoid three specific tournaments of size 5. We use the theory of flag algebras as a main tool for this problem and combinatorial settings obtained from semidefinite method.