浙江龙网

  1. 首页 > 生活百科 > >

关键性|姚期智：做研究最好的方法是提出深刻、大胆和关键性的问题( 三 )


现在我将对每个主题的主要问题及其重要性进行讨论 。
第一个是 1977 年提出的极大极小算法问题 。 它在我心中有很特殊的位置 ， 因为这是我第一次提出了自己的研究问题 ， 并找到了很好的解决方法 。 我们知道 ， 算法本质上和食谱很像 。 例如在烹饪中 ， 食谱会告诉你每步的步骤 ， 例如放3盎司盐或几克肉 。
20 世纪70年代中期 ， 一种新的算法引起了人们的注意 ， 即“随机化算法”（Randomized algorithm） 。 这种新算法结合了随机移动（stochastic moves） 。 如果用烹饪来比喻的话就是 ， 不明确告诉你有放两勺盐的步骤 ， 而是让你用扔硬币决定是放两勺盐 ， 还是放一杯红酒 。
因此 ， 对于传统的思维方式来说 ， 这看起来是一种疯狂的做事方式 。 但在20世纪70年代 ， 人们已经证明以这种方式执行算法是有优势的 ， 在某些情况下 ， 它们会产生一些令人惊叹的结果 。 但人们还无法理解这些算法的局限性 。
因此 ， 这让我产生了一个问题 。 到底哪算法个更好？是当时刚刚提出的随机化方法 ， 还是用传统的方法观察数据分布 ， 并在执行过程中调整呢？
一旦用这种方式提出了这个问题 ， 那么就出现了一种令人惊喜的联系 ， 让人们可以对随机化算法有了很多的了解 。
当把随机化算法与传统分布方法进行比较时 ， 可以将其视为随机化算法和数据之间的博弈 。 算法（可以根据数据）选择如何随机移动 ， 而数据可以选择分布方式 ， 从而使算法的运行变得更加困难 。
在博弈论极大极小原理的作用下下这两种方法恰好达到了它们的极限 。
这个联系给出了我们想要证明的定理 ， 也就是说事实上这两种方法是相同的 。 这为理解随机化算法提供了新途径 。 在现在 ， 这种在当时还算新颖的算法已经成为许多密码技术和人工智能算法的默认模式 。
人们想了解随机化算法的局限性是有原因的 。 因此 ， 在40多年的时间里 ， 我发现的算法仍然被许多研究人员用来来解决他们的问题 。
第二个主题是我在1979年提出的通信复杂性 。
让我先解释一下这个数学问题 ， 爱丽丝和鲍勃是两个在不同地点的人 ， 他们各自持有一条 n 个比特的数据 ， 比如x和y 。 我们想要解决的问题是 ， 假设它们想要联合计算某个量f ， 它们之间需要通信多少比特 ， 这就是这个函数的通信复杂度 。
当然 ， 这取决于你在计算什么函数 ， 例如 ， 要计算这两个整数的和是奇数还是偶数只需要两个比特的通信 。 每个人只需告诉对方它是偶数还是奇数 ， 然后他们就可以知道答案了 。
另一方面 ， 如果你想计算x是否大于y ， 那么它将需要n比特 。 你需要把整个字符串从一个人发送给另一个人才能解决这个问题 。
更深一层的是 ， 你必须意识到并证明 ， 没有比这种方式来解决这个问题更好的方法了 。 一般来说 ， 这是一个相当困难的问题 。 如果我给你一个关于F的计算复杂性 ， 那需要相当深入的数学分析才能完成 。
考虑通信复杂度的原因是 ， 计算模式在20世纪70年代末发生了很明显的变化 。 从之前大家都熟悉的大型计算机 ， 逐渐转向我们现在熟悉的计算机网络 。 人们对以分布式方式解决问题感兴趣 ， 许多人愿意协作解决问题 。
因此 ， 这意味着我们必须把过去的计算模型调整为网络模型 。 在这个新的世界里 ， 通信成本通常是很高的 ， 因为我们必须移动数据 。
因此 ， 我刚刚向你们的介绍的通信复杂度的概念就是为了模拟和反映这种变化 。 自从该模型被提出和分析以来 ， 通信复杂性在从芯片设计到数据流的各个领域都得到了广泛的应用 。

推荐阅读


上一篇：刘晓惠|海南：到2025年吸引国际教育消费回流5万人以上

下一篇：蒋栓德|阳信县举行高考先进集体表彰会