源于几类信息科学问题的极值组合构型

发布时间：2017-12-31 08:45

本文关键词：源于几类信息科学问题的极值组合构型　出处：《浙江大学》2016年博士论文　论文类型：学位论文

【摘要】：信息科学与组合数学的交叉历来已久。信息科学在具体应用层面刺激着组合数学的发展,组合数学的体系的日臻成熟为信息科学的研究提供了理论支撑。信息科学中的若干问题,本质上都可以转化为一些组合数学中的极值构型问题。本学位论文将从组合数学的观点出发,融汇应用了图论、概率方法、极值组合等相关工具,对若干信息科学中的问题进行了一定的思考与推进。在第1章绪论部分,我们将简要介绍本文所涉及的各信息科学问题的相关背景,并概述本文对此问题所做的推进工作。在第2章中,我们的研究对象为置换群上的置换码与蛇形码,它们在电力线技术、分组密码、闪存中的排序调制等领域有着广泛应用。我们将对码字数目的研究转化为图论上的问题,通过构造合适的染色方案给出了图的独立数,进而分别改进了汉明距离和Kendall's τ-距离下的置换码的下界。Kendall's τ-距离下的蛇形码问题在奇数阶置换群和偶数阶置换群上有明显的区别。在S2n+1上我们严格证明了'Horovitz-Etzion构造”的可行性,并在其基础上进行微调得到了更优的蛇形码。在S2n+2上我们利用之前S2n+1中的蛇形码为基础进行复制与拼接,得到了非平凡的蛇形码构造,在渐进意义下达到最优。在第3章中,我们的研究对象为源于数字产品版权保护背景的合谋-安全码及相关哈希函数族。我们将对码字数目的研究转化为超图上的问题,进而借助超图的独立数的相关结论,改进了特定参数条件下完全哈希函数族、防诬陷码、可分离码的下界。这种利用超图模型的分析方法尚属首次。在第4章中,我们研究的问题是怎样的一个可逆二元矩阵中拥有最大比例的2×2可逆子矩阵。这个纯粹的组合问题的研究背景可追溯于图灵奖得主Ron Rivest为进一步加强分组密码的安全性所提出的一种预处理步骤—AONT变换。我们通过建立问题的整数规划,结合概率方法的分析,完全确定了此问题的最优解,并以分圆构造为基础给出了近似最优的矩阵构造方法。在第5章中,我们研究的问题为多部希尔伯特空间中的不可扩展乘积基的最小规模问题。此问题是量子信息学中的最基本问题之一,在量子信息的诸多领域有着广泛的应用。我们综合利用图的正交表示、循环图的连通性、图的1-因子分解等若干图论工具,决定了一系列参数下的最小规模UPB的大小的准确值。在第6章中对其它在研问题做了简要汇报。
[Abstract]:Cross information science and math has always been for a long time. Information Science in the specific application level to stimulate the development of combinatorial mathematics, combinatorial mathematics system has matured for information science research provides a theoretical support. Some problems in Information Science, into some mathematical combination of extreme configuration issues can be essentially this. This dissertation will start from combinatorial mathematics point of view, combined application of graph theory, probability method, extreme combination of tools, some of the problems in the information science and promote certain thinking. In the first chapter, we will briefly introduce the background of the information science problems involved in this thesis, and promote the work of an overview of this issue do. In the second chapter, the object of our study for replacement group on the code and Snake code, their technology in power line block cipher in flash memory Sort of modulation has been widely used. We will aim to study the number of code words into graph theory problems, by constructing appropriate coloring scheme given independence number graph, and then improved the Hamming distance and Kendall's tau distance under permutation codes lower bound of.Kendall's tau is obviously different from the distance of the snake in the code of odd order and even order permutation group on permutation groups in S2n+1. We strictly proved the feasibility of'Horovitz-Etzion structure, and fine tune has better code on the basis of serpentine in S2n+2. We use the S2n+1 code before snake based replication and splicing, are non trivial the Snake code structure, to achieve the optimal in the asymptotic sense. In the third chapter, the object of our study is to protect the copyright of digital products in the background of collusion - safety codes and related hash function family. We will Objective to study the number of code words into the hypergraph problem, relevant conclusions and using independent number hypergraph, improved hash function and completely specified parameter conditions, frameproof codes, can be separated from the lower bound of the codes. The analytic method of the hypergraph model is for the first time. In the fourth chapter, we study the problem of a a reversible two yuan how the matrix has the largest proportion of 2 * 2 matrix inverse. The research background of this purely combinatorial problem can be traced back to the Turing Award winner Ron Rivest in order to further strengthen the security of the proposed block cipher is a preprocessing step for AONT transform. We established by integer programming problems. Analysis with probability method, completely determine the optimal solution of this problem, and to construct circular matrix constructing method is given based on the approximate optimal. In the fifth chapter, we study the problem for many Hilbert Unextendible product basis the minimum size of the problem space. This is one of the basic problems in quantum information science, is widely used in many fields of quantum information. We synthesize the graph orthogonal representation, connectivity of circulant graphs, 1- factor decomposition to graph theory, decision the exact value of a series of parameters under the minimum size of the size of UPB. In the sixth chapter of the research in other problems are briefly reported.

【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157

【相似文献】