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模式，并对大量数据上排序算法的平均行为进行分类。这项研究采用了现代和经典的理论数学技术来创建这种大规模分析的工具：目标是开发可以在软件中实现并易于他人应用的严格方法。计算渐近行为的关键思想是通过生成函数对描述某类对象的数列进行编码，该数列是一个无限和，其项描述该数列。已知的理论是推导出由生成函数所满足的方程，生成函数列举具有各种性质的对象，然后作为序列的隐式编码。计算工具可以使这个过程自动化。对于单变量函数的生成，现在已经建立的分析组合学领域展示了如何使用复分析的工具来确定渐近行为。对于多元生成函数——例如，在计算具有多个参数的对象的极限定理时——我们知道的要少得多。本研究发展了快速发展的多变量解析组合学领域，它借鉴并扩展了不同数学领域的方法，如微分几何、拓扑学和计算机代数。我们利用深厚的数学技术来开发易于使用的软件，用于分析离散结构，这些软件可以被不同领域的其他研究人员使用。此外，通过扩展以前的方法，本工作还推进了基础数学理论。理论工作以有影响力的前沿应用为指导，包括量子计算、生物信息学和排队论。