本文轉(zhuǎn)自：http://bbs.gxnu.edu.cn/bbsanc.php?path=%2Fgroups%2FGROUP_5%2FProgramming%2Fother%2FM.1029997222.A

A.M.?Turing?Award
?
ACM's?most?prestigious?technical?award?is?accompanied?by?a?prize?of?$25,000.
?It?is?given?to?an?individual?selected?for?contributions?of?a?technical?natu
re?made?to?the?computing?community.?The?contributions?should?be?of?lasting?a
nd?major?technical?importance?to?the?computer?field.Financial?support?of?the
?Turing?Award?is?provided?by?InterTrust?Technologies?Corporation's?Strategic
?Technologies?and?Architectural?Research?Laboratory?(STAR?Lab).
?
Award?Recipients
1966?A.J.?Perlis
1967?Maurice?V.?Wilkes
1968?Richard?Hamming
1969?Marvin?Minsky
1970?J.H.?Wilkinson
1971?John?McCarthy
1972?E.W.?Dijkstra
1973?Charles?W.?Bachman
1974?Donald?E.?Knuth

1974?Donald?E.?Knuth
1975?Allen?Newell
1975?Herbert?A.?Simon
1976?Michael?O.?Rabin
1976?Dana?S.?Scott
1977?John?Backus
1978?Robert?W.?Floyd
1979?Kenneth?E.?Iverson
1980?C.?Antony?R.?Hoare
1981?Edgar?F.?Codd
1982?Stephen?A.?Cook
1983?Ken?Thompson
1983?Dennis?M.?Ritchie
1984?Niklaus?Wirth
1985?Richard?M.?Karp
1986?John?Hopcroft
1986?Robert?Tarjan
1987?John?Cocke
1988?Ivan?Sutherland
1989?William?(Velvel)?Kahan
1990?Fernando?J.?Corbato'
1991?Robin?Milner
1992?Butler?W.?Lampson

1988?Ivan?Sutherland
1989?William?(Velvel)?Kahan
1990?Fernando?J.?Corbato'
1991?Robin?Milner
1992?Butler?W.?Lampson
1993?Juris?Hartmanis
1993?Richard?E.?Stearns
1994?Edward?Feigenbaum
1994?Raj?Reddy
1995?Manuel?Blum
1996?Amir?Pnueli
1997?Douglas?Engelbart
1998?James?Gray
1999?Frederick?P.?Brooks,?Jr.
2000?Andrew?Chi-Chih?Yao

[1986]碩果累累的算法大師--約翰·霍潑克洛夫特和羅伯特·塔揚(yáng)

? ? ? 1986年圖靈獎(jiǎng)由康乃爾大學(xué)機(jī)器人實(shí)驗(yàn)室主任約翰·霍潑克洛夫特(John?Edward?Hopcroft)?和普林斯頓大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·塔揚(yáng)(Robert?Endre?Tarjan)共享，而塔揚(yáng)曾是霍?潑克洛夫特的學(xué)生。這師生兩人由于在數(shù)據(jù)結(jié)構(gòu)和算法的分析和設(shè)計(jì)方面的許多創(chuàng)造性?貢獻(xiàn)而共同獲此殊榮，在業(yè)界傳為美談。霍潑克洛夫特1939年10月7日生于西雅圖。1961?年在西雅圖大學(xué)獲得電氣工程學(xué)士學(xué)位以后，進(jìn)入斯坦福大學(xué)研究生院深造，1962年獲?得碩士學(xué)位，1964年獲得博士學(xué)位，也就是說(shuō)只用了3年時(shí)間他就拿下了2個(gè)學(xué)位，霍?潑克洛夫特的勤奮和?聰穎由此可見(jiàn)。學(xué)成以后，霍潑克洛夫特曾先后在普林斯頓大學(xué)、??的?爾大學(xué)、斯坦福大學(xué)等著名學(xué)府工作，也曾任職于NSF(美國(guó)科學(xué)基金會(huì))和NRC(美?國(guó)國(guó)家研究院)，從事對(duì)科學(xué)研究的規(guī)劃和行政管理工作，但時(shí)間不長(zhǎng)。
???????? 霍潑克洛夫特成為著名的計(jì)算機(jī)科學(xué)家起源于一個(gè)?十分偶然的機(jī)會(huì)。霍潑克洛夫?特學(xué)習(xí)的專(zhuān)業(yè)是電氣工程，原先對(duì)計(jì)算機(jī)科學(xué)沒(méi)有多少知?識(shí)，只學(xué)過(guò)一門(mén)“開(kāi)關(guān)?特學(xué)習(xí)的專(zhuān)業(yè)是電氣工程，原先對(duì)計(jì)算機(jī)科學(xué)沒(méi)有多少知?識(shí)，只學(xué)過(guò)一門(mén)“開(kāi)關(guān)電路和邏輯設(shè)計(jì)”算多少有些關(guān)系。因此他原打算畢業(yè)后去西海?岸的一所大學(xué)執(zhí)教電氣工程方面的課程。但就在畢業(yè)以前，有一次他偶然經(jīng)過(guò)他的導(dǎo)師、?研究神經(jīng)網(wǎng)絡(luò)的先驅(qū)和著名學(xué)者威德羅(Bernard?Widrow)辦公室的門(mén)口，當(dāng)時(shí)，普林頓?大學(xué)的麥克盧斯基教授(Edward?McCluskey，曾任IEEE計(jì)算機(jī)協(xié)會(huì)主席)正為籌建數(shù)字系?統(tǒng)實(shí)驗(yàn)室打電話給?w羅，請(qǐng)他推薦博士生去那里工作。威德羅一眼瞥見(jiàn)從門(mén)口走過(guò)的?霍潑克洛夫特，覺(jué)得勤奮好學(xué)，悟性又高的這位得意門(mén)生正是一個(gè)值得推薦的人才，當(dāng)?即把霍潑克洛夫特叫進(jìn)辦公室，并把電話聽(tīng)筒遞給了他。霍潑克洛夫特在電話里聽(tīng)了麥?克盧斯基對(duì)對(duì)普林斯頓大學(xué)擬建數(shù)字系統(tǒng)實(shí)驗(yàn)室的情況介紹，以后又前去面談了一次，實(shí)?地了解一番以后，對(duì)這一新的學(xué)科產(chǎn)生了興?趣，欣然接受了普林斯頓的聘任，從而改變?了他一生的道路。 ?

? ? ? ?年青的霍潑克洛夫特來(lái)到普林斯頓之后接受的第一?項(xiàng)任務(wù)是開(kāi)設(shè)一門(mén)新課：自動(dòng)機(jī)理論。這對(duì)他來(lái)說(shuō)是富有挑戰(zhàn)性的，因?yàn)樗安⑽唇?觸過(guò)這個(gè)課題。面對(duì)挑戰(zhàn)，他以極大的熱情收集、鉆研和消化了大量有關(guān)材料，加以分?析、綜合和比較。這樣，在霍潑克洛夫特的努力下，有關(guān)自動(dòng)機(jī)理論的一些分散、復(fù)雜?的材料第一次被全面地條理化、系統(tǒng)化，因此他的講課理所當(dāng)然地受到了學(xué)生極大的歡迎。后來(lái)，霍潑克洛夫特和厄爾曼(J.D.Ullman)又合作編寫(xiě)了《形式語(yǔ)言及其與自動(dòng)機(jī)的?關(guān)系》(《Formal?Language?and?Their?Relation?to?Automata》，Addison-Wesley,1969)一書(shū)，這?本書(shū)被認(rèn)為是自動(dòng)機(jī)理論中有代表性的一部著作。

? ? ? ?然而，霍潑克洛夫特更感興趣的課題是算法。當(dāng)時(shí)，?算法復(fù)雜性理論雖已由哈特馬尼斯(J.Hartmanis)、斯坦恩斯(R.Stearns,這兩人是1993年圖靈?獎(jiǎng)獲得者)和布魯姆(M.Blam，1995年圖靈獎(jiǎng)獲得者)等人奠定了基礎(chǔ)，但對(duì)具體算法的效?率和優(yōu)劣的判斷尚未建立起客觀和明確的準(zhǔn)則，因此，往往出現(xiàn)下述情況：有人公布了?一個(gè)算法，給出對(duì)若干樣本問(wèn)題的執(zhí)行時(shí)間；過(guò)了一段時(shí)間，另外一個(gè)人發(fā)布“改進(jìn)算?法”，給出對(duì)相同樣?趕□D的執(zhí)行時(shí)間(當(dāng)然比前者少)。而實(shí)際上，這很可能是由于機(jī)器?性能提高或(和)語(yǔ)言改進(jìn)所致，所謂“改進(jìn)算法”其實(shí)不見(jiàn)得比原算法高明。霍潑克洛夫?特對(duì)這種情況很不滿意，決心加以解決。經(jīng)過(guò)反復(fù)研究，他終于提出了一種稱(chēng)為“最壞?情況漸近分析法”(Worst-case?asymptoticanalysis?of?algorithm)，這種方法先確定問(wèn)題和大小?尺度，然后把計(jì)算時(shí)間當(dāng)作問(wèn)題大小尺度的一個(gè)函數(shù)去算出計(jì)算時(shí)間的增長(zhǎng)率，以此衡?量算法的效率和優(yōu)劣。這個(gè)方法由于與機(jī)器性能及所用語(yǔ)言無(wú)關(guān)，成為測(cè)量算法好壞的?數(shù)學(xué)準(zhǔn)則，被學(xué)界所廣泛認(rèn)同和接受。
? ? ? ?但是導(dǎo)致他和塔揚(yáng)共同獲得圖靈獎(jiǎng)的最主要貢獻(xiàn)則?是他們解決了圖論算法中的一些難題。1970年，霍潑克洛夫特在?的?爾大學(xué)獲得一年休?假(他是1967年被另一圖靈獎(jiǎng)獲得者哈特馬尼斯招至麾下的)。他決定回母校斯坦福大學(xué)?到克努特(D.Knuth)教授名下做研究，因?yàn)榭伺?亓□M只比他年長(zhǎng)一歲，但因在1967年和1968年連出兩卷《計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)》(《The?Art?of?ComputerProgramming》)而已名?滿天下，成為算法領(lǐng)域的權(quán)威。克努特知道霍潑克洛夫特對(duì)算法感興趣并有獨(dú)到見(jiàn)解，?就把他和自己的得意門(mén)生、研究方向也是算法的塔揚(yáng)安排在一個(gè)辦公室，為他們的合作?創(chuàng)造了條件。他們選擇了圖論中與實(shí)際應(yīng)用有很大關(guān)系的圖的連通性和平面性測(cè)試難題?進(jìn)行攻關(guān)。拿平面圖來(lái)說(shuō)，它對(duì)印刷有很大關(guān)系的圖的連通性和平面性測(cè)試難題?進(jìn)行攻關(guān)。拿平面圖來(lái)說(shuō)，它對(duì)印刷電路板設(shè)計(jì)這樣一類(lèi)問(wèn)題有十分重要的意義。學(xué)過(guò)?圖論的人都知道，平面圖的判斷問(wèn)題，在數(shù)學(xué)上已由波蘭數(shù)學(xué)家?guī)炖蟹蛩够?Kuratowski)?于1930年解決。庫(kù)拉托夫斯基的判據(jù)原理看似簡(jiǎn)單，但實(shí)現(xiàn)起來(lái)很難。對(duì)于有100個(gè)頂?點(diǎn)的圖，用普通的算法，計(jì)算機(jī)需要1萬(wàn)億˙才能確定其是否為平面圖!因此，尋找高效?的平面圖測(cè)試算法成為擺在當(dāng)時(shí)計(jì)算機(jī)科學(xué)家面前的一大難題。霍潑克洛夫特和塔揚(yáng)都?是富有創(chuàng)造性的人，又都善于合作共事，因此當(dāng)兩朵智慧的火花碰在一起時(shí)，就很快迸?發(fā)出耀眼的光芒!在解決這個(gè)難題的過(guò)程中，霍潑克洛夫特首先提出了?一種新的思路、新?的算法，經(jīng)過(guò)塔揚(yáng)的反復(fù)推敲和完善，一種適于解這類(lèi)問(wèn)題的新的算法終于誕生了，這?就是“深度優(yōu)先搜索算法”(depth-first?search?algorithm)。利用這種算法對(duì)圖進(jìn)行搜索時(shí)，?結(jié)點(diǎn)擴(kuò)展的次序是向某一個(gè)分枝縱深推進(jìn)，到底后再回溯，這樣就能保證所有的邊在搜?索過(guò)程中都經(jīng)過(guò)一次，并且只經(jīng)過(guò)一次，從而大大提高了效率。新算法的運(yùn)行時(shí)間是線?性的，也就是說(shuō)時(shí)間與圖的大小成正比關(guān)系，大小翻一倍，解問(wèn)題所需的時(shí)間也只翻一?倍。相比之下，若用庫(kù)拉托夫斯基判斷的老算法，那么當(dāng)圖的大小翻一倍時(shí)，所需時(shí)間?要增加60倍以上。利用他們創(chuàng)造的新算法，塔揚(yáng)用Algolw為一個(gè)包含900個(gè)結(jié)點(diǎn)和2694?條邊的圖編制了一個(gè)測(cè)試其平面性的程序，程序只有500行，在IBM360/67上運(yùn)行，只?用了12秒就得到了結(jié)果。霍潑克洛夫特和塔揚(yáng)把他們的研究成果寫(xiě)成論文在《Journal?of?the?ACM》上發(fā)表，引起學(xué)術(shù)界很大的轟動(dòng)。而他們創(chuàng)造的深度優(yōu)先算法則被推廣到信息?檢索、國(guó)際象棋比賽程序、專(zhuān)家系統(tǒng)中的沖突消解策略等許多方面。在霍潑克洛夫特和?塔揚(yáng)獲得圖靈獎(jiǎng)的授獎(jiǎng)儀式上，當(dāng)年的計(jì)算機(jī)象棋程序比賽的優(yōu)勝者就說(shuō)，他的程序中?使用了霍潑克洛夫特和塔揚(yáng)所發(fā)明的深度優(yōu)先搜索算法，這是他的程序所以能出奇制勝?的關(guān)鍵。

? ? ? ? 在取得輝煌成功之后，霍潑克洛夫特和塔揚(yáng)并不滿足，他們致力于開(kāi)發(fā)效率更高的算法。不久，他們又提出了一種新的數(shù)據(jù)結(jié)構(gòu)叫“雙堆?棧疊”（pile?of?twin?stacks），這種新的數(shù)據(jù)結(jié)構(gòu)被深度優(yōu)先搜索算法的優(yōu)點(diǎn)更加發(fā)揚(yáng)光?大。塔揚(yáng)的一個(gè)學(xué)生用這種新的數(shù)據(jù)結(jié)構(gòu)和算法編寫(xiě)了一個(gè)Algolw程序，只有250行，在IBM?370/168上測(cè)試有8000個(gè)結(jié)點(diǎn)的圖的平面性只用了8秒鐘。
?
? ? ? ? 霍潑克洛夫特除了和塔揚(yáng)合作取得上述成果外，在數(shù)?據(jù)結(jié)構(gòu)和算法方面還有其他?一系列創(chuàng)造。比如常用于索引組織的著名數(shù)據(jù)結(jié)構(gòu)B樹(shù)(B-tree)?是一種平衡的多分樹(shù)，由于對(duì)查找、插入、刪除等操作能始終保持動(dòng)態(tài)平衡，具有高效?的特性。霍潑克洛夫特在對(duì)B樹(shù)進(jìn)行深入研究以后，為了進(jìn)一步提高其操作效率和空間?利用率，提出了它的一種變形叫2-3樹(shù)，這種樹(shù)的每個(gè)結(jié)點(diǎn)有2個(gè)鍵，每個(gè)鍵都有2-3個(gè)?兒子。
? ? ? ?霍潑克洛夫特著述頗豐，除前面已經(jīng)提到過(guò)的他的處?女作以外，還有以下多部著作問(wèn)世：
? ? ??《計(jì)算機(jī)算法的設(shè)計(jì)與分析》、《數(shù)據(jù)結(jié)構(gòu)和算法》?、?《自動(dòng)機(jī)理論，語(yǔ)言和計(jì)算的導(dǎo)論》和《計(jì)算機(jī)科學(xué)?：成就與機(jī)遇》。
? ? ? ?霍潑克洛夫特最近的興趣集中在機(jī)器人學(xué)方面，這從?他現(xiàn)任?的?爾大學(xué)機(jī)器人實(shí)?驗(yàn)室主任這一點(diǎn)上可以看出。

? ? ? 一個(gè)富于幻想、追求新鮮事物的人。他幼時(shí)對(duì)天文學(xué)很感?興趣，夢(mèng)想成為第一個(gè)登上火星的人。小學(xué)七年級(jí)時(shí)他又開(kāi)始讀《科學(xué)美國(guó)人》(《Scientific?American》，這是美國(guó)最著名的科普雜志之一)，尤其對(duì)著名數(shù)學(xué)家馬丁·加德那(M.Gardner)?開(kāi)設(shè)的趣味數(shù)學(xué)專(zhuān)欄深感興趣(馬西·加德那所著的《啊哈!靈機(jī)一動(dòng)》由上海科技出版社?于1981年譯成中文出版，被中國(guó)科學(xué)家評(píng)為“20世紀(jì)科普佳作”之一而進(jìn)行推介)。1964?年，塔揚(yáng)參加一個(gè)中學(xué)生科學(xué)夏令營(yíng)，第一次接觸計(jì)算機(jī)，立即被神奇的計(jì)算機(jī)所吸引。?因此，當(dāng)他上加州理工學(xué)院時(shí)，雖然學(xué)的專(zhuān)業(yè)是數(shù)學(xué)，但同時(shí)還輔修了當(dāng)時(shí)學(xué)校開(kāi)設(shè)的?所有有關(guān)計(jì)算機(jī)的課程。1969年他取得學(xué)士學(xué)位以后，進(jìn)入斯坦福大學(xué)研究生院，師從?著名的計(jì)算機(jī)科學(xué)家、后來(lái)在1974年榮獲圖靈獎(jiǎng)的克特。1970年，在克努特的有意安?排下，他與到斯坦福來(lái)度學(xué)術(shù)假的康乃爾大學(xué)教師霍潑克洛夫特在一個(gè)辦公室開(kāi)始了對(duì)?圖論算法的共同研究。他們的這個(gè)課題實(shí)際上是在有“人工智能之父”之稱(chēng)的麥卡錫?(J.McCarthy)的建議下進(jìn)行的。當(dāng)時(shí)塔揚(yáng)正選修麥卡錫開(kāi)設(shè)的“符號(hào)處理”(Symbolic?processing)課程，學(xué)習(xí)由麥卡錫開(kāi)發(fā)的第一個(gè)人工智能語(yǔ)言Lip。作為作業(yè)，麥卡錫讓學(xué)?生編寫(xiě)程序以驗(yàn)證給定的圖是否是平面的，并建議學(xué)生們?cè)诔绦蛑惺褂脦?kù)拉托夫斯基條?件。塔揚(yáng)雖然一開(kāi)始就意識(shí)到這樣得出的算法效率太低，考慮“另起爐灶”，但不知從?何入手。這時(shí)霍潑克洛夫特提出的新思路、新算法啟發(fā)了他，他仔細(xì)考慮了它，并力圖?使霍潑克洛夫特的算法中的原則更加嚴(yán)密、更加完善，終于使深度優(yōu)先搜索算法完美實(shí)?現(xiàn)，取得成功。
創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的图灵奖得主（一）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。