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
1700496594
算法之美：指导工作与生活的算法 抽样的优势
1700496595
1700496596
多项式身份测试表明，有时我们的工作是更好地检查随机的价值（从我们想知道的两个表达式中取样），而不是试图理清它们的内部工作。在某种程度上，这似乎相当直观。现在有两种难以区别的设备，要确定它们是两种不同的设备还是两种相同的设备，我们大多数人都会随意地按下按钮，而不是打开箱子来检查线路。而且我们也不会特别惊讶，例如，一个电视中的毒枭只要用刀随机划开货物中的几捆，便可以对整批货物的质量有一定的把握。
1700496597
1700496598
不过，也有一些案例中我们没有使用随机性，也许我们应该用。
1700496599
1700496600
可以说，20世纪最重要的政治哲学家是哈佛大学的约翰·罗尔斯，他为自己设定了一项雄心勃勃的任务：试图协调两个看似对立的关键理念：自由与平等。当一个社会更自由，或者更平等时，它会更“公正”吗？这两者真的必须互相排斥吗？罗尔斯提出了一种他称之为“无知之幕”的问题。他说，想象一下，你即将出生，却不知道自己出生后是怎样的：男人还是女人，富人还是穷人，城市还是农村，有病还是健康。在了解你的地位之前，你必须选择你所生活的社会。你想要什么？罗尔斯认为，拉开无知之幕，对各种社会安排进行评估，我们会更容易对理想中的安排达成共识。
1700496601
1700496602
然而，罗尔斯的思想实验没有考虑到的是，在这样的幕布后面理解一个社会的计算成本。在这种假设下，我们怎么可能希望掌握所有相关信息？暂且不提正义和公正的重大问题，并尝试运用罗尔斯的方法仅仅对例如健康保险条例等提出改变。也许，在美国，出生后成为中西部的一名镇书记的概率，乘以不同的卫生保健计划的分布，这可用在中西部直辖市上，再乘以保险精算数据提供的可能性，例如胫骨骨折的概率，再乘以在中西部医院可能的保险计划所给定的，胫骨骨折的一般处理的平均医疗费用。那么，拟议的保险修订对国家来说是“好”还是“坏”？我们几乎不能指望用这种方式评估一个受伤的心，更不用说数亿人的生命了。
1700496603
1700496604
罗尔斯的哲学批评家们详细地讨论了我们应该如何从无知的面纱中获得信息的问题。例如，我们是否应该尝试尽量扩大平均幸福、中位数幸福、总幸福或别的什么，其中的每一种方法都很著名，但其却将自己置身于有害的反乌托邦之中，如作家厄休拉·勒吉恩所设想的奥米勒斯城的文明——开放。在这个国家里，繁荣与和谐无处不在，一个孩子却被迫生活在悲惨的境地。这些都是应得的批判，而罗尔斯故意回避了这些问题，因为我们不知道如何处理从幕布后面得到的信息。然而，也许更大的问题首先是如何收集这些信息。
[
上一页 ]
[ :1.700496555e+09 ]
[
下一页 ]