2000年图灵奖

大家好，我是执念斩长河。今天讲述的是中国首位图灵奖获得者姚期智。图灵奖奖励他为计算机复杂性理论做出巨大的贡献。读完本篇博文大家轻松获得：

• 姚期智论文涵盖计算机全部复杂性
• 破解最小生成树线性复杂度的顶级秘籍
• 表是否能排序问题的解决

姚期智祖籍湖北孝感，1946年12月24日生于上海，幼年即随父母去台湾。1967年在台湾大学毕业以后，去美国深造。他原先所学的专业是物理，但他感觉计算机发展潜力大，然后放弃原专业，从而下决心学习计算机科学。 因此，在1972年取得令人羡慕的哈佛大学物理学博士学位，并做了一年博士后研究工作之后，他出人意料地选择到伊利诺伊大学研究生院继续学习，攻读计算机科学博士学位。

姚期智对计算机理论地众多贡献是根本性的，意义重大的，其中包括基于复杂性的伪随机数生成理论、密码学、通信复杂性等。 姚期智在近1/4世纪中发表的近百篇学术论文，几乎覆盖了计算机复杂性的所有方面，也涉及算法与分析的许多重要问题，他的研究结果和所采用的证明方法，常常使计算机理论界对一些核心课题的认识和理解产生飞跃。

姚期智进入计算机科学理论领域是那篇“寻找最小生成树的O（|E|loglog|V|）算法”震惊当时计算机领域，以致于后来在姚期智论文的影响下，发现了寻找最小生成树的线性时间算法。 学过《数据结构》的同学知道，两种最小生成树方法一个prim和kruskal都只不过是O（ElogV)，可想而知姚期智的计算机基础功底。
       在数据组织方面，人们历来认为排序表(sorted table)是一种良好的结构，可以检索更快。但姚期智论文证明只有很少时候条件成立，绝大多数效率不咋地。这为后来出现最佳概率化散列模式和字典实现方式奠定了基础。

真为中国人感到自豪，挺进图灵殿堂！