Effective tools for the analysis of discrete structures

分析离散结构的有效工具

• 批准号: RGPIN-2021-02382
• 负责人: Melczer, Stephen
• 金额: $ 3.35万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=741946
• 关键词: Effective; tools; analysis; discrete; structures

The need to analyze patterns and predict the cost of computing with complex systems has never been greater than it is today. In computer science, digital information is modeled using discrete structures, such as graphs (which model connections in networks like the internet) and formal words (which model sequences of letters like DNA). A fundamental problem in computer science, and the related field of combinatorics, is thus the derivation of large-scale behaviour of structures from their formal definitions. This is often accomplished by providing an "asymptotic" estimate for the number of objects with size n (for instance, the number of graphs with n nodes) whose error goes to zero as n gets arbitrarily large. One can also examine the behaviour of parameters among objects of large size (for instance, counting the number of DNA-like sequences with a fixed number of letters by the number of times it contains some fixed pattern). Strikingly, for large classes of structures the behaviour of parameters is dictated by well-known limit theorems from probability. Such results can predict phase transitions in statistical mechanical models, separate DNA patterns which arise via natural selection from random noise, and classify the average behaviour of sorting algorithms on vast amounts of data. This research adapts theoretical mathematical techniques -- both modern and classical -- to create tools for this large-scale analysis: the goal is to develop rigorous methods that can be implemented in software and easily applied by others. The key idea to calculating asymptotic behaviour is to encode a sequence of numbers describing some family of objects by its generating function, an infinite sum whose terms describe the sequence. Well known theories exist to derive equations satisfied by the generating functions enumerating objects with various properties, which then serve as implicit encodings of the sequences. Computational tools can be used to automate much of this process. For generating functions in a single variable, the now well-established field of analytic combinatorics shows how to use tools from complex analysis to determine asymptotic behaviour. For multivariate generating functions -- needed, for instance, when calculating limit theorems for objects with multiple parameters -- much less is known. This research develops the rapidly growing field of analytic combinatorics in several variables, which draws on and extends methods from areas of mathematics as diverse as differential geometry, topology, and computer algebra. We exploit deep mathematical techniques to develop easy-to-use software for the analysis of discrete structures that can be put to use by other researchers across diverse fields. Furthermore, by extending previous methods this work also pushes forward the underlying mathematical theory. The theoretical work is guided by impactful and cutting-edge applications, which include quantum computing, bioinformatics, and queuing theory.

分析模式和预测复杂系统计算成本的需求从未像今天这样强烈。在计算机科学中，数字信息是使用离散结构建模的，例如图形（对互联网等网络中的连接进行建模）和正式单词（对DNA等字母序列进行建模）。因此，计算机科学和相关组合学领域的一个基本问题是从结构的形式定义中推导出结构的大尺度行为。这通常是通过提供大小为n的对象的数量（例如，具有n个节点的图的数量）的“渐近”估计来实现的，当n变得任意大时，其误差为零。人们还可以检查大尺寸对象中参数的行为（例如，通过它包含某种固定模式的次数来计算具有固定字母数的DNA样序列的数量）。引人注目的是，对于大类的结构，参数的行为是由著名的概率极限定理决定的。这些结果可以预测统计力学模型中的相变，将自然选择产生的DNA模式与随机噪声分开，并对大量数据的排序算法的平均行为进行分类。这项研究采用了现代和经典的理论数学技术，为这种大规模的分析创建工具：目标是开发可以在软件中实现并易于他人应用的严格方法。计算渐近行为的关键思想是通过其生成函数对描述某个对象族的数字序列进行编码，生成函数是一个无穷和，其项描述了该序列。众所周知的理论存在，以获得满足的生成函数枚举具有各种属性的对象，然后作为序列的隐式编码的方程。计算工具可以用来自动化这个过程的大部分。对于单变量的生成函数，现在已经很成熟的分析组合学领域展示了如何使用复分析的工具来确定渐近行为。对于多元生成函数--例如，当计算具有多个参数的对象的极限定理时--所知要少得多。这项研究发展了快速增长的多变量分析组合学领域，该领域借鉴并扩展了微分几何，拓扑学和计算机代数等数学领域的方法。我们利用深入的数学技术来开发易于使用的软件，用于分析离散结构，这些结构可以被不同领域的其他研究人员使用。此外，通过扩展以前的方法，这项工作也推动了基本的数学理论。理论工作由有影响力的前沿应用程序指导，包括量子计算，生物信息学和排队论。