Singularity analysis and the large scale behaviour of combinatorial structures

奇点分析和组合结构的大规模行为

• 批准号: RGPIN-2017-04157
• 负责人: Mishna, Marni
• 金额: $ 1.89万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634853
• 关键词: Singularity; analysis; large; scale; behaviour

Many problems from the natural sciences and computing theory are modelled using discrete combinatorial objects, such as trees, sequences, and random walks. Interesting applications require an understanding of the properties of these objects when they are extremely large. The models aid in predicting the run-time of algorithms, properties of genomes, and phase transitions in chemical processes. Naive strategies are quickly overwhelmed by the sheer size of the objects. Formal power series (known as generating functions in this context) have proved to be an efficient and effective way to study enumerative questions, offer insights into distributions of important parameters, and other large scale behavioural questions notably when tools like exhaustive generation are no longer feasible.

自然科学和计算理论中的许多问题都是使用离散组合对象建模的，例如树、序列和随机漫步。有趣的应用程序需要在这些对象非常大时了解它们的属性。这些模型有助于预测算法的运行时间、基因组的性质和化学过程中的相变。单纯的策略很快就会被对象的庞大规模所淹没。形式幂级数（在这种情况下称为生成函数）已被证明是研究枚举问题的有效方法，提供了对重要参数分布的见解，以及其他大规模行为问题，特别是当穷举生成等工具不再可行时。