Phase Transition in a Random Fragmentation Problem with Applications to Computer Science
Phase Transition in a Random Fragmentation Problem with Applications to Computer Science
复制标题
随机碎片问题中的相变及其在计算机科学中的应用
DOI：
10.1088/0305-4470/35/32/101
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
S. Majumdar
中科院分区：
文献类型：
--
作者：
D. Dean;S. Majumdar
我们研究了一个碎片化问题，其中一个大小为x的初始对象被分成m个随机碎片，x>x 0，其中x 0是一个原子截止。当所有碎片的尺寸都小于x0时，分裂过程停止。然而，当分支数m通过临界值m = mc时，分裂事件总数的波动（用方差表征）一般会经历非平凡的相变。对于m m c，它们是非常大的和非高斯的。我们应用这个一般结果来分析计算机科学中的两种不同的搜索算法。
We study a fragmentation problem where an initial object of sizex is broken into m random pieces provided x>x 0 where x0 is an atomic cut-off. Subsequently, the fragmentation process continues for each of those daughter pieces whose sizes are bigger than x0 .T heprocess stops when all the fragments have sizes smaller than x0 .W es ho wt ha tt he fluctuation of the total number of splitting events, characterized by the variance, generically undergoes a nontrivial phase transition as one tunes the branching numberm through a critical value m = mc. For m m c they are anomalously large and non-Gaussian. We apply this general result to analyse two different search algorithms in computer science.