Probabilistic Considerations in the Analysis of Algorithms

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

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/