<p>This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an <i>optimal realization</i> of a given finite metric space: a weighted graph which preserves the metric's distances and has minimal total edge weight. This problem is known to be NP-hard, and solutions are not necessarily unique.</p><p>It has been conjectured that <i>extremally weighted</i> optimal realizations may be found as subgraphs of the <i>hereditarily optimal realization</i> Γ_d, a graph which in general has a higher total edge weight than the optimal realization but has the advantages of being unique, and possible to construct explicitly via the <i>tight span</i> of the metric.</p><p>In Paper I, we prove that the graph Γ_d is equivalent to the 1-skeleton of the tight span precisely when the metric considered is <i>totally split-decomposable</i>. For the subset of totally split-decomposable metrics known as <i>consistent</i> metrics this implies that Γ_d is isomorphic to the easily constructed <i>Buneman graph</i>.</p><p>In Paper II, we show that for any metric on at most five points, any optimal realization can be found as a subgraph of Γ_d.</p><p>In Paper III we provide a series of counterexamples; metrics for which there exist extremally weighted optimal realizations which are not subgraphs of Γ_d. However, for these examples there also exists at least one optimal realization which is a subgraph.</p><p>Finally, Paper IV examines a weakened conjecture suggested by the above counterexamples: can we always find some optimal realization as a subgraph in Γ_d? Defining <i>extremal</i> optimal realizations as those having the maximum possible number of shortest paths, we prove that any embedding of the vertices of an extremal optimal realization into Γ_d is injective. Moreover, we prove that this weakened conjecture holds for the subset of consistent metrics which have a 2-dimensional tight span</p>

This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an optimal realization of a given finite metric space: a weighted graph which preserves the metric's distances and has minimal total edge weight. This problem is known to be NP-hard, and solutions are not necessarily unique. It has been conjectured that extremally weighted optimal realizations may be found as subgraphs of the hereditarily optimal realization Γd, a graph which in general has a higher total edge weight than the optimal realization but has the advantages of being unique, and possible to construct explicitly via the tight span of the metric. In Paper I, we prove that the graph Γd is equivalent to the 1-skeleton of the tight span precisely when the metric considered is totally split-decomposable. For the subset of totally split-decomposable metrics known as consistent metrics this implies that Γd is isomorphic to the easily constructed Buneman graph. In Paper II, we show that for any metric on at most five points, any optimal realization can be found as a subgraph of Γd. In Paper III we provide a series of counterexamples; metrics for which there exist extremally weighted optimal realizations which are not subgraphs of Γd. However, for these examples there also exists at least one optimal realization which is a subgraph. Finally, Paper IV examines a weakened conjecture suggested by the above counterexamples: can we always find some optimal realization as a subgraph in Γd? Defining extremal optimal realizations as those having the maximum possible number of shortest paths, we prove that any embedding of the vertices of an extremal optimal realization into Γd is injective. Moreover, we prove that this weakened conjecture holds for the subset of consistent metrics which have a 2-dimensional tight span

Orientadores: Sueli Irene Rodrigues Costa, Jose Plinio de Oliveira Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T23:35:30Z (GMT). No. of bitstreams: 1 Torezzan_Cristiano_D.pdf: 2362096 bytes, checksum: 1680bc5fc7cb94a63b0b11b50ac5a1c4 (MD5) Previous issue date: 2009 / Resumo: Códigos esféricos em espaços euclidianos n-dimensionais são conjuntos finitos de pontos sobre superfícies esféricas e têm sido amplamente estudados em conexão com a transmissão de sinais sobre um canal Gaussiano. Para este propósito deseja-se maximizar a distância mínima entre dois pontos quaisquer do código, o que está fortemente relacionado com o problema mais geral do empacotamento em esferas, o qual contempla aplicações em outras áreas. Na primeira parte deste trabalho estudamos códigos esféricos gerados como órbita de um vetor unitário sob a ação de um grupo comutativo de matrizes ortogonais, os denominados códigos de grupo comutativo. Propomos um método para obter o melhor código de grupo comutativo n-dimensional de ordem M, que baseia-se na associação entre tais códigos em dimensão 2k e reticulados k-dimensionais. Utilizando fatorações matriciais conhecidas, como as formas normais de Hermite e Smith, demonstramos que é possível reduzir o número de casos a serem analisados através da identificação de códigos isométricos que podem ser descartados. O problema da busca do vetor inicial ótimo para códigos de grupo comutativo é formalmente estabelecido com um problema de programação linear e utilizado em uma das etapas do método. Apresentamos resultados numéricos, incluindo tabelas com códigos de grupo comutativo ótimos em várias dimensões. Outra contribuição deste trabalho é a introdução de uma nova família de códigos esféricos, na qual os pontos são alocados sobre a superfície da esfera unitária 2k-dimensional em camadas de toros planares. Em cada uma das camadas deste código, pode-se estabelecer um código de grupo para a geração dos sinais e utilizar os resultados acima mencionados. Além de limitantes, inferior e superior, para o número de pontos, um método para construção destes códigos é apresentado explicitamente e alguns exemplos são construídos. Os resultados mostram que tais códigos têm desempenho comparável aos melhores códigos esféricos estruturados conhecidos, com destaque para uma potencial vantagem no processo de codificação/decodificação, decorrente da homogeneidade, estrutura de grupo e associação a reticulados na metade da dimensão / Abstract: Spherical codes in Euclidean spaces are finite sets of points on the surface of a multidimensional sphere and have been widely studied in connection with the signal transmission over a Gaussian channel. For this purpose one fundamental issue is to maximize the minimum distance between two code points, what is strongly related to the more general problem of sphere packing. In the first part of this work we study spherical codes generated as orbit of a initial vector under the action of a commutative group of orthogonal matrices, the so called commutative group codes. A method for searching the best n-dimensional commutative group code of order M is presented. Based on the well known Hermite and Smith normal form decomposition of matrices, and also on the relation between 2k-dimensional com- mutative group codes and k-dimensional lattices, we show that it is possible to reduce the number of cases to be analyzed through the identification of isometric codes which can be discarded. The initial vector problem for these codes is formally established as a linear programming problem and used as a sub-routine of the method. Numerical results are presented, including tables of good commutative groups codes in several dimensions. Other contribution of this work is a new class of spherical codes, constructed by placing points on flat tori layers. The codebook on each torus can be generated by a commutative group of orthogonal matrices, using the results previously mentioned. Upper and lower bounds on performance are derived and a systematic method for constructing the codes is presented. Some examples are constructed and the results exhibit good performance when compared to the best known structured spherical codes, with some advantage in the encoding/decoding process, due to the homogeneity, group structure and the relation with lattices in the half of the dimension / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Cristiano Torezzan / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Cientíca / Made available in DSpace on 2018-08-19T06:29:05Z (GMT). No. of bitstreams: 1 Gouvea_DrielsonDavisonSilva_M.pdf: 2943642 bytes, checksum: 7e5df67721c42a7942f4baee18f152f9 (MD5) Previous issue date: 2011 / Resumo: Neste trabalho estuda-se o problema do vetor mais próximo em reticulados. Este problema consiste em encontrar um vetor de um reticulado mais próximo de um ponto dado do Rn e é conhecido também como problema da decodificação em reticulados. Estuda-se de forma específica algoritmos para o problema do vetor mais próximo para os reticulados raízes Zn, An e Dn. Além de uma breve revisão da literatura, os algoritmos para decodificação nesses reticulados são apresentados em detalhes, incluindo exemplos e também os códigos utilizados para implementação desses métodos na linguagem do software livre Scilab. Algumas simulações numéricas foram feitas utilizando esses códigos para investigar o tempo gasto na decodificação em função da dimensão do reticulado / Abstract: In this paper we study the nearest vector problem in lattices. This problem consists in finding a vector of a lattice closest to a given point of Rn and is also known as the decoding problem in lattices. It is studied in a specific algorithms for the nearest vector problem for lattices roots Zn, An and Dn. Besides a brief review of the literature, algorithms for decoding these lattices are presented in detail, including examples and also the codes used to implement these methods in the language of the free software Scilab. Some numerical simulations were done using these codes to investigate the time spent in decoding according to the size of the lattice / Mestrado / Matemática Universitária / Mestre em Matemática Universitária

Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Cientifica / Made available in DSpace on 2018-08-19T16:10:47Z (GMT). No. of bitstreams: 1 Jorge_GrasieleCristiane_D.pdf: 3823740 bytes, checksum: 772a88bd2136b4afb884a6e824f37bce (MD5) Previous issue date: 2012 / Resumo: O uso de códigos e reticulados em teoria da informação e na "chamada criptografia pós-quântica" vem sendo cada vez mais explorado. Neste trabalho estudamos temas relacionados a estas duas vertentes. A análise de reticulados foi feita via as métricas euclidiana e da soma. Para a métrica euclidiana, estudamos um algoritmo que procura pela treliça mínima de um reticulado com sub-reticulado ortogonal. No caso bidimensional foi possível caracterizar todos os sub-reticulados ortogonais de um reticulado racional qualquer. No estudo de reticulados via métrica da soma, trabalhamos com duas relações entre códigos e reticulados, conhecidas como "Construção A" e "Construção B". Generalizamos a Construção B para uma classe de códigos q-ários... Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: The use of codes and lattices in Information Theory and in the so-called "Post-quantum Cryptography" has been increasingly explored. In this work we have studied topics related to these two aspects. The analysis of lattices was made via Euclidean and sum metrics. For the Euclidean metric we studied an algorithm that searches for a minimum trellis of a lattice with orthogonal sublattice. In the two-dimensional case it has been possible to characterize all orthogonal sublattices of any rational lattice. In the study of lattices via sum metric, we worked with two relations between codes and lattices, the so-called "Construction A " and "Construction B". We generalized Construction B for the class of q-ary codes...Note: The complete abstract is available with the full electronic document / Doutorado / Matematica / Doutor em Matemática

Orientador: Sueli Irene Rodrigues Costa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-20T11:38:10Z (GMT). No. of bitstreams: 1 Ferrari_AgnaldoJose_D.pdf: 2344410 bytes, checksum: faa96ccdd8ff4ec461abc4f69d6cc999 (MD5) Previous issue date: 2012 / Resumo: Neste trabalho abordamos a construção de reticulados usando propriedades da Teoria Algébrica dos Números. Enfocamos a construção de alguns reticulados com características especiais, conhecidos na literatura, via reticulados ideais, através de uma abordagem matricial e algorítmica...Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: In this work we approach lattice constructions using properties of algebraic number theory. One focus is on the construction of some well known lattices via ideal lattices, through a matrix and algorithmic approach...Note: The complete abstract is available with the full electronic document / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

La tomographie consiste à reconstruire un objet nD à partir de projections (n-1)D. Cette discipline soulève plusieurs questions auxquelles la recherche essaie d’apporter des réponses. On s’intéresse dans cette thèse à trois aspects de cette problématique : 1) la reconstruction de l’image 2D à partir de projections dans un cadre rarement étudié qui est celui des sources ponctuelles ; 2) l’unicité de cette reconstruction ; 3) l'estimation d’informations concernant un objet sans passer par l'étape de reconstitution de son image. Afin d’aborder le problème de reconstruction pour la classe des ensembles convexes, nous définissons une nouvelle classe d’ensembles ayant des propriétés de convexité qu’on appelle convexité par quadrants pour des sources ponctuelles. Après une étude de cette nouvelle classe d’ensembles, nous montrons qu’elle présente des liens forts avec la classe des ensembles convexes. Nous proposons alors un algorithme de reconstruction d’ensemblesconvexes par quadrants qui, si l’unicité de la reconstruction est garantie, permet de reconstruire des ensembles convexes en un temps polynomial. Nous montrons que si une conjecture, que nous avons proposée, est vraie, les conditions de l’unicité pour les ensembles convexes par quadrants sont les mêmes que celles pour les ensembles convexes. Concernant le troisième aspect étudié dans cette thèse, nous proposons une méthode qui permet d’estimer, à partir d’une seule projection, la surface d’un ensemble 2D. Concernant l’estimation du périmètre d’un ensemble 2D, en considérant les projections par une deuxième source d’un ensemble convexe, nous obtenons deux bornes inférieures et une borne supérieure pour le périmètre de l’objet projeté. / Tomography is about reconstructing an nD object from its (n-1)D projections. This discipline addresses many questions to which research tries to provide answers. In this work, we are interested to three aspects: 1) the 2D image reconstruction from projections in a rarely studies framework that is the point sources; 2) the uniqueness of this reconstruction; 3) estimating information about an object without going through the step of reconstructing its image. To approach the problem of tomographic reconstruction for the class of convex sets, we define a new class of sets having properties of convexity called quadrant convexity for point sources. After a study of this new class of sets, we show that it presents strong links with the class of convex sets. Wepropose a reconstruction algorithm for quadrant-convex sets that, if the uniqueness of the reconstruction is guaranteed, allows the reconstruction of convex sets in polynomial time. We also show that if a conjecture we have proposed is true the conditions of uniqueness for quadrant-convex sets are the same as those for convex sets. Regarding the third aspect studied in this thesis, we focus on two quantitative properties that are the surface and the perimeter. We propose a method to estimate, from only one projection, the surface of a 2D set. We obtain two lower bounds and an upper bound for the perimeter of a projected convexobject by considering the projections from a second point source.

Une théorie fixé de la gravitation est loin d' être complète. La théorie plus prometteuse parmi ces théories de la gravité dans ce siècle est la relativité générale (RG), qui est toujours rencontre des obstacles par plusieurs problèmes. Les problèmes que nous soulignons dans cette thèse sont les aspects thermodynamiques et la quantification de la gravitation. Les tentatives proposées pour comprendre d'aspect thermodynamique de RG ont déjà été étudiés par la thermodynamique des trous noirs, alors que la théorie de la gravité quantique a déjà eu plusieurs des candidats, l'un d' entre eux était la gravité quantique à boucles (LQG), celui qui est la théorie base de notre travail. La théorie correcte de la gravité quantique devrait offrir une limite classique qui est correcte et consistent , ce qui évidemment , la relativité générale. / A fixed theory of gravity is far from being complete. The most promising theory of gravity in this century is general relativity (GR), which is still plagued by several problems. The problems we highlight in this thesis are the thermodynamical aspects and the quantization of gravity. Attempts to understand the termodynamical aspect of GR have already been studied through the thermodynamics of black holes, while the theory of quantum gravity has already had several candidates, one of them being the canonical loop quantum gravity (LQG), which is the base theory in our work.

No description available.

<p>The first class of problem we study deals with geometric matchings. Given a set<br />of points in the plane, we study perfect matchings of those points by straight line<br />segments so that the segments do not cross. Bottleneck matching is such a matching that minimizes the length of the longest segment. We are interested in finding a bottleneck matching of points in convex position. In the monochromatic case, where any two points are allowed to be matched, we give an O(n ²)-time algorithm for finding a bottleneck matching, improving upon previously best known algorithm of O(n ³) time complexity. We also study a bichromatic version of this problem, where each point is colored either red or blue, and only points of different color can be matched. We develop a range of tools, for dealing with bichromatic non-crossing matchings of points in convex<br />position. Combining that set of tools with a geometric analysis enable us to solve the<br />problem of finding a bottleneck matching in O(n ²) time. We also design an O(n)-time<br />algorithm for the case where the given points lie on a circle. Previously best known results were O(n 3 ) for points in convex position, and O(n log n) for points on a circle.<br />The second class of problems we study deals with dilation of geometric networks.<br />Given a polygon representing a network, and a point p in the same plane, we aim to<br />extend the network by inserting a line segment, called a feed-link, which connects<br />p to the boundary of the polygon. Once a feed link is fixed, the geometric dilation<br />of some point q on the boundary is the ratio between the length of the shortest path<br />from p to q through the extended network, and their Euclidean distance. The utility of<br />a feed-link is inversely proportional to the maximal dilation over all boundary points.<br />We give a linear time algorithm for computing the feed-link with the minimum overall<br />dilation, thus improving upon the previously known algorithm of complexity that is<br />roughly O(n log n).</p> / <p>Prva klasa problema koju proučavamo tičee se geometrijskih mečinga. Za dat skup tačaaka u ravni, posmatramo savr&scaron;ene mečinge tih tačaka spajajućii ih&nbsp; dužima koje &nbsp; se ne smeju sećui. Bottleneck mečing je takav mečing koji minimizuje dužinu najduže duži. Na&scaron; cilj je da nađemo bottleneck mečiing tačaka u konveksnom položaju.Za monohromatski slučaj, u kom je dozvoljeno upariti svaki par tačaka, dajemo algoritam vremenske složenosti O(n ²) za nalaženje bottleneck mečinga. Ovo&nbsp; je bolje od prethodno najbolji poznatog algoritam, čiija je složenost O(n ³). Takođe proučavamo bihromatsku verziju ovog problema, u kojoj je svaka tačka&nbsp; obojena ili u crveno ili u plavo, i dozvoljeno je upariti samo tačke različite boje. Razvijamo niz alata za rad sa bihromatskim nepresecajućim mečinzima tačaka u konveksnom položaju. Kombinovanje ovih alata sa geometrijskom analizom omogućava nam da re&scaron;imo problem nalaženja bottleneck mečinga u O(n ² ) vremenu. Takođe, konstrui&scaron;emo algoritam vremenske složenosti O(n) za slučaj kada&nbsp; sve date tačkke leže na krugu. Prethodno najbolji poznati algoritmi su imali složenosti&nbsp; O(n ³ ) za tačkeke u konveksnom položaju i O(n log n) za tačke na krugu.<br />Druga klasa problema koju proučaavamo tiče se dilacije u geometrijskim mrežama. Za datu mrežu predstavljenu poligonom, i tačku p u istoj ravni, želimo pro&scaron;iriti mrežu&nbsp; dodavanjem duži zvane feed-link koja povezuje p sa obodom poligona. Kada je feed- link fiksiran, defini&scaron;emo geometrijsku dilaciju neke tačke q na obodu kao odnos izme&nbsp; đu&nbsp; dužine najkraćeg puta od p do q kroz pro&scaron;irenu mrežu i njihovog Euklidskog rastojanja. Korisnost feed-linka je obrnuto proporcionalna najvećoj dilaciji od svih ta čaka na obodu poligona. Konstrui&scaron;emo algoritam linearne vremenske složenosti koji nalazi feed-link sa najmanom sveukupnom dilacijom. Ovim postižemo bolji rezultat od prethodno najboljeg poznatog algoritma složenosti približno O(n log n).</p>