Research in Combinatorial Algorithms

组合算法研究

• 批准号: RGPIN-2014-04883
• 负责人: Ruskey, Frank
• 金额: $ 2.84万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634879
• 关键词: Research; Combinatorial; Algorithms

Combinatorial algorithms are a core foundational area of computer science. The area is focused on algorithms that operate on finite structures, particularly those that have precise mathematical descriptions. The objective of this research is to identify some problems and structures that are fundamental, find clever ways to solve the problems algorithmically, write code to implement them efficiently, and analyze them mathematically. Also, my grad students and I are not afraid to pursue in considerable detail some side-angle problem that arises in these steps, if such problem seems somehow intellectually interesting and challenging. This proposal focuses on five areas: Gray codes and de Bruijn cycles, nested recurrence relations, Venn diagrams, tatami tilings, and bobbin lace.Gray codes and de Bruijn Cycles:Search spaces are often highly-structured and huge; we intend to continue our development of efficient algorithms for searching, exhaustively and otherwise, in these spaces. Of primary interest are combinatorial Gray codes, which are exhaustive lists in which successive combinatorial objects differ by only a constant amount. Such Gray codes are a necessary precursor to the most efficient of all generation algorithms, those in which only a constant amount of work is done between successive objects generated. Gray codes and de Bruijn cycles have many applications, including computational biology, position detection on rotating axles, combination lock breaking, etc.Nested recurrence relations:Recurrence relations are a fundamental tool of computer science and mathematics. In recent years, we have begun trying to better understand "nested recurrence relations" (NRRs), which have received scant attention in the past as compared with the traditional non-nested recurrence relations. The prototypical NRR is Hofstadter's recurrence: Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2)), popularized in the Pulitzer Prize winning book "Godel, Escher, Bach: An Eternal Golden Braid". The key syntactic features of this recurrence are that it only uses addition, subtraction, and composition --- and the depth of nesting of the composition is at least two. The recurrences we intend to study all have these key features. We will classify them according to whether they are decidable or not, and provide combinatorial bijections for them whenever possible.Venn and Euler DiagramsMost people are familiar with small "Venn" diagrams, and their use in conveying set relationships and explaining syllogisms. Our research is focused on finding symmetric Venn diagrams, both in the plane and also on the sphere, and on exhaustive listing of diagrams with a small number of curves. Bobbin Lace:Bobbin lace is an old art form, dating back to at least the 16th century, for making fine lace fabric patterns. Given the regular and often symmetric qualities of these patterns, amazingly, there seems to never have been an attempt to precisely catalog and understand the possible patterns, although some ad hoc observational listing and classification has been done. Our aim is to provide a firm mathematical and computational base for bobbin lace patterns.Tatami Tilings:A tiling of an orthogonal region with rectangles is said to be tatami if no four rectangles meet. Such a restriction has a long history in the arrangement of tatami mats on the floors of Japanese rooms. Previous to my work in this area, there were only a couple of mentions of them in puzzle books and in architectural journals. This is somewhat surprising, since the tatami constraint is perhaps the most natural local constraint to place on a tiling. We will continue our investigations into the properties of these tilings and their generalizations.

组合算法是计算机科学的核心基础领域。该领域专注于在有限结构上运行的算法，特别是那些具有精确数学描述的算法。这项研究的目的是确定一些基本问题和结构，找到巧妙的算法解决问题的方法，编写代码以有效地实现它们，并进行数学分析。此外，我和我的研究生并不害怕对这些步骤中出现的一些侧面问题进行相当详细的研究，如果这些问题在智力上看起来很有趣并且具有挑战性的话。该提案重点关注五个领域：格雷码和 de Bruijn 循环、嵌套递归关系、维恩图、榻榻米瓷砖和梭芯花边。格雷码和 de Bruijn 循环：搜索空间通常是高度结构化且巨大的；我们打算继续开发有效的算法，在这些空间中进行彻底的搜索和其他搜索。主要感兴趣的是组合格雷码，它是详尽的列表，其中连续的组合对象仅相差一个常数。这种格雷码是所有生成算法中最有效的必要先驱，在这些生成算法中，在生成的连续对象之间仅完成恒定量的工作。格雷码和 de Bruijn 循环有很多应用，包括计算生物学、旋转轴上的位置检测、密码锁破解等。 嵌套递归关系：递归关系是计算机科学和数学的基本工具。近年来，我们开始尝试更好地理解“嵌套递归关系”（NRR），与传统的非嵌套递归关系相比，它在过去很少受到关注。典型的 NRR 是霍夫施塔特的递推式：Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2))，在普利策奖获奖著作《哥德尔、埃舍尔、巴赫：永恒的金辫子》中广为人知。这种递归的关键语法特征是它只使用加法、减法和组合——并且组合的嵌套深度至少为二。我们打算研究的复发都具有这些关键特征。我们将根据它们是否可判定对它们进行分类，并尽可能为它们提供组合双射。 维恩图和欧拉图大多数人都熟悉小型“维恩”图，以及它们在表达集合关系和解释三段论中的用途。我们的研究重点是寻找平面和球面上的对称维恩图，以及包含少量曲线的图的详尽列表。梭芯花边：梭芯花边是一种古老的艺术形式，至少可以追溯到 16 世纪，用于制作精美的蕾丝织物图案。令人惊讶的是，考虑到这些模式的规则且通常是对称的特性，尽管已经完成了一些临时观察列表和分类，但似乎从未尝试过精确编目和理解可能的模式。我们的目标是为梭芯花边图案提供坚实的数学和计算基础。 榻榻米瓷砖：如果没有四个矩形相交，则矩形正交区域的平铺称为榻榻米。这种限制在日式房间地板上榻榻米的布置中由来已久。在我从事这一领域的工作之前，拼图书籍和建筑期刊中只提到过几次。这有点令人惊讶，因为榻榻米约束可能是对瓷砖施加的最自然的局部约束。我们将继续研究这些瓷砖的特性及其概括。