张利华
2000年图灵奖获得者-姚期智的拓变人生
2021-10-17 23:47
阅读:1429

      姚期智,祖籍湖北孝感,1946年12月24日出生于上海。
      幼年随父母去了台湾,1967年台湾大学毕业后到美国深造,1972年获得哈佛大学物理学博士学位。
      做了一年博士后研究工作后,姚期智选择伊利诺依大学攻读计算机科学博士学位,1975年获得计算机科学博士学位。之后曾经先后在麻省理工学院(1975-1976),斯坦福大学(1976-1981),加州大学伯克利分校(1981-1982),斯坦福大学(1982-1986)。
     之所以获得ACM图灵奖,其主要贡献在于计算理论,其中包括基于复杂性的伪随机数生成理论(Complexity-based theory of pseudorandom number generation)、密码学(Cryptograpy)、通信复杂性(Communication complex)等。
      在近四分之一个世纪里发表的近百篇学术论文,几乎涵盖了计算复杂性的所有方面,也涉及算法设计与分析的许多重要问题。他的研究结果和所采用的证明方法,常常使计算机理论界对一些核心课题的认识和理解产生飞跃。
    比如,1975年发表的“寻找最小生成树的O(|E|log log|V|)算法”证明了之前常用的最小生成数Kruskal算法-时间复杂度为O(Elog V)的极限是可以打破的。1981年发表的“表应该被排序吗?”(Should Tables be  Sorted?),使人们对应如何有效地存储信息这一重要问题的认识发生了革命性的变革,该文中所采用的Cell Probe模型在数据结构和算法的设计与分析的研究中产生了深远的影响。1982年发表的“活板门函数的理论与应用”(Theory and Applications    of Trapdoor Function)首次定义了计算熵(computational entropy),引出了一系列有关定理和推论,极大推动了密码学的发展。
    上述只是他众多研究成果的一部分。在荣获图灵奖前,他就于1987年获得波利亚(George Polya)、1996获得首届克努特奖。1998年,还当选为美国科学院院士,2000年当选美国艺术与科学院数学部院士。
    他于1971年与来自台湾的华裔科学家储枫结婚,两人志趣相投,还联名发表过许多研究论文。
     2004年当选为中国科学院外籍院士,同年出任清华大学高等研究中心教授。

拓展阅读 吴鹤龄 崔林 《图灵和ACM图灵奖(1966-2011)》第四版,纪念图灵百年诞辰 2012年6月出版

转载本文请联系原作者获取授权,同时请注明本文来自张利华科学网博客。

链接地址:https://wap.sciencenet.cn/blog-520919-1308324.html?mobile=1

收藏

分享到:

当前推荐数:3
推荐人:
推荐到博客首页
网友评论0 条评论
确定删除指定的回复吗?
确定删除本博文吗?