Research in Combinatorial Algorithms

组合算法研究

• 批准号: RGPIN-2014-04883
• 负责人: Ruskey, Frank
• 金额: $ 2.84万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708030
• 关键词: 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循环： 搜索空间通常是高度结构化和巨大的;我们打算继续开发高效的搜索算法，在这些空间中进行穷举或其他搜索。 主要感兴趣的是组合格雷码，它是穷举列表，其中连续的组合对象仅相差一个常量。 这种格雷码是所有生成算法中最有效的算法的必要前提，在这些算法中，在生成的连续对象之间只进行恒定量的工作。 格雷码和德布鲁因循环有许多应用，包括计算生物学、旋转轴上的位置检测、密码锁破解等。 嵌套递归关系： 递归关系是计算机科学和数学的基本工具。 近年来，我们已经开始尝试更好地理解“嵌套递归关系”（NRR），这在过去很少受到关注相比，传统的非嵌套递归关系。 典型的NRR是霍夫施塔特的递归：Q（n）= Q（n-Q（n-1））+Q（n-Q（n-2）），在普利策奖获奖书《哥德尔，巴赫：永恒的金辫子》中普及。 这种递归的关键句法特征是它只使用加法、减法和复合-并且复合的嵌套深度至少为2。 我们打算研究的递归都具有这些关键特征。 我们将根据它们是否是可判定的进行分类，并尽可能为它们提供组合双射。 维恩图和欧拉图 大多数人都熟悉小的“维恩”图，以及它们在表达集合关系和解释三段论中的用途。 我们的研究集中在寻找对称的维恩图，无论是在平面上，也在球体上，并与少量的曲线图的详尽清单。 线轴花边： 线轴花边是一种古老的艺术形式，至少可以追溯到16世纪，用于制作精美的花边织物图案。 令人惊讶的是，考虑到这些模式的规则性和对称性，似乎从来没有人试图精确地编目和理解可能的模式，尽管已经做了一些特别的观察列表和分类。 我们的目标是提供一个坚实的数学和计算基础的线轴花边模式。 榻榻米瓷砖： 如果没有四个矩形相交，则将具有矩形的正交区域的平铺称为榻榻米。 这种限制在日本房间地板上的榻榻米垫的安排中有着悠久的历史。 在我从事这一领域的工作之前，只有几本解谜书籍和建筑期刊提到过它们。 这有点令人惊讶，因为榻榻米约束可能是放置在瓷砖上的最自然的局部约束。 我们将继续研究这些镶嵌的性质及其推广。