前 言
　　本書(shū)是在加州大學(xué)Berkeley分校和San Diego分校本科生算法課程講義的基礎(chǔ)上，歷經(jīng)十年，逐漸整理、日益完善而成的。我們教授此門(mén)課程的方法在過(guò)去幾年間經(jīng)歷了巨大變革，它一方面照顧到了學(xué)生的背景(學(xué)生們除編程之外并不具備正式而完善的應(yīng)用技巧)，一方面反映了算法領(lǐng)域總體上走向成熟的趨勢(shì)，正如過(guò)去數(shù)十年我們已經(jīng)見(jiàn)證了的。隨著當(dāng)初的教學(xué)講義被逐漸提煉成娓娓道來(lái)的文字，我們也逐漸調(diào)整著課程的結(jié)構(gòu)，以突出教學(xué)材料編排中蘊(yùn)含的“故事情節(jié)”。因此，本書(shū)的內(nèi)容經(jīng)過(guò)仔細(xì)選擇后才得以結(jié)集成篇。我們不求把此書(shū)編成一本算法百科全書(shū)，這使我們可以自由地把大多數(shù)傳統(tǒng)算法書(shū)籍未曾強(qiáng)調(diào)或忽略的主題包含進(jìn)來(lái)。
　　我們根據(jù)學(xué)生的特點(diǎn)(這些特點(diǎn)也是當(dāng)今計(jì)算機(jī)科學(xué)專(zhuān)業(yè)的大多數(shù)本科生所共有的)，提煉出能使每個(gè)算法運(yùn)轉(zhuǎn)下去的簡(jiǎn)潔數(shù)學(xué)思想，而不是沉湎于正式而冗長(zhǎng)的理論證明。換言之，我們?cè)诨盍�和刻板之間，更強(qiáng)調(diào)前者。我們發(fā)現(xiàn)，學(xué)生更能接受這種形式帶來(lái)的數(shù)學(xué)的生命力。正是在這些簡(jiǎn)潔有力的數(shù)學(xué)思想的推動(dòng)下，我們才得以展開(kāi)我們的闡述。
　　一旦按照這種方式來(lái)理解算法，那么從它的歷史本源開(kāi)始研究就顯得很有意義，并且，對(duì)于今天的我們來(lái)說(shuō)，一方面，歷史的主題看似那樣的熟悉，另一方面，其與今天的對(duì)比卻又是那樣的顯著：數(shù)論、素性測(cè)試和因子分解。這就是本書(shū)第一部分的主題，此外它還包括RSA密碼系統(tǒng)、整數(shù)乘法的分治算法、排序與尋找中項(xiàng)以及快速Fourier變換。本書(shū)還包含其他三個(gè)部分：其中第二部分堪稱(chēng)本書(shū)內(nèi)容最傳統(tǒng)的章節(jié)，主要圍繞數(shù)據(jù)結(jié)構(gòu)和圖論展開(kāi)。這一部分中，錯(cuò)綜復(fù)雜的問(wèn)題結(jié)構(gòu)和用于解決問(wèn)題的簡(jiǎn)潔明快的偽代碼形成了鮮明對(duì)比。如果希望以傳統(tǒng)的方式進(jìn)行講授，可以直接從本書(shū)的第二部分開(kāi)始，這部分自成體系(在序言之后)，如有需要，可再跳回第一部分。在本書(shū)的第一和第二部分，我們介紹了某些用于解決特定問(wèn)題的技術(shù)(例如貪心算法和分治技術(shù))；第三部分介紹一些強(qiáng)有力的算法設(shè)計(jì)技術(shù)，它們被廣泛地用于解決實(shí)際問(wèn)題：如動(dòng)態(tài)規(guī)劃技術(shù)(一種新穎的可用于清除學(xué)生的傳統(tǒng)學(xué)習(xí)障礙的方法)和線性規(guī)劃技術(shù)(一種簡(jiǎn)潔而直觀地處理單純形法、對(duì)偶問(wèn)題以及原問(wèn)題的簡(jiǎn)化問(wèn)題的技術(shù))。本書(shū)最后的第四部分介紹了對(duì)付困難問(wèn)題的方法：NP完全性、各種啟發(fā)式算法以及量子算法，后者或許是當(dāng)今最前沿的課題。碰巧的是，我們關(guān)于算法的講述在本書(shū)的末尾又回到了最初討論的問(wèn)題：針對(duì)因子分解問(wèn)題的Shor量子算法。
　　本書(shū)包含了三個(gè)附加的脈絡(luò)。為了保持全書(shū)的可讀性(兼顧學(xué)生的不同需求和興趣)和邏輯的完整性，它們以三組自成系列的“灰色方框”形式出現(xiàn)，分別對(duì)應(yīng)于一些算法技術(shù)的歷史背景、對(duì)所介紹算法如何在實(shí)際中應(yīng)用(突出了互聯(lián)網(wǎng)應(yīng)用)的描述，以及對(duì)相關(guān)數(shù)學(xué)知識(shí)的簡(jiǎn)要闡釋。
我們的很多同事為此書(shū)的出版做出了重要貢獻(xiàn)。在此對(duì)Dimitris Achlioptas、Dorit Aharanov、Mike Clancy、Jim Demmel、Monika Henzinger、Mike Jordan、Milena Mihail、Gene Myers、Dana Randall、Satish Rao、Tim Roughgarden、Jonathan Shewchuk、Martha Sideri、Alistair Sinclair，以及David Wagner表示由衷的感謝，他們均對(duì)本書(shū)提出了寶貴意見(jiàn)，并對(duì)本書(shū)的初稿作了校對(duì)。Satish Rao、Leonard Schulman和Vijay Vazirani對(duì)本書(shū)幾個(gè)核心章節(jié)的內(nèi)容給出了重要建議。Gene Myers、Satish Rao、Luca Trevisan、Vijay Vazirani和Lofti Zadeh提供了本書(shū)的習(xí)題。最后，向加州大學(xué)Berkeley分校和San Diego分校的同學(xué)們表示感謝，是他們推動(dòng)了本書(shū)的出版工作，并參與審閱本書(shū)的手稿。