Orientador: Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T18:42:28Z (GMT). No. of bitstreams: 1 Rezende_GermanoAbudde_D.pdf: 1418033 bytes, checksum: 61d29b02274278ede5ffca797e26371a (MD5) Previous issue date: 2014 / Resumo: A geometria de distâncias é o estudo da geometria baseado no conceito de distância. Ela é útil em várias aplicações, onde os dados de entrada consistem de um conjunto incompleto de distâncias, e a saída é um conjunto de pontos no espaço euclidiano, que realiza as distâncias dadas. No Problema de Geometria de Distâncias (DGP), é dado um inteiro K > 0 e um grafo simples, não direcionado, G = (V,E,d), cujas arestas são ponderadas por uma função não negativa d. Queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Um DGPk (com K fixado) está fortemente relacionado a um outro tipo de problema, que trata dos possíveis completamentos de uma certa matriz de distâncias euclidianas. Este último pode ser visto, em um certo sentido, como o "dual do primeiro problema". Neste trabalho, exploramos essa dualidade com a finalidade de propor melhorias no método Branch-and-Prune aplicado a uma versão discreta do DGPk / Abstract: Distance Geometry is the study of geometry based on the concept of distance. It is useful in many applications where the input data consists of an incomplete set of distances, and the output is a set of points in some Euclidean space which realizes the given distances. In the Distance Geometry Problem (DGP), it is given an integer K > 0 and a simple undirected weighted graph G = (V,E,d), whose edges are weighted by a non-negative function d. We want to determine if there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space satisfying all distance constraints given by d. A DGPk (with K fixed) is closely related to another type of problem, which treats the possible completions of a certain Euclidean distance matrix. In some sense, this is the "dual" of the first problem. We explore this duality in order to improve the Branch-and-Prune method applied to a discrete version of the DGPk / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T22:04:46Z (GMT). No. of bitstreams: 1 Fidalgo_FelipeDelfiniCaetano_D.pdf: 5383479 bytes, checksum: 8f7bf5142b44fa99ea2742f6183ee1c6 (MD5) Previous issue date: 2015 / Resumo: Motivado por estudos em estruturas 3D de proteínas, biomoléculas imprescindíveis no estudo da vida, surgiu um problema chamado Discretizable Molecular Distance Geometry Problem (DMDGP) que provou ser NP-Difícil. Para resolvê-lo, existe um algoritmo da literatura, Branch & Prune (BP), que utiliza uma estratégia combinatória de exploração de uma árvore binária de soluções associada ao problema. Além disso, foram descobertas relações de simetria que permitem obter uma solução, a partir de outra, através de reflexões nos chamados vértices de simetria. Alguns pesquisadores passaram a realizar este trabalho em paralelo (ParallelBP), dividindo uma instância em sub-instâncias, resolvendo localmente com o BP (o que pode ser feito em duas direções) e unindo as sub-soluções com movimentos rígidos, com o intuito de determinar as soluções em menor tempo. Nossa proposta é fornecer uma estratégia Dividir-e-Conquistar para resolver o DMDGP, de modo a melhorar a abordagem em paralelo. Ela possui três estágios. Inicialmente, dividimos uma instância em sub-instâncias duas-a-duas sobrepostas através dos vértices de simetria. Depois, utiliza-se os chamados gaps para decidir a direção em que o BP deve fornecer a solução local. Por fim, utilizamos rotações baseadas na Álgebra de Quatérnios para combinar as sub-soluções em soluções factíveis / Abstract: Motived by studies in 3D structures of proteins, essential biomolecules for Life, arised a problem called Discretizable Molecular Distance Geometry Problem (DMDGP) which proved to be NP-Hard. Aiming to solve it, there is an algorithm in the literature, Branch & Prune (BP), which uses a combinatorial strategy of exploring a binary tree of solutions that is associated to the problem. Moreover, some symmetry relations have been discovered which allows the obtainance of one solution from the other one by means of reflections in the so-called symmetry vertices. Some researchers started to do this work using parallel computing (ParallelBP), dividing one instance into sub-instances, solving the problem locally with the BP (what can be done in two directions) and joining the sub-solutions with rigid movements, with the objective of determining the solutions in a smaller time. Our purpose, thus, is to provide a Divide-and-Conquer strategy to solve the DMDGP in order to improve the parallel version. It has three stages. Initially, the instance is divided into sub-instances two-by-two overlapping by means of the symmetry vertices. After, the so-called gaps are used to decide the direction that the BP ought to provide the local solution. Finally, we propose to use Quaternion Rotations to combine sub-solutions into feasible solutions / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada