1700496530
将针扔到画了线的纸上几千次是一种有趣的消遣（对一些人来说），但这需要计算机的发展，使取样成为一种实用的方法。之前，当数学家和物理学家们试着用随机性来解决问题时，他们必须辛苦地用手来计算，这就很难产生足够的样本以带来精确的结果。尤其是在第二次世界大战期间，洛斯阿拉莫斯美国国家实验室开发的计算机为计算带来了飞跃。
1700496531
1700496532
斯塔尼斯拉夫·乌拉姆是一位数学家，他曾助力于开发原子弹。他在波兰长大，1939年移居美国，并于1943年加入曼哈顿计划。在短暂回归学术界后，他于1946年回到了洛斯阿拉莫斯，从事热核武器设计。但他患了脑炎并做了脑部急救手术。当他从疾病中恢复过来时，他担心自己是否能恢复数学能力。
1700496533
1700496534
康复期间，乌拉姆玩了很多纸牌，尤其是单人纸牌（也称为克朗代克）。正如任何一个纸牌游戏玩家所知道的那样，某一些洗牌方式就是会让游戏无法获胜。乌拉姆也是这样玩的，他问自己一个自然的问题：洗出能获得胜利的好牌的概率是多少呢？
1700496535
1700496536
在像单人纸牌游戏这样的游戏中，你可以通过各种可能性的空间来推理，这几乎让你无法抗拒。翻第一张牌，还有52种可能的游戏来跟踪。翻第二张，对于第一张有51种可能性。这意味着在我们开始玩之前，已经有了成千上万种可能性。斯科特·菲茨杰拉德曾写道：“一流的智力，就是大脑中能够同时存在两种对立的想法，它们还能同时正常运转。”这或许是真的，但真正一流的智商、人类群者其他任何东西，并不能同时存在80×1067种可能的洗牌方式，且还依然有希望继续正常运转。
1700496537
1700496538
在尝试了一些复杂的组合计算并放弃之后，乌拉姆开始了一种不同的方法，它的优势就是其具有的简单性：去玩游戏就好了。
1700496539
1700496540
我注意到，可能更实用的（尝试）是放下牌，跟着过程发展进行实验，只是注意成功出现的比例，而不是试图计算出所有组合的可能性，这种可能性都是以指数倍递增的，最后的数量大得惊人，除了最基本的情况，没有其他办法估计。这在智力上即使不是完全的羞辱，结果也是惊人的，理性或传统思维的局限会给人一种没那么可怕的感觉。在一个非常复杂的问题中，实际的抽样要好于对所有的可能链都进行检验。
1700496541
1700496542
当他说“更好”时，请注意，他并不一定是指抽样分析比详尽的分析能为你提供更精确的答案：抽样过程中总会有一些错误存在，虽然可以通过确保样品真正的随机性以及提高样品的数量来减少这种错误出现的可能。他说“抽样会更好”的意思是，因为它最终会给你一个答案，而其他方法都无法做到。
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
[
上一页 ]
[ :1.70049653e+09 ]
[
下一页 ]