NorthChinaElectricPowerUniversity6.提出著名公式“算法数据结构程序”瑞士的提出著名公式“数据结构=程序教授则为1984年提出著名公式算法+数据结构程序”瑞士的N.Wirth教授则为教授则为年度的图灵奖得主。度的图灵奖得主。7.对组合优化算法、
网络流有效算法、NP完全性和随机算法研究很有造诣对组合优化算法、网络流有效算法、完全性和随机算法研究很有造诣对组合优化算法的、美国加州大学伯克利分校著名教授R.M.Karp的论文“Reducibility美国加州大学伯克利分校著名教授的论文“的论文amongcombinationalproblems”荣获荣获1985年度图灵奖。年度图灵奖。荣获年度图灵奖8.美国教授美国教授J.E.Hopcrft和他的学生和他的学生R.E.Tarjan博士因在算法及数据结构的博士因在算法及数据结构的美国教授和他的学生博士设计和分析中所取得的决定性成果而获奖。设计和分析中所取得的决定性成果而获奖。9.在计算复杂性领域作出卓越贡献的美国的在计算复杂性领域作出卓越贡献的美国的J.Hartmanis和R.E.Steams教授和教授在计算复杂性领域作出卓越贡献的美国的荣获1993年度图灵奖。荣获年度图灵奖。年度图灵奖10.1995年的图灵奖发给在计算复杂性、10.1995年的图灵奖发给在计算复杂性、密码学算法和程序验证技术方面年的图灵奖发给在计算复杂性取得重要成就的美国教授M.BlumM.Blum。取得重要成就的美国教授M.Blum。11.1996年图灵奖获得者:阿米尔?伯努利(Amir11.1996年图灵奖获得者:阿米尔?伯努利(AmirPnueli)年图灵奖获得者引入计算机科学。引入计算机科学。把时态逻辑
12.2000年图灵奖获得者姚期智,因在计算理论方面基础性的工作而获奖,12.2000年图灵奖获得者姚期智,因在计算理论方面基础性的工作而获奖,年图灵奖获得者姚期智包括伪随机性数产生、密码
系统、
通信复杂性理论等。包括伪随机性数产生、密码系统、通信复杂性理论等。2002年图灵奖获得者年图灵奖获得者RonaldRivest工作组工作组,13.2002年图灵奖获得者RonaldL.Rivest工作组,因他们在公共密匙算法上所做的杰出贡献(RSA算法是当前在互联网传输、(RSA算法是当前在互联网传输法上所做的杰出贡献(RSA算法是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制)中被广泛使用的安全基本机制)。
NorthChinaElectricPowerUniversity
§2HistoricalBackground
Thequestionofwhetheraproblemcanbesolvedusinganeffectiveprocedure,whichisequivalenttothecontempo
rarynotionofthealgorithmreceivedalotofattention.Forthispurpose,theneedaroseforamodelofcomputationbythehelpofwhichaproblemcanbeclassifiedassolvableifitispossibletoconstructanalgorithmtosolvethatproblemusingthatmodel.SomeofthesemodelsaretherecursivefunctionofGodel,λ-calculusofChurch,PostmachinesofPostandtheTuringmachinesofTuring.ByChurchThesis,allthesemodelshavethesamepower,inthesensethatifaproblemissolvableononeofthem,thenitissolvableonallothers.
NorthChinaElectricPowerUniversity
Results
Itturnsoutthat“almostall”p