Parallel Algorithms and Complexity Theory

并行算法和复杂性理论

• 批准号: 8703196
• 负责人: Walter Ruzzo
• 金额: $ 26.09万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1987
• 资助国家: 美国
• 起止时间: 1987-08-01 至 1991-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8703196&HistoricalAwards=false
• 关键词: Parallel; Algorithms; Complexity; Theory

The goals of the proposed research are to understand the nature of parallel computation, to develop theoretical foundations for the design and analysis of algorithms for parallel computer systems, and to apply these principles to discover appropriate parallel computer architectures and algorithms. Some of the specific areas in which research has been and is being conducted are: (1) parallel algorithms for a variety of natural problems, (2) models of parallel computers and their interrelationships, (3) lower bounds or other evidence that specific problems cannot be efficiently solved by parallel machines, and (4) implementation and measurement of parallel algorithms on currently available processors. This is an excellent proposal by a very fine researcher. The proposed study of parallel computing is fundamental for progress in computer science at this time.

拟议研究的目标是了解 平行 计算，发展理论基础的设计和 分析 并行计算机系统的算法，并应用这些原则 到 发现适当的并行计算机架构和算法。 一些 已进行及正在进行的研究的具体范畴 为： (1)各种自然问题的并行算法，（2）模型 的 并行计算机及其相互关系，（3）下限或 其他 无法有效解决具体问题的证据 平行 机器，以及（4）并行算法的实现和测量 对 目前可用的处理器。 这是一个非常好的研究人员提出的一个很好的建议。 拟议 研究 并行计算是计算机科学发展的基础 在这个 时间