Thesis advisor: Howard Straubing / The use of computer programs to automatically solve logic puzzles is examined in this work. A typical example of this type of logic puzzle is one in which there are five people, with five different occupations and five different color houses. The task is to use various clues to determine which occupation and which color belongs to each person. The clues to this type of puzzle often are statements such as, ''John is not the barber,'' or ''Joe lives in the blue house.'' These puzzles range widely in complexity with varying numbers of objects to identify and varying numbers of characteristics that need to be identified for each object. With respect to the theoretical aspects of solving these puzzles automatically, this work proves that the problem of determining, given a logic puzzle, whether or not that logic puzzle has a solution is NP-Complete. This implies, provided that P is not equal to NP, that, for large inputs, automated solvers for these puzzles will not be efficient in all cases. Having proved this, this work proceeds to seek methods that will work for solving these puzzles efficiently in most cases. To that end, each logic puzzle can be encoded as an instance of boolean satisfiability. Two possible encodings are proposed that both translate logic puzzles into boolean formulas in Conjunctive Normal Form. Using a selection of test puzzles, a group of boolean satisfiability solvers is used to solve these puzzles in both encodings. In most cases, these simple solvers are successful in producing solutions efficiently. / Thesis (BS) — Boston College, 2009. / Submitted to: Boston College. College of Arts and Sciences. / Discipline: College Honors Program. / Discipline: Computer Science.

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-09-11T21:07:22Z (GMT). No. of bitstreams: 1 Fortuna_ViniciusJose_M.pdf: 2317520 bytes, checksum: 52e18a1fcb2b671c1296276814c65290 (MD5) Previous issue date: 2005 / Resumo: Uma das principais formas de se medir a distância evolutiva entre espécies é avaliando-se quão transformado um genoma foi em relação a outro. Tais transformações são conhecidas como rearranjos de genoma. Neste trabalho estaremos analisando o rearranjo chamado de transposição, evento que troca de posição dois blocos consecutivos de genes de um mesmo cromossomo. Mais especificamente, buscamos encontrar o número mínimo de transposições que transforma um cromos somo em outro, valor conhecido como distância de transposição. Matematicamente, consideramos os cromossomos como permutações e o problema de se transformar uma permutação em outra pode ser visto como uma ordenação. Em nosso estudo, introduzimos uma operação de remoção de elementos, ferramenta ainda pouco explorada no estudo da distância de transposição, mas que nos possibilitou obter um limite superior para a distância de transposição. Também sugerimos novas formas de se utilizar a remoção de elementos e a análise de subseqüências de permutações. Como forma de se tentar obter novos conhecimentos sobre o problema da distância de transposição, consideramos a variação do problema em que somente transposições de prefixo são permitidas. Zanoni Dias propôs um algoritmo polinomial que transforma qualquer permutação de comprimento n em sua reversa em f3n/41 passos, porém sem uma prova completa. Modificamos esse algoritmo, mantendo o número de passos, e apresentamos uma prova completa da correção do algoritmo modificado. Ainda no problema de distância de transposição de prefixo, analisamos as permutações cujas distâncias se igualam ao limite inferior de distância de pontos de quebra. Tais permutações são fáceis de serem ordenadas por transposições de prefixo em tempo polinomial, pois possuem ordenação ótima única e bem definida. Ao final chegamos à conclusão que as permutações que são fáceis de se ordenar no problema de transposições de prefixo também são fáceis no problema de transposições, o que prova que a variação do problema auxilia no estudo do problema original / Abstract: One of the main ways of measuring the evolution distance among species is to evaluate how large chunks have moved when comparing two genomes. Such changes are know as genome rearrangements. In this work we analyze a rearrangement event called transposition that changes the position of two consecutive blocks of genes in a chromosome. More specifically, we look for the minimum number of transpositions needed to transform a chromosome into another. This value is called the transposition distance. Mathematically, chromosomes are regarded as permutations and changing one genome into another can be seen as a sorting problem. In our study, we introduce an operation of element removal from permutations, which has not been fully explored, but allowed us to find an upper bound for the transposition distance. We also suggest new ways of making use of element removal and the analysis of permutation subsequences. In the hope of obtaining new knowledge about the problem of transposition distance, we considered the variation of the problem where we allow prefix transpositions only. Zanoni Dias developed a polynomial algorithm that changes any permutation into its reverse using f3n/41 steps, but without a proof of its correctness. We have modified this algorithm, keeping the number of steps, and presented a complete proof of the correction of the modified algorithm. Still about the prefix transposition distance, we have analyzed those permutations whose distance equals the breakpoint lower bound. Such permutations are easily sorted by prefix transpositions in polynomial time, since they have a unique and well-defined optimum sorting. Finally, we concluded that the permutations that are easily sorted in the prefix transposition problem are also easily sorted in the transposition problem, which proves that the variation of the problem helps the study of the original problem / Mestrado / Mestre em Ciência da Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-14T23:05:02Z (GMT). No. of bitstreams: 1 Silva_CandidaNunesda_D.pdf: 1443438 bytes, checksum: c37eb2de501a4f5b10d9c8681c3a0971 (MD5) Previous issue date: 2009 / Resumo: Esta tese trata de fluxos inteiros e colorações em grafos, problemas intimamente relacionados. Concentramos nossa atenção nas Conjeturas de Tutte sobre 5-, 4- e 3-fluxos, as quais foram propostas entre as décadas de 50 e 70 e permanecem abertas até hoje. Apresentamos três abordagens para o ataque das conjeturas, com ênfase na Conjetura dos 3-Fluxos. Na primeira abordagem propomos o estudo dos grafos fluxo-críticos, aqueles que não admitem um k-fluxo, mas que passam a admitir quando sujeitos a uma simples operação de redução. O interesse no estudo dessa classe de grafos vem da observação de que todo contra-exemplo mínimo para qualquer uma das conjeturas de Tutte é fluxo-crítico. Na segunda abordagem estudamos a conexidade cíclica do contra-exemplo mínimo para uma conjetura equivalente à Conjetura dos 3-Fluxos. Na terceira abordagem buscamos uma nova demonstração do Teorema de Grötzsch, o qual é o dual planar da Conjetura dos 3-Fluxos, que não utilize a Fórmula de Euler como a demonstração original. / Abstract: The theme of this thesis is nowhere-zero flows and colourings of graphs, two subjects that are closely related. We focus mainly on the three Conjectures of Tutte concerning 5-, 4- and 3-nowhere-zero flows. These conjectures were proposed, respectively, in the 50's, 60's and 70's; all of them remain open so far. In this thesis we present three different approaches for the study of Tutte's Conjectures, with emphasis on the 3-Flow Conjecture. In the first approach, we introduce the concept of flow-critical graph. A graph is flowcritical if it does not admit a nowhere-zero k-flow but, when a simple reduction operation is applied, the resulting graph does admit a nowhere-zero k-flow. The motivation for the study of such graphs is due to the observation that any minimum counterexample for any of Tutte's conjectures lies in this particular class. In the second approach, we study the cyclic-connectivity of a minimum counterexample for an equivalent version of the 3-Flow Conjecture. In the third approach, we give a new proof for Gr¨otzsch's Theorem that differs from the original in the fact that it does not depend on Euler's Formula. / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T11:49:51Z (GMT). No. of bitstreams: 1 Bracht_EvandroCesar_M.pdf: 694440 bytes, checksum: b7f0c4ac260849f98329f238c91ec2bd (MD5) Previous issue date: 2004 / Resumo: Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional / Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is consistent with some observed data that we have about the problem. In this work we present a study of approximation algorithms for the metric labeling problem. The known approximation algorithms for this problem are based on solutions of large linear programs and are impractical for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed by a primal-dual technique which, although has a factor greater than the previous algorithms, can be applied to large sized instances. We also show that the analysis is tight, up to a constant factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these instances our algorithm presents good quality solutions with a considerable gain of computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T00:31:09Z (GMT). No. of bitstreams: 1 Vignatti_AndreLuis_M.pdf: 1110014 bytes, checksum: 4a8c19589a3914eb255c6938623be094 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudamos a interação entre duas áreas: otimização combinatória e compartilhamento de custos (cost-sharing), que é a arte de dividir os custos associados a construção e manutenção de uma solução a qual um grupo de usuários é beneficiado. Apresentamos algoritmos para problemas de projeto de redes, tendo como objetivo principal os problemas ¿Connected Facility Location¿ e ¿Rent-or-Buy¿. Estes dois problemas são NP-difíceis, pois têm como caso particular o problema da arvore mínima de Steiner, que tambem é NP-dificil. Na primeira parte do trabalho, temos a seguinte questão como motivação: ¿Como projetar uma boa rede, ou seja, uma rede que satisfaça todas as propriedades do problema e ao mesmo tempo minimize o custo de construção desta rede?¿ 'E nesta parte que os algoritmos de aproximação entram em ação. Uma vez que esse custo for determinado, na segunda parte do trabalho, uma outra questão surge: ¿Como dividir esse custo entre todos os usuários que participam da rede de uma maneira ¿justa¿? Nesta parte, usaremos o compartilhamento de custos juntamente com as tecnicas de algoritmos de aproximação para responder a essa questão / Abstract: We consider the interplay of two areas: combinatorial optimization and cost-sharing in network design problems. In the first, we are interested to find a solution with small cost. In the second we would like to share the solution cost between its users. We present algorithms for the problems ¿Connected Facility Location¿ and ¿Rent-or-Buy¿. These two problems are NP-hard, since they have as a particular case the minimum Steiner tree problem, which is a known NP-hard problem. In the first part of this work, we have the following question as motivation: ¿how to design a good network, i.e., one that satisfies all problem requirements and minimize the overall network construction cost?¿ In this part, approximation algorithms takes action. Once this cost is determinated, in the second part of the work, another question arises: ¿How to distribute this cost among all users that participate in the network in a ¿fair¿ way? In this part, we will use cost-sharing together with approximation algorithms techniques to answer this question / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientador: Zanoni Dias / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T23:02:27Z (GMT). No. of bitstreams: 1 Galvao_GustavoRodrigues_M.pdf: 1280667 bytes, checksum: 0809ad85a3b7f16ff5d7af5fc4124f0a (MD5) Previous issue date: 2012 / Resumo: Ao longo da evolução, mutações globais podem alterar a ordem dos genes de um genoma. Tais mutações são chamadas de eventos de rearranjo. Em Rearranjo de Genomas, estimamos a distância evolutiva entre dois genomas calculando-se a distância de rearranjo entre eles, que é o tamanho da menor sequência de eventos de rearranjo que transforma um genoma no outro. Representando genomas como permutações, nas quais os genes aparecem como elemento, à distância de rearranjo pode ser obtido resolvendo-se o problema combinatório de ordenar uma permutação utilizando o menor número de eventos de rearranjo. Este problema, que é referido como Problema da Ordenação por Rearranjo, varia de acordo com os tipos de eventos de rearranjo considerados. Nesta dissertação, focamos nosso estudo em dois tipos de eventos: reversões e transposições. Variações do Problema da Ordenação por Rearranjo que consideram esses eventos têm se mostrado difíceis de ser resolvida otimamente, por isso a maior parte dos algoritmos propostos - os quais denominamos genericamente por algoritmos de rearranjo de genomas - são aproximados e é esperado que os próximos avanços ocorram nesse sentido. Em razão disso, desenvolvemos uma ferramenta que avalia as respostas desses algoritmos. Para ilustrar sua aplicação, nós a utilizamos para avaliar as respostas de 16 algoritmos de rearranjo de genomas aproximados relativos a 6 variações do Problema da Ordenação por Rearranjo. Além da ferramenta, este trabalho traz outras contribuições. Desenvolvemos um algoritmo exato para calcular distâncias de rearranjo que é mais eficiente em termos de uso de memória do que qualquer outro algoritmo que encontramos na literatura. Apresentamos conjecturas que dizem respeito à forma como as distâncias de rearranjo se distribuem. Validamos conjecturas referentes ao diâmetro, que é o maior valor alcançável pela distância de rearranjo entre uma permutação qualquer e a identidade considerando-se todas as permutações com o mesmo número de elementos. Apresentamos demonstrações formais para o fator de aproximação de alguns dos algoritmos avaliados. Por fim, mostramos que os fatores de aproximação de 7 dos 16 algoritmos avaliados não podem ser melhorados, o que contradiz algumas hipóteses levantadas na literatura, e conjecturamos que os fatores de aproximação de outros 6 algoritmos também não possam / Abstract: During evolution, global mutations may modify the gene order in a genome and such mutations are called rearrangement events. In Genome Rearrangements, we estimate the evolutionary distance between two genomes by computing the rearrangement distance between them, which is the length of the shortest sequence of rearrangement events that transforms one genome into the other. Representing genomes as permutations, in which genes appear as elements, the rearrangement distance can be obtained by solving the combinatorial problem of sorting a permutation using a minimum number of rearrangement events. This problem is referred to as Rearrangement Sorting Problem and varies accordingly to the types of rearrangement events considered. In this dissertation, we focus on two types of rearrangement events: reversals and transpositions. Variants of Rearrangement Sorting Problem involving these events have been shown to be difficult to solve optimally, therefore most of the proposed algorithms - which we denominate generically as genome rearrangement algorithms - are approximations, which have been the expected direction to follow. For this reason, we developed a tool that evaluates the results of these algorithms. To illustrate its application, we used it to evaluate the results of 16 genome rearrangement algorithms regarding 6 variants of Rearrangement Sorting Problem. Besides this tool, we developed an exact algorithm for computing rearrangement distances that is more efficient in terms of memory than any algorithm we have found in literature. Additionally, we presented conjectures on how the rearrangement distance are distributed and validated them regarding their diameter, which is the greatest value that the rearrangement distance between a permutation and the identity can reach considering all permutations with the same number of elements. Moreover, we presented formal proofs on the approximation ratio of some of the evaluated algorithms and showed that the approximation ratio of 7 out of the 16 evaluated algorithms cannot be improved, which contradicts some hypothesis raised in literature. Lastly, we conjectured that the approximation ratio of another 6 algorithms also cannot be improved / Mestrado / Ciência da Computação / Mestre em Ciência da Computação