算法设计与分析：Turing奖介绍

图灵奖（Turing）简介世界上第一台电子计算机ENIAC于1946年2月诞生在美国宾夕法尼亚大学莫尔学院。但学术界公认，电子计算机的理论和模型是由英国数学家图灵(AlanMathisonTuring，1912-1954)在1936年发表的一篇论文“论可计算数及其在判定问题中的应用”中奠定了基础的。因此，当美国计算机协会ACM在1966年纪念电子计算机诞生20周年，也就是图灵的有历史意义的论文发表30周年的时候，决定设立计算机界的第一个奖项，并且很自然地把它命名为“图灵奖”以纪念这位计算机科学理论的奠基人。

图灵奖是计算机界最负盛名的奖项,有“计算机界诺贝尔奖”之称。图灵奖对获奖者的要求极高,评奖程序也极严,一般每年只奖励一名计算机科学家,只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖.目前图灵奖由英特尔公司赞助,奖金为100,000美元。每年，美国计算机协会（ACM）将要求提名人推荐本年度的图灵奖候选人，并附加一份200到500字的文章，说明被提名者为什么应获此奖。评选委员会对被提名者进行严格的评审，并最终确定当年的获奖者。AlanTuring生平简介1912年6月23日，出生于英国伦敦。1931-1934年，在英国剑桥大学国王学院学习。1932-1935年，研究量子力学、概率论和逻辑学。1935年，由于独立发现中心极限定理，获Smith奖，年仅23岁被选为剑桥大学国王学院院士。1936年，研究可计算理论，提出“图灵机”的构想。1936-1938年，在美国普林斯顿大学做博士研究，涉及逻辑学、代数和数论等领域。1938-1939年，返回剑桥从事研究工作，并应邀加入英国政府破译二战德军密码的工作。1940-1942年，作为主要参与者和贡献者之一，成功破译德军U-潜艇密码。AlanTuring生平简介1943-1945年，担任英美密码破译部门的总顾问。1945年，应邀在英国国家物理实验室从事计算机理论研究工作。1946年，被英国皇室授予OBE爵士勋衔。1947-1948年，从事计算机程序理论的研究，并同时在神经网络和人工智能领域作出开创性的理论研究。1948年，应邀加入英国曼彻斯特大学从事研究工作，担任曼彻斯特大学计算实验室副主任。1949年，把计算机实际用于数学研究。1950年，发表论文“计算机器与智能”，为人工智能科学提供开创性的构思。提出著名的“图灵测试”理论。AlanTuring生平简介1951年，提出生物增长的非线性理论研究。年仅39岁被选为英国皇家学会会员。1952年，有同性恋倾向的图灵被捕入狱。法庭审判过程中，图灵明确告知人们自己并没有做错什么事，然而为了避免被判刑入狱，图灵被迫选择了为期一年的雌性激素注射的所谓“治疗”，才得以重返研究工作。1953-1954年，继续在生物和物理学等方面的研究。被迫承受对同性恋倾向的“治疗”，致使原本热爱体育运动的图灵在身心上受到极大的伤害。1954年6月7日，42岁的图灵死于家中的床上，床头有一个咬了一半的，在氰化物溶液中浸泡过的苹果，警方调查结论是自杀。图灵终生未娶。AlanTuring的主要贡献24岁提出图灵机理论31岁参与Colossus的研制（二战时英国破解德国通讯密码的计算机，核心成员）33岁时构思了仿真系统35岁提出了自动程序设计的概念38岁设计了“图灵测试”39岁提出了关于生物增长的非线性理论有“计算机之父”、“人工智能之父”、“破译之父”等美誉。有人甚至认为，他的贡献及对未来世界的影响几乎可与牛顿、爱因斯坦等人比肩。图灵相信如果模拟人类大脑的思维就可以做出一台可以思考的机器，它于1950写文章提出了著名的“图灵测试”，测试是让人类考官通过键盘向一个人和一个机器发问，这个考官不知道他现在问的是人还是机器。如果在经过一定时间的提问以后，这位人类考官不能确定谁是人谁是机器，那这个机器就有智力了。

算法在CS中占有重要地位的一个体现

——有超过1/3的Turing奖获奖者其成果与算法有关。首位亚裔图灵奖得主 2000年 AndrewChi-ChihYao(姚期智)

——(授予姚期智图灵奖以表彰其在)计算理论领域的基础性的卓越贡献,其中包括产生伪随机数的复杂性理论,密码系统和通讯复杂性等.于1987年获得美国工业与应用数学学会GeorgePolya奖,1996年获得美国计算机学会算法与计算理论分会(ACMSIGACT)DonaldE.Knuth奖.于1998年当选为美国科学院院士,于2000年当选为美国科学与艺术学院院士,并于2004年当选为中国科学院外籍院士。1946年12月24日生于上海,美国国籍.于1967年获得台湾大学物理学士学位,1972年获得美国哈佛大学物理博士学位,1975年获得美国伊利诺依大学计算机科学博士学位.曾先后在美国麻省理工学院数学系,斯坦福大学计算机系,加利福尼亚大学伯克利分校计算机系、普林斯顿大学计算机科学系任助理教授,教授.

现任清华大学高等研究中心

(TheCenterforAdvancedStudyinTsinghuaUniversity)教授.姚期智之妻储枫（FrancisYao），自2004年起在香港城市大学电脑科学系担任系主任。首位女性图灵奖得主

2006年 FrancesE.Allen(弗朗西斯·

艾伦)

——在编译器优化技术理论和实践做出的先驱性贡献，这些理论和实践是现代优化编译和自动并行执行的基础。Frances1957年加盟IBMWatson研究中心.是IBM历史上第一位女院士,深刻影响计算机工业界。RSA算法的发明者

2002年 RonaldL.

Rivest

(隆·

里维斯特),

AdiShamir(阿迪·

沙米尔)和

LeonardM.

Adleman

(雷奥纳德·

阿德尔曼)

——使得公钥密码技术在实际中可用的创造性贡献Shamir&Rivest&Adleman

有关AlanTuring的一些轶事两次报考剑桥三圣学院（TrinityCollege，最负盛名）未被录取，只好进了剑桥国王学院（King’sCollege）攻读数学。不善言辞，有些木讷害羞，常咬指甲。在剑