1964年，塔揚(yáng)參加一個(gè)中學(xué)生科學(xué)夏令營，第一次接觸計(jì)算機(jī)，立即被神奇的計(jì)算機(jī)所吸引。因此，當(dāng)他上加州理工學(xué)院時(shí)，雖然學(xué)的專業(yè)是數(shù)學(xué)，但同時(shí)還輔修了當(dāng)時(shí)學(xué)校開設(shè)的所有有關(guān)計(jì)算機(jī)的課程。1969年他取得學(xué)士學(xué)位以后，進(jìn)入斯坦福大學(xué)研究生院，師從著名的計(jì)算機(jī)科學(xué)家、后來在1974年榮獲圖靈獎(jiǎng)的克努特。1970 年，在克努特的有意安排下，他與到斯坦福來度學(xué)術(shù)假的康乃爾大學(xué)教師霍潑克洛夫特在一個(gè)辦公室開始了對(duì)圖論算法的共同研究。他們的這個(gè)課題實(shí)際上是在有 “人工智能之父”之稱的麥卡錫(J.McCarthy)的建議下進(jìn)行的。當(dāng)時(shí)塔揚(yáng)正選修麥卡錫開設(shè)的“符號(hào)處理”(Symbolicprocessing)課程，學(xué)習(xí)由麥卡錫開發(fā)的第一個(gè)人工智能語言Lip。作為作業(yè)，麥卡錫讓學(xué)生編寫程序以驗(yàn)證給定的圖是否是平面的，并建議學(xué)生們?cè)诔绦蛑惺褂脦炖�托夫斯基條件。塔揚(yáng)雖然一開始就意識(shí)到這樣得出的算法效率太低，考慮“另起爐灶”，但不知從何入手。這時(shí)霍潑克洛夫特提出的新思路、新算法啟發(fā)了他，他仔細(xì)考慮了它，并力圖使霍潑克洛夫特的算法中的原則更加嚴(yán)密、更加完善，終于使深度優(yōu)先搜索算法完美實(shí)現(xiàn)，取得成功。

　　1992年，塔揚(yáng)以平面圖測(cè)試的高效算法為題完成了博士論文，以優(yōu)異成績通過 論文答辯取得博士學(xué)位，這時(shí)離他取得碩士學(xué)位剛剛一年。學(xué)成以后，塔揚(yáng)先是跟隨霍潑克洛夫特去了康乃爾大學(xué)，以后又先后在加州大學(xué)伯克利分校、母校斯坦福大學(xué)以及貝爾實(shí)驗(yàn)室工作過，其主要興趣和研究方向仍是和生產(chǎn)、生活有密切聯(lián)系的一些算法問題和發(fā)現(xiàn)新的數(shù)據(jù)結(jié)構(gòu)。塔揚(yáng)到康乃爾大學(xué)后研究和解決的第一個(gè)問題是所謂“合并-搜索問題”。這也是圖論算法中的一個(gè)問題。在許多圖論算法中，要將圖的結(jié)點(diǎn)分成若干不同的組，叫做“分區(qū)”(Partition)。在算法過程中，不同的分區(qū)有時(shí)需要合并成較大的分區(qū)，這是合并搜索問題中的“合并”操作。算法中也經(jīng)常需要判斷兩個(gè)結(jié)點(diǎn)是否屬于同一分區(qū)，這是合并搜索問題中的“搜索”操作。為了提高效率，搜索操作應(yīng)盡可能地編短搜索路徑，這叫“路徑壓縮”(Pathcompression)。這個(gè)問題看似簡單，其實(shí)不然，包括一些知名學(xué)者在內(nèi)的人在研究和分析這個(gè)問題的時(shí)候都犯了這樣那樣的錯(cuò)誤。塔揚(yáng)深入研究了這個(gè)問題，最后利用阿克曼函數(shù)(Ackermannfunction，這是數(shù)學(xué)家阿克曼在1928年找到的一個(gè)可計(jì)算、但不是原始遞歸的函數(shù))成功地解決并分析了“合并-搜索問題”。 在研究合并-搜索問題的過程中，塔揚(yáng)還提出了所謂“分?jǐn)偂彼惴ǖ母拍�。分�(jǐn)?amortization)這個(gè)詞是塔揚(yáng)從財(cái)會(huì)術(shù)語中借用過來的，因?yàn)樗�揚(yáng)發(fā)現(xiàn)，有時(shí)雖然單個(gè)操作可能很費(fèi)時(shí)間，但通過路徑壓縮卻可以大大減少以后查找操作所需的時(shí)間，這就是說，一個(gè)查找操作額外做的工作可以“分?jǐn)偂苯o從中受益的多個(gè)查找操作，因此從整體上看是提高了效率。分?jǐn)偟母拍顚��?duì)算法的注意力從關(guān)注單個(gè)操作的時(shí)間轉(zhuǎn)向關(guān)注整個(gè)操作的平均時(shí)間，在算法設(shè)計(jì)與分析中引起了一場(chǎng)革命。 1975年，塔揚(yáng)和他的學(xué)生在斯坦福研究對(duì)于天然氣和石油管道運(yùn)輸這類問題有很大意義的最大網(wǎng)絡(luò)流問題。這個(gè)問題由于對(duì)經(jīng)濟(jì)和交通、通信的巨大實(shí)際意義而吸引了許多學(xué)者。福特(L.Ford)和富爾克森(D.Falkerson)早在1956年就提出了解決這個(gè)問題的第一個(gè)計(jì)算機(jī)算法，但是某些情況下效率不高，甚至無法找到正確答案。十年后埃德蒙多(J.Edmcnds)和卡潑(R.Karp，1985年圖靈獎(jiǎng)獲得者)改進(jìn)了這個(gè)算法，使之有更高的效率。塔揚(yáng)發(fā)現(xiàn)，最大網(wǎng)絡(luò)流問題的關(guān)鍵不在乎算法本身而在于數(shù)據(jù)結(jié)構(gòu)。經(jīng)過艱苦探索，塔揚(yáng)和他的學(xué)生終于發(fā)明了一種稱為“動(dòng)態(tài)樹”(dynamictree)的新的數(shù)據(jù)結(jié)構(gòu)，在此基礎(chǔ)上他們開發(fā)成功了前所未有的最大網(wǎng)絡(luò)流高效算法，獲得了廣泛采用。1980年，塔揚(yáng)在貝爾實(shí)驗(yàn)室繼續(xù)研究這一課題，將他以前提出的分?jǐn)偟母拍钣糜诰W(wǎng)絡(luò)流問題，發(fā)現(xiàn)如果不集中于最壞情況，而去關(guān)注平均時(shí)間，也就是說不追求在最壞情況下的有效，而是追求在分?jǐn)偟那闆r下有效，可以使最大網(wǎng)絡(luò)流問題獲得更好的結(jié)果。循著這一方向，塔揚(yáng)和他的學(xué)生提出了“自調(diào)整”(self-adjusting)數(shù)據(jù)結(jié)構(gòu)的概念，并發(fā)明了一種有著良好特性的新的數(shù)據(jù)結(jié)構(gòu)——“八字形樹”(splaytree)。目前，在算法設(shè)計(jì)中利用塔

　　揚(yáng)提出的分?jǐn)倎硖岣咝�率已成為重要的方法之一�?0年代初，塔揚(yáng)一方面在貝爾實(shí)驗(yàn)室工作，一方面在紐約大學(xué)當(dāng)兼職教授。他和紐約大學(xué)的幾個(gè)研究生開始了一項(xiàng)新的研究——研究能夠長期保存信息的數(shù)據(jù)結(jié)構(gòu)，即利用這種數(shù)據(jù)結(jié)構(gòu)不但可以跟蹤其最近的信息，還可以跟蹤其過去的信息，塔揚(yáng)稱他們?cè)O(shè)計(jì)出來的這種數(shù)據(jù)結(jié)構(gòu)為“持久性數(shù)據(jù)結(jié)構(gòu)”(persistentdatastructure)。利用塔揚(yáng)的持久性數(shù)據(jù)結(jié)構(gòu)訪問其當(dāng)前信息的速度和通常的數(shù)據(jù)結(jié)構(gòu)幾乎一樣快，而要獲得過去的信息只需要程序付出一點(diǎn)點(diǎn)額外的代價(jià)。持久性數(shù)據(jù)結(jié)構(gòu)已經(jīng)在計(jì)算幾何和并行處理中獲得應(yīng)用，但其更重要的應(yīng)用領(lǐng)域是時(shí)態(tài)數(shù)據(jù)庫(temporaldatabase)，尤其是歷史性數(shù)據(jù)庫(historicaldatabase)。 塔揚(yáng)由于他的一系列創(chuàng)造性工作而獲得許多榮譽(yù)。除了圖靈獎(jiǎng)以外，1983年他被國際數(shù)學(xué)會(huì)IMU授予以著名數(shù)學(xué)家內(nèi)蘭林那命名的信息科學(xué)獎(jiǎng)(NeranlinnalprizeinInformationScience)，1984年美國科學(xué)院授予他研究創(chuàng)新獎(jiǎng)(NationalAcademyofScienceAwardforInitiativesinResearch)。1987年和1988年他先后當(dāng)選為美國科學(xué)院院士和美國工程院院士。

　　在接受圖靈獎(jiǎng)時(shí)，霍潑克洛夫特和塔揚(yáng)分別發(fā)表了演說，前者的演說題為“計(jì)算機(jī)科學(xué)：作為一門學(xué)科的出現(xiàn)”(Computerscience：theEmergenceofaDiscipline)，后者的演說題為“算法設(shè)計(jì)”(AlgorithmDesign)。兩人還聯(lián)合接受了記者卡倫·弗蘭克爾(KarenA.Frenkel)的采訪。兩篇演說及與記者的對(duì)話刊于《CommunicationsofACM》，1987.3.，197-222頁。頒獎(jiǎng)典禮是在德克薩斯州的達(dá)拉斯舉行的1986年秋季聯(lián)合計(jì)算機(jī)會(huì)議期間舉行的。

　　霍潑克洛夫特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í)間不長�；魸娍寺宸蛱爻蔀橹�名的計(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)生了興趣，欣然接受了普林斯頓的聘任，從而改變了他一生的道路。

　　圖靈獎(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)”之稱。