Orientador: Reginaldo Palazzo Junior / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T22:23:13Z (GMT). No. of bitstreams: 1 Queiroz_CatiaReginadeOliveiraQuilles_D.pdf: 1560188 bytes, checksum: 2b21f95bbc77dac42e165eb38509518e (MD5) Previous issue date: 2011 / Resumo: Neste trabalho apresentamos a construção de códigos geometricamente uniformes derivados de grafos sobre anéis quocientes de inteiros e de ordens dos quatérnios. Inicialmente propomos um procedimento para a geração de códigos quase-perfeitos derivados de grafos sobre anéis quocientes de inteiros, que além de serem geometricamente uniformes, são capazes de corrigir mais padrões de erros que os códigos perfeitos, porém com uma menor cardinalidade. Além disso, observamos que os códigos perfeitos são um caso particular dos códigos quase-perfeitos. Os códigos geometricamente uniformes derivados de quocientes de ordens dos quatérnios foram obtidos de forma similar, porém a geometria relacionada é a hiperbólica e os códigos derivados estão no plano hiperbólico. A estrutura algébrica associada a essa classe de códigos não havia sido obtida até então para esta geometria. Apresentamos ainda um procedimento para o rotulamento de pontos gerados por tesselações do plano hiperbólico no disco de Poincaré, e obtemos a representação geométrica dos códigos obtidos / Abstract: In this work we present the construction of geometrically uniform codes derived from graphs over quotient rings of integers and quaternion orders. Initially we propose a procedure to generate quasi-perfect codes derived from graphs over quotient rings of integers, which in addition to preserving the property of being geometrically uniform codes they are able to correct more error patterns than the perfect codes, by decreasing its cardinality. Furthermore, we observe that the perfect codes are a particular case of the quasi-perfect codes. The geometrically uniform codes derived from quotient of the quaternion orders are obtained similarly as in the previous case, however the related geometry is the hyperbolic and the derived codes are on the hyperbolic plane. The algebraic structure associated with this class of codes had not been obtained so far for this geometry. We also present a procedure for labeling the points generated by tesselations of the Poincaré disk, and showing the geometric representation of the aforementioned codes / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientadores: Reginaldo Palazzo Junior, Eduardo Brandani da Silva / Tese (doutorado) - Universidade Estadula de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T12:13:26Z (GMT). No. of bitstreams: 1 Albuquerque_ClariceDiasde_D.pdf: 1059216 bytes, checksum: 2cecc7c883d512057587e36d3635e775 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho apresentamos um amplo estudo de códigos quânticos topológicos, trazendo inovação para esta área. Inicialmente geramos novos códigos quânticos teóricos, dentre os quais se destaca a classe [[d2,2,d]] cujos parâmetros são os melhores ate então apresentados para este tipo de código. Nesta proposta sistematizamos a construção de códigos teóricos baseados em teoria de grupos e também em analise combinatória. Com respeito aos códigos quânticos topológicos em superfícies com gênero g = 2, apresentamos uma construção baseada em geometria hiperbólica, generalizando a construção de Kitaev. Reproduzimos e ampliamos a classe de códigos quânticos com distancia 3 decorrentes de mergulhos de grafos completos em superfícies com gêneros específicos obtidos primeiramente por Bombin e Martin-Delgado, com o diferencial de descreve-los geometricamente e exibir claramente seus parâmetros. Obtemos uma classe de códigos MDS Maximum Distance Separable). Explicitamos em tabelas os melhores códigos para superfícies com gênero g = 2,3,4 e 5 obtidos a partir dessa construção, e analisamos esses resultados. / Abstract: In this work we present an extensive study of topological quantum codes. As a consequence, new promising ideas, concepts and results are also presented. First of all, new toric quantum codes are constructed among which the [[d2,2,d]] class stands out as the best known so far. This proposed construction of toric codes is realized based upon group theory and combinatorial analysis. Regarding the topological quantum codes in surfaces with genus g = 2, we consider a construction method based on hyperbolic geometry and so generalizing Kitaev's construction. We reproduce and enlarge the class of quantum codes with distance 3 as a consequence of the embedding of complete graphs in surface with specific genus. This class was first proposed by Bombin andMartin-Delgado. The latter class is geometrically described and its parameters are explicitly exhibited. We also obtain a class of MDS (Maximum Distance Separable) codes in surfaces with genus g = 2,3,4 and 5, obtained by the proposed construction are tabulated and analyzed. / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientadores: Sueli Irene Rodrigues Costa, Patricia Helena Araujo da Silva Nogueira / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-15T04:07:16Z (GMT). No. of bitstreams: 1 Naves_LigiaRodriguesBernabe_M.pdf: 1248780 bytes, checksum: a87e22d1d349ffc57557fdb83454f7d3 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho, estudamos a teoria de reticulados com foco na densidade de empacotamento, a qual possui várias aplicações e possibilita estabelecer interessantes conexões entre tópicos de álgebra linear, cálculo de várias variáveis e geometria discreta. No primeiro capítulo, introduzimos conceitos fundamentais sobre reticulados. No segundo capítulo, abordamos a densidade de empacotamentos esféricos e analisamos a importância e a dificuldade de se conhecer os empacotamentos mais densos. Discutimos também exemplos de reticulados com densidade máxima em suas dimensões. No terceiro capítulo, detalhamos a demonstração do teorema de Minkowski - Hlawka, que fornece um limitante inferior para a densidade de empacotamentos reticulados. Apresentamos também o problema dos fat struts, que tem origem em teoria de comunicação e que se relaciona com a busca de reticulados-projeção de densidade máxima / Abstract: This dissertation addresses the lattice theory with focus on packing density, which has many applications and allows to establish interesting connections between topics of linear algebra, calculus of several variables and discrete geometry. The first chapter is an introduction to the main concepts and properties of lattices. In the second chapter we discuss the sphere packing density problem, its importance and the difficulty in finding denser packings. Examples of lattices with maximum density are analyzed for lower dimensions. In the third chapter we detail the proof of the theorem of Min-kowski - Hlawka which provides a lower bound for lattice packing density of lattices in any dimension. We also present the problem of the fat struts which comes from communication theory and is related to the search for denser projection lattices / Mestrado / Geometria Topologia / Mestre em Matemática

Orientadores: Sueli Irene Rodrigues Costa, João Eloir Strapasson / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-24T22:37:48Z (GMT). No. of bitstreams: 1 Campello_A._D.pdf: 21969130 bytes, checksum: 2383d030b9ec589aaedae38670dbb458 (MD5) Previous issue date: 2014 / Resumo: O conteúdo desta tese reside na interface entre Matemática Discreta (particularmente reticulados) e Teoria da Informação. Dividimos as contribuições originais do trabalho em quatro capítulos, de modo que os dois primeiros são relativos a resultados teóricos acerca de duas importantes classes de reticulados (os reticulados q-ários e os reticulados projeção), e os dois últimos referem-se a aplicações em codificação contínua fonte-canal. Nos primeiros capítulos, exibimos resultados sobre decodificação de reticulados q-ários e sobre ladrilhamentos associados a códigos corretores de erros perfeitos na norma l_p. No que tange a reticulados projeção, nossas contribuições incluem o estudo de sequências de projeção de um dado reticulado n-dimensional convergindo para qualquer reticulado k-dimensional fixado, k < n, incluindo uma análise de convergência de tais sequências. Esses novos resultados relativos a projeções estendem e aprimoram recentes trabalhos no tema e são elementos de base para as aplicações consideradas no restante da tese. Nos dois últimos capítulos, consideramos o problema de transmitir uma fonte com alfabeto contínuo através de um canal gaussiano no caso em que a dimensão da fonte, k, é menor que a dimensão do canal, n. Para fontes unidimensionais, exibimos códigos baseados em curvas na superfície de toros planares com performance significativamente superior aos propostos anteriormente na literatura no que diz respeito ao erro quadrático médio atingido. Para k > 1, mostramos como aplicar projeções de reticulados para obter códigos cujo erro quadrático médio possui decaimento ótimo com respeito à relação sinal-ruído do canal (chamados de assintoticamente ótimos). Através de técnicas provenientes da bela teoria de dissecção de poliedros, apresentamos as primeiras construções de códigos assintoticamente ótimos para fontes com dimensão maior do que 1 / Abstract: The contents of this thesis lie in the interface between Discrete Mathematics (particularly lattices) and Information Theory. The original contributions of this work are organized so that the first two chapters are devoted to theoretical results on q-ary and projection lattices, whereas the last ones are related to the construction of continuous source-channel codes. In the first chapters, we exhibit results on decoding q-ary lattices and on finding tilings associated to perfect error-correcting codes in the l_p norm. Regarding projection lattices, our contributions include the study of sequences of projections of a given n-dimensional lattice converging to any k-dimensional target lattice, as well as a convergence analysis of such sequences. These new results on projections extend and improve recent works on the topic and serve as building blocks for the applications to be developed throughout the last part of the thesis. In the last two chapters, we consider the problem of constructing mappings for the transmission of a continuous alphabet source over a Gaussian channel, when the channel dimension, n, is strictly greater than the source dimension, k. For one-dimensional sources, we exhibit codes based on curves on flat tori with performance significantly superior to the previous proposals in the literature with respect to the mean squared error achieved. For k > 1, we show how to apply projections of lattices to obtain codes whose mean squared error decays optimally with respect to the signal-to-noise ratio of the channel (referred to as asymptotically optimal codes). Through techniques from the rich theory of dissections of polyhedra, we present the first constructions of provenly asymptotically optimal codes for sources with dimension greater than 1 / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Peter Sussner / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-21T14:39:08Z (GMT). No. of bitstreams: 1 Medeiros_CarlosRenato_M.pdf: 3281824 bytes, checksum: 90da4e6d96fe7557a92fa34f461172e7 (MD5) Previous issue date: 2012 / Resumo: Em meados dos anos 90, a memória associativa morfológica (MAM) foi apresentada como um modelo de memória associativa distributiva que realiza determinadas operações morfológicas definidas na teoria matemática de álgebra mini-max. Os modelos de MAMs vêm em duas versões diferentes que são tolerantes a diferentes tipos de ruído nos padrões de entrada. Para superar esta desvantagem, recorremos à teoria mais recente da morfologia matemática em inf-semirreticulado cujos operadores elementares são autoduais e definimos um modelo de memória associativa neste quadro / Abstract: In the mid 1990's, the morphological associative memory (MAM) was introduced as a distributive associative memory model that performs certain morphological operations defined in the mathematical theory of mini-max algebra. MAM models come in two different versions that are tolerant to different types of noise in the input patterns. To overcome this drawback, we resort to the more recent theory of mathematical morphology (MM) on inf-semilattices whose elementary operators are self-dual and we define an associative memory (AM) model in this framework / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Sueli Irene Rodrigues Costa / 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-20T13:21:10Z (GMT). No. of bitstreams: 1 Tsuchiya_LucianaYoshie_M.pdf: 11296327 bytes, checksum: 3b12c518b500ac555263de03beead341 (MD5) Previous issue date: 2012 / Resumo: Reticulados no 'R^n' são conjuntos discretos de pontos gerados como combinações inteiras de vetores linearmente independentes. A estrutura e as propriedades de reticulados vêm sendo exploradas em diversas áreas, dentre elas a Teoria da Informação. Neste trabalho fizemos um estudo de reticulados q-ários na métrica da soma, os quais estão relacionados aos códigos q-ários. Iniciamos com o estudo de reticulados gerais abordando questões como, densidade de empacotamento, determinação da região de Voronoi, equivalência de reticulados e processos de decodificação, fazendo um paralelo destas questões na métrica euclidiana e na métrica da soma. Em seguida, no Capitulo 2, tratamos brevemente os conceitos de códigos corretores de erros, onde os códigos q-ários estão inseridos e códigos lineares definidos sobre corpos finitos. No estudo dos códigos q-ários consideramos a distancia de Lee que e uma alternativa a usual métrica de Hamming. Por fim, no Capitulo 3, abordamos os reticulados q-ários que são obtidos a partir de códigos q-ários pelo processo conhecido como Construção A. Estudamos uma forma de se decodificar um reticulado q-ário via a Construção A, usando a decodificação do código e vice-versa e discutimos um algoritmo de decodificação (Lee Sphere Decoding) para reticulados q-ários que possuem matriz geradora de formato especial / Abstract: Lattices in 'R^n' are discrete sets of points generated as integer combinations of linearly independent vectors. The structure and properties of lattices have been explored in several areas, including Information Theory. In this work, we study q-ary lattices which are obtained from q-ary codes in the sum metric. We begin the study of general lattices, approaching topics as packing density, Voronoi regions, lattice equivalence and decoding processes, considering both the Euclidean and sum metric. In Chapter 2, we introduce some error correcting codes concepts focusing on q-ary codes and the more general class of linear codes defined over finite fields. In the study of q-ary codes, we consider the Lee distance, as an extension and alternative to the usual Hamming metric. Finally, in Chapter 3, we approach the q-ary latt ices, which are obtained from q-ary codes via the so called Construction A. We study a q-ary lattice decoding process, relate it to the associate code decoding and discuss a decoding algorithm for lattices which have special generator matrices / Mestrado / Matematica / Mestre em Matemática

The purpose of this project was to study the classical result in this direction discovered by O. Ore in 1938, as well as related theorems and corollaries. Ore's Theorem and its corollaries provide us with several results relating distributive lattices with cyclic groups.

We present a novel theorem of Borel Combinatorics that sheds light on the types of continuous functions that can be defined on the Cantor space. We specifically consider the part X=F(2ᴳ) from the Cantor space, where the group G is the additive group of integer pairs ℤ². That is, X is the set of aperiodic {0,1} labelings of the two-dimensional infinite lattice graph. We give X the Bernoulli shift action, and this action induces a graph on X in which each connected component is again a two-dimensional lattice graph. It is folklore that no continuous (indeed, Borel) function provides a two-coloring of the graph on X, despite the fact that any finite subgraph of X is bipartite. Our main result offers a much more complete analysis of continuous functions on this space. We construct a countable collection of finite graphs, each consisting of twelve "tiles", such that for any property P (such as "two-coloring") that is locally recognizable in the proper sense, a continuous function with property P exists on X if and only if a function with a corresponding property P' exists on one of the graphs in the collection. We present the theorem, and give several applications.

In this work, we present a lattice QCD calculation of two closely related quantities: 1). The 𝜋𝜋 scattering phase shift for both 𝑰=0 and 𝑰=2 channels at seven energies in total, and 2). The 𝜟𝑰=1/2, 𝛫 → 𝜋𝜋 decay amplitude 𝐴₀ and 𝜖′, the measure of direct CP violation. These two results improve our earlier calculation presented in 2015 [1]. The calculation is performed on an ensemble of 32³ × 64 lattice with 𝛼⁻¹=1.3784(68)GeV. This is a physical calculation, where the chiral symmetry breaking is controlled by the 2+1 flavor Möbius Domain Wall Fermion, and we take the physical value for both kaon and pion. The G-parity boundary condition is used and carefully tuned so that the ground state energy of the 𝜋𝜋₁₌₀ state matches the kaon mass. Three sets of 𝜋𝜋 interpolating operators are used, including a scalar bilinear ``σ" operator and paired single-pion bilinear operators with the constituent pions carrying various relative momenta. Several techniques, including correlated fits and a bootstrap determination of the 𝑝-value have been used, and a detailed analysis of all major systematic error is performed. The 𝜋𝜋 scattering phase shift results are presented in Fig. 5.10 and Tab. 5.12. For the Kaon decay amplitude, we finally get Re(𝐴₀) = 2.99(0.32)(0.59) × 10⁻⁷GeV, which is consistent with the experimental value of Re(𝐴₀) = 3.3201(18) × 10⁻⁷GeV, and Im(𝐴₀) = -6.98(0.62)(1.44) × 10⁻¹¹GeV. Combined with our earlier lattice calculation of 𝐴₂ [2], we obtained Re(𝜖′/𝜖) = 21.7(2.6)(6.2)(5.0) × 10⁻⁴, which agrees well with the experimental value of Re(𝜖′/𝜖) = 16.6(2.3) × 10⁻⁴, and Re(𝐴₀)/Re(𝐴₂) = 19.9(2.3)(4.4), consistent with the experimental value of Re(𝐴₀)/Re(𝐴₂) = 22.45(6), known as the 𝜟𝑰=1/2 rule.

Recently, Formal Concept Analysis has proven to be an efficient method for the analysis and representation of information. However, the possibility to visualize concept hierarchies is being affected by the difficulty of drawing attractive diagrams automatically. Reducing the number of edge crossings seems to increase the readability of those drawings. This dissertation concerns with a mandatory prerequisite of this constraint, namely the characterization and visual representation of planar lattices. The manifold existing approaches and algorithms are thereby considered under a different point of view. It is well known that exactly the planar lattices (or planar posets) possess an additional order ``from left to right''. Our aim in this work is to define left-relations and left-orders more precisely and to describe several aspects of planar lattices with their help. The three approaches employed structure the work in as many parts: Left-relations on lattices allow a more efficient consideration of conjugate orders since they are uniquely determined by the sorting of the meet-irreducibles. Additionally, the restriction on the meet-irreducibles enables us to achieve an intuitive description of standard contexts of planar lattices similar to the consecutive-one property. With the help of left-relations on diagrams, planar lattices can indeed be drawn without edge crossings in the plane. Thereby, lattice-theoretically found left-orders can be detected in the graphical representation again. Furthermore, we modify the left-right-numbering algorithm in order to obtain attribute-additive and plane drawings of planar lattices. Finally, we will consider left-relations on contexts. They turn out to be fairly similar structures to the Ferrers-graphs. Planar lattices can be characterized by a property of these graphs, namely the bipartiteness. We will constructively prove this result. Subsequently, we can design an efficient algorithm that finds all non-similar plane diagrams of a lattice. / Die Formale Begriffsanalyse hat sich in den letzten Jahren als effizientes Werkzeug zur Datenanalyse und -repräsentation bewährt. Die Möglichkeit der visuellen Darstellung von Begriffshierarchien wird allerdings durch die Schwierigkeit, ansprechende Diagramme automatisch generieren zu können, beeinträchtigt. Offenbar sind Diagramme mit möglichst wenig Kantenkreuzungen für den menschlichen Anwender leichter lesbar. Diese Arbeit beschäftigt sich mit mit einer diesem Kriterium zugrunde liegenden Vorleistung, nämlich der Charakterisierung und Darstellung planarer Verbände. Die schon existierenden vielfältigen Ansätze und Methoden werden dabei unter einem neuen Gesichtspunkt betrachtet. Bekannterweise besitzen genau die planaren Verbände (bzw. planare geordnete Mengen) eine zusätzliche Ordnung &amp;quot;von links nach rechts&amp;quot;. Unser Ziel in dieser Arbeit ist es, solche Links-Relationen bzw. Links-Ordnungen genauer zu definieren und verschiedene Aspekte planarer Verbände mit ihrer Hilfe zu beschreiben. Die insgesamt drei auftretenden Sichtweisen gliedern die Arbeit in ebensoviele Teile: Links-Relationen auf Verbänden erlauben eine effizientere Behandlung konjugierter Ordnungen, da sie durch die Anordnung der Schnitt-Irreduziblen schon eindeutig festgelegt sind. Außerdem erlaubt die Beschränkung auf die Schnitt-Irreduziblen eine anschauliche Beschreibung von Standardkontexten planarer Verbände ähnlich der consecutive-one property. Mit Hilfe der Links-Relationen auf Diagrammen können planare Verbände tatsächlich eben gezeichnet werden. Dabei lassen sich verbandstheoretisch ermittelte Links-Ordnungen in der graphischen Darstellung wieder finden. Weiterhin geben wir in eine Modifikation des left-right-numbering an, mit der planare Verbände merkmaladditiv und eben gezeichnet werden können. Schließlich werden wir Links-Relationen auf Kontexten betrachten. Diese stellen sich als sehr ähnlich zu Ferrers-Graphen heraus. Planare Verbände lassen sich durch eine Eigenschaft dieser Graphen, nämlich die Bipartitheit, charakterisieren. Wir werden dieses Ergebnis konstruktiv beweisen und darauf aufbauend einen effizienten Algorithmus angeben, mit dem alle nicht-ähnlichen ebenen Diagramme eines Verbandes bestimmt werden können.