Gray Codes, Efficient Generation, and Structure in Combinatorial Families

组合族中的格雷码、高效生成和结构

• 批准号: 9302505
• 负责人: Carla Savage
• 金额: $ 10.8万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-07-01 至 1997-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9302505&HistoricalAwards=false
• 关键词: Gray; Codes; Efficient; Generation; Structure

This award supports the research of Professor Savage to work in combinatorics. One of the fundamental problems in the area of combinatorial algorithms is that of efficiently generating items in a particular class in such a way that each item is generated exactly once. Asymptotic improvement in the efficiency of combinatorial generation requires not only good data structures and algorithm design techniques, but more often, some new insight into the structure of the combinatorial class involved. These structure questions are in the realm of well-known open problems in discrete mathematics, graph theory, group theory, and combinatorics. It is these type of problems that Professor Savage will address. The research is in the general area of combinatorics. Combinatorics attempts to find efficient methods to study how discrete collections can be organized. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, as in telephone systems, and the design of algorithms in computer science all deal with discrete objects, and this makes use of combinatorial research.

该奖项支持萨维奇教授的研究工作， 在组合学中。 这一领域的一个基本问题是， 组合算法是一种有效地生成项目的算法 在一个特定的类中， 就一次 效率的渐近改进 组合生成不仅需要良好的数据结构， 和算法设计技术，但更多的时候，一些新的见解， 所涉及的组合类的结构。 这些 结构问题属于著名的开放性问题 在离散数学，图论，群论， 组合学 正是这类问题， 萨维奇将发表演讲。 该研究是在组合学的一般领域。 组合数学试图找到有效的方法来研究如何 可以组织离散的集合。 离散的行为 系统对于现代通信是极其重要的。 为 例如，大型网络的设计，如电话系统， 计算机科学中的算法设计都涉及到 离散的物体，这就利用了组合研究。