Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2005. / Includes bibliographical references (leaves 82-84). Also available in electronic version.

Thesis (Ph. D.)--Ohio State University, 2005. / Title from first page of PDF file. Document formatted into pages; contains xv, 151 p.; also includes graphics. Includes bibliographical references (p. 134-151). Available online via OhioLINK's ETD Center

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Thesis (M.Sc.)--York University, 2005. Graduate Programme in Mathematics and Statistics. / Typescript. Includes bibliographical references (leaves 99-102). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url%5Fver=Z39.88-2004&res%5Fdat=xri:pqdiss &rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR11932

Thesis (M.S.)--University of North Carolina at Greensboro, 2007. / Title from PDF title page screen. Advisor: Francine Blanchet-Sadri; submitted to the Dept. of Computer Science. Includes bibliographical references (p. 70-73).

Thesis (Ph. D.)--Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 115-119).

The traveling salesperson (or, salesman) problem (TSP) is a well known and important combinatorial optimization problem. The goal is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Despite this simple problem statement, solving the TSP is difficult since it belongs to the class of NP-complete problems. The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. Typical applications in operations research include vehicle routing, computer wiring, cutting wallpaper and job sequencing. The main application in statistics is combinatorial data analysis, e.g., reordering rows and columns of data matrices or identifying clusters. In this paper, we introduce the R package TSP which provides a basic infrastructure for handling and solving the traveling salesperson problem. The package features S3 classes for specifying a TSP and its (possibly optimal) solution as well as several heuristics to find good solutions. In addition, it provides an interface to Concorde, one of the best exact TSP solvers currently available. (authors' abstract)

Determining the minimum distance between two objects is a problem that has been solved using many different approaches. Most methods proposed so far are, in essence, limited to solve the problem amongst convex polyhedra. Thus, to deal with concave objects, these methods partition concave objects into convex sub-objects and solve the convex problem between all possible sub-object combinations. This adds a large computational expense, especially when the concave objects in the scene are complicated, or when concave quadratically bound objects are to be linearized. In this work, two optimization-based formulations are proposed to solve the minimum distance problem without the need for partitioning concave objects into convex sub-objects. The first one, referred to as the continuous approach, uses concepts of computational solid geometry in order to represent objects with concavities. On the other hand, in the second formulation, referred to as the combinatorial approach, the geometries of the objects are replaced by large sets of points arranged in surface meshes. Since the optimization problem is not unimodal (i.e., has more than one local minimum point), global optimization techniques are used. Simulated Annealing and Genetic Algorithms, with constraint handling techniques such as penalty and repair strategies are used in the continuous approach. In order to eliminate the computational expense of determining the feasibility of every trial point, the combinatorial approach replaces the objects' geometry by a set of points on the surface of each object. This reduces the minimum distance problem to an unconstrained combinatorial optimization problem where the combination of points (one on each object) that minimizes the distance between objects is the solution. Additionally, Genetic Algorithms with niche formation techniques were developed in order to allow the distance algorithm to track multiple minima. In a series of numerical examples, a preliminary implementation of the proposed algorithms has proven to be robust and equivalent, in terms of computational efficiency, to some conventional approaches. / Graduate

The main results of this dissertation are various algorithms related to partially ordered sets. The dissertation basically consists of two parts. The first part treats algorithms that generate ideals of partially ordered sets. The second part concerns the generation of partially ordered sets themselves. First, we present two algorithms for listing ideals of a forest poset. These algorithms generate ideals in a Gray Code manner, that is, consecutive ideals differ by exactly one element. Both algorithms use storage O(n), where n is the number of elements in the poset. The first algorithm traverses, at each phase, the current ideal being listed and runs in time O(nN), where N is the number of ideals of the poset. The second algorithm mimics the first but eliminates the traversal and runs in time O(N). This algorithm has the property that the amount of computation between successive ideals is O(1). Secondly, we give orderly algorithms for constructing acyclic digraphs, acyclic transitive digraphs, finite topologies and finite topologies and finite lattices. For the first time we show that the number of finite lattices on 11, 12, and 13 elements are 37622, 262775, and 2018442, respectively, and the number of finite topologies on 8 and 9 elements are 35979 and 363083, respectively. We also describe orderly algorithms for generating k-colored graphs. We present, in particular, an algorithm for generating connected bicolorable graphs. We also prove some properties of a canonic matrix which might be generally useful for improving the efficiency of orderly algorithms. / Graduate

Made available in DSpace on 2014-06-12T16:01:15Z (GMT). No. of bitstreams: 2 arquivo7278_1.pdf: 2063761 bytes, checksum: eaeb6780fe875052548e747b8a3af1a9 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005 / A regulação gênica está intimamente ligada com a transcrição de proteínas, e esse mecanismo é muito importante para o desenvolvimento dos seres vivos, pois é através dele que os organismos conseguem sintetizar proteínas. Um interessante problema da biologia moderna é o entendimento de mecanismos da regulação da transcrição. Muitos aspectos dessa regulação envolvem fatores de transcrição (proteínas ligantes ao DNA). Esses fatores regulam a expressão gênica pela conexão em posições específicas de regiões do genoma (conjunto de genes de uma espécie) que podem estar próximas ou não, como veremos em maiores detalhes oportunamente. Os fatores de transcrição conectam-se a subseqüências especificas de DNA, os promotores, que podem, com dificuldade, ser determinados por análises biológicas. Esse alto grau de dificuldade motiva os cientistas a procurarem meios computacionais mais rápidos e eficientes para solucionar o problema da busca pelos sítios de ligação dos promotores. O crescente aumento da disponibilidade de seqüências completas de genoma motiva tentativas de entender e modelar o mecanismo regulatório através de análises computacionais. A identificação de sítios de ligação envolve duas etapas principais: aprender modelos de sítios de ligação e buscar sítios em novas seqüências. Parte do trabalho foi desenvolver uma ferramenta para auxiliar os cientistas na busca por essas regiões especiais, os motifs, no genoma. Como desenvolvemos essa ferramenta usando Java, combinamos o fonema inglês da letra "J" com o sufixo "nom" da palavra "genom" para compor o nome da ferramenta e a chamamos de Jnom. A primeira tarefa é aprender modelos de sítios de ligação em potencial em um dado genoma. Usam-se exemplos de sítios de ligação verificados biologicamente e tenta-se encontrar sítios similares em outras regiões promotoras. Em seguida, é necessário descobrir uma seqüência de motifs em uma coleção de longas seqüências que são supostamente ligadas pelo mesmo fator. Neste caso, um motif encontrado indica um possível fator desconhecido que regula o conjunto de genes. A natureza combinatória dos fatores de transcrição é o mecanismo pelo qual as células dos seres superiores (eucariotes) atuam para controlar a expressão de conjuntos inteiros de genes. A intenção deste trabalho é investigar essa natureza combinante e tentar utilizar esse fato para melhorar o desempenho em relação a ferramentas existentes. O principal objetivo dessa pesquisa é construir uma ferramenta capaz de considerar a ação combinada dos fatores de transcrição através da seqüência de genes para encontrar novos motifs a partir de alguns já conhecidos