計(jì)算復(fù)雜性課件

可計(jì)算性與計(jì)算復(fù)雜性李占山1000個(gè)圖片的拼圖，如果沒(méi)有考慮把握技巧，那么對(duì)于每個(gè)圖片有正反面、左右和對(duì)錯(cuò)3種組合8種狀態(tài)，這樣我們把所有圖片拼在一起需要考慮81000種狀態(tài)（步驟）情況拼圖，這是一個(gè)驚人的數(shù)字，用計(jì)算機(jī)求解在我們的有生之年是看不到結(jié)果的。難道這個(gè)問(wèn)題就沒(méi)有結(jié)果了嗎？非也，我們?nèi)瞬皇窃谕孢@種游戲嗎？我只用了一兩天甚至更短的時(shí)間就成功了，哪有你老師說(shuō)的那么復(fù)雜？那樣不是很郁悶嗎？我拼圖成功很是快樂(lè)，為什么？拼圖游戲從拼圖游戲到解現(xiàn)實(shí)生活中的實(shí)際問(wèn)題的解決---同學(xué)，游戲不是這樣玩的！我們的課程可以使你從可郁悶性與郁悶復(fù)雜性到可快樂(lè)性與快樂(lè)復(fù)雜性的。怎么辦？分類分解問(wèn)題唄！首先把圖片都翻到相同一面，最壞時(shí)要做1000次，如果圖片字母標(biāo)號(hào)有20種，然后把它們根據(jù)字母標(biāo)號(hào)分成20子類，每一子類再根據(jù)字母正反分為2個(gè)子子類，同樣拼圖時(shí)相鄰的圖片是交錯(cuò)排列的，按照這樣的分類方法進(jìn)行拼圖看看最壞時(shí)我們需要多少個(gè)步驟？玩游戲是一門(mén)學(xué)問(wèn)呦！1000+1000+20250個(gè)狀態(tài)（步驟），這些狀態(tài)步驟完全在你的有限時(shí)間掌控之中，因此能夠在一兩天甚至更短時(shí)間內(nèi)完成拼圖任務(wù)。嗷！原來(lái)是這樣的呀！看來(lái)學(xué)好這門(mén)課會(huì)使我們從可郁悶性與郁悶復(fù)雜性到可快樂(lè)性與快樂(lè)復(fù)雜性的?。?！為了學(xué)好這門(mén)課程我們有必要介紹這門(mén)課程的本質(zhì)與定位以及一些重要?dú)v史人物，他們是？？？？？

計(jì)算學(xué)科（ComputingScience）即我們所熟悉的計(jì)算機(jī)科學(xué)與技術(shù)(ComputerScienceandTechnology)。計(jì)算學(xué)科是對(duì)描述和變換信息的算法過(guò)程，包括其理論、分析、設(shè)計(jì)、效率分析、實(shí)現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究的一門(mén)學(xué)科。它涉及計(jì)算過(guò)程的分析如可計(jì)算性、算法，研究有關(guān)計(jì)算機(jī)的各種現(xiàn)象、揭示其規(guī)律與本質(zhì)如計(jì)算機(jī)的設(shè)計(jì)和使用、可計(jì)算性硬件和軟件的實(shí)際實(shí)現(xiàn)問(wèn)題。

計(jì)算學(xué)科的基本問(wèn)題是能行與效率的問(wèn)題,即它的核心問(wèn)題是“能行”問(wèn)題(Practicability)：1)什么是（實(shí)際）可計(jì)算的？什么是（實(shí)際）不可計(jì)算的？2)如何保證計(jì)算的自動(dòng)性、有效性及正確性？

1985年春，ACM（美國(guó)計(jì)算機(jī)協(xié)會(huì)）和IEEE－CS（國(guó)際電子電氣工程師學(xué)會(huì)計(jì)算機(jī)分會(huì)）組成聯(lián)合攻關(guān)小組，開(kāi)始了對(duì)“計(jì)算作為一門(mén)學(xué)科”的存在性證明。1989年1月，該小組提交了《計(jì)算作為一門(mén)學(xué)科》（Computingasadiscipline）的報(bào)告。第一次給出了計(jì)算學(xué)科一個(gè)透徹的定義，回答了計(jì)算學(xué)科中長(zhǎng)期以來(lái)一直爭(zhēng)論的一些問(wèn)題，完成了計(jì)算學(xué)科的“存在性”證明，還提出了未來(lái)計(jì)算科學(xué)教育必須解決的二個(gè)重大問(wèn)題――整個(gè)學(xué)科核心課程詳細(xì)設(shè)計(jì)及整個(gè)學(xué)科綜述性導(dǎo)引課程的構(gòu)建。1991年，在這報(bào)告的基礎(chǔ)上提交了關(guān)于計(jì)算學(xué)科教學(xué)計(jì)劃CC1991（ComputingCurricula1991）。2001年12月，提交了最終的CC2001報(bào)告。

《計(jì)算作為一門(mén)學(xué)科》報(bào)告及CC1991、CC2001一起解決了三個(gè)重要問(wèn)題：第一個(gè)重大問(wèn)題（計(jì)算作為一門(mén)學(xué)科的存在性證明）的解決。對(duì)學(xué)科本身的發(fā)展至關(guān)重要。如果在眾多分支領(lǐng)域都取得了重大成果并已得到廣泛應(yīng)用的“計(jì)算”，連作為一門(mén)學(xué)科的地位都不清楚，那么它的發(fā)展勢(shì)必要受到很大的限制。

第二個(gè)重大問(wèn)題（整個(gè)學(xué)科核心課程詳細(xì)設(shè)計(jì)）的解決，將為高校制定計(jì)算機(jī)教學(xué)計(jì)劃奠定基礎(chǔ)。確定一個(gè)公認(rèn)的本科生應(yīng)該掌握的核心內(nèi)容，將避免教學(xué)計(jì)劃設(shè)計(jì)中的隨意性，從而為我們科學(xué)地制定教學(xué)計(jì)劃奠定基礎(chǔ)。

第三個(gè)重大問(wèn)題（整個(gè)學(xué)科綜述性導(dǎo)引課程的構(gòu)建）的解決，將使人們對(duì)整個(gè)學(xué)科的認(rèn)知科學(xué)化、系統(tǒng)化和邏輯化。如果人們對(duì)計(jì)算學(xué)科的認(rèn)知能建立在公理化的基礎(chǔ)之上，則該學(xué)科可被認(rèn)為是嚴(yán)謹(jǐn)?shù)目茖W(xué)、成熟的學(xué)科，從而有助于它的發(fā)展，并將由此而得到人們的尊重。

攻關(guān)小組的結(jié)論是：計(jì)算學(xué)科所研究的根本問(wèn)題是能行問(wèn)題（什么能被（有效地）自動(dòng)進(jìn)行）。計(jì)算學(xué)科的基本原理已納入理論、抽象和設(shè)計(jì)這3個(gè)具有科學(xué)技術(shù)方法意義的過(guò)程中。學(xué)科的各分支領(lǐng)域正是通過(guò)這3個(gè)過(guò)程來(lái)實(shí)現(xiàn)它們各自的目標(biāo)。而這3個(gè)過(guò)程要解決的都是計(jì)算過(guò)程中的“能行性”和“有效性”問(wèn)題。

與數(shù)學(xué)相比，電子技術(shù)的重要性對(duì)計(jì)算科學(xué)而言不如數(shù)學(xué)，因?yàn)閿?shù)學(xué)提供了計(jì)算科學(xué)最重要的學(xué)科思想和方法論基礎(chǔ)，而電子技術(shù)只提供了電子計(jì)算機(jī)的實(shí)現(xiàn)技術(shù)，它僅僅只是對(duì)計(jì)算科學(xué)許多思想和方法的一種當(dāng)前最現(xiàn)實(shí)、最有效的實(shí)現(xiàn)技術(shù)手段而已。當(dāng)科學(xué)技術(shù)的手段提到發(fā)展時(shí)，完全有可能有某一項(xiàng)新技術(shù)歸結(jié)為有效地取代電子技術(shù)（如光技術(shù)、生物技術(shù)等等），但計(jì)算科學(xué)的數(shù)學(xué)基礎(chǔ)可能變化不大。

從事計(jì)算科學(xué)的人都知道，計(jì)算科學(xué)中不僅許多理論是用數(shù)學(xué)描述的，而且許多技術(shù)也是用數(shù)學(xué)描述的。大多數(shù)計(jì)算科學(xué)理論不僅僅是對(duì)研究對(duì)象變化規(guī)律的陳述，而且由于能行性這一本質(zhì)的核心問(wèn)題和特點(diǎn)的作用，理論描述中常通過(guò)方法折射出技術(shù)的思想和步驟，而從理論通過(guò)方法跨越到技術(shù)則完全取決于理論的深刻認(rèn)識(shí)和理解。一個(gè)人如果看懂了以形式化方法描述的技術(shù)文獻(xiàn)，自然明白技術(shù)上應(yīng)該怎樣去做。

至于計(jì)算機(jī)技術(shù)專業(yè)的學(xué)生為何要學(xué)習(xí)數(shù)學(xué)這個(gè)問(wèn)題的答案，了解了上面所講的計(jì)算學(xué)科與數(shù)學(xué)的關(guān)系后就不言而喻了：計(jì)算機(jī)科學(xué)植根于數(shù)學(xué)，但又不同于數(shù)學(xué)，從而可計(jì)算理論的基礎(chǔ)知識(shí)就需要掌握，因?yàn)檫@能夠提高我們本身的邏輯推理能力、抽象思維能力和形式化思維能力，從而今后在學(xué)習(xí)任何一門(mén)計(jì)算機(jī)科學(xué)的專業(yè)主干課程時(shí)，都不會(huì)遇上任何思維理解上的困難。

當(dāng)前計(jì)算機(jī)科學(xué)在發(fā)展過(guò)程中面對(duì)著如下兩個(gè)問(wèn)題：

一是信息革命要求計(jì)算機(jī)科學(xué)要將計(jì)算機(jī)的應(yīng)用擴(kuò)大到包含所有的問(wèn)題領(lǐng)域和深入到每個(gè)問(wèn)題領(lǐng)域的深處而越來(lái)越細(xì)致越來(lái)越復(fù)雜；二是一旦讓計(jì)算機(jī)去解決問(wèn)題，那么計(jì)算機(jī)應(yīng)自動(dòng)地在有限和有效的時(shí)間內(nèi)得出解。前者指出計(jì)算機(jī)科學(xué)的任務(wù)就是要用計(jì)算機(jī)的硬件、外設(shè)和軟件構(gòu)成一個(gè)系統(tǒng)，使得許多不同領(lǐng)域的問(wèn)題都能在這樣的計(jì)算機(jī)系統(tǒng)中得到解決。為了完成這個(gè)任務(wù)，就必須用一種符號(hào)語(yǔ)言構(gòu)成一個(gè)包括了不同領(lǐng)域的通用模型。

計(jì)算理論就是指出構(gòu)成一個(gè)包括了不同領(lǐng)域的通用模型的思維方法，并且告訴我們?cè)鯓佑貌煌恼Z(yǔ)言（符號(hào)語(yǔ)言、圖形語(yǔ)言、邏輯語(yǔ)言等）從最簡(jiǎn)單的對(duì)象（集合）出發(fā)表示通用模型。后者指出計(jì)算機(jī)科學(xué)必須了解讓計(jì)算機(jī)去解決問(wèn)題在通用模型中的結(jié)構(gòu)，由于要求在有限和有效時(shí)間內(nèi)計(jì)算機(jī)自動(dòng)完成，那么問(wèn)題求解的方法必然是構(gòu)造性的。

(2)從計(jì)算機(jī)科學(xué)學(xué)生能力角度培養(yǎng)的看計(jì)算理論的作用。計(jì)算機(jī)出現(xiàn)的五十多年間，人們追求著和出現(xiàn)了許多計(jì)算機(jī)信息革命帶來(lái)的信息產(chǎn)品，但是信息產(chǎn)品受工業(yè)產(chǎn)品的觀念上的影響，使得計(jì)算機(jī)科學(xué)的學(xué)科發(fā)展帶來(lái)了偏差，使得整個(gè)學(xué)科的發(fā)展都是“軟件跟著硬件走”。我們不能將自己的學(xué)生培養(yǎng)成計(jì)算機(jī)系統(tǒng)的奴隸，而應(yīng)該培養(yǎng)成計(jì)算機(jī)系統(tǒng)的主人，我們的學(xué)生不能給計(jì)算機(jī)系統(tǒng)所塑造，將他們變成計(jì)算機(jī)，而是教育學(xué)生怎樣地塑造計(jì)算機(jī)系統(tǒng)。

在計(jì)算機(jī)科學(xué)知識(shí)掌握的過(guò)程中應(yīng)是“硬件跟著軟件走，軟件跟著模型走，模型跟著學(xué)科實(shí)際應(yīng)用走；學(xué)科實(shí)際應(yīng)用跟著自然走”。而最主要的培養(yǎng)環(huán)節(jié)應(yīng)該是軟件跟著模型走，模型跟著學(xué)科實(shí)際應(yīng)用走。關(guān)于學(xué)生的培養(yǎng)目標(biāo)就是要培養(yǎng)自己的學(xué)生能夠根據(jù)實(shí)際應(yīng)用問(wèn)題提出計(jì)算機(jī)應(yīng)用的模型，并用硬件和軟件資源去構(gòu)造計(jì)算機(jī)系統(tǒng)去完成模型中所提出來(lái)的工作。

首先，計(jì)算機(jī)系統(tǒng)要解決的問(wèn)題并不是個(gè)別的問(wèn)題，也并不是某個(gè)領(lǐng)域上的特殊問(wèn)題，要解決某個(gè)領(lǐng)域的所有能用計(jì)算機(jī)進(jìn)行計(jì)算的問(wèn)題，因此，關(guān)于計(jì)算機(jī)科學(xué)的思維方法必須是在足夠通用的層面上的思維方法。如果所掌握或所習(xí)慣的思維方法僅限制在是某些特殊的領(lǐng)域，那么，隨著計(jì)算機(jī)應(yīng)用的不斷擴(kuò)大和計(jì)算機(jī)信息革命的不斷擴(kuò)大，將會(huì)使得思維的方法帶有很大的局限性。當(dāng)然，最通用的層面是自然層面，然而，自然層面上的對(duì)象還不能為現(xiàn)代計(jì)算機(jī)(現(xiàn)代計(jì)算模型)所了解。因?yàn)椋覀冞x擇塑造計(jì)算機(jī)系統(tǒng)的層面既帶有最大的通用性，又能為現(xiàn)代計(jì)算機(jī)系統(tǒng)所了解的層面。在現(xiàn)代計(jì)算技術(shù)的支持下，這個(gè)層面就是符號(hào)處理層面。

其次，我們是要去塑造計(jì)算機(jī)系統(tǒng)，我們的所有思維都要立足于能“塑造”性，因此，思維的可構(gòu)造性，即在考慮構(gòu)成計(jì)算機(jī)系統(tǒng)的所有對(duì)象都必須能夠有某種方法在有限的時(shí)間內(nèi)構(gòu)造出來(lái)。因此塑造計(jì)算機(jī)系統(tǒng)的基本思維是構(gòu)造性思維。以上描述了計(jì)算理論的學(xué)科定位下面我們來(lái)看相關(guān)的歷史人物簡(jiǎn)介計(jì)算理論的開(kāi)拓者—圖靈阿蘭·圖靈，1912年6月23日出生于英國(guó)倫敦。其祖父曾獲得劍橋大學(xué)數(shù)學(xué)榮譽(yù)學(xué)位，但他父親的數(shù)學(xué)才能平平。因此，圖靈的家庭教育，對(duì)他以后在數(shù)學(xué)及計(jì)算機(jī)方面的成就并沒(méi)有多少幫助。

小時(shí)侯的圖靈生性活潑好動(dòng)，很早就表現(xiàn)出對(duì)科學(xué)的探索精神。據(jù)他母親回憶，3歲時(shí)，小圖靈就進(jìn)行了他的首次實(shí)驗(yàn)，嘗試把一個(gè)玩具木頭人的小胳膊、小腿掰下來(lái)栽到花園里，等待長(zhǎng)出更多的木頭人。到了8歲，他更開(kāi)始嘗試寫(xiě)一部科學(xué)著作，題目為《關(guān)于一種顯微鏡》。在這部很短的書(shū)中，天才兒童圖靈拼錯(cuò)了很多單詞，句法也有些問(wèn)題，但寫(xiě)得還能讓人看懂，很像那么一回事兒。在書(shū)的開(kāi)頭和結(jié)尾，他都用同一句話“首先你必須知道光是直的”作前后呼應(yīng)，但中間的內(nèi)容卻很短，短得破了科學(xué)著作的記錄。圖靈曾說(shuō):“我似乎總想從最普通的東西中弄出些名堂?！本瓦B和小朋友們玩足球，他也能放棄當(dāng)前鋒進(jìn)球這樣出風(fēng)頭的事，只喜歡在場(chǎng)外巡邊，因?yàn)檫@樣能有機(jī)會(huì)去計(jì)算球飛出邊界的角度。他的老師認(rèn)為:“圖靈的頭腦思維可以像袋鼠一樣進(jìn)行跳躍。”圖靈是個(gè)天才。他16歲就開(kāi)始研究愛(ài)因斯坦的相對(duì)論。1931年，圖靈考入劍橋大學(xué)國(guó)王學(xué)院，開(kāi)始他的數(shù)學(xué)生涯，研究量子力學(xué)、概率論和邏輯學(xué)。在校期間，圖靈還是現(xiàn)代語(yǔ)言哲學(xué)大師維特根斯坦班上最出色的學(xué)生。他對(duì)由劍橋大學(xué)的羅素和懷特海創(chuàng)立的數(shù)理邏輯很感興趣。數(shù)理邏輯的創(chuàng)建，主要是為了對(duì)付“悖論”?！般Ｕ摗?paradox)是人類思維中最狡猾的兩面派，最早起源于古希臘克里特島上有個(gè)叫愛(ài)皮梅尼特的“智者”，他說(shuō):“所有的克里特島人都說(shuō)謊”。我們可以把它簡(jiǎn)化為:“我說(shuō)的這句話是假話”。這就出現(xiàn)一種兩面都無(wú)法自圓的怪圈:如果他沒(méi)有說(shuō)謊，那他這句話是錯(cuò)的，他是在說(shuō)謊;如果他真的在說(shuō)謊，那他說(shuō)自己在說(shuō)謊是對(duì)的，所以他又沒(méi)有說(shuō)謊。羅素和懷特海把它從邏輯、集合論以及數(shù)論中驅(qū)逐出去，最后又想盡辦法歸入《數(shù)學(xué)原理》之中。

圖靈一上大學(xué)，就迷上了《數(shù)學(xué)原理》。在1931年，著名的“哥德?tīng)柖ɡ怼背霈F(xiàn)后(該定理認(rèn)為沒(méi)有一種公理系統(tǒng)可以導(dǎo)出數(shù)論中所有的真實(shí)命題，除非這種系統(tǒng)本身就有悖論)，天才的圖靈在數(shù)理邏輯大本營(yíng)的劍橋大學(xué)提出一個(gè)設(shè)想:能否有這樣一臺(tái)機(jī)器，通過(guò)某種一般的機(jī)械步驟，能在原則上一個(gè)接一個(gè)地解決所有的數(shù)學(xué)問(wèn)題。大學(xué)畢業(yè)后，圖靈去美國(guó)普林斯頓大學(xué)攻讀博士學(xué)位，還順手發(fā)明過(guò)一個(gè)解碼器。在那里，他遇見(jiàn)了馮·諾依曼，后者對(duì)他的論文擊節(jié)贊賞，并隨后由此提出了“存儲(chǔ)程序”概念。圖靈學(xué)成后又回到他的母校任教。在短短的時(shí)間里，圖靈就發(fā)表了幾篇很有份量的數(shù)學(xué)論文，為他贏得了很大的聲譽(yù)。

在劍橋，圖靈可稱得上是一個(gè)怪才，一舉一動(dòng)常常出人意料。他是個(gè)單身漢和長(zhǎng)跑運(yùn)動(dòng)員。在他的同事和學(xué)生中間，這位衣著隨便、不打領(lǐng)帶的著名教授，不善言辭，有些木訥、害羞，常咬指甲，但他更多地以自己杰出的才智贏得了人們的敬意。圖靈每天騎自行車上班，因?yàn)榛歼^(guò)敏性鼻炎，一遇到花粉，就會(huì)鼻涕不止，大打噴嚏。于是，他就常常在上班途中戴防毒面具，招搖過(guò)市，這早已成為劍橋的一大奇觀。圖靈的自行車經(jīng)常半路掉鏈子，但他就是不肯去車鋪修理。每次騎車時(shí)，他總是嘴里念念有詞，在心里細(xì)細(xì)計(jì)算，這鏈條也怪，總是轉(zhuǎn)到一定的圈數(shù)就滑落了，而圖靈竟然能夠做到在鏈條下滑前一剎那停車，讓旁觀者佩服不已，以為圖靈在玩雜技。后來(lái)圖靈又居然在腳踏車旁裝了一個(gè)小巧的機(jī)械記數(shù)器，到圈數(shù)時(shí)就停，歇口氣換換腦子，再重新運(yùn)動(dòng)起來(lái)。

1936年，圖靈向倫敦權(quán)威的數(shù)學(xué)雜志投了一篇論文，題為《論數(shù)字計(jì)算在決斷難題中的應(yīng)用》。在這篇開(kāi)創(chuàng)性的論文中，圖靈給“可計(jì)算性”下了一個(gè)嚴(yán)格的數(shù)學(xué)定義，并提出著名的“圖靈機(jī)”(TuringMachine)的設(shè)想?！皥D靈機(jī)”不是一種具體的機(jī)器，而是一種思想模型，可制造一種十分簡(jiǎn)單但運(yùn)算能力極強(qiáng)的計(jì)算機(jī)裝置，用來(lái)計(jì)算所有能想像得到的可計(jì)算函數(shù)。裝置由一個(gè)控制器和一根假設(shè)兩端無(wú)界的工作帶(起存儲(chǔ)器的作用)組成。工作帶被劃分為大小相同的方格，每一格上可書(shū)寫(xiě)一個(gè)給定字母表上的符號(hào)。控制器可以在帶上左右移動(dòng)，它帶有一個(gè)讀寫(xiě)頭，可讀出控制器所訪問(wèn)的格子上的符號(hào)，也能改寫(xiě)或抹去這一符號(hào)，最后便會(huì)得出一個(gè)你期待的結(jié)果。外行人看了會(huì)墜入云里霧里，而內(nèi)行人則稱它是“闡明現(xiàn)代電腦原理的開(kāi)山之作”，并冠以“理想計(jì)算機(jī)”的名稱。這篇論文在紙上談了一把兵，創(chuàng)造出一個(gè)“圖靈機(jī)”來(lái)。但現(xiàn)代通用電腦確實(shí)是用相應(yīng)的程序來(lái)完成任何設(shè)定好的任務(wù)。這一理論奠定了整個(gè)現(xiàn)代計(jì)算機(jī)的理論基礎(chǔ)?！皥D靈機(jī)”更在電腦史上與“馮·諾依曼機(jī)”齊名，被永遠(yuǎn)載入計(jì)算機(jī)的發(fā)展史中。1931年，年輕的法國(guó)數(shù)學(xué)家赫爾布蘭德（JacquesHerbrand，1908～1931）對(duì)遞歸函數(shù)進(jìn)行了研究，并給著名邏輯學(xué)家哥德?tīng)枺↘urtG?del，1906～1978）寫(xiě)信敘述了自己的研究結(jié)果。哥德?tīng)柈?dāng)時(shí)正處于自己一生中最重大的成果—哥德?tīng)柌煌耆远ɡ淼难芯繒r(shí)期，他沒(méi)有仔細(xì)看赫爾布蘭德的來(lái)信內(nèi)容，因此沒(méi)有立即對(duì)赫爾布蘭德的工作做出回應(yīng)。那一年的夏天，年僅23歲的赫爾布蘭德在攀登阿爾卑斯山時(shí)不幸遇難，他的工作因此被暫時(shí)埋沒(méi)了。

與赫爾布蘭德的研究差不多同時(shí)，1931年秋天，普林斯頓大學(xué)的美國(guó)邏輯學(xué)家丘奇（AlonzoChurch，1903～1995）也在積極從事邏輯及算法的研究，并且發(fā)展出了一種新的邏輯體系。丘奇在普林斯頓開(kāi)了一門(mén)邏輯課，他讓自己的兩個(gè)學(xué)生克林（StephenKleene，1909～1994）與羅瑟（JohnRosser，1907～1989）對(duì)這一體系做細(xì)致的研究。兩個(gè)學(xué)生都是一流好手，他們的研究很快就有了結(jié)果，但這結(jié)果大大出乎丘奇的意料。他們發(fā)現(xiàn)丘奇的那套體系竟然是自相矛盾的！命運(yùn)似乎只有一個(gè)：放棄。幸運(yùn)的是，丘奇的那套體系中有一個(gè)組成部分是自洽的，因此可以保留下來(lái)，這部分叫做蘭姆達(dá)運(yùn)算（λ－calculus）。這種蘭姆達(dá)運(yùn)算可以用來(lái)定義函數(shù)，而所有用蘭姆達(dá)運(yùn)算定義的函數(shù)都是可以有效計(jì)算的。在對(duì)蘭姆達(dá)運(yùn)算做了研究之后，丘奇提出了一個(gè)大膽的猜測(cè)，他猜測(cè)所有可以有效計(jì)算的函數(shù)都可以用蘭姆達(dá)運(yùn)算來(lái)定義。于是克林開(kāi)始進(jìn)行研究，結(jié)果克林和丘奇得到一類可計(jì)算的函數(shù)，他們稱之為A可定義函數(shù)。

1934年春天，哥德?tīng)栐谄樟炙诡D大學(xué)做了一系列講演。丘奇向到普林斯頓大學(xué)訪問(wèn)的哥德?tīng)柦榻B了他的猜測(cè)，哥德?tīng)枀s不以為然。丘奇不服氣，請(qǐng)哥德?tīng)柦o出一個(gè)他認(rèn)為合適的描述。一兩個(gè)月后，哥德?tīng)柧徒o出了一種完全不同的描述，這種描述的基礎(chǔ)正是3年前赫爾布蘭德在給他的信中敘述的結(jié)果。哥德?tīng)枌?duì)這一結(jié)果進(jìn)行了完善，這一結(jié)果被人們稱為赫爾布蘭德－哥德?tīng)栠f歸函數(shù)。與此同時(shí)，丘奇和克林在1936年分別發(fā)表論文，證明A可定義函數(shù)類正好就是一般遞歸函數(shù)類。有了這個(gè)有力的證據(jù)，丘奇于是公開(kāi)發(fā)表他的"論點(diǎn)"。這樣，丘奇與哥德?tīng)柛髯越o出了一種體系，描述可以有效計(jì)算的函數(shù)。丘奇與克林很快證明，這兩種看上去完全不同的描述方式實(shí)際上是彼此等價(jià)的。

兩位著名邏輯學(xué)家的工作殊途同歸，大大增強(qiáng)了丘奇的信心。他相信人們已經(jīng)找到了可以有效計(jì)算的函數(shù)的普遍定義。但哥德?tīng)柤捌渌恍┤藢?duì)此卻仍然懷有疑慮。最終打消這種疑慮的是英國(guó)數(shù)學(xué)家圖靈（AlanTuring，1912～1954）。

1937年圖靈證明了用圖靈機(jī)可計(jì)算的函數(shù)類與可定義函數(shù)類是一致的，當(dāng)然，也就和一般遞歸函數(shù)類相重合。這樣一來(lái)，丘奇的論點(diǎn)與圖林的論點(diǎn)就是一回事。當(dāng)時(shí)許多人對(duì)于丘奇的論點(diǎn)表示懷疑，由于圖林的思想表述得如此清楚，從而消除了許多人的疑慮，哥德?tīng)柧褪瞧渲幸晃?。從這時(shí)起大家對(duì)于丘奇-圖靈論點(diǎn)一般都抱支持的態(tài)度了。數(shù)理邏輯學(xué)家歌德?tīng)?/p>

1947年美國(guó)數(shù)學(xué)家波斯特（EmilPost，1897～1954）找到了第一個(gè)邏輯領(lǐng)域以外的不可判定命題。波斯特是一位有著深刻洞察力的邏輯學(xué)家，7歲時(shí)隨父母從波蘭移民到美國(guó)，是美國(guó)邏輯學(xué)的先驅(qū)之一。他10年前就得到了與哥德?tīng)柌煌耆远ɡ硐嗨频慕Y(jié)果，由于想對(duì)結(jié)果作更全面的分析而沒(méi)有及時(shí)發(fā)表。他也是最早意識(shí)到希爾伯特第十問(wèn)題可能會(huì)有否定答案的數(shù)學(xué)家之一。1944年，他在一篇文章中明確提出希爾伯特第十問(wèn)題“期待一個(gè)不可解性證明”。當(dāng)時(shí)波斯特在紐約市立大學(xué)任教，他的這一觀點(diǎn)深深打動(dòng)了一位學(xué)生，使后者走上了畢生鉆研希爾伯特第十問(wèn)題的征途。這位學(xué)生名叫戴維斯（MartinDavis，1928～），是解決希爾伯特第十問(wèn)題的關(guān)鍵人物。圖靈獎(jiǎng)與計(jì)算理論圖靈獎(jiǎng)是由ACM于1966年首次設(shè)立的獎(jiǎng)項(xiàng),它是為了紀(jì)念“計(jì)算機(jī)科學(xué)之父”圖靈而設(shè)立的,專門(mén)獎(jiǎng)勵(lì)那些在計(jì)算機(jī)科學(xué)研究中做出創(chuàng)造性貢獻(xiàn)、推動(dòng)了計(jì)算機(jī)科學(xué)技術(shù)發(fā)展的杰出科學(xué)家。雖然沒(méi)有明確規(guī)定，但從實(shí)際執(zhí)行過(guò)程來(lái)看，圖靈獎(jiǎng)偏重于在計(jì)算機(jī)科學(xué)理論和軟件方面作出貢獻(xiàn)的科學(xué)家。獎(jiǎng)金金額不算太高，設(shè)獎(jiǎng)初期為2萬(wàn)美元，1989年增至2萬(wàn)5千美元，獎(jiǎng)金通常由計(jì)算機(jī)界的一些大企業(yè)提供（通過(guò)與ACM簽定協(xié)議）。由于圖靈獎(jiǎng)對(duì)獲獎(jiǎng)?wù)咭髽O高，評(píng)獎(jiǎng)程序又極嚴(yán)，一般每年只獎(jiǎng)勵(lì)一名計(jì)算機(jī)科學(xué)家，只有極少數(shù)年度有兩名合作者或在同一方向作出貢獻(xiàn)的科學(xué)家共享此獎(jiǎng)。因此它是計(jì)算機(jī)界最負(fù)盛名、最崇高的一個(gè)獎(jiǎng)項(xiàng)，有‘計(jì)算機(jī)界的諾貝爾獎(jiǎng)“之稱。從1966年到2000年共有41位科學(xué)家獲此殊榮，在這些學(xué)者中從事計(jì)算復(fù)雜性理論研究的有11人，幾乎占四分之一。他們是？？？？1976年圖靈獎(jiǎng)獲得者拉賓和斯科特1976年的圖靈獎(jiǎng)由當(dāng)時(shí)在以色列希伯萊大學(xué)的教授拉賓和英國(guó)牛津大學(xué)的數(shù)理邏輯教授斯科特共同獲得。他們是師兄弟，兩人在50年代中期先后師從于著名的數(shù)理邏輯與計(jì)算機(jī)科學(xué)家丘奇（他對(duì)可計(jì)算性理論做出了實(shí)質(zhì)性貢獻(xiàn)，如判定問(wèn)題的解、演算的發(fā)明，90歲還在發(fā)表論文，圖靈也是他的學(xué)生），并在有限自動(dòng)機(jī)及其判定問(wèn)題的研究中進(jìn)行合作，奠定了非確定性有限自動(dòng)機(jī)的理論基礎(chǔ)，之后，他們的研究方向不盡相同，拉賓側(cè)重于計(jì)算理論，而斯科特側(cè)重于邏輯學(xué)在計(jì)算機(jī)科學(xué)中的應(yīng)用，在各自的領(lǐng)域中又分別獲得重大成果，做出了創(chuàng)造性貢獻(xiàn)。計(jì)算機(jī)科學(xué)家、數(shù)理邏輯學(xué)家丘奇拉賓是1931年出生于德國(guó)的布雷斯勞的猶太人，1948年以色列建國(guó)以后成為以色列公民，20世紀(jì)50年代拉賓博士畢業(yè)于普林斯頓大學(xué)，使拉賓成名的是IBM研究中心1957年向他和師弟斯科特提供的允許他們做自己感興趣的工作。于是他們二人聯(lián)手研究圖靈機(jī)----有限狀態(tài)自動(dòng)機(jī)。他們定義了一種新的、“非確定性”行為的有限狀態(tài)自動(dòng)機(jī)(NDFSA)，這種機(jī)器在讀去到一定的輸入后，有一個(gè)可以進(jìn)入的可能的新的狀態(tài)的‘菜單’可供選擇，這樣對(duì)給定的輸入計(jì)算便不單一了，每個(gè)選擇代表一種可能的計(jì)算。拉賓和斯科特將圖靈的有限狀態(tài)自動(dòng)機(jī)從確定性一種擴(kuò)展到非確定的另一種形式，極大地推動(dòng)了有限狀態(tài)自動(dòng)機(jī)理論的發(fā)展，雖然非確定性有限狀態(tài)自動(dòng)機(jī)的能力并不比確定性的有任何增加（拉賓和斯科特已經(jīng)證明他們等價(jià)），但是它可以簡(jiǎn)化機(jī)器描述和加快解題速度。后來(lái)的時(shí)間證明，非確定性有限狀態(tài)自動(dòng)機(jī)在機(jī)器翻譯、文獻(xiàn)檢索和字處理程序等應(yīng)用中都起到了重要作用。他們的研究結(jié)果發(fā)表于2年后的1959年IBM雜志上，題目為“有限自動(dòng)機(jī)及其判定問(wèn)題”。1958年夏天拉賓又來(lái)到IBM，當(dāng)時(shí)“人工智能之父”麥卡錫（1971年圖靈獎(jiǎng)獲得者）正在那里研究往巴克斯（1977年圖靈獎(jiǎng)獲得者）發(fā)明的FORTRAN語(yǔ)言中加入表處理功能，他給拉賓出了一道難題：設(shè)計(jì)一種口令即使口令被敵方竊取，也無(wú)法進(jìn)入系統(tǒng)。拉賓經(jīng)過(guò)艱苦探索，終于利用馮諾伊曼開(kāi)發(fā)的一個(gè)單向函數(shù)解決了這個(gè)問(wèn)題。正是這個(gè)問(wèn)題促使拉賓進(jìn)一步研究計(jì)算任務(wù)的最小計(jì)算量這一一般性問(wèn)題，也就是計(jì)算的固有難度問(wèn)題，從而使拉賓成為最早研究計(jì)算復(fù)雜性問(wèn)題的先驅(qū)之一。他的研究結(jié)果“計(jì)算速度和遞歸集合的分類”與“函數(shù)的計(jì)算難度和遞歸集合的偏序”分別于1959和1960年在耶路撒冷發(fā)表。論文中雖然沒(méi)有用“計(jì)算復(fù)雜性‘這個(gè)名詞而用了”計(jì)算速度“和”計(jì)算難度“，但學(xué)術(shù)界公認(rèn)這兩篇論文是研究計(jì)算復(fù)雜性的最早、最權(quán)威的論文中的兩篇，對(duì)1964年正式提出”計(jì)算復(fù)雜性“這一術(shù)語(yǔ)的哈特馬尼斯和斯特恩斯（這2人是1993年圖靈獎(jiǎng)獲得者，后面介紹）以及計(jì)算復(fù)雜性理論的另一奠基人布盧姆（1995年圖靈獎(jiǎng)獲得者，后面介紹）都產(chǎn)生了深刻影響。其中布盧姆正是聽(tīng)到了拉賓的有關(guān)演講才開(kāi)始研究計(jì)算復(fù)雜性并完成博士論文的。斯科特比拉賓小一歲，1932年出生于加利福尼亞，在加州大學(xué)伯克利分校獲得學(xué)士學(xué)位后，進(jìn)入普林斯頓大學(xué)研究生院深造，與拉賓一起師從于阿隆索丘齊。丘齊對(duì)學(xué)生要求很嚴(yán)，布置的問(wèn)題也很難，斯科特開(kāi)始時(shí)難以適應(yīng)，精神很緊張，經(jīng)常夜里作惡夢(mèng)。但經(jīng)過(guò)努力，終于可以從容應(yīng)付。1957年他與師兄拉賓一起完成了對(duì)圖靈機(jī)的研究，提出了非確定性有限狀態(tài)自動(dòng)機(jī)的理論以后，在1958年取得博士學(xué)位。之后他先后在芝加哥大學(xué)、加州大學(xué)伯克利分校、斯坦福大學(xué)、普林斯頓大學(xué)和牛津大學(xué)等國(guó)際知名高等學(xué)府任教。1981年被卡內(nèi)基梅隆大學(xué)聘為計(jì)算機(jī)科學(xué)、數(shù)理邏輯和哲學(xué)教授。斯科特的主要興趣和研究方向是邏輯學(xué)，包括集合論、模型論、自動(dòng)機(jī)理論、非經(jīng)典邏輯中的模態(tài)邏輯和直覺(jué)主義邏輯。斯科特的最大貢獻(xiàn)是他與斯特雷奇合作，20世紀(jì)60年代提出了程序設(shè)計(jì)語(yǔ)言的“標(biāo)志語(yǔ)義模型”為標(biāo)志語(yǔ)義學(xué)奠定了堅(jiān)實(shí)的基礎(chǔ)。1978年圖靈獎(jiǎng)獲得者弗洛伊德歷屆圖靈獎(jiǎng)得主基本上都有高學(xué)歷、高學(xué)位，絕大多數(shù)都有博士學(xué)位，但事情總有例外，1978年圖靈獎(jiǎng)得主、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授弗洛伊德就是一位“自學(xué)成才的計(jì)算機(jī)科學(xué)家”。說(shuō)他自學(xué)成才并不是說(shuō)他沒(méi)有接受過(guò)高等教育，他是芝加哥大學(xué)的畢業(yè)生，但學(xué)的是文學(xué)，1953年獲得文學(xué)學(xué)位，由于當(dāng)時(shí)經(jīng)濟(jì)不景氣，成為西屋電氣公司一名計(jì)算機(jī)操作員，他不懂計(jì)算機(jī)，但是個(gè)有心人，受過(guò)良好高等教育很快對(duì)計(jì)算機(jī)產(chǎn)生了興趣開(kāi)始學(xué)習(xí)相關(guān)知識(shí)，1956年成為程序員，1965年被卡內(nèi)基-梅隆大學(xué)聘為副教授，1970年聘為教授。大家現(xiàn)在熟知的優(yōu)先文法，界限上下文文法都是他20世紀(jì)60年代提出的，優(yōu)先文法解決了自底向上的語(yǔ)法分析中的首要問(wèn)題：如何找到”句柄“，也就是當(dāng)前需要?dú)w約的符號(hào)串。1964年與威廉姆斯共同發(fā)明了堆排序算法HEAPSORT，這是與英國(guó)學(xué)者霍爾（1980年圖靈獎(jiǎng)獲得者）發(fā)明的QUICKSORT齊名的高效排序算法之一。1982年圖靈獎(jiǎng)獲得者庫(kù)克NP完全性理論的奠基人庫(kù)克1939年出生于紐約州的布法羅。1957年中學(xué)畢業(yè)后，到密歇根大學(xué)學(xué)科學(xué)工程，一年級(jí)時(shí)選擇了一門(mén)新開(kāi)設(shè)的課程—程序設(shè)計(jì)，作為作業(yè)，他編了一個(gè)ALGOL程序驗(yàn)證歌德巴赫猜想，由此他對(duì)計(jì)算機(jī)科學(xué)發(fā)生了興趣。1961年庫(kù)克獲得學(xué)士學(xué)位以后，轉(zhuǎn)入哈佛大學(xué)研究生院深造，第二年就取得了理科碩士學(xué)位，他接著攻讀了數(shù)學(xué)博士學(xué)位，原先打算研究代數(shù)學(xué)。然而這時(shí)他遇到了一些教師，對(duì)他產(chǎn)生了很大的影響，改變了他的興趣和方向。首先是哈佛研究生院對(duì)新興學(xué)科十分重視，雖然當(dāng)時(shí)計(jì)算復(fù)雜性理論這一學(xué)科還處于萌芽和初創(chuàng)時(shí)期，他們就邀請(qǐng)了這方面的一些先驅(qū)與奠基人，包括拉賓、哈特馬尼斯和斯特恩斯，由于對(duì)拉賓等人講學(xué)或做報(bào)告內(nèi)容產(chǎn)生興趣，庫(kù)克他們的研究和探索的問(wèn)題發(fā)生了極大的興趣，從而把自己的研究定在這個(gè)方向。博士畢業(yè)后當(dāng)時(shí)美籍華人數(shù)學(xué)家王浩提出的圖靈機(jī)的一種變形叫B機(jī)器也引起了他的興趣。王浩指出，甚至在無(wú)限的時(shí)間里，要想證明確定謂詞演算中的某個(gè)公式是否可滿足，在計(jì)算上都是不可能的，因此王浩從復(fù)雜性角度去研究，他的工作給了庫(kù)克極大的啟發(fā)，庫(kù)克從比較單純和簡(jiǎn)單的命題演算公式的自動(dòng)證明入手研究計(jì)算復(fù)雜性，果然成功了，１９７１年發(fā)表了“定理證明過(guò)程的復(fù)雜性”。在這篇論文中庫(kù)克首次明確提出了NP完全問(wèn)題，并奠定了NP完全性理論的基礎(chǔ)。以后我們將講授這些內(nèi)容。1985年圖靈獎(jiǎng)獲得者卡普發(fā)明“分枝限界法”的三棲學(xué)者卡普是美國(guó)加州大學(xué)計(jì)算機(jī)、數(shù)學(xué)和工業(yè)工程三個(gè)系的教授，他被授予圖靈獎(jiǎng)也是因?yàn)樵谒惴ㄔO(shè)計(jì)與分析、計(jì)算復(fù)雜性理論等方面的創(chuàng)造性貢獻(xiàn)，生于１９３５年的卡普興趣廣泛聰明過(guò)人，在哈佛大學(xué)時(shí)文理兼修，1955年先獲得文學(xué)學(xué)士學(xué)位，第2年又獲得理科碩士學(xué)位，之后進(jìn)入哈佛計(jì)算機(jī)實(shí)驗(yàn)室攻讀博士學(xué)位，1959年獲得數(shù)學(xué)博士學(xué)位后進(jìn)入IBM。

當(dāng)時(shí)，正是計(jì)算機(jī)科學(xué)的創(chuàng)立時(shí)期，高級(jí)語(yǔ)言剛剛誕生不久，計(jì)算機(jī)應(yīng)用開(kāi)始被社會(huì)所重視并逐漸走向普及。有關(guān)數(shù)據(jù)結(jié)構(gòu)、算法、計(jì)算復(fù)雜性等課題吸引著眾多學(xué)者的注意。IBM作為美國(guó)乃至世界最大的計(jì)算機(jī)廠商，理所當(dāng)然成為這些研究問(wèn)題的中心之一，集中了大批最優(yōu)秀的研究人員，在那里卡普主要研究了路徑問(wèn)題、背包問(wèn)題、覆蓋問(wèn)題、匹配問(wèn)題，調(diào)度問(wèn)題等，但這些問(wèn)題都存在組合爆炸問(wèn)題。２０世紀(jì)６０年代初卡普仔細(xì)研究了路徑問(wèn)題中的旅行商問(wèn)題，和同事海爾特經(jīng)過(guò)反復(fù)研究，終于提出了一種稱為”分枝限界法“的新方法。該方法要點(diǎn)是：對(duì)解集合反復(fù)進(jìn)行分枝，每次分枝時(shí)都對(duì)所得的子集計(jì)算最優(yōu)解的界，如果對(duì)某個(gè)子集求得的界不優(yōu)于已知的允許解，則拋棄這個(gè)子集不再分枝。否則繼續(xù)分枝以探索更好的解。１９６８年卡普來(lái)到加州大學(xué)伯克利分校。這里是計(jì)算機(jī)科學(xué)理論的又一個(gè)研究中心，庫(kù)克、布盧姆（１９８５年圖靈獎(jiǎng)獲得者）等一批知名學(xué)者當(dāng)時(shí)都在那里，學(xué)術(shù)氣氛十分濃厚。布盧姆是計(jì)算復(fù)雜性的主要奠基人之一，庫(kù)克則與1971年最早提出”NP完全性“問(wèn)題，在這樣環(huán)境下，卡普對(duì)計(jì)算復(fù)雜性問(wèn)題的研究日益深入。１９７２年卡普發(fā)表的論文“組合問(wèn)題中的可歸約性”發(fā)展和加強(qiáng)了由庫(kù)克提出的”NP完全性”理論。尤其是庫(kù)克僅證明了命題演算的可滿足性問(wèn)題是NP完全的，而卡普則證明了從組合優(yōu)化中引出的大多數(shù)經(jīng)典問(wèn)題，包括背包問(wèn)題、覆蓋問(wèn)題、匹配問(wèn)題、路徑問(wèn)題、調(diào)度問(wèn)題等，都是NP完全問(wèn)題：只要證明其中任何一個(gè)問(wèn)題是屬于P類的，就可以解決計(jì)算復(fù)雜性理論中的最大的一個(gè)難題P=?NP這是卡普論文的主要貢獻(xiàn)和意義。1986年圖靈獎(jiǎng)獲得者霍普克洛夫斯特和陶爾揚(yáng)霍普克洛夫斯特１９３９年出生于西雅圖，１９６１年西雅圖大學(xué)畢業(yè)后進(jìn)入斯坦福大學(xué)研究生院深造，博士畢業(yè)后到普林斯頓大學(xué)工作。他成為著名的計(jì)算機(jī)科學(xué)家起源于一個(gè)十分偶然的機(jī)會(huì)。他學(xué)習(xí)的是電器工程專業(yè)，對(duì)計(jì)算機(jī)科學(xué)原本沒(méi)有多少知識(shí)。原打算到一所西海岸大學(xué)教授電器工程方面的課程。畢業(yè)前夕，有一次路過(guò)導(dǎo)師的辦公室門(mén)口，當(dāng)時(shí)普林斯頓大學(xué)的麥克盧斯基正為籌建”數(shù)字需要實(shí)驗(yàn)室“給霍普克洛夫斯特的老師打電話讓推薦博士，他的老師一眼瞥見(jiàn)了他，覺(jué)得勤奮好學(xué)、悟性又高的得意門(mén)生正是值得推薦的人才，就把他叫進(jìn)來(lái)并把話筒遞給他，經(jīng)過(guò)交談與考察，他接受了普林斯頓大學(xué)的邀請(qǐng)，從而改變了一生的道路。

年輕的霍普克洛夫斯特到普林斯頓之后接受的第1個(gè)任務(wù)是開(kāi)設(shè)一門(mén)新課程：自動(dòng)機(jī)理論，這對(duì)他來(lái)說(shuō)是富有挑戰(zhàn)性的，因?yàn)樗安](méi)有接觸過(guò)這個(gè)課程。面對(duì)挑戰(zhàn)，他虛心地請(qǐng)麥克盧斯基推薦關(guān)有參考資料。由于當(dāng)時(shí)沒(méi)有任何一所學(xué)校開(kāi)設(shè)過(guò)自動(dòng)機(jī)理論的課程，也沒(méi)有一本書(shū)籍，到底應(yīng)該講什么心里也沒(méi)有底。通過(guò)大量翻閱文獻(xiàn)，他開(kāi)設(shè)了包括圖靈、麥柯勞赫和皮孜、拉賓和斯科特、巴克斯和諾爾、哈特馬尼斯和斯特恩斯以及喬姆斯基所寫(xiě)的6篇論文課程。他對(duì)圖靈的計(jì)算模型，麥柯勞赫和皮孜的神經(jīng)網(wǎng)絡(luò)，拉賓和斯科特的有限自動(dòng)機(jī)，巴克斯和諾爾描述程序的BNF，喬姆斯基的上下文無(wú)關(guān)文法等進(jìn)行了深入專研與消化，并加以分析、綜合和比較，逐漸理出了頭緒，成功地開(kāi)出了新課。后來(lái)與厄爾曼合作編寫(xiě)了《形式語(yǔ)言及其與自動(dòng)機(jī)的關(guān)系》，感興趣的同學(xué)可以作為參考書(shū)閱讀。１９７０年霍普克洛夫斯特和陶爾揚(yáng)合作提出了深度優(yōu)先算法等一些圖論中的難題而獲圖靈獎(jiǎng)。陶爾揚(yáng)1948年生于加利福尼亞，從小就是一個(gè)富于幻想、追求新鮮事物的人，幼年夢(mèng)想成為登上火星的人，小學(xué)7年級(jí)開(kāi)始看《科學(xué)美國(guó)人》雜志。1964年，陶爾揚(yáng)參加了一個(gè)中學(xué)生夏令營(yíng)，第一次接觸了計(jì)算機(jī)，立即被神奇的計(jì)算機(jī)所吸引，因此他上加州理工學(xué)院時(shí)，輔修了學(xué)校開(kāi)設(shè)的所有計(jì)算機(jī)課程，1969年畢業(yè)后進(jìn)入斯坦福大學(xué)師從于著名的計(jì)算機(jī)科學(xué)家克納斯(Knuth，1974年圖靈獎(jiǎng)得主)，1970年在克納斯的有意安排下與康乃爾大學(xué)到普林斯頓學(xué)術(shù)休假的霍普克洛夫斯特共同研究圖論的算法。這個(gè)課題實(shí)際上是”人工智能之父“麥卡錫的建議下進(jìn)行的，霍普克洛夫斯特的新思路