SGER: Multidisciplinary Aspects of Computation Theory

SGER：计算理论的多学科方面

• 批准号: 0344187
• 负责人: Jack Lutz
• 金额: $ 7.49万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-09-01 至 2006-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0344187&HistoricalAwards=false
• 关键词: SGER; Multidisciplinary; Aspects; Computation; Theory

This project will explore a multidisciplinary collection of related problems inwhich the theory of computing plays a fundamental role. The problems involvea variety of topics in computational complexity, algorithmic information theory,stochastic processes, statistical inference, arti.cial intelligence, fractal geometry,dynamical systems, game theory, and other areas, but they have several crucialcommonalities: The problems are ones that involve computability and/or complexity theoryin fundamental conceptual respects. The problems are stochastic in the sense that they or their solutions involve some sort of randomness. The problems are dynamic in the sense that they or their solutions involve analyticor topological methods in addition to the discrete and algebraic methods that more typically arise in the theory of computing. The problems are strategic in the sense that they or their solutions involve the design and analysis of algorithmic strategies for betting, prediction, learning, game-playing, or some other task that is carried out in an environmentcontaining adversity.

这个项目将探讨一个多学科的收集相关的问题，其中计算理论起着根本性的作用。这些问题涉及计算复杂性、算法信息论、随机过程、统计推断、阿尔蒂智能、分形几何、动力系统、博弈论和其他领域的各种主题，但它们有几个关键的共同点：这些问题涉及基本概念方面的可计算性和/或复杂性理论。这些问题是随机的，因为它们或它们的解包含某种随机性。这些问题是动态的，因为它们或它们的解决方案除了在计算理论中更典型地出现的离散和代数方法之外，还涉及解析或拓扑方法。这些问题是战略性的，因为它们或它们的解决方案涉及赌博、预测、学习、玩游戏或其他在逆境环境中执行的任务的算法策略的设计和分析。