吉布斯分布是一类重要的概率模型,它在概率论、统计物理和计算机科学等领域有着非常广泛的应用。采样是关于吉布斯分布的核心计算任务,它要求算法按照给定的分布生成一个随机样本。吉布斯分布的采样问题是理论计算机科学的重要课题之一,人们致力于探索有严格理论保障的算法以及采样问题的计算复杂性。经过数十年的深入研究,拒绝采样、马尔可夫链蒙特卡洛方法等采样技术逐渐被发展起来,很多重要的采样问题被成功解决。虽然先前的研究回答了关于采样的若干基本问题,但是目前已知的采样算法较少,分析工具也有待加强,一些重要的问题没有得到很好的解决。例如对于均匀采样逻辑公式满足解的问题,因为很多经典算法无法适用,所以长期缺乏高效算法;对于均匀采样合法图染色问题,因为缺乏有力的分析工具,所以目前已知的算法收敛条件和猜想依然有很大差距。这些公开问题代表了当前技术上的本质障碍,解决这些问题需要在原理层面上做出创新。另一方面,在大数据时代,很多新的采样问题涌现出来。一些经典的采样技术只能给出高度串行、适用于静态数据的采样算法。而在如今的应用中,并行的、动态的采样算法越来越受到关注。传统的采样理论难以胜任新的问题,在大数据背景下,人们需要建立新的采样理论体系。本文研究吉布斯分布的采样算法。对于大数据背景下的新问题,本文从分布式采样和动态采样这两个具体问题入手,给出有理论保障的算法并研究新模型下采样问题的复杂性。对于一些经典的公开问题,本文提出新的算法设计和分析技术来突破先前的障碍,从而得到更快的采样算法。第一个课题是分布式采样问题。我们在分布式计算的LOCAL模型上研究吉布斯分布的采样。在这个模型中,每个节点通过收集局部信息输出一个随机变量,所有节点输出变量的联合分布为目标吉布斯分布。我们给出全新的分布式采样算法,证明分布式采样问题的下界,并且在分布式计算模型上复现图灵机模型上的若干经典结论,例如采样问题和计数问题的计算等价性,采样问题的计算相变现象。这些结论揭示了分布式采样和传统串行采样之间的联系,对理解分布式采样的原理有重要意义。第二个课题是动态采样问题。假设我们有一个吉布斯分布以及一个服从此分布的随机样本。给定一个更新操作,它把当前吉布斯分布更新成一个新的吉布斯分布。算法需要以相对较小的增量代价,把原随机样本更新成一个服从新分布的随机样本。我们给出了两种设计动态采样算法的技术。第一个是条件吉布斯技术,它不仅能解决动态采样问题,也能用于设计精确采样算法,还和吉布斯分布的空间混合性质有密切的联系。第二个技术是动态马尔可夫链技术,它能把一些原本静态的马尔可夫链蒙特卡洛方法动态化,从而一些静态采样的成果可以直接用应用到动态采样上来。最后一个课题是具体问题的快速采样算法。一些吉布斯分布在我们的研究之前只有运行时间为nf（θ）的算法,其中n是吉布斯分布变量数;θ是吉布斯分布的某个参数,例如变量的最大度数;f（θ）是θ的一个多项式函数或指数函数。这类采样算法只对θ=O（1）的问题有多项式运行时间,且多项式的指数非常巨大。我们的工作将解决问题的复杂度优化到poly（nθ）的时间,有些问题的时间复杂度可以和n呈接近线性的关系。在技术上,我们对具体问题提出了新的算法设计技术和算法分析技术,从原理上突破了先前的技术障碍。