软件学报

作者：凤维明，尹一通

单位：凤维明，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002311,尹一通，计算机软件新技术国家重点实验室(南京大学), 江苏 南京 21002302

关键词：采样;分布式计算;计算复杂性;吉布斯分布;马尔可夫链

基金：国家重点研发计划重点专项(2018YFB1003202)

采样是一类基本的计算问题.从一个解空间中依特定概率分布进行随机采样,这一问题在近似计数、概率推断、统计学习等方面都有着诸多重要的应用.在大数据时代,采样问题的分布式算法与分布式计算复杂性受到越来越多的关注.近年来,有一系列的工作对分布式采样理论展开系统性的研究.综述了分布式采样的重要结论,主要包括有严格理论保障的分布式采样算法、采样问题在分布式模型上的计算复杂性以及采样与推断等问题在分布式计算模型中的相互联系.

来源：2022年第10期

《软件学报》期刊编辑部

查看软件学报杂志2022年第10期