Effective tools for the analysis of discrete structures

分析离散结构的有效工具

• 批准号: RGPIN-2021-02382
• 负责人: Melczer, Stephen
• 金额: $ 3.35万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749571
• 关键词: 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 模式，并对大量数据的排序算法的平均行为进行分类。这项研究采用了现代和经典的理论数学技术来创建用于大规模分析的工具：目标是开发可以在软件中实现并易于被其他人应用的严格方法。计算渐近行为的关键思想是通过生成函数对描述某些对象族的数字序列进行编码，生成函数是一个无限和，其项描述了该序列。存在众所周知的理论来推导由枚举具有各种属性的对象的生成函数满足的方程，然后将其用作序列的隐式编码。计算工具可用于使这一过程的大部分自动化。为了在单个变量中生成函数，现在成熟的分析组合领域展示了如何使用复杂分析中的工具来确定渐近行为。对于多元生成函数——例如，在计算具有多个参数的对象的极限定理时所需要的——我们知之甚少。这项研究发展了快速发展的多个变量的解析组合领域，它借鉴并扩展了微分几何、拓扑和计算机代数等不同数学领域的方法。我们利用深入的数学技术来开发易于使用的软件，用于分析离散结构，可供不同领域的其他研究人员使用。此外，通过扩展以前的方法，这项工作还推动了基础数学理论的发展。理论工作以有影响力的前沿应用为指导，包括量子计算、生物信息学和排队论。