本文轉自：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]碩果累累的算法大師--約翰·霍潑克洛夫特和羅伯特·塔揚

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

? ? ? ?年青的霍潑克洛夫特來到普林斯頓之后接受的第一?項任務是開設一門新課：自動機理論。這對他來說是富有挑戰性的，因為他之前并未接?觸過這個課題。面對挑戰，他以極大的熱情收集、鉆研和消化了大量有關材料，加以分?析、綜合和比較。這樣，在霍潑克洛夫特的努力下，有關自動機理論的一些分散、復雜?的材料第一次被全面地條理化、系統化，因此他的講課理所當然地受到了學生極大的歡迎。后來，霍潑克洛夫特和厄爾曼(J.D.Ullman)又合作編寫了《形式語言及其與自動機的?關系》(《Formal?Language?and?Their?Relation?to?Automata》，Addison-Wesley,1969)一書，這?本書被認為是自動機理論中有代表性的一部著作。

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

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

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