算法設(shè)計與分析 第2版
本書是作者在多年從事算法設(shè)計與分析課程教學(xué)和研究的基礎(chǔ)上編寫而成，系統(tǒng)地介紹了算法設(shè)計與分析的理論、方法和技術(shù)。內(nèi)容圍繞兩條主線來組織。一條主線是介紹典范性的算法問題，如排序、選擇、圖遍歷等。 另一條主線是介紹典范性的算法設(shè)計分析策略，如分治、貪心、動態(tài)規(guī)劃等算法設(shè)計策略和對手分析、平攤分析等算法分析策略。本書中兩條主線交替進行，每條主線又各自分為基本和進階兩部分。
算法是計算的靈魂（spirit of computing），而算法設(shè)計與分析的基礎(chǔ)知識是計算機科學(xué)的基石。算法設(shè)計與分析的內(nèi)容很豐富，可以從不同視角進行組織與闡述。一種視角是關(guān)注經(jīng)典的算法問題，如排序、選擇、查找、圖遍歷等；另一種視角是關(guān)注經(jīng)典的算法設(shè)計策略，如分治、貪心、動態(tài)規(guī)劃等。
根據(jù)這一“二維視角”，本書的核心內(nèi)容分為四塊，如圖1 所示。從問題的視角看，主要有兩類問題。第一類為序...
本書是作者在多年從事算法設(shè)計與分析課程教學(xué)和研究的基礎(chǔ)上編寫而成，系統(tǒng)地介紹了算法設(shè)計與分析的理論、方法和技術(shù)。內(nèi)容圍繞兩條主線來組織。一條主線是介紹典范性的算法問題，如排序、選擇、圖遍歷等。 另一條主線是介紹典范性的算法設(shè)計分析策略，如分治、貪心、動態(tài)規(guī)劃等算法設(shè)計策略和對手分析、平攤分析等算法分析策略。本書中兩條主線交替進行，每條主線又各自分為基本和進階兩部分。
算法是計算的靈魂（spirit of computing），而算法設(shè)計與分析的基礎(chǔ)知識是計算機科學(xué)的基石。算法設(shè)計與分析的內(nèi)容很豐富，可以從不同視角進行組織與闡述。一種視角是關(guān)注經(jīng)典的算法問題，如排序、選擇、查找、圖遍歷等；另一種視角是關(guān)注經(jīng)典的算法設(shè)計策略，如分治、貪心、動態(tài)規(guī)劃等。
根據(jù)這一“二維視角”，本書的核心內(nèi)容分為四塊，如圖1 所示。從問題的視角看，主要有兩類問題。第一類為序相關(guān)的問題，包括基于比較的排序、選擇與查找；第二類為圖相關(guān)的問題，包括基本的圖遍歷問題以及最小生成樹、最短路徑等圖優(yōu)化問題。從策略的視角看，主要有兩類策略。第一類為遍歷策略，包括線性表上的遍歷和圖上的遍歷；第二類為優(yōu)化策略，在序相關(guān)的問題上主要體現(xiàn)為分治策略，在圖相關(guān)的問題上體現(xiàn)為貪心策略與動態(tài)規(guī)劃策略。
圖1 二維視角下的核心內(nèi)容
上述核心內(nèi)容是算法設(shè)計與分析中最基礎(chǔ)的知識與最典型的技術(shù)。以此為基礎(chǔ)，本書進一步討論更深入的算法設(shè)計與分析技術(shù)。一類是圍繞經(jīng)典數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計與分析，另一類是進階的算法分析策略。此外，本書集中討論抽象的—— 與機器、實現(xiàn)語言無關(guān)的—— 算法設(shè)計與分析。為此，在主體內(nèi)容之前，本書首先講解計算模型的基礎(chǔ)知識，它是后續(xù)抽象的算法設(shè)計與分析的基礎(chǔ)。本書的最后介紹計算復(fù)雜性的基礎(chǔ)知識，試圖讓讀者在了解各類算法問題、學(xué)習(xí)各種算法設(shè)計與分析技術(shù)之后，對算法問題的難度有一個總體的認識。本書內(nèi)容的總體結(jié)構(gòu)如圖2所示。
本書的內(nèi)容是作者在多年授課的過程中逐漸積淀而成的，因而它不是對算法設(shè)計與分析知識的一個百科全書式的覆蓋，而是對一些重點內(nèi)容更專注的討論。本書的內(nèi)容和組織方式是面向一個學(xué)期的授課而設(shè)計的。在授課形式方面，我們將課程分為主課與輔課兩種形式。主課主要圍繞典型的問題、經(jīng)典的算法展開，而輔課則主要圍繞算法策略展開。若干次的主課講授形成一個階段，每一個階段結(jié)束后，通過一次輔課從策略的視角回顧最近階段的一組算法，同時補充新的素材對相應(yīng)的策略進行進一步的討論。
圖2 本書內(nèi)容總體結(jié)構(gòu)
在知識講授之外，實踐也是算法設(shè)計與分析課程的重要組成部分。算法課程的實踐分為兩類。一類是傳統(tǒng)的習(xí)題。本書習(xí)題大體按照這樣的順序給出：首先是緊扣書本知識的習(xí)題，例如一些簡單定理的證明、緊扣算法細節(jié)的一些問題等；其次是應(yīng)用題，它需要讀者對一個具有一定現(xiàn)實意義的問題進行建模，并用書中的算法知識來解決問題。另一類是編程實現(xiàn)題。本書的應(yīng)用題大都可以用于算法編程實現(xiàn)的訓(xùn)練。在實際授課中，我們挑選了部分應(yīng)用題作為編程實現(xiàn)題，并基于開源的OnlineJudge 平臺進行自動評測，取得了良好的效果。
本書的素材主要源自南京大學(xué)計算機系本科生“算法設(shè)計與分析”課程的授課內(nèi)容。其中一部分素材來源于共同授課的其他老師，包括前期負責(zé)講授主課并指導(dǎo)輔課教學(xué)的陳道蓄老師，以及后期共同分班講授這門課程的錢柱中、張勝、徐經(jīng)緯老師。還有一部分素材來源于經(jīng)典的算法教科書和國外大學(xué)的授課教師在其課程網(wǎng)站上發(fā)布的課程材料。另外，還要感謝“算法設(shè)計與分析”課程早期的兩位助教魏恒峰和楊怡玲，他們對大量的課程資料進行了整理與提煉。最后要感謝上過這門課的學(xué)生，他們創(chuàng)造性的提問與解題時所犯的錯誤為本書提供了寶貴的素材。
黃宇，南京大學(xué)計算機科學(xué)與技術(shù)系教授，博士生導(dǎo)師，主要研究方向為分布式算法、分布式系統(tǒng)和軟件方法學(xué)。曾主持兩項國家自然科學(xué)基金項目，并作為主要成員參與了國家973計劃、國家自然科學(xué)基金創(chuàng)新群體項目等多項國家重大科研項目。2014年獲得南京大學(xué)登峰人才支持計劃資助，2011年獲教育部技術(shù)發(fā)明獎。所指導(dǎo)的博士論文榮獲2016年中國計算機學(xué)會博士學(xué)位論文獎。已在IEEE Trans on Computers、IEEE Trans on Parallel and Distributed Systems、IEEE PerCom等重要國際期刊及會議上發(fā)表多篇論文。