O presente trabalho é um esforço de apresentar, organizado em forma de survey, um conjunto de resultados que ilustram a aplicação de um certo método probabilístico. Embora não apresentemos resultados novos na área, acreditamos que a apresentação sistemática destes resultados pode servir para a compreensão de uma ferramenta útil para quem usa dos métodos probabilísticos na sua pesquisa em combinatória. Os resultados de que falaremos tem aparecido na última década na literatura especializada e foram usados na investigação de problemas que resitiram a outras aproximações mais clássicas. Em vez de teorizar sobre o método a apresentar, nós adotaremos a estratégia de apresentar três problemas, usando-os como exemplos práticos da aplicação do método em questão. Surpeendentemente, apesar da dificuldade que apresentaram para ser resolvidos, estes problemas compartilham a caraterística de poder ser formulados muito intuitivamente, como veremos no Capítulo 1. Devemos advertir que embora os problemas que conduzem nossa exposição pertençam a áreas tão diferentes quanto teoria de números, geometria e combinatória, nosso intuito é fazer énfase no que de comum tem as suas soluções e não das posteriores implicações que estes problemas tenham nas suas respectivas áreas. Ocasionalmente comentaremos sim, outras possíveis aplicações das ferramentas usadas para solucionar estes problemas de motivação. Os problemas de que trataremos tem-se caracterizado por aguardar várias décadas em espera de solução: O primeiro, da teoria de números, surgiu na pesquisa de séries de Fourier que Sidon realizava a princípios de século e foi proposto por ele a Erdös em 1932. Embora tenham havido, desde 1950, diversos avanços na pesquisa deste problema, o resultado de que falaremos data de 1981. Já o segundo problema, da geometria, é uma conjectura formulada em 1951 por Heilbronn e refutada finalmente em 1982. O último problema, de combinatória, é uma conjectura de Erdös e Hanani de 1963, que foi tratada em diversos casos particulares até ser finalmente resolvida em toda sua generalidade em 1985. / The following work is an effort to present, in survey form, a collection of results that illustrate the application of a certain probabilistic method in combinatorics. We do not present new results in the area; however, we do believe that the systematic presentation of these results can help those who use probabilistic methods comprenhend this useful technique. The results we refer to have appeared over the last decade in the research literature and were used in the investigation of problems which have resisted other, more classical, approaches. Instead of theorizing about the method, we adopted the strategy of presenting three problems, using them as practical examples of the application of the method in question. Surpisingly, despite the difficulty of solutions to these problems, they share the characteristic of being able to be formulated very intuitively, as we will see in Chapter One. We should warn the reader that despite the fact that the problems which drive our discussion belong to such different fields as number theory, geometry and combinatorics, our goal is to place emphasis on what their solutions have in common and not on the subsequent implications that these problems have in their respective fields. Occasionally, we will comment on other potential applications of the tools utilized to solve these problems. The problems which we are discussing can be characterized by the decades-long wait for their solution: the first, from number theory, arose from the research in Fourier series conducted by Sidon at the beginning of the century and was proposed by him to Erdös in 1932. Since 1950, there have been diverse advances in the understanding of this problem, but the result we talk of comes from 1981. The second problem, from geometry, is a conjecture formulated in 1951 by Heilbronn and finally refuted in 1982. The last problem, from combinatorics, is a conjecture formulated by Erdös and Hanani in 1963 that was treated in several particular cases but was only solved in its entirety in 1985.

Orientador: Viviane Clotilde da Silva. / Com: Produto educacional: Explorando conceitos básicos de análise combinatória nos anos finais do ensino fundamental: caderno do professor. / Dissertação (Mestrado em Ensino de Ciências Naturais e Matemática) - Programa de Pós-Graduação em Ensino de Ciências Naturais e Matemática, Universidade Regional de Blumenau, Blumenau.

O planejamento operacional de redes de média e baixa tensão consiste em determinar as melhores intervenções a serem aplicadas nas redes atuais de forma a otimizar os investimentos e atender aos critérios técnicos de operação. Na Média Tensão (MT) são usuais alterações como alocação de capacitores, alteração de cabos e remanejamento de cargas para obter uma melhoria para o sistema. Normalmente os objetivos são a minimização de perdas, melhora do nível de tensão e redução do custo das intervenções realizadas. Na Baixa Tensão (BT) são aplicadas intervenções relacionadas a substituição de cabos, alteração da posição do transformador e balanceamento de cargas. As alterações propostas visam melhorar os índices de equilíbrio de cargas, carregamento de transformadores e queda de tensão ao longo da rede MT e BT. Neste trabalho considera-se a minimização dos investimentos para a realização de alterações nos alimentadores e circuitos de BT, levando em conta a inserção de Geração Distribuída (GD) como solução alternativa. As dificuldades do problema de otimização resultam do tamanho dos sistemas reais e da possibilidade de alternativas que podem ser aplicadas durante o estudo. Para resolver o problema de explosão combinatória resultante das possíveis combinações de alternativas, os modelos propostos neste trabalho utilizam técnicas de computação evolutiva. Os modelos desenvolvidos respeitam aspectos técnicos e econômicos envolvidos em cada solução. A metodologia é aplicada em uma rede real partindo-se de uma base de dados georrefenciada. / The operational planning of medium and low voltage networks consists in determining the best interventions to be applied to existing networks in order to optimize investments and meet the technical criteria for operation. In the Medium Voltage (MV) capacitor allocation, recabling and relocation of loads are useful to achieve an improvement to the system. Usually the objectives are power losses minimization, voltage level improvement and cost reduction of the interventions carried out. In the Low Voltage (LV) interventions for replacing cables and transformer position and load relocation are commonly considered. The proposed changes are aimed at improving the load balance, transformer loading and voltage drops across LV network circuits. This work considers the investment minimization to intervene inMV and LV networks, considering Distributed Generation (DG) insertion as an alternative solution. The dificulties of optimization problem result from the size of the real systems and the possibility of alternatives that can be applied during the study. In order to solve the combinatorial explosion problem resulting from possible combinations of alternatives, the model proposed in this work uses evolutionary computational techniques. The developed models take into account technical and economical aspects involved in each solution. The methodology is applied in a real network starting from a georeferenced database.

Made available in DSpace on 2015-03-04T18:51:08Z (GMT). No. of bitstreams: 1 Dissertacao Luciana1.pdf: 6052653 bytes, checksum: 9c7348d9ada9fa32dce1bedcfa34e110 (MD5) Previous issue date: 2008-05-13 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Finding the structure of an arbitrary protein is vital for the understanding of its functionality. Many models had been developed for the ab initio prediction, and the lattice model is one of these models. Lattice models specify that each amino acid occupies a lattice position, consecutive amino acids occupy adjacent positions and a protein conformation is given by a path in this lattice. We have some forms to codify an amino acid sequence computationally. The main method is the usage of internal coordinates, however we can find in literature codifications using cartesian coordinates and torsion angles. We introduce a new codification of the data for lattice models, in which a protein with amino acids is configured as a numerical sequence in a three-dimensional lattice of size and all the possible movements for each amino acid are intuitive and correspond to add and to subtract , and . With the goal of exemplifying the development of this new codification, we construct a specific genetic algorithm for the protein structure prediction (PSP) problem. We analyze the development of this algorithm in four models, , , e , and tests using found proteins in literature and in the Protein Data Bank are carried out. / Encontrar a estrutura de uma proteína arbitrária é vital para a compreensão da funcionalidade desta proteína. Muitos modelos foram desenvolvidos para a predição em primeiros princípios, entre eles modelos de grades. Em modelos de grades, cada aminoácido ocupa uma posição da grade, com aminoácidos consecutivos ocupando posições adjacentes. Uma possível conformação da proteína é dada por um caminho nesta grade. Em uma grade, temos várias formas de codificar computacionalmente uma seqüência de aminoácidos. O método mais usado é o de coordenadas internas, mas também encontramos na literatura codificações por coordenadas cartesianas e ângulos de torção. Neste trabalho, introduzimos uma nova codificação dos dados para modelos de grades. Nesta codificação, uma proteína com n aminoácidos é configurada como uma seqüência numérica, com valores variando entre 0 e no caso bidimensional e e no caso tridimensional. Nesta grade, os possíveis movimentos para cada aminoácido são intuitivos e correspondem a somar e subtrair 1 e n no caso bidimensional e , e no caso tridimensional. Para exemplificarmos o desenvolvimento desta nova codificação, desenvolvemos um algoritmo genético específico para o problema de predição da estrutura da proteína (PSP). Analisamos o desenvolvimento deste algoritmo em quatro modelos, , , e , e realizamos testes com proteínas encontradas na literatura e no Protein Data Bank.

Esta tese de mestrado se propõe a resolver alguns problemas interessantes na área de Computação e Matemática, utilizando técnicas de Análise Combinatória, Teoria dos Grafos, Funções Geratrizes, Programação Dinâmica e Álgebra Linear. No decorrer da tese são abordados 3 problemas cujas soluções apresentam enfoque original, sob o ponto de vista da Teoria da Computação. O primeiro problema é o problema de Ulam (no capítulo referente a este problema, um novo algoritmo heurístico que interpreta o papel de um dos jogadores é apresentado). O segundo problema trata da contagem do número de matrizes de sinais alternantes e o último problema trata da contagem do número recobrimentos por dominós de uma dada figura plana (ou pareamentos perfeitos em grafos bipartidos).

O planejamento operacional de redes de média e baixa tensão consiste em determinar as melhores intervenções a serem aplicadas nas redes atuais de forma a otimizar os investimentos e atender aos critérios técnicos de operação. Na Média Tensão (MT) são usuais alterações como alocação de capacitores, alteração de cabos e remanejamento de cargas para obter uma melhoria para o sistema. Normalmente os objetivos são a minimização de perdas, melhora do nível de tensão e redução do custo das intervenções realizadas. Na Baixa Tensão (BT) são aplicadas intervenções relacionadas a substituição de cabos, alteração da posição do transformador e balanceamento de cargas. As alterações propostas visam melhorar os índices de equilíbrio de cargas, carregamento de transformadores e queda de tensão ao longo da rede MT e BT. Neste trabalho considera-se a minimização dos investimentos para a realização de alterações nos alimentadores e circuitos de BT, levando em conta a inserção de Geração Distribuída (GD) como solução alternativa. As dificuldades do problema de otimização resultam do tamanho dos sistemas reais e da possibilidade de alternativas que podem ser aplicadas durante o estudo. Para resolver o problema de explosão combinatória resultante das possíveis combinações de alternativas, os modelos propostos neste trabalho utilizam técnicas de computação evolutiva. Os modelos desenvolvidos respeitam aspectos técnicos e econômicos envolvidos em cada solução. A metodologia é aplicada em uma rede real partindo-se de uma base de dados georrefenciada. / The operational planning of medium and low voltage networks consists in determining the best interventions to be applied to existing networks in order to optimize investments and meet the technical criteria for operation. In the Medium Voltage (MV) capacitor allocation, recabling and relocation of loads are useful to achieve an improvement to the system. Usually the objectives are power losses minimization, voltage level improvement and cost reduction of the interventions carried out. In the Low Voltage (LV) interventions for replacing cables and transformer position and load relocation are commonly considered. The proposed changes are aimed at improving the load balance, transformer loading and voltage drops across LV network circuits. This work considers the investment minimization to intervene inMV and LV networks, considering Distributed Generation (DG) insertion as an alternative solution. The dificulties of optimization problem result from the size of the real systems and the possibility of alternatives that can be applied during the study. In order to solve the combinatorial explosion problem resulting from possible combinations of alternatives, the model proposed in this work uses evolutionary computational techniques. The developed models take into account technical and economical aspects involved in each solution. The methodology is applied in a real network starting from a georeferenced database.

O presente trabalho é um esforço de apresentar, organizado em forma de survey, um conjunto de resultados que ilustram a aplicação de um certo método probabilístico. Embora não apresentemos resultados novos na área, acreditamos que a apresentação sistemática destes resultados pode servir para a compreensão de uma ferramenta útil para quem usa dos métodos probabilísticos na sua pesquisa em combinatória. Os resultados de que falaremos tem aparecido na última década na literatura especializada e foram usados na investigação de problemas que resitiram a outras aproximações mais clássicas. Em vez de teorizar sobre o método a apresentar, nós adotaremos a estratégia de apresentar três problemas, usando-os como exemplos práticos da aplicação do método em questão. Surpeendentemente, apesar da dificuldade que apresentaram para ser resolvidos, estes problemas compartilham a caraterística de poder ser formulados muito intuitivamente, como veremos no Capítulo 1. Devemos advertir que embora os problemas que conduzem nossa exposição pertençam a áreas tão diferentes quanto teoria de números, geometria e combinatória, nosso intuito é fazer énfase no que de comum tem as suas soluções e não das posteriores implicações que estes problemas tenham nas suas respectivas áreas. Ocasionalmente comentaremos sim, outras possíveis aplicações das ferramentas usadas para solucionar estes problemas de motivação. Os problemas de que trataremos tem-se caracterizado por aguardar várias décadas em espera de solução: O primeiro, da teoria de números, surgiu na pesquisa de séries de Fourier que Sidon realizava a princípios de século e foi proposto por ele a Erdös em 1932. Embora tenham havido, desde 1950, diversos avanços na pesquisa deste problema, o resultado de que falaremos data de 1981. Já o segundo problema, da geometria, é uma conjectura formulada em 1951 por Heilbronn e refutada finalmente em 1982. O último problema, de combinatória, é uma conjectura de Erdös e Hanani de 1963, que foi tratada em diversos casos particulares até ser finalmente resolvida em toda sua generalidade em 1985. / The following work is an effort to present, in survey form, a collection of results that illustrate the application of a certain probabilistic method in combinatorics. We do not present new results in the area; however, we do believe that the systematic presentation of these results can help those who use probabilistic methods comprenhend this useful technique. The results we refer to have appeared over the last decade in the research literature and were used in the investigation of problems which have resisted other, more classical, approaches. Instead of theorizing about the method, we adopted the strategy of presenting three problems, using them as practical examples of the application of the method in question. Surpisingly, despite the difficulty of solutions to these problems, they share the characteristic of being able to be formulated very intuitively, as we will see in Chapter One. We should warn the reader that despite the fact that the problems which drive our discussion belong to such different fields as number theory, geometry and combinatorics, our goal is to place emphasis on what their solutions have in common and not on the subsequent implications that these problems have in their respective fields. Occasionally, we will comment on other potential applications of the tools utilized to solve these problems. The problems which we are discussing can be characterized by the decades-long wait for their solution: the first, from number theory, arose from the research in Fourier series conducted by Sidon at the beginning of the century and was proposed by him to Erdös in 1932. Since 1950, there have been diverse advances in the understanding of this problem, but the result we talk of comes from 1981. The second problem, from geometry, is a conjecture formulated in 1951 by Heilbronn and finally refuted in 1982. The last problem, from combinatorics, is a conjecture formulated by Erdös and Hanani in 1963 that was treated in several particular cases but was only solved in its entirety in 1985.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

O problema da árvore geradora de comunicação ótima recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é a soma sobre cada par de vértice da distância entre eles na árvore vezes o requerimento entre eles. Este problema é NP-difícil, assim como vários casos particulares dele. Neste trabalho estudamos algumas variantes deste problema, introduzimos novos casos particulares que são também NP-difíceis e propomos esquemas de aproximação polinomial para alguns deles. / The optimum communication spanning tree problem receives a graph with non-negative lengths over the edges and non-negative requirements for each pair of nodes; being the objective to find a spanning tree of the graph that minimizes the communication cost, which is given by the sum, over each pair of nodes, of the distance, in the tree, between the nodes multiplied by the requirement between them. This problem and several of its particular cases are NP-hard. In this work we study some of the variants, also we introduce new NP-hard particular cases of the problem and propose polynomial approximation schemes for some of them.

Made available in DSpace on 2015-03-05T13:59:42Z (GMT). No. of bitstreams: 0 Previous issue date: 2 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o Problema de Roteamento de Veículos em que apenas a restrição da capacidade do veículo é considerada. O objetivo deste problema é atender a uma rede de clientes, através da criação de rotas de custo mínimo que respeitem a capacidade do veículo. Para gerar soluções para este problema uma aplicação será desenvolvida utilizando a metaheurística Busca Tabu. A Busca Tabu permite que estratégias de intensificação e diversificação sejam utilizadas para guiar a procura de boas soluções. Para esta aplicação dois tipos de movimentos geradores de vizinhança serão utilizados: a realocação de vértices e a troca de vértices entre rotas. Os resultados obtidos nesta aplicação serão comparados com resultados de heurísticas clássicas e com resultados publicados por outros autores que utilizam a Busca Tabu na abordagem do Problema de Roteamento de Veículos