計(jì)算機(jī)日常運(yùn)用的卓越思想
計(jì)算機(jī)科學(xué)中的偉大思想是如何誕生的？以下遴選部分思想進(jìn)行介紹：
● 20世紀(jì)30年代，在第一臺數(shù)字計(jì)算機(jī)被發(fā)明以前，一位英國天才開創(chuàng)了計(jì)算機(jī)科學(xué)研究領(lǐng)域。之后，這位天才還繼續(xù)證明了，不管未來建造的計(jì)算機(jī)運(yùn)行多快、功能多強(qiáng)大、設(shè)計(jì)得多好，仍舊有一些問題將是計(jì)算機(jī)不能解決的。
● 1948年，一位供職于電話公司的科學(xué)家發(fā)表了一篇論文，由此開創(chuàng)了信息理論研究領(lǐng)域。這位科學(xué)家的工作讓計(jì)算機(jī)能以完美的精確度傳輸信息，即便大部分?jǐn)?shù)據(jù)都因?yàn)楸桓蓴_而遭受破壞。
● 1956年，一群學(xué)者在達(dá)特茅斯（Dartmouth）舉行會議。這次會議的目標(biāo)很清晰，也很大膽，那就是開創(chuàng)人工智能領(lǐng)域的研究。在取得了許多重大成功，也經(jīng)歷了無數(shù)次失望之后，我們?nèi)云诖�出現(xiàn)一個真正的智能計(jì)算機(jī)程序。
● 1969年，IBM（國際商業(yè)機(jī)器公司）的一名研究人員發(fā)明了一種在數(shù)據(jù)庫中組織信息的先進(jìn)方法。目前，絕大多數(shù)在線交易都使用該技術(shù)存儲及檢索信息。
● 1974 年，英國政府秘密通信實(shí)驗(yàn)室的研究人員發(fā)明了一種讓計(jì)算機(jī)實(shí)現(xiàn)安全通信的方法，即另一臺計(jì)算機(jī)可以查看在計(jì)算機(jī)之間交換的所有信息。這些研究人員為政府保密所限不過幸運(yùn)的是，三名美國專家獨(dú)立開發(fā)并拓展了這項(xiàng)重大發(fā)明，為互聯(lián)網(wǎng)上所有的安全通信打下了基礎(chǔ)。
● 1996 年，斯坦福大學(xué)的兩名博士生決定聯(lián)手搭建一個互聯(lián)網(wǎng)搜索引擎。幾年后，他們創(chuàng)辦了谷歌公司互聯(lián)網(wǎng)時代的第一個數(shù)字巨頭。
我們在享受21 世紀(jì)技術(shù)驚人增長的同時，使用計(jì)算機(jī)設(shè)備不管是現(xiàn)有最強(qiáng)大的一組機(jī)器，還是最新、最時尚的手持設(shè)備不可避免地要依賴計(jì)算機(jī)科學(xué)的基礎(chǔ)思想，而這些思想都誕生于20 世紀(jì)。想一想：你今天做過什么令人印象深刻的事情嗎？好吧，這個問題的答案取決于你怎么看。也許是你搜索了包含數(shù)十億份文檔的資料庫， 從中選出兩三份與你的需求最相關(guān)的文檔？即便有能夠影響所有電子設(shè)備的電磁干擾，你在存儲或傳輸數(shù)百萬條信息的過程中，也沒犯一點(diǎn)兒錯誤？你是否成功地完成了一次在線交易，即便同時有成千上萬名消費(fèi)者在訪問同一個服務(wù)器？你是否在能夠被其他數(shù)十臺計(jì)算機(jī)嗅探到的線路中傳輸了一些機(jī)密信息（比如信用卡卡號）？你是否運(yùn)用過壓縮的魔力，將數(shù)兆的照片壓縮成更易于管理的大小，以便附在電子郵件中發(fā)送？你是否在手持設(shè)備上觸發(fā)了人工智能，以自動糾正你在手持設(shè)備的小巧鍵盤上輸入的內(nèi)容？
這些令人印象深刻的壯舉都有賴于之前提到的偉大發(fā)明或發(fā)現(xiàn)。然而，絕大多數(shù)計(jì)算機(jī)用戶每天都會多次運(yùn)用這些天才的想法，卻從沒有意識到！本書旨在向大眾解釋這些觀點(diǎn)我們每天使用的計(jì)算機(jī)科學(xué)的偉大思想。在解釋每一個觀點(diǎn)時，我都假設(shè)讀者不了解有關(guān)計(jì)算機(jī)科學(xué)的任何知識。
算法：指尖精靈的構(gòu)件
到目前為止，我一直在談計(jì)算機(jī)科學(xué)的偉大思想，但計(jì)算機(jī)科學(xué)家們會將許多重要思想形容為算法。那么思想和算法之間有什么區(qū)別？究竟什么是算法？這一問題最簡單的答案是，算法是一張精確的處方，它按順序詳細(xì)列出了解決一個問題所需要的具體步驟。我們小時候在學(xué)校學(xué)到的一種算法就是很好的例子：將兩個大數(shù)字相加的算法。如下例所示。這個算法涉及一連串的步驟，開始的步驟如下：首先，將兩個數(shù)的最末位數(shù)相加，寫下結(jié)果的最末位數(shù)，將剩下的數(shù)放到左側(cè)的下一欄；接著，將下一欄的數(shù)相加，再將除了結(jié)果末位數(shù)的數(shù)字和前一欄余下的數(shù)相加……依此類推。
請注意算法步驟近乎機(jī)械化的感覺。事實(shí)上，這是算法的關(guān)鍵特點(diǎn)之一：每步都必須絕對精確，沒有任何人類意圖或推測摻雜其中。這樣，每個完全機(jī)械化的步驟才能被編入計(jì)算機(jī)。算法的另一個重要特點(diǎn)是，不管輸入什么，算法總能運(yùn)行。我們在學(xué)校學(xué)到的相加算法就擁有這一特性：不管你想把哪兩個數(shù)相加，運(yùn)用算法最終都會得出正確答案。比如，用這一算法將兩個長達(dá)1 000 位的數(shù)相加，你肯定能得到答案，盡管這需要相當(dāng)長的時間。
對把算法定義為一張精確的機(jī)械化的處方的說法，你也許會略感好奇。這張?zhí)幏骄烤挂�多精確？要進(jìn)行哪些基本操作？比如，在上面的相加算法中，簡單地說一句把兩個數(shù)相加是不是就行了？ 還是說我們要在加法表上列出所有位的數(shù)字？這些細(xì)節(jié)看起來也許有點(diǎn)兒乏味，甚至?xí)�顯得有點(diǎn)兒學(xué)究氣，但它們其實(shí)離真相不遠(yuǎn)了： 這些問題的真正答案正處于計(jì)算機(jī)科學(xué)的核心，并且也和哲學(xué)、物理學(xué)、神經(jīng)科學(xué)及遺傳學(xué)有聯(lián)系。有關(guān)算法究竟是什么的深層問題都?xì)w結(jié)于一個前提眾所周知的邱奇 圖靈論題（Church-Turing thesis）。我們將在第九章重溫這些問題，屆時我們還將討論計(jì)算的理論極限，以及邱奇 圖靈論題的一些方面。同時，將算法比作一張非常精確的處方這一非正式觀點(diǎn)，其效果會非常好。
現(xiàn)在我們知道了什么是算法，但算法和計(jì)算機(jī)有什么聯(lián)系呢？關(guān)鍵在于，計(jì)算機(jī)需要用非常精確的指令編程。因此，在能讓計(jì)算機(jī)為我們解決某個特定問題之前，我們需要為那個問題開發(fā)一種算法。在數(shù)學(xué)和物理學(xué)等其他學(xué)科中，重要的結(jié)果通常是由一個方程式獲得的。（著名的例子包括勾股定理a2 b2=c2 或愛因斯坦的質(zhì)量守恒定理E = mc2。）相反，計(jì)算機(jī)科學(xué)的偉大思想通常是來形容如何解決一個問題的當(dāng)然，是使用一種算法。因此，本書的主要目的是，解釋讓計(jì)算機(jī)成為你的個人天賦的東西計(jì)算機(jī)每天使用的偉大算法。
一種偉大的算法由什么構(gòu)成？
這會引出一個刁鉆的問題：什么才是真正偉大的算法？潛在的候選算法清單相當(dāng)長，但我用幾條基本標(biāo)準(zhǔn)縮減了用于本書的候選算法清單。第一條也是最重要的一條標(biāo)準(zhǔn)是，偉大的算法要被普通計(jì)算機(jī)用戶每天用到。第二條重要的標(biāo)準(zhǔn)是，偉大的算法應(yīng)該能處理具體的現(xiàn)實(shí)問題，如壓縮一個特定文件或通過一個噪鏈精確地傳輸文件。對已經(jīng)了解部分計(jì)算機(jī)科學(xué)的讀者而言，第XIII頁文字框中的內(nèi)容將解釋前面兩大標(biāo)準(zhǔn)的部分后果。
第三個標(biāo)準(zhǔn)是，算法主要和計(jì)算機(jī)科學(xué)理論相關(guān)。這排除了主要和計(jì)算機(jī)硬件如CPU（中央處理器）、監(jiān)視器，以及網(wǎng)絡(luò)有關(guān)的技術(shù)。這條標(biāo)準(zhǔn)也減輕了對基礎(chǔ)設(shè)施如互聯(lián)網(wǎng)設(shè)計(jì)的重視。為什么我要著重于計(jì)算機(jī)科學(xué)理論？部分原因是公眾對計(jì)算機(jī)科學(xué)認(rèn)知的不平衡：有一種廣泛的觀點(diǎn)認(rèn)為，計(jì)算機(jī)科學(xué)基本上就是編程（如軟件）和設(shè)備設(shè)計(jì)（如硬件）。事實(shí)上，最美妙的計(jì)算機(jī)科學(xué)思想中有許多是十分抽象的，并不屬于以上任意一類。我希望通過強(qiáng)調(diào)這些理論思想，讓更多人將計(jì)算機(jī)科學(xué)作為一門知識學(xué)科來理解。
你也許已經(jīng)注意到了，我列出的標(biāo)準(zhǔn)可能會遺漏一些偉大的算法，但我從一開始就避免了定義偉大這個極其麻煩的問題。針對這一問題，我依賴于自己的直覺。在本書說明的每種算法中，其核心都是一個讓整件事情奏效的精巧把戲（trick）。對我而言，當(dāng)這個把戲顯露出來時，那個啊哈時刻（即ahamoment，指用戶體驗(yàn)產(chǎn)品時眼前一亮的那一刻）會讓解釋這些算法成為令人愉悅的經(jīng)歷，我希望你也能有此感受。我會用到把戲這個詞很多次，需要指出的是，我并非指那些卑劣或騙人的把戲孩子可能會用在弟弟或妹妹身上的那種把戲。相反，本書中的把戲類似于交易訣竅或魔術(shù)：為達(dá)成目標(biāo)而采用的聰明技巧，否則目標(biāo)很難達(dá)成或根本不可能達(dá)成。
因此，根據(jù)直覺，我選出了自認(rèn)為是計(jì)算機(jī)科學(xué)世界中最精巧、最神奇的把戲。在英國數(shù)學(xué)家高德菲·哈羅德·哈代（G. H. Hardy） 的《一個數(shù)學(xué)家的辯白》（A Mathematicians Apology）中，作者試圖向公眾解釋數(shù)學(xué)家從事數(shù)學(xué)的原因美是第一道測試：丑陋的數(shù)學(xué)在這個世界中無永存之地。這道美的測試也適用于在計(jì)算機(jī)科學(xué)中蘊(yùn)含的理論思想。因此，選取在本書中出現(xiàn)的算法的最后一條標(biāo)準(zhǔn)，就是哈代的也許可以這么稱呼美的測試：我希望至少能成功地向讀者展示部分美我在每種算法中感受到的美。
第一條標(biāo)準(zhǔn)要被普通計(jì)算機(jī)用戶每天用到排除了主要由計(jì)算機(jī)專業(yè)人士使用的算法，如編譯器和程序驗(yàn)證技術(shù)。第二條標(biāo)準(zhǔn)解決某個特定問題的具體程序排除了許多作為計(jì)算機(jī)科學(xué)本科課程核心內(nèi)容的偉大算法，如排序算法（快速排序等）、圖形算法（迪杰斯特拉最短路徑算法等）、數(shù)據(jù)結(jié)構(gòu)（哈希表等）。這些算法的偉大性毋庸置疑，而且很輕易地就滿足了第一條標(biāo)準(zhǔn)，因?yàn)槠胀ㄓ脩羰褂玫慕^大多數(shù)應(yīng)用程序都會反復(fù)應(yīng)用這些算法。但這些算法太通用了：它們能被用來解決眾多問題。在本書中，我決定要專注于解決特定問題的算法，因?yàn)閷ζ胀ㄓ?jì)算機(jī)用戶而言，這些算法能讓他們擁有更清晰的動機(jī)。
接下來我將談?wù)勥x擇展示的這些算法。搜索引擎的巨大影響， 也許是算法技術(shù)影響所有計(jì)算機(jī)用戶最明顯的例子，我自然也將部分互聯(lián)網(wǎng)搜索的核心算法收在了本書中。第一章描述了搜索引擎如何使用索引尋找與請求匹配的文件，而第二章則解釋了網(wǎng)頁排名（PageRank）算法谷歌公司為保證匹配度最高的文件出現(xiàn)在搜索結(jié)果列表頂部的原始算法。
即便我們不經(jīng)常想這件事情，絕大多數(shù)人也能意識得到，為提供出人意料的強(qiáng)大搜索結(jié)果，搜索引擎會落實(shí)一些深邃的計(jì)算機(jī)科學(xué)思想。相反，其他一些偉大的算法也經(jīng)常被用到，但計(jì)算機(jī)用戶對此甚至都沒有意識到。第三章描述的公鑰加密（Public Key Cryptography） 就是這樣一種算法。用戶每次訪問一個安全網(wǎng)站（地址以https而非http開頭），都會用到公鑰加密的一個方面眾所周知的密鑰交換（key exchange）來展開一段安全對話。第三章就是在解釋密鑰交換過程的實(shí)現(xiàn)原理。
第四章的主題是糾錯碼（Error Correcting Codes），這是我們經(jīng)常使用但沒有意識到的另一類算法。事實(shí)上，糾錯碼極有可能是有史以來唯一一種使用次數(shù)最頻繁的偉大算法。糾錯碼可以讓計(jì)算機(jī)識別并糾正在儲存或傳輸數(shù)據(jù)時出現(xiàn)的錯誤，而不必依靠備份或再次傳輸。
糾錯碼無處不在：它們被用于所有硬盤驅(qū)動器、眾多網(wǎng)絡(luò)傳輸、CD （數(shù)字光盤）和DVD（高密度數(shù)字視頻光盤），甚至還存在于一些計(jì)算機(jī)的內(nèi)存中。不過，糾錯碼的能力太強(qiáng)了，以至于我們意識不到它們的存在。
第五章稍微有點(diǎn)兒特殊，它介紹的是圖形識別算法（Pattern Recognition Algorithm）。圖形識別算法也能進(jìn)入偉大的計(jì)算機(jī)科學(xué)思想榜單，但它違背了第一條標(biāo)準(zhǔn)：要被普通計(jì)算機(jī)用戶每天用到。圖形識別屬于計(jì)算機(jī)識別高度可變信息如筆跡、講話和人臉的技術(shù)。事實(shí)上，在21 世紀(jì)的第一個十年里，絕大多數(shù)日常計(jì)算并沒有用到這些技術(shù)。但在2010 年，圖形識別的重要性急劇增大：配備小型屏幕鍵盤的移動設(shè)備需要自動糾錯，平板設(shè)備必須識別手寫輸入，而且所有這些設(shè)備（特別是智能手機(jī)）越來越趨向于語音操作。一些網(wǎng)站甚至使用圖形識別來決定向用戶展示哪種廣告。另外， 我對圖形識別也有偏好，因?yàn)樗�是我的研究領(lǐng)域。因此，第五章描述了三種最有趣、最成功的圖形識別技術(shù)：最近鄰分類器（Nearest-neighbor Classifier）、決策樹（Decision Tree），以及神經(jīng)網(wǎng)絡(luò)（Neural Network）。
第六章討論了壓縮算法。壓縮算法組成了另一組使計(jì)算機(jī)變成我們指尖精靈的偉大思想。計(jì)算機(jī)用戶的確會時不時地直接進(jìn)行壓縮，也許是為了節(jié)省磁盤空間，也許是為了縮減照片容量，以便用電子郵件發(fā)出。不過在私底下，壓縮使用的頻率要更高：我們根本沒有意識到，我們的下載或上傳也可以通過壓縮以節(jié)省帶寬，而數(shù)據(jù)中心通常會壓縮消費(fèi)者的數(shù)據(jù)以降低成本。電子郵件提供商提供給你的5 GB（計(jì)算機(jī)存儲單位）空間，經(jīng)壓縮后很有可能只占據(jù)電子郵件提供商5 GB空間的很小一部分。
第七章講到了數(shù)據(jù)庫中運(yùn)用的一些基礎(chǔ)算法。這一章側(cè)重為實(shí)現(xiàn)一致性指一個數(shù)據(jù)庫中的關(guān)系不互相沖突而采用的聰明技巧。沒有這些精巧的技術(shù)，我們的絕大部分在線生活［包括網(wǎng)絡(luò)購物以及通過Facebook（臉書）之類的社交網(wǎng)站進(jìn)行互動］就會消亡于眾多計(jì)算機(jī)錯誤中。這一章解釋了一致性真正的問題是什么，以及計(jì)算機(jī)科學(xué)家是如何解決這一問題的。前提是不犧牲我們所期望的在線系統(tǒng)擁有的高效性。
在第八章，我們會了解理論計(jì)算機(jī)科學(xué)無可爭議的瑰寶之一：數(shù)字簽名。乍看之下，用數(shù)字形式簽署一份電子文檔似乎不可能。你也許會想，這種簽名必須由數(shù)字信息組成，而任何想要偽造簽名的人都可以毫不費(fèi)力地拷貝這些信息。這一悖論的解決方案，就是計(jì)算機(jī)科學(xué)取得的最令人矚目的成就之一。
第九章采取了截然不同的視角：與其描述一種已經(jīng)存在的偉大算法，我們不如去了解一種假如存在則必然會偉大的算法。不過我們會震驚地發(fā)現(xiàn)，這種特別偉大的算法不可能存在。這表明計(jì)算機(jī)解決問題的能力存在絕對極限，而我們將簡單地從哲學(xué)和生物學(xué)角度探討這一結(jié)果的應(yīng)用。
在結(jié)語部分，我們會總結(jié)偉大算法的一些共性，花些時間暢想未來會怎樣。會有更多偉大算法出現(xiàn)嗎？或者說，我們已經(jīng)發(fā)現(xiàn)了所有偉大的算法？
在此，不得不提前說一下本書的風(fēng)格。任何科普作品都必須清楚地告知讀者信息來源，但引用會破壞文本的流暢性，并讓讀者產(chǎn)生閱讀學(xué)術(shù)著作的感覺。由于可讀性和易讀性是本書的首要目標(biāo)，所以本書正文不會出現(xiàn)引用。不過，我清楚地記錄了所有來源，并在本書末尾的注釋板塊中列出，還時不時地附上拓展評論。這個板塊還列出了一些額外材料，以便感興趣的讀者能去尋找更多和計(jì)算機(jī)科學(xué)中偉大算法有關(guān)的信息。
為什么我們要關(guān)注這些偉大的算法？
希望對這些迷人思想的快速總結(jié)能讓你渴望深入了解它們的運(yùn)行方式。不過，也許你仍然在思考：本書的終極目標(biāo)是什么？讓我簡短地介紹一下本書的真正目的。這本書絕不是一本問答式操作手冊。在讀完本書后，你不會成為計(jì)算機(jī)安全方面的專家，也不會成為人工智能或其他領(lǐng)域的專家。你也許能學(xué)到一些有用的技能，這倒是真的。比如：你會對如何檢查安全網(wǎng)站憑證以及已簽名軟件包了解更多；你能在有損和無損壓縮之間針對不同任務(wù)做出明智選擇；通過理解搜索引擎索引和排名技術(shù)的某些方面，你能更高效地使用搜索引擎。
然而，這些相對于本書真正的目的不過是微小的紅利。在讀完本書后，你不會成為一名更加熟練的計(jì)算機(jī)用戶，但你會更加珍視每天在所有計(jì)算設(shè)備上不停使用的思想的美。
為什么這是件好事？我用類比的方式來說明。我肯定不是一位天文學(xué)專家事實(shí)上，我在這個領(lǐng)域里相當(dāng)無知，我想知道更多。但每當(dāng)我注視夜空時，我知道的少量天文學(xué)知識增強(qiáng)了我此刻的享受。有時，我對所見事物的理解，讓我產(chǎn)生了一種滿足和驚奇的感覺。希望在讀完本書后，你在使用計(jì)算機(jī)時也能經(jīng)常獲得同樣的滿足和驚奇之感，這也是我殷切的希望。你將真正珍視我們時代最常見、最神秘的黑盒子：你的個人電腦，你指尖的精靈。