Practical combinatorial algorithms

实用组合算法

• 批准号: RGPIN-2018-04211
• 负责人: Sawada, Joe
• 金额: $ 2.48万
• 依托单位: University of Guelph
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=685334
• 关键词: Practical; combinatorial; algorithms

Combinatorial objects such as strings, permutations, trees and graphs are often used as the fundamental building blocks to model real world problems. For instance, DNA sequences can be though of as strings over a four character alphabet C,G,A,T. Routing your mobile calls in wireless networks can be modelled by paths in simple undirected graphs. Other applications that apply algorithms on combinatorial objects include: musical composition, bell-ringing, theatrics, and quantum error correcting codes. Yes, combinatorial algorithms are used in all areas of the arts and sciences! ******By modelling these real world problems with fundamental combinatorial objects we gain access to a wealth of mathematical knowledge that can be applied to solve the problem. A primary objective of this research program is to expand the simplicity and efficiency of algorithms for these core combinatorial objects AND to make them more accessible to other researchers. The very nature of these problems helps to achieve another objective which is to engage students at the undergraduate level and get them excited about computational problems related to fundamental mathematical objects. Mentoring and training the next generation is at the core of this research program.

组合对象，如字符串，排列，树和图通常被用作基本的积木模型真实的世界的问题。 例如，DNA序列可以被认为是四个字符字母表C、G、A、T上的字符串。 在无线网络中路由移动的呼叫可以用简单无向图中的路径来建模。 在组合对象上应用算法的其他应用包括：音乐作曲、敲钟、戏剧和量子纠错码。 是的，组合算法被用于艺术和科学的所有领域！** 通过用基本组合对象对这些真实的世界问题进行建模，我们可以获得丰富的数学知识，这些知识可以应用于解决问题。 该研究计划的主要目标是扩展这些核心组合对象的算法的简单性和效率，并使它们更容易被其他研究人员使用。 这些问题的本质有助于实现另一个目标，即吸引本科生，让他们对与基本数学对象相关的计算问题感到兴奋。 指导和培训下一代是这项研究计划的核心。