Probabilistic Considerations in the Analysis of Algorithms

算法分析中的概率考虑

• 批准号: 0502793
• 负责人: ALAN FRIEZE
• 金额: $ 20万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0502793&HistoricalAwards=false
• 关键词: Probabilistic; Considerations; Analysis; Algorithms

SUMMARYIntellectual MeritProbabilistic considerations arise in the analysis of algorithms in at least two important ways. First of all, in a randomized algorithm the outcomes of random events are used to determine the progress of the algorithm. Randomization is now a standard tool of the computer scientist. A second area of consideration is when the problem instances come from some probability distribution and one wants to understand the average performance of a particular algorithm, which is often far better than its worst case. Both aspects are extremely important and this proposal describes a number of problems in these two areas.Broader ImpactResults from this work will be disseminated at scientic workshops and at seminars at other institutions, both nationally and internationally. Results obtained will be published in journals and conference proceedings. The P.I. takes care to ensure that all of his recent papers are available on-line on his home-page. Work on Monte-Carlo Markov Chain analysis has an impact on Probability Theory and Sta- tistical Physics. In addition the proposal will have an impact on education, mainly at the graduate level. The PI tries to embed the knowledge gained from his research into courses and tries to involve his graduate students (currently four of them) as much as possible in any research that he does. Sometimes the work involved is of such a nature that it can lead to meaningful summer projects for bright undergraduates. In such cases the P.I. has sought and will seek additional support from the NSF and Carnegie Mellon University. In the recent past the P.I. has supervised such projects on Small-World networks, on Resource Discovery in Distributed Networks, on aDirected Model of Web-Graphs and on a Graph Version of Nim. In addition, the P.I. is actively involved in the NSF funded Aladdin project in the Computer Science Department at CMU and this has a signicant out-reach component. Together with Danny Sleator, the P.I. runs a popular puzzle page:http://www.cs.cmu.edu/puzzle/

摘要智力优点在算法分析中至少以两种重要方式出现概率考虑。首先，在随机算法中，随机事件的结果用于确定算法的进度。随机化现在是计算机科学家的标准工具。第二个需要考虑的领域是，当问题实例来自某种概率分布并且人们想要了解特定算法的平均性能时，该算法通常比最坏情况要好得多。这两个方面都极其重要，该提案描述了这两个领域的许多问题。更广泛的影响这项工作的结果将在国内和国际其他机构的科学研讨会和研讨会上传播。获得的结果将发表在期刊和会议记录中。 P.I.小心确保他最近的所有论文都可以在他的主页上在线获取。蒙特卡洛马尔可夫链分析工作对概率论和统计物理学产生了影响。此外，该提案还将对教育产生影响，主要是在研究生阶段。 PI 试图将从他的研究中获得的知识嵌入到课程中，并尝试让他的研究生（目前有四名）尽可能多地参与他所做的任何研究。有时，所涉及的工作性质如此，可以为聪明的本科生带来有意义的暑期项目。在这种情况下，P.I.已经并将继续寻求美国国家科学基金会和卡内基梅隆大学的额外支持。最近，P.I.监督了小世界网络、分布式网络中的资源发现、网络图定向模型和 Nim 的图版本等项目。此外，P.I.积极参与 CMU 计算机科学系 NSF 资助的阿拉丁项目，该项目具有重要的外展部分。与丹尼·斯利特 (Danny Sleator) 一起，P.I.运行一个流行的拼图页面：http://www.cs.cmu.edu/puzzle/