Research in Combinatorial Algorithms

组合算法研究

• 批准号: RGPIN-2014-04883
• 负责人: Ruskey, Frank
• 金额: $ 2.84万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=566806
• 关键词: 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 Diagrams Most 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是Hofstadter递归：Q(N)=Q(n-Q(n-1))+Q(n-Q(n-2))，在普利策奖获得者著作《戈德尔、埃舍尔、巴赫：永恒的金辫子》中广为流传。这种循环的关键句法特征是它只使用加法、减法和构图-而且构图的嵌套深度至少为两个。我们打算研究的递归都具有这些关键特征。我们将根据它们是否可判定对它们进行分类，并尽可能地为它们提供组合双射。维恩图和欧拉图大多数人都熟悉小的“维恩图”，以及它们在表达集合关系和解释三段论时的用途。我们的研究集中在寻找平面上和球面上的对称Venn图，以及具有少量曲线的图的穷举列表。线轴花边：线轴花边是一种古老的艺术形式，至少可以追溯到16世纪，用于制作精美的花边面料图案。令人惊讶的是，鉴于这些模式的规律性且往往是对称的，似乎从来没有人试图准确地对可能的模式进行分类和分类，尽管已经进行了一些特别的观察性清单和分类。我们的目标是为线轴花边图案提供坚实的数学和计算基础。如果没有四个长方形相交，则称一个带有矩形的直角区域的平铺就是鞑靼米。这样的限制在日式房间的地板上布置鞑靼米垫已经有很长的历史了。在我从事这方面的工作之前，在拼图书籍和建筑期刊中只有几次提到它们。这有点令人惊讶，因为鞑靼米约束可能是放置在瓷砖上的最自然的局部约束。我们将继续研究这些平铺的性质及其推广。