1700496543
1700496544
乌拉姆的想法（抽样可以在其他分析方法失败时取得成功）在解决洛斯阿拉莫斯出现的一些困难的核物理问题时也至关重要。核反应是一种分支过程，可能也会像纸牌那样疯狂地增加：一个粒子分裂为两个，每一个都可能会撞击其他的，再导致它们分裂，一直这样发展下去。准确地计算出这一过程中某些特定结果的可能性，在许多粒子的相互作用下，都已经难到几乎不可能的程度。但如果进行模拟，每一次的交互作用就像打开一张新的纸牌，提供了一种选择。
1700496545
1700496546
乌拉姆与约翰·冯·诺伊曼进一步发展了这个想法，并与另一位来自曼哈顿计划的物理学家尼古拉斯·梅特罗波利斯合作，在洛斯阿拉莫斯的计算机上实现了这个方法。梅特罗波利斯将这一方法（将详尽的概率计算用抽样模拟进行代替）命名为蒙特卡罗法，这种方法因摩纳哥的蒙特卡罗赌场而得名，因为该场所同样依赖于变幻莫测的机会与运气。洛斯阿拉莫斯的团队便能够用它来解决核物理中的关键问题。今天，蒙特卡罗方法已经成为科学计算的基石之一。
1700496547
1700496548
许多如计算亚原子粒子的相互作用或在纸牌上的获胜机会这样的问题，是它们内在具有的概率，所以通过像蒙特卡罗法这样随机的方法来解决这些问题很有道理。但关于随机性的作用也许最让人惊讶的是，它可以被用在机会看似发挥不了作用的情况下。即使你想要回答一个只有“是”或“否”，“真”或“假”的答案的问题（其中没有任何其他可能性）掷几个骰子仍然是解决方案的一部分。
1700496549
1700496550
[1]有趣的是，偶然间，其中的一些实验对π值的估计似乎产生了比预期更好的效果，这表明他们可能是故意缩短了最佳停止点，或者干脆伪造。例如，1901年，意大利数学家马里奥·拉扎里尼据说做了3408次实验，并最终估计π≈355/113=3.1415929（π到小数点后7位的实际值是3.1415927）。但如果针与纸上的线相交的机会只有一次，那估计会没那么精准（3.1398或3.1433），这让拉扎里尼的报告显得可疑。拉普拉斯可能已经发现，我们可以使用贝叶斯法则来确认，这个结果不太可能来自一个有效的实验。
1700496551
1700496552
1700496553
1700496554
1700496556
算法之美：指导工作与生活的算法 随机算法
1700496557
1700496558
第一个在计算机科学中展示随机算法广泛应用的人是迈克尔·拉宾，这一展示令人惊讶。他1931年出生于德国的布雷斯劳（“二战”后，该地变为波兰的弗罗茨瓦夫），拉宾的祖辈有很多都是犹太拉比。他的家人于1935年离开德国巴勒斯坦，他从那时起，开始从他父亲为他铺下的犹太教之路转到美丽的数学之路——他在希伯来大学本科生涯的早期就研究了阿兰·图灵的理论，后又移民到美国普林斯顿大学攻读博士学位。拉宾赢得相当于计算机科学界的诺贝尔奖的图灵计算机科学奖，因为其扩展了理论计算机科学，以适应在“不确定性”的情况下，一台机器不被要求去做出单一选择，而是可能有多个路径可以走。在1975年的休假中，拉宾来到麻省理工学院，寻找一个新的研究方向。
1700496559
1700496560
他发现其中存在一个最古老的问题：如何识别质数（素数）。利用算法寻找质数至少可以追溯到古希腊时期，当时的数学家使用一个简单的方法称为厄拉多塞筛算法。该算法的工作原理如下：要找到所有小于n的质数，首先要写下所有从1到n的序列中的数字。然后去掉所有是2的倍数的数字，除了2本身（就是去掉4、6、8、10、12等）。取下一个还没有划掉的最小的数（在本例中，就是3）并划掉所有这一数字的倍数（6、9、12、15）。继续这样下去，最后剩下的数就是质数。
1700496561
1700496562
几千年来，对质数的研究，如G.H.哈代所说，一直被认为是数学中“最明显无用的分支之一”。但在20世纪，它开始变得有用，它成为密码学和网络安全的关键。事实上，把质数相乘比把它们因数析出要容易得多。足够大的质数（例如一个千位数）的乘法可以在几分之一秒内完成，但析出因数就可能需要几百万年，这就产生了所谓的“单向函数”。在现代加密术中，例如，当只有发送方和接收方知道秘密质数相乘能得到巨大的合数时，便可以将这个数公开传播而不用担心了，因为对该产品的密码析出因数将耗费任何企图窃取者太长时间而不值得尝试。因此，几乎所有的安全通信网络，无论是商业、银行还是电子邮件，都是从寻找质数开始的。
1700496563
1700496564
对密码的这种应用突然使查找和检查质数的算法具有非常重要的作用。虽然厄拉多塞筛算法是可行的，但它的效率并不高。如果你想要检查一个特定的数是否是质数（或称测试其“素性”），筛算法需要试图除以所有质数直到其平方根。检查一个6位的数字是否为质数，需要将它除以168个所有少于1000的质数，这好像还不是太糟糕。但检查一个12位的数字是否为质数，就要将它除以78498个小于100万的质数，那么这就明显开始失控了。现代密码学中使用的质数有几百位长（还是忘了它吧）。
1700496565
1700496566
在麻省理工学院，拉宾遇到了加里·米勒，他是加州大学伯克利分校计算机科学系的毕业生。在米勒的博士论文中，他开发出了一种有趣的、有发展潜力的，也更快的算法，用于测试优先级，但有一个小问题：它并非永远有效。
1700496567
1700496568
米勒发现一组方程（用n和x两个数表示），如果n是质数，无论x代入什么值，它总能成立。如果该方程式不成立，即使只有一个x的值，n也不可能是质数。在这些情况下，x被称为对抗素性的“证人”。然而，问题是误报：即使n不是质数，这个方程仍然会在某些时候成立。这让米勒的想法无法确定。
1700496569
1700496570
拉宾意识到，这是一个超出通常确定的计算机科学世界中被认为有价值的领域。如果n实际上是非质数，那么多少个x的可能值会给出误报并认为它是一个质数？拉宾指出，答案不超过1/4。所以对于一个随机的x值，如果米勒的方程成立，只有1/4的概率n不是质数。关键是，每次我们采样一个新的随机x，并用米勒的方程检验这个n是质数的方法，但结果不是，就要再以4的倍数往下降。重复这个步骤10次，假阳性的概率是4-10——小于0.001‰。仍然没有足够的确定性？再检查5次，就会下降到0.000001‰。
1700496571
1700496572
沃恩·普拉特是另一位麻省理工学院的计算机科学家，他研究了拉宾的算法，并在冬天的一个深夜算出结果，而拉宾正在家里举办一个光明节聚会。拉宾记得是在午夜前后接到的电话：
1700496573
1700496574
“迈克尔，我是沃恩。我得出了这些实验的结果。快去拿铅笔和纸，把结果写下来。”他说，2400-593是质数。所有的素数的结果p中小于300的用k表示。K×338+821和k+823×338的两个结果是孪生素数。[1]这些构成了那时已知的最大孪生素数。我听后觉得头发都竖了起来。真是难以置信。真是难以置信。
1700496575
1700496576
米勒-拉宾素数测试，就现在所知的，给我们提供了一种用任意程度的确定性快速识别即使特别大的质数的方法。
1700496577
1700496578
这里，我们可能会问一个哲学问题——“是”的意思是什么。我们已经非常习惯于数学应该是一种确定的领域，如果我们听到一些数字“可能是质数”或“几乎肯定是质数”一定觉得非常奇怪。“肯定到底是有多肯定呢？”在实践中，加密互联网连接和数字交易的现代加密系统，被设置的误报率在1×1024以内。换句话说，这是一个有24个零的小数，比地球上一粒沙粒还小。这个标准是在将米勒-拉宾测试应用仅40次之后产生的。的确，你从来不会完全确定，但是你可以非常接近确定，或是非常快确定。
1700496579
1700496580
尽管你可能从来没有听说过米勒-拉宾测试，但你的笔记本电脑、平板电脑和手机都对其很熟悉。在其被发现后的几十年，它仍然在许多领域中被用作查找和检查素数的标准方法。当你在网上使用信用卡时，它也在幕后工作着，几乎任何时候安全通信都是在空中或通过电线发送的。
1700496581
1700496582
在米勒和拉宾的成果问世之后的几十年里，我们不知道是否会有一种有效的算法，允许以确定性的方式，用绝对的确定性对素性进行测试。2002年，印度理工学院的三位科学家的确发现了这样一个方法，但像米勒—拉宾这样的随机算法要快得多，因此今天仍在实践中使用。
1700496583
1700496584
对于其他一些问题，随机抽样仍然是唯一已知的有效解决途径。数学中有一个奇特的例子，就是所谓的“多项式身份测试”。“如果你有两个多项式表达式，如2x3+13x2+22x+8，以及（2x+1）×（x+2）×（x+4），找出这些表达式实际上是否为相同的函数（通过算出所有乘法，然后比较结果），这会非常耗时，尤其是随着变量数量的增加。
1700496585
1700496586
在这里，随机性提供了一种可以推进向前的方法：生成一些随机的x并将其代入。如果这两个表达式是不同的，那么如果它们对随机生成的输入给出相同的答案，这将是一个很大的巧合。如果它们对第二个随机输入又给出相同的答案，这将是更大的巧合。如果连续三次随机输入都相同又是更大的巧合。因为没有已知的确定性算法可有效地测试多项式身份，这种随机的方法（重复观测快速接近确定性）是我们可以使用的唯一实际的方法。
1700496587
1700496588
[1]孪生素数是连续奇数，并且都是质数，比如5和7。
1700496589
1700496590
1700496591
1700496592
[
上一页 ]
[ :1.700496543e+09 ]
[
下一页 ]