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