Orientador: Andreia Cristina Ribeiro / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T11:28:46Z (GMT). No. of bitstreams: 1 Assis_LucianaMafaldaEliasde_M.pdf: 10126493 bytes, checksum: bb2628e76f90df6deb24a9011e535714 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho são apresentados vários resultados importantes da Análise Combinatória com destaque para o Princípio da Inclusão e Exclusão. Relevantes aplicações deste princípio são abordadas / Abstract: In this work we present important results from enumerative combinatorics, with an emphasis on the Principle of Inclusion and Exclusion. Relevant applications of this principle are presented to illustrate its use / Mestrado / Mestre em Matemática

Orientador : Luiz Paulo de Alcantara / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-07-19T01:03:40Z (GMT). No. of bitstreams: 1 Gonzalez_CarlosGustavo_D.pdf: 1718213 bytes, checksum: bf9cc685d8b4e892bab370b4ddb18d01 (MD5) Previous issue date: 1994 / Resumo: Não informado / Abstract: Not informed. / Doutorado / Doutor em Filosofia

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-25T10:24:33Z (GMT). No. of bitstreams: 1 FeresJunior_Jorge_M.pdf: 656533 bytes, checksum: f89557654d48cebb7328f9f5ebbc8d0f (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação estudamos permutações que evitam determinados padrões. Mais especificamente, nosso foco é a contagem de tais permutações. Dentre as várias formas de descrever uma permutação, adotamos a ''representação posicional em linha'', apresentando um tratamento sistemático nesta área de padrão proibido, estudando operações, simetrias, estruturas, transformações, e principalmente, técnicas de contagem para este fim / Abstract: In this dissertation, we study permutations avoiding certain patterns. More specifically, our focus is on counting such permutations. Among the many ways to describe a permutation, we adopted the "positional representation in line" presenting a systematic treatment of this area of forbidden pattern, studying operations, symmetries, structures, transformations, and especially counting techniques for this purpose / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

O estudo do comportamento assintótico de densidades de algumas subestruturas é uma das principais áreas de estudos em combinatória. Na Teoria das Permutações, fixadas permutações ?1 e ?2 e um inteiro n > 0, estamos interessados em estudar o comportamento das densidades de ?1 e ?2 na família de permutações de tamanho n. Assim, existem duas direções naturais que podemos seguir. Na primeira direção, estamos interessados em achar a permutação de tamanho n que maximiza a densidade das permutações ?1 e ?2 simultaneamente. Para n suficientemente grande, explicitamos a densidade máxima que uma família de permutações podem assumir dentre todas as permutações de tamanho n. Na segunda direção, estamos interessados em achar a permutação de tamanho n que minimiza a densidade de ?1 e ?2 simultaneamente. Quando ?1 é a permutação identidade com k elementos e ?2 é a permutação reversa com l elementos, Myers conjecturou que o mínimo é atingido quando tomamos o mínimo dentre as permutações que não possuem a ocorrência de ?1 ou ?2. Mostramos que se restringirmos o espaço de busca somente ao conjunto de permutações em camadas, então a Conjectura de Myers é verdadeira. Por outro lado, na Teoria dos Grafos, o problema de encontrar um circuito Hamiltoniano é um problema NP-completo clássico e está entre os 21 problemas Karp. Dessa forma, uma abordagem comum na literatura para atacar esse problema é encontrar condições que um grafo deve satisfazer e que garantem a existência de um circuito Hamiltoniano em tal grafo. O célebre resultado de Dirac afirma que se um grafo G de ordem n possui grau mínimo pelo menos n/2, então G possui um circuito Hamiltoniano. Seguindo a linha de Dirac, mostramos que, dados inteiros 1 6 l 6 k/2 e ? > 0 existe um inteiro n0 > 0 tal que, se um hipergrafo k-uniforme H de ordem n satisfaz ?k-2(H) > ((4(k - l) - 1)/(4(k - l)2) + ?) (n 2), então H possui um l-circuito Hamiltoniano. / The study of asymptotic behavior of densities of some substructures is one of the main areas in combinatorics. In Permutation Theory, fixed permutations ?1 and ?2 and an integer n > 0, we are interested in the behavior of densities of ?1 and ?2 among the permutations of size n. Thus, there are two natural directions we can follow. In the first direction, we are interested in finding the permutation of size n that maximizes the density of the permutations ?1 and ?2 simultaneously. We explicit the maximum density of a family of permutations between all the permutations of size n. In the second direction, we are interested in finding the permutation of size n that minimizes the density of ?1 and ?2 simultaneously. When ?1 is the identity permutation with l elements and ?2 is the reverse permutation with k elements, Myers conjectured that the minimum is achieved when we take the minimum among the permutations which do not have the occurrence of ?1 or ?2. We show that if we restrict the search space only to set of layered permutations and k > l, then the Myers\' Conjecture is true. On the other hand, in Graph Theory, the problem of finding a Hamiltonian cycle is a NP-complete problem and it is among the 21 Karp problems. Thus, one approach to attack this problem is to find conditions that a graph must meet to ensure the existence of a Hamiltonian cycle on it. The celebrated result of Dirac shows that a graph G of order n that has minimum degree at least n/2 has a Hamiltonian cycle. Following the line of Dirac, we show that give integers 1 6 l 6 k/2 and gamma > 0 there is an integer n0 > 0 such that if a hypergraph k-Uniform H of order n satisfies ?k-2(H) > ((4(k-l)-1)/(4(k-l)2)+?) (n 2), then H has a Hamiltonian l-cycle.

Dissertação (mestrado profissional) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas, Programa de Pós-Graduação em Matemática, Florianópolis, 2014. / Made available in DSpace on 2014-08-06T18:00:43Z (GMT). No. of bitstreams: 1 326843.pdf: 625671 bytes, checksum: bffa5b605939a9c07c84054b4c36a477 (MD5) Previous issue date: 2014 / Este trabalho tem como objetivo ser uma breve introdução à Álgebra. Na parte inicial foi introduzido o conceito de permutação e sua definição como funções bijetivas de um conjunto em si mesmo. Na sequência, foi introduzido o conceito de grupo e subgrupo e apresentadas algumas das propriedades básicas de tais estruturas. No terceiro capítulo foram expostos e discutidos os conceitos de homomorfismo e de isomorfismo de modo a pavimentar o caminho para a demonstração do Teorema de Cayley que foi abordado no capítulo seguinte. Encerrando o trabalho foi apresentado um plano de aula de modo a sugerir uma aplicação do conteúdo abordado para uma turma de Ensino Médio.<br>

Submitted by ANA KARLA PEREIRA RODRIGUES (anakarla_@hotmail.com) on 2017-08-30T14:02:41Z No. of bitstreams: 1 arquivototal.pdf: 1530287 bytes, checksum: bd20f7e7a563f1aa0ad40d276bc400f9 (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2017-08-30T14:19:18Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 1530287 bytes, checksum: bd20f7e7a563f1aa0ad40d276bc400f9 (MD5) / Made available in DSpace on 2017-08-30T14:19:18Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1530287 bytes, checksum: bd20f7e7a563f1aa0ad40d276bc400f9 (MD5) Previous issue date: 2015-07-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work we discuss the procedures for solving polynomials equations of degree n 4; n 2 N via circulant matrices, highlighting a new perspective to obtain the Cardano- Tartaglia formulae. This brings up a new look on connected subjects, including the elimination of the term of degree (n􀀀1) and the characterization of real polynomials with all real roots. The method is based on searching a circulant matrix whose characteristic polynomial is identical to the one with the same roots we desire to nd. This approach provides us a simple and uni ed method for all equations through degree four. / Neste trabalho abordamos via matrizes circulantes a resolução de equações polinomiais de grau n 4; n 2 N , destacando uma nova perspectiva para obtenção das fórmulas de Cardano-Tartaglia. Além disso, ele oportuniza uma nova maneira de olhar para questões conexas, incluindo a eliminação do termo de grau (n 􀀀 1) e a caracterização de equações reais com todas as raízes reais. O método é baseado na busca de uma matriz circulante cujo polinômio característico seja idêntico ao das raízes que queremos encontrar. Essa metodologia nos fornece um método simples e uni cado para todas equações até quarto grau.

Submitted by (lucia.rodrigues@ufrpe.br) on 2017-03-29T14:53:15Z No. of bitstreams: 1 Walfrido Siqueira Campos Junior.pdf: 422142 bytes, checksum: a769780b0d11bc646f87ad7036267f6b (MD5) / Made available in DSpace on 2017-03-29T14:53:15Z (GMT). No. of bitstreams: 1 Walfrido Siqueira Campos Junior.pdf: 422142 bytes, checksum: a769780b0d11bc646f87ad7036267f6b (MD5) Previous issue date: 2014-06-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work consists of the presentation of a simple permutation, seen as function. This function is bijective, hence admits inverse (inverse permutation). The composition of this function with the same it is also bijective (composed permutation). We will also see the permutations with repetition, circular without repetition and repetition, beyond chaotic permutations, which are those in which no element occupies its original position. The work is also part of the de nition and presentation of a group of permutations consisting of 3 properties in which the composition of functions satisfy all of them. This is our highest goal. Still show the parity of the permutation, as well as their applications in cases of determinants. / Este trabalho consta da apresentação de uma permutação simples, vista na forma de função. Essa função é bijetora, portanto admite inversa (permutação inversa). A composição dessa função com ela mesma, também é bijetora (permutação composta). Veremos também as permutações com repetição, circulares sem repetição e com repetição, além das permutações caóticas, que são aquelas em que nenhum elemento ocupa sua posição inicial. O trabalho consta também da definição e apresentação de um Grupo das permutações que consiste em 3 propriedades na qual a composição das funções satisfazem todas elas. Esse e o nosso maior objetivo. Mostraremos ainda a paridade da permutação, bem como suas aplicações em casos de determinantes.

Orientador: João Meidanis / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T00:56:27Z (GMT). No. of bitstreams: 1 GomesMira_CleberValgas_D.pdf: 1443128 bytes, checksum: adcf8d553b49f20bbad0fc0f56cc2aba (MD5) Previous issue date: 2007 / Resumo: O sucesso na obtenção de cadeias completas de DNA de alguns organismos tem incentivado a busca de novas técnicas computacionais capazes de analisar esse montante de informação para aplicá-lo na descoberta de novos remédios, aumento da produção de alimentos e investigação do processo de evolução dos seres vivos, entre outras aplicações. A comparação de seqüências de DNA (ou RNA) de diferentes espécies é uma das técnicas importantes para desvendar novas propriedades biológicas. Uma das maneiras de se comparar dois genomas é analisar como os dois se distinguem com base em certas mutações chamadas eventos de rearranjo em genomas. Nessa técnica de comparação, um genoma é modelado como uma seqüência de regiões que são conservadas em um conjunto de genomas. O problema de rearranjos em genomas consiste genericamente em encontrar, dados dois genomas como entrada e um conjunto de tipos de eventos de rearranjo permitidos, uma seqüência mínima de tais eventos de rearranjo que transforme um genoma em outro. No formalismo clássico de rearranjos em genomas, um genoma tem sido modelado como um conjunto de seqüências de inteiros. Cada número inteiro representa um gene e o seu sinal representa a orientação do gene no genoma. O problema de rearranjos em genomas nesse modelo é analisado de forma geral por meio de diversos diagramas e grafos que representam certas propriedades do par de genomas na entrada do problema. Neste trabalho, usamos um novo modelo para rearranjos em genomas proposto por Meidanis e Dias [39]: o formalismo algébrico. Em vez de se basear na análise de diagramas, o formalismo algébrico usa permutações na modelagem de genomas e, principalmente, utiliza resultados de grupos de permutações para analisar as propriedades de genomas e os efeitos de eventos de rearranjo. A motivação para o desenvolvimento do formalismo algébrico é a possibilidade de formalização de argumentos sobre rearranjos por meio de métodos algébricos, em vez da utilização de recursos gráficos como é feito no formalismo clássico. Esperamos que, por meio do desenvolvimento de um novo formalismo para o tratamento de problemas de rearranjos em genomas, algoritmos mais eficientes para a resolução desses problemas, ou maneiras mais simples de demonstrar alguns dos resultados clássicos na área sejam encontrados com maior facilidade. Nesse trabalho, apresentamos duas soluções simples e eficientes derivadas diretamente do formalismo algébrico para dois problemas de rearranjos em genomas (o problema de rearranjos em genomas por intercâmbio de blocos e reversões com sinais e o problema de rearranjo em genomas por fissões, fusões e reversões com sinais). Também discutimos e propomos um algoritmo polinomial para o problema de rearranjos em genomas por transposições generalizadas. Acreditamos que o sucesso na solução desses problemas possa ser estendido para outros problemas de rearranjos em genomas com a consolidação dos conceitos fundamentais do formalismo algébrico. Esperamos com essa tese convencer o leitor de que o formalismo algébrico é um modelo representativo e poderoso para tratar genomas compostos por cromossomos circulares e ao lidar com a atribuição de pesos a eventos de rearranjo. Por outro lado, não defendemos que o formalismo clássico seja simplesmente substituído pelo formalismo algébrico. Ambos os formalismos podem ser beneficiados por um processo semelhante, porém em menor escala, ao sucesso do desenvolvimento da Geometria Analítica e da Geometria Tradicional / Abstract: The success in obtaining complete sequences of DNA of some species has encouraged the search for new computational techniques for the analysis of such huge amount of information. One hopes that the results of this research could be applied for the development of new medicines, increasing food crops productivity, better understanding of the evolutionary process in live beings, among other applications. One technique for the genome analysis is the comparison of DNA (or RNA) sequences from different species. Such a comparison may reveal the similarities and differences between the genomes, which could be used in phylogeny reconstruction for instance. Two genomes can be compared by the analysis of their differences based on mutational events called genome rearrangements. The genome rearrangement problem (also called a sorting problem) consists of finding a minimum sequence of rearrangement events that transforms one genome into another and the number of rearrangement events in the sequence is called the genomic distance. In the classical formalism for genome rearrangements, a genome is usually modeled by a set of sequences of integers. Each integer represents a gene and its sign stands for the orientation of the gene in the genome. The genome rearrangement problem in this model is analyzed generally with tools such as diagrams and graphs that convey the properties of the genomes in the problem input. We use instead a new model for genome rearrangements proposed by Meidanis and Dias [39]: the algebraic formalism. Instead of being based on the analysis of diagrams, the algebraic formalism uses permutations to model genomes and the results from permutation group theory for the analysis of the properties of genomes and the effects of rearrangement events. The motivation for the development of the algebraic formalism is the possibility of stating arguments more formally by means of algebraic methods than by using graphical resources as the classical formalism does. We hope that more efficient algorithms for genome rearrangement problems or simpler proofs for classical results in the area will be more easily found due to the development of a new formalism. We present a simple, efficient solution based on the algebraic formalism for two genome rearrangement problems (the problem of genome rearrangements by block-interchanges and signed reversals and the problem of genome rearrangements by fissions, fusions, and signed reversals). We also discuss and offer a solution for the problem of genome rearrangements by generalized transpositions. We believe that the success in solving those genome rearrangement problems could be extended to other problems by consolidating the fundamental concepts of the algebraic formalism. We hope that the reader will be convinced that the algebraic formalism is representative and powerful in dealing with circular chromosomes and modeling the assignment of weights to rearrangement events. On the other hand, we do not argue in favor of a substitution of the classical formalism by the algebraic formalism. Both of these formalisms could profit by a similar, even though on a smaller scale, success of the development of the Analytic Geometry and the Traditional Geometry / Doutorado / Doutor em Ciência da Computação

O estudo do comportamento assintótico de densidades de algumas subestruturas é uma das principais áreas de estudos em combinatória. Na Teoria das Permutações, fixadas permutações ?1 e ?2 e um inteiro n > 0, estamos interessados em estudar o comportamento das densidades de ?1 e ?2 na família de permutações de tamanho n. Assim, existem duas direções naturais que podemos seguir. Na primeira direção, estamos interessados em achar a permutação de tamanho n que maximiza a densidade das permutações ?1 e ?2 simultaneamente. Para n suficientemente grande, explicitamos a densidade máxima que uma família de permutações podem assumir dentre todas as permutações de tamanho n. Na segunda direção, estamos interessados em achar a permutação de tamanho n que minimiza a densidade de ?1 e ?2 simultaneamente. Quando ?1 é a permutação identidade com k elementos e ?2 é a permutação reversa com l elementos, Myers conjecturou que o mínimo é atingido quando tomamos o mínimo dentre as permutações que não possuem a ocorrência de ?1 ou ?2. Mostramos que se restringirmos o espaço de busca somente ao conjunto de permutações em camadas, então a Conjectura de Myers é verdadeira. Por outro lado, na Teoria dos Grafos, o problema de encontrar um circuito Hamiltoniano é um problema NP-completo clássico e está entre os 21 problemas Karp. Dessa forma, uma abordagem comum na literatura para atacar esse problema é encontrar condições que um grafo deve satisfazer e que garantem a existência de um circuito Hamiltoniano em tal grafo. O célebre resultado de Dirac afirma que se um grafo G de ordem n possui grau mínimo pelo menos n/2, então G possui um circuito Hamiltoniano. Seguindo a linha de Dirac, mostramos que, dados inteiros 1 6 l 6 k/2 e ? > 0 existe um inteiro n0 > 0 tal que, se um hipergrafo k-uniforme H de ordem n satisfaz ?k-2(H) > ((4(k - l) - 1)/(4(k - l)2) + ?) (n 2), então H possui um l-circuito Hamiltoniano. / The study of asymptotic behavior of densities of some substructures is one of the main areas in combinatorics. In Permutation Theory, fixed permutations ?1 and ?2 and an integer n > 0, we are interested in the behavior of densities of ?1 and ?2 among the permutations of size n. Thus, there are two natural directions we can follow. In the first direction, we are interested in finding the permutation of size n that maximizes the density of the permutations ?1 and ?2 simultaneously. We explicit the maximum density of a family of permutations between all the permutations of size n. In the second direction, we are interested in finding the permutation of size n that minimizes the density of ?1 and ?2 simultaneously. When ?1 is the identity permutation with l elements and ?2 is the reverse permutation with k elements, Myers conjectured that the minimum is achieved when we take the minimum among the permutations which do not have the occurrence of ?1 or ?2. We show that if we restrict the search space only to set of layered permutations and k > l, then the Myers\' Conjecture is true. On the other hand, in Graph Theory, the problem of finding a Hamiltonian cycle is a NP-complete problem and it is among the 21 Karp problems. Thus, one approach to attack this problem is to find conditions that a graph must meet to ensure the existence of a Hamiltonian cycle on it. The celebrated result of Dirac shows that a graph G of order n that has minimum degree at least n/2 has a Hamiltonian cycle. Following the line of Dirac, we show that give integers 1 6 l 6 k/2 and gamma > 0 there is an integer n0 > 0 such that if a hypergraph k-Uniform H of order n satisfies ?k-2(H) > ((4(k-l)-1)/(4(k-l)2)+?) (n 2), then H has a Hamiltonian l-cycle.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-11-11T17:41:45Z No. of bitstreams: 2 Dissertação - Edson Praxedes dos Santos Junior - 2014.pdf: 13478577 bytes, checksum: b27d0c248d9fab2b9ccbb4c02b7d2b63 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2014-11-11T17:46:05Z (GMT) No. of bitstreams: 2 Dissertação - Edson Praxedes dos Santos Junior - 2014.pdf: 13478577 bytes, checksum: b27d0c248d9fab2b9ccbb4c02b7d2b63 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-11-11T17:46:05Z (GMT). No. of bitstreams: 2 Dissertação - Edson Praxedes dos Santos Junior - 2014.pdf: 13478577 bytes, checksum: b27d0c248d9fab2b9ccbb4c02b7d2b63 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-03-07 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This study aimed to systematize a formula that gives the number of chaotic permutations of n objects by means of the principle of inclusion and exclusion. To do so, are developed and validated, throughout the text, basic and advanced tools of combinatorics. There is also a section devoted to problems which can be solved by the formula outa obtained and in which approaches the formula for obtaining the number of chaotic permutations by means of recurrence. / O presente trabalho teve como objetivo principal, sistematizar uma fórmula que fornece o número de permutações caóticas de n objetos por meio do princípio da inclusão e exclusão. Para isso, são desenvolvidas e validadas, ao longo do texto, ferramentas básicas e avançadas da análise combinatória. Há também uma seção destinada a problemas, que podem ser solucionados por meio da fórmula obtida e outra na qual aborda a fórmula da obtenção do número de permutações caóticas por meio de recorrência.