Probabilistic Considerations in the Analysis of Algorithms

CCR-9814411 FriezeProbability在算法分析中至少以两种重要的方式出现。 首先，在随机算法中，随机事件的结果用于确定算法的进度。 随机化现在是计算机科学家的标准工具。 第二个考虑的领域是当问题实例来自某种概率分布时，人们希望了解特定算法的平均性能，这通常比最坏的情况要好得多。 在随机算法领域考虑的主题包括矩阵分解，随机游动，快速混合马尔可夫链和最小独立性。 概率分析中考虑的主题包括近似算法、数据包路由和计算生物学。

CCR-9814411FriezeProbabilistic 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.This project attacks a number of problems in these two areas. Topic considered in the area of randomized algorithms included decomposition of matrices, random walks, rapidly mixing Markov chains and min-wise independence. Topics considered in probabilistic analysis include approximation algorithms, packet routing and computational biology.