精华区文章阅读

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: 姚期智:开华裔获图灵之先河
发信站: 哈工大紫丁香 (2001年08月23日17:25:08 星期四), 站内信件

资料来源：计算机世界
wizefox整理

世纪的第一个春天刚刚来临，从大洋彼岸就传来一个令人振奋的消息：
美国计算机学会(ACM)决定把2000年度的图灵奖授予华裔计算机科学家、
现普林斯顿大学教授姚期智。这是有“计算机世界的诺贝尔奖”之称的
图灵奖35年来首次授予一位华裔学者，是值得全世界华人为之骄傲的。

姚期智(Yao Chi-chih)的英文名字是安德鲁·姚(Andrew C.Yao)。
他祖藉湖北孝感，1946年12月24日出生于上海，幼年随父母去台湾省。1
967年在台湾大学毕业以后，去美国深造，原先所学专业是物理
。但20世纪60年代以来计算机技术的迅猛发展和计算机在各行各业的广
泛应用吸引了他的目光，他敏锐地意识到这是一个十分重要并具有巨大发
展空间的新兴学科，从而决心放弃原先专业而转到计算机科学上来。因此，
在1972年取得令人羡慕的哈佛大学物理学博士学位以后，他出人意料地又
来到伊利诺大学研究生院继续学习。伊利诺大学在计算机科学技术方面当
时处于美国领先地位。姚期智于1975年在伊利诺大学取得他的第二个博士
学位——计算机科学博士学位。之后，他曾先后在麻省理工学院
(1975～1976)、斯坦福大学(1976～1981，1983～1986)、
加州大学伯克利分校(1981～1983)等美国著名高等学府从事
教学与研究，1986年加盟普林斯顿大学至今。

姚期智对计算机科学技术所作出的贡献主要在计算理论方面。ACM在授奖
决定中指出，姚期智对计算理论的众多贡献是根本性的、意义重大的，
其中包括基于复杂性的伪随机数生成理论、密码学和通信复杂性。最近
1/4个世纪中姚期智发表的近百篇学术论文，几乎覆盖了计算复杂性的
所有方面。姚期智进入计算机科学领域最早的论文之一《寻找最小生成
树的O(|E|log log|V|)算法》一文就引起轰动，因为学术界原先认为，
寻找最小生成树算法的时间复杂度的下界是O(E log V)，而姚期智的论
文证明这个极限是可以打破的。在姚的这一开创性工作的基础上，经过近
20年的努力，人们终于设计出了寻找最小生成树的线性时间算法。

在数据组织方面，人们历来以为排序表(Sorted Table)是一种良好的结
构，在其中检索信息有最快的响应。姚期智经过深入研究，发现这只在少
数特定条件下才成立，而对于允许有任意信息编码的表而言，在排序表中
检索信息的效率远不是最佳的。他的研究结果在《表应该被排序吗?》一
文中发表以后，人们对信息应如何有效地存储在认识上发生了革命性的变
化。该文为后来出现最佳概率化哈希模式和字典实现方式奠定了基础。姚
在该文中所采用的证明方法则被称为“Cell Probe”模型而被广泛应用
，在数据结构和算法的分析与设计的研究中产生了深远的影响。

姚期智对伪随机数生成理论的诸多贡献集中反映在他1982年的论文《活板
门函数的理论和应用》中。在这篇有开创性意义的论文中，姚期智先证明
了著名的BlumMicali发生器所产生的随机数实际上是伪随机的，并由此
导出了在随机数生成技术中一个十分重要的概念，即“随机性和难度”的
折衷。论文还首次定义了“计算熵”(Computational Entropy)的概念，
对它进行了深入研究，引出了一系列有关定理和推论，推动了密码学的发
展。而姚期智自己则在1986年的论文《如何产生和交换秘密信息》中进一
步提出了一种称为“健忘的电路模拟”的密码技术，利用这种技术能秘密
而可靠地计算出任意函数。

随着Internet的普及和互联网的飞速发展，对通信复杂性的研究成为姚关
注的一个重点。他在这方面发表的论文如《电路和通信复杂性的近期进展》
被认为是经典之作，经常被其他论文引用。姚期智为通信建立了基本模型，
提出了分析方法，从而使通信复杂性发展成为一个重要的研究领域，并获
得了多方面的和意想不到的应用。

姚期智近期的研究集中于量子通信和计算。量子计算是以量子力学理论和
量子器件为基础、新近发展起来的一种新的计算技术，它不但能降低传统
计算技术的计算复杂性，还能解决一些传统计算机根本无法处理的问题。
姚期智在DARPA/ITO的资助下，已经在这方面的研究中取得若干成果，
发表了一些引人注目的论文，如《Quantum Bit Escrow》、
《Quantum Cryptography with Imperfect Apparatus》、
《Security of Quantum Protocol against Coherent Measurements》等。

在此次荣获图灵奖之前，姚期智在1996年获得以算法设计大师
克努特(Donald Ervin Knuth,1994年图灵奖获得者)命名的首
届克努特奖。去年4月，姚期智被选为美国艺术和科学院教学部
院士，他也是我国《软件学报》(英文版)的副主编，

曾到祖国内地参加学术活动。

姚期智的夫人弗朗西丝·姚(Frances F.Yao)也是来自中
国台湾省的华裔科学家，他们是志趣相投的一对伉俪，曾联名发表许多研究论文。
--


<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]

Algorithm 版 (精华区)