随机性及其应用研究  

On Randomness and Its Application

作　　者：杨帆[1] 郑建武[2] 刘明生[2] 

机构地区：[1]石家庄市公路桥梁投资开发管理中心,050011 [2]石家庄铁道学院信息工程系,050043

出　　处：《计算机系统应用》2007年第2期18-20,共3页Computer Systems & Applications

摘　　要：本文首先讨论“随机性”与“高效计算”之间的关系,并强调引入“随机性”于问题求解的意义与重要性。随后给出产生“随机性”的现实途径及为计算引入“随机性”的两种不同方式,即“在线”方式与“离线”方式;通过对概率图灵机求解判定问题的讨论,来说明两种引入“随机性”方式之间的等价关系。最后,本文指出现实的随机算法设计与实现并没有为计算引入真正的“随机性”。

关 键 词：随机性 随机算法 概率图灵机 高效计算 在线 离线 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]