霍潑克洛夫特1939年10月7日生于 西雅圖。1961年在西雅圖大學(xué)獲得電氣工程學(xué)士學(xué)位以后，進(jìn)入斯坦福大學(xué)研究生院深造，1962年獲得碩士學(xué)位，1964年獲得博士學(xué)位，也就是說只用了3年時(shí)間他就拿下了2個(gè)學(xué)位，霍潑克洛夫特的勤奮和聰穎由此可見。學(xué)成以后，霍潑克洛夫特曾先后在普林斯頓大學(xué)、康乃爾大學(xué)、斯坦福大學(xué)著名學(xué)府工作，也曾任職于NSF(美國科學(xué)基金會(huì))和NRC(美國國家研究院)，從事對(duì)科學(xué)研究的規(guī)劃和行政管理工作，但時(shí)間不長(zhǎng)。

　　霍潑克洛夫特成為著名的計(jì)算機(jī)科學(xué)家起源于一個(gè)十分偶然的機(jī)會(huì)�；魸娍寺宸蛱貙W(xué)習(xí)的專業(yè)是電氣工程，原先對(duì)計(jì)算機(jī)科學(xué)沒有多少知識(shí)，只學(xué)過一門“開關(guān)電路和邏輯設(shè)計(jì)”算多少有些關(guān)系。因此他原打算畢業(yè)后去西海岸的一所大學(xué)執(zhí)教電氣工程方面的課程。

　　但就在畢業(yè)以前，有一次他偶然經(jīng)過他的導(dǎo)師、研究神經(jīng)網(wǎng)絡(luò)的先驅(qū)和著名學(xué)者威德羅(BernardWidrow)辦公室的門口，當(dāng)時(shí)，普林斯頓大學(xué)的麥克盧斯基教授(EdwardMcCluskey，曾任IEEE計(jì)算機(jī)協(xié)會(huì)主席)正為籌建數(shù)字系統(tǒng)實(shí)驗(yàn)室打電話給威德羅，請(qǐng)他推薦博士生去那里工作。威德羅一眼瞥見從門口走過的霍潑克洛夫特，覺得勤奮好學(xué)，悟性又高的這位得意門生正是一個(gè)值得推薦的人才，當(dāng)即把霍潑克洛夫特叫進(jìn)辦公室，并把電話聽筒遞給了他�；魸娍寺宸蛱卦陔娫捓锫犃他溈吮R斯基對(duì)普林斯頓大學(xué)擬建數(shù)字系統(tǒng)實(shí)驗(yàn)室的情況介紹，以后又前去面談了一次，實(shí)地了解一番以后，對(duì)這一新的學(xué)科產(chǎn)生了興趣，欣然接受了普林斯頓的聘任，從而改變了他一生的道路。

　　年青的霍潑克洛夫特來到普林斯頓之后接受的第一項(xiàng)任務(wù)是開設(shè)一門新課：自動(dòng)機(jī)理論。這對(duì)他來說是富有挑戰(zhàn)性的，因?yàn)樗�之前并未接觸過這個(gè)課題。面對(duì)挑戰(zhàn)，他以極大的熱情收集、鉆研和消化了大量有關(guān)材料，加以分析、綜合和比較。這樣，在霍潑克洛夫特的努力下，有關(guān)自動(dòng)機(jī)理論的一些分散、復(fù)雜的材料第一次被全面地條理化、系統(tǒng)化，因此他的講課理所當(dāng)然地受到了學(xué)生極大的歡迎。后來，霍潑克洛夫特和厄爾曼(J.D.Ullman)又合作編寫了《形式語言及其與自動(dòng)機(jī)的關(guān)系》 (《FormalLanguageandTheirRelationtoAutomata》，Addison-Wesley,1969)一書，這本書被認(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ì)若干樣本問題的執(zhí)行時(shí)間；過了一段時(shí)間，另外一個(gè)人發(fā)布“改進(jìn)算法”，給出對(duì)相同樣本問題的執(zhí)行時(shí)間(當(dāng)然比前者少)。而實(shí)際上，這很可能是由于機(jī)器性能提高或(和)語言改進(jìn)所致，所謂“改進(jìn)算法”其實(shí)不見得比原算法高明。霍潑克洛夫特對(duì)這種情況很不滿意，決心加以解決。經(jīng)過反復(fù)研究，他終于提出了一種稱為“最壞情況漸近分析法”(Worst-caseasymptoticanalysisofalgorithm)，這種方法先確定問題和大小尺度，然后把計(jì)算時(shí)間當(dāng)作問題大小尺度的一個(gè)函數(shù)去算出計(jì)算時(shí)間的增長(zhǎng)率，以此衡量算法的效率和優(yōu)劣。這個(gè)方法由于與機(jī)器性能及所用語言無關(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)榭伺�特雖然只比他年長(zhǎng)一歲，但因在1967年和1968年連出兩卷《計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)》 (《TheArtofComputerProgramming》)而已名滿天下，成為算法領(lǐng)域的權(quán)威。克努特知道霍潑克洛夫特對(duì)算法感興趣并有獨(dú)到見解，就把他和自己的得意門生、研究方向也是算法的塔揚(yáng)安排在一個(gè)辦公室，為他們的合作創(chuàng)造了條件。他們選擇了圖論中與實(shí)際應(yīng)用有很大關(guān)系的圖的連通性和平面性測(cè)試難題進(jìn)行攻關(guān)。拿平面圖來說，它對(duì)印刷電路板設(shè)計(jì)這樣一類問題有十分重要的意義。學(xué)過圖論的人都知道，平面圖的判斷問題，在數(shù)學(xué)上已由波蘭數(shù)學(xué)家?guī)炖�托夫斯�?Kuratowski)于1930年解決。庫拉托夫斯基的判據(jù)原理看似簡(jiǎn)單，但實(shí)現(xiàn)起來很難。對(duì)于有100個(gè)頂點(diǎn)的圖，用普通的算法，計(jì)算機(jī)需要1萬億步才能確定其是否為平面圖!因此，尋找高效的平面圖測(cè)試算法成為擺在當(dāng)時(shí)計(jì)算機(jī)科學(xué)家面前的一大難題�；魸娍寺宸蛱睾退�揚(yáng)都是富有創(chuàng)造性的人，又都善于合作共事，因此當(dāng)兩朵智慧的火花碰在一起時(shí)，就很快迸發(fā)出耀眼的光芒!在解決這個(gè)難題的過程中，霍潑克洛夫特首先提出了一種新的思路、新的算法，經(jīng)過塔揚(yáng)的反復(fù)推敲和完善，一種適于解這類問題的新的算法終于誕生了，這就是“深度優(yōu)先搜索算法”(depth-firstsearchalgorithm)。利用這種算法對(duì)圖進(jìn)行搜索時(shí)，結(jié)點(diǎn)擴(kuò)展的次序是向某一個(gè)分枝縱深推進(jìn)，到底后再回溯，這樣就能保證所有的邊在搜索過程中都經(jīng)過一次，并且只經(jīng)過一次，從而大大提高了效率。新算法的運(yùn)行時(shí)間是線性的，也就是說時(shí)間與圖的大小成正比關(guān)系，大小翻一倍，解問題所需的時(shí)間也只翻一倍。相比之下，若用庫拉托夫斯基判斷的老算法，那么當(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)把他們的研究成果寫成論文在《JournaloftheACM》上發(fā)表，引起學(xué)術(shù)界很大的轟動(dòng)。而他們創(chuàng)造的深度優(yōu)先算法則被推廣到信息檢索、國際象棋比賽程序、專家系統(tǒng)中的沖突消解策略等許多方面。在霍潑克洛夫特和塔揚(yáng)獲得圖靈獎(jiǎng)的授獎(jiǎng)儀式上，當(dāng)年的計(jì)算機(jī)象棋程序比賽的優(yōu)勝者就說，他的程序中使用了霍潑克洛夫特和塔揚(yáng)所發(fā)明的深度優(yōu)先搜索算法，這是他的程序所以能出奇制勝的關(guān)鍵。

　　在取得輝煌成功之后，霍潑克洛夫特和塔揚(yáng)并不滿足，他們致力于開發(fā)效率更高的算法。不久，他們又提出了一種新的數(shù)據(jù)結(jié)構(gòu)叫“雙堆棧疊”（pileoftwinstacks），這種新的數(shù)據(jù)結(jié)構(gòu)被深度優(yōu)先搜索算法的優(yōu)點(diǎn)更加發(fā)揚(yáng)光大。塔揚(yáng)的一個(gè)學(xué)生用這種新的數(shù)據(jù)結(jié)構(gòu)和算法編寫了一個(gè)Algolw程序，只有250行，在IBM370/168上測(cè)試有8000個(gè)結(jié)點(diǎn)的圖的平面性只用了8秒鐘。

　　霍潑克洛夫特除了和塔揚(yáng)合作取得上述成果外，在數(shù)據(jù)結(jié)構(gòu)和算法方面還有其他一系列創(chuàng)造。比如常用于索引組織的著名數(shù)據(jù)結(jié)構(gòu)B樹(B-tree)是一種平衡的多分樹，由于對(duì)查找、插入、刪除等操作能始終保持動(dòng)態(tài)平衡，具有高效的特性。霍潑克洛夫特在對(duì)B樹進(jìn)行深入研究以后，為了進(jìn)一步提高其操作效率和空間利用率，提出了它的一種變形叫2-3樹，這種樹的每個(gè)結(jié)點(diǎn)有2個(gè)鍵，每個(gè)鍵都有2-3個(gè)兒子。

　　《計(jì)算機(jī)算法的設(shè)計(jì)與分析》

　　《數(shù)據(jù)結(jié)構(gòu)和算法》

　　《自動(dòng)機(jī)理論，語言和計(jì)算的導(dǎo)論》

　　《計(jì)算機(jī)科學(xué)：成就與機(jī)遇》

　　書名：《形式語言及其與自動(dòng)機(jī)的關(guān)系》

　　作者：(美)霍普克羅夫特(J.E.Hopcroft),(美)厄爾曼(J.D.Ullman)著

　　價(jià)格：RMB1.05

　　發(fā)行地：北京

　　出版社：科學(xué)出版社

　　出版時(shí)間：1979年

　　頁數(shù)：316頁

　　開本：19cm

　　 圖靈獎(jiǎng)

　　圖靈獎(jiǎng)，是國際計(jì)算機(jī)協(xié)會(huì)（ACM）于1966年設(shè)立的，又叫“A.M.圖靈獎(jiǎng)”，專門獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人。其名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭·圖靈，這個(gè)獎(jiǎng)設(shè)立目的之一是紀(jì)念這位科學(xué)家。獲獎(jiǎng)?wù)叩呢暙I(xiàn)必須是在計(jì)算機(jī)領(lǐng)域具有持久而重大的技術(shù)先進(jìn)性的。大多數(shù)獲獎(jiǎng)?wù)呤怯?jì)算機(jī)科學(xué)家。

　　圖靈獎(jiǎng)是計(jì)算機(jī)界最負(fù)盛名的獎(jiǎng)項(xiàng)，有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱。圖靈獎(jiǎng)對(duì)獲獎(jiǎng)?wù)叩囊�求極高，評(píng)獎(jiǎng)程序也極嚴(yán)，一般每年只獎(jiǎng)勵(lì)一名計(jì)算機(jī)科學(xué)家，只有極少數(shù)年度有兩名以上在同一方向上做出貢獻(xiàn)的科學(xué)家同時(shí)獲獎(jiǎng)。目前圖靈獎(jiǎng)由英特爾公司贊助，獎(jiǎng)金為100,000美元。

　　每年，美國計(jì)算機(jī)協(xié)會(huì)將要求提名人推薦本年度的圖靈獎(jiǎng)候選人，并附加一份200到500字的文章，說明被提名者為什么應(yīng)獲此獎(jiǎng)。任何人都可成為提名人。美國計(jì)算機(jī)協(xié)會(huì)將組成評(píng)選委員會(huì)對(duì)被提名者進(jìn)行嚴(yán)格的評(píng)審，并最終確定當(dāng)年的獲獎(jiǎng)?wù)摺?

　　截止至2005年，獲此殊榮的華人僅有一位，他是2000年圖靈獎(jiǎng)得主姚期智。

　　圖靈獎(jiǎng)對(duì)獲獎(jiǎng)?wù)叩囊�求極高，評(píng)獎(jiǎng)程序極嚴(yán)，一般每年只獎(jiǎng)勵(lì)一名計(jì)算機(jī)科學(xué)家，只有極少數(shù)年度有兩名在同一方向上做出貢獻(xiàn)的科學(xué)家同時(shí)獲獎(jiǎng)。因此，盡管“圖靈”的獎(jiǎng)金數(shù)額不算高，但它卻是計(jì)算機(jī)界最負(fù)盛名的獎(jiǎng)項(xiàng)，有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱。