Efficient algorithms for sequencing, counting, manipulating and visualizating discrete structures

用于对离散结构进行排序、计数、操作和可视化的高效算法

• 批准号: 3379-2009
• 负责人: Ruskey, Frank
• 金额: $ 2.19万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=503432
• 关键词: Efficient; algorithms; sequencing; counting; manipulating

The purpose of this research is to investigate essential algorithmic and mathematical properties of certain fundamental discrete structures, including Venn/Euler diagrams, Gray codes, nested recurrence relations, and polynomials over finite fields. Of these structures, Venn/Euler diagrams will be most familiar to the general public. Formally, a Venn diagram consists of n simple closed curves drawn in the plane with the property that each of the 2^n intersections of the interiors or exteriors of the curves is non-empty and connected. If regions are allowed to be empty, then it is an Euler diagram. There is a demand for software that will render "Venn" diagrams of populations in such a way that the area of each region is in proportion to the size of the underlying population. Basic questions about when this is possible, and if possible, how to best draw the diagram from the users point of view, are still unresolved, although some progress has been made. One goal of this research is to resolve these questions.

本研究的目的是研究某些基本离散结构的基本算法和数学性质，包括维恩/欧拉图、格雷码、嵌套递归关系和有限域上的多项式。 在这些结构中，维恩/欧拉图将是公众最熟悉的。 形式上，维恩图由在平面上绘制的n条简单闭合曲线组成，其性质是曲线的内部或外部的2^n个交点中的每一个都是非空的和连通的。 如果允许区域为空，则它是欧拉图。 需要一种软件来绘制人口的“维恩”图，使每个区域的面积与底层人口的规模成比例。 虽然已经取得了一些进展，但关于何时可以这样做，以及如果可能的话，如何从用户的角度最好地绘制图表的基本问题仍然没有得到解决。 本研究的目的之一就是解决这些问题。