本書是國際著名算法專家李德財教授主編的系列叢書"Lecture Notes Series on Computing”中的一本。本書涵蓋了絕大多數(shù)算法設(shè)計中的一般技術(shù)，在表達(dá)每一種技術(shù)時，闡述它的應(yīng)用背景，注意用與其他技術(shù)比較的方法說明它的特征，并提供大量相應(yīng)實(shí)際問題的例子。全書分七部分19章，從算法設(shè)計和算法分析的基本概念和方法入手，先后介紹了遞歸技術(shù)、分治、動態(tài)規(guī)劃、貪心算法、圖的遍歷等技術(shù)，對NP完全問題進(jìn)行了基本但清楚的討論。
序言
多年來，我一直在尋找一本適合國內(nèi)計算機(jī)專業(yè)學(xué)生用的有關(guān)算法方面的國外教材。盡管在國內(nèi)引進(jìn)了一些不錯的國外教材，但總有篇幅過多，內(nèi)容不夠新穎或數(shù)據(jù)結(jié)構(gòu)內(nèi)容夾雜其中等等這樣那樣的不甚滿意之處。
不久前我有幸看到世界科學(xué)圖書出版社出版的由M．H．Alsuwaiyel撰寫的“Algorithms Design Techniques and Analysis”，它是以國際著名算法專家，我國臺灣出身的李德財教授所主編的系列從書“LectureNotesSeriesonComputing”中的一本。雖然此書不是美國的大學(xué)教材，而是沙特阿拉伯的大學(xué)計算機(jī)系教材，但是我很快就被該書的組織簡明、概括，且包含當(dāng)前市面上算法較少涉及的概率算法和近似算法的基本內(nèi)容所吸引。它是一本適合本科生學(xué)習(xí)算法的好書。
該書涉及數(shù)據(jù)結(jié)構(gòu)的部分較少，即使有一些，描述上也很快與算法中比較復(fù)雜的集合查找和合并運(yùn)算等相結(jié)合，讓讀者不會感到和已經(jīng)學(xué)過的數(shù)據(jù)結(jié)構(gòu)重復(fù)。這比較適合國內(nèi)大學(xué)計算機(jī)系中數(shù)據(jù)結(jié)構(gòu)和算法分成兩門課開設(shè)的實(shí)際狀況。
對于想了解NP完全問題基本概念的讀者，本書的篇幅給了他們基本但又清楚的描述。本書還包括計算幾何一章，其取材也是適中的。
概率算法和近似算法是近20年來算法研究迅猛發(fā)展的領(lǐng)域，本書給予了足夠的重視，這是本書特色之一，是我向國內(nèi)學(xué)生特別推薦的主要原因。
本書的另一特色是以算法的設(shè)計技術(shù)為綱，講述一個又一個的算法技術(shù)，然后分析其算法復(fù)雜性。
我希望該書(簡體中文版)的出版能彌補(bǔ)短期內(nèi)暫時無合適中文算法教材的空白。誠摯地向國內(nèi)的廣大算法老師推薦采用本書作為教材。
本書由上海應(yīng)用技術(shù)學(xué)院的吳偉昶老師在算法界的老前輩方世昌教授的協(xié)助下翻譯。吳偉昶多年來對算法很專研，在翻譯過程中對原著的少量錯誤進(jìn)行了糾正。方世昌教授是算法名著“The Design and Analysis of Computer Algorithms by Aho，Hopcroft and Ullman(1974)”我國最早譯本之一的譯者，雖然該書至今還沒有理想的譯本正式出版，但是方的譯本在20世紀(jì)80年代的我國高校計算機(jī)系師生中廣泛流傳，對算法在我國的普及做出了不可磨滅的貢獻(xiàn)。我堅信本譯本的出版將對我國高校計算機(jī)系的算法教學(xué)起到很大的推動作用。
朱洪
復(fù)旦大學(xué)
譯者序
算法設(shè)計與分析是計算機(jī)科學(xué)技術(shù)中處于核心地位的一門專業(yè)基礎(chǔ)課，越來越受到重視。本書系統(tǒng)地介紹了一些常用的、經(jīng)典的算法設(shè)計技術(shù)，并給出了詳細(xì)的復(fù)雜性分析。全書分七部分19章，內(nèi)容含有遞歸技術(shù)、分治、動態(tài)規(guī)劃、貪心算法、圖的遍歷等，同時也包括了近年來發(fā)展迅速的近似算法、概率算法和幾何算法，對于NP完全問題等復(fù)雜性理論的基礎(chǔ)內(nèi)容，也做了基本的、清楚的描述。本書結(jié)構(gòu)合理，選材適度，陳述簡明易讀，每章附有適量的各種類型練習(xí)，沒有過難或研討性題目，適合于教學(xué)和自學(xué)。出版后已被許多大學(xué)選做本科和研究生的教材及參考書。
多年來，我一直在尋找一本適合國內(nèi)計算機(jī)專業(yè)學(xué)生用的有關(guān)算法方面的國外教材。盡管在國內(nèi)引進(jìn)了一些不錯的國外教材，但總有篇幅過多，內(nèi)容不夠新穎或數(shù)據(jù)結(jié)構(gòu)內(nèi)容夾雜其中等等這樣那樣的不甚滿意之處。
不久前我有幸看到世界科學(xué)圖書出版社出版的由M．H．Alsuwaiyel撰寫的“Algorithms Design Techniques and Analysis”，它是以國際著名算法專家，我國臺灣出身的李德財教授所主編的系列從書“LectureNotesSeriesonComputing”中的一本。雖然此書不是美國的大學(xué)教材，而是沙特阿拉伯的大學(xué)計算機(jī)系教材，但是我很快就被該書的組織簡明、概括，且包含當(dāng)前市面上算法較少涉及的概率算法和近似算法的基本內(nèi)容所吸引。它是一本適合本科生學(xué)習(xí)算法的好書。
該書涉及數(shù)據(jù)結(jié)構(gòu)的部分較少，即使有一些，描述上也很快與算法中比較復(fù)雜的集合查找和合并運(yùn)算等相結(jié)合，讓讀者不會感到和已經(jīng)學(xué)過的數(shù)據(jù)結(jié)構(gòu)重復(fù)。這比較適合國內(nèi)大學(xué)計算機(jī)系中數(shù)據(jù)結(jié)構(gòu)和算法分成兩門課開設(shè)的實(shí)際狀況。
對于想了解NP完全問題基本概念的讀者，本書的篇幅給了他們基本但又清楚的描述。本書還包括計算幾何一章，其取材也是適中的。
概率算法和近似算法是近20年來算法研究迅猛發(fā)展的領(lǐng)域，本書給予了足夠的重視，這是本書特色之一，是我向國內(nèi)學(xué)生特別推薦的主要原因。
本書的另一特色是以算法的設(shè)計技術(shù)為綱，講述一個又一個的算法技術(shù)，然后分析其算法復(fù)雜性。
我希望該書(簡體中文版)的出版能彌補(bǔ)短期內(nèi)暫時無合適中文算法教材的空白。誠摯地向國內(nèi)的廣大算法老師推薦采用本書作為教材。
本書由上海應(yīng)用技術(shù)學(xué)院的吳偉昶老師在算法界的老前輩方世昌教授的協(xié)助下翻譯。吳偉昶多年來對算法很專研，在翻譯過程中對原著的少量錯誤進(jìn)行了糾正。方世昌教授是算法名著“The Design and Analysis of Computer Algorithms by Aho，Hopcroft and Ullman(1974)”我國最早譯本之一的譯者，雖然該書至今還沒有理想的譯本正式出版，但是方的譯本在20世紀(jì)80年代的我國高校計算機(jī)系師生中廣泛流傳，對算法在我國的普及做出了不可磨滅的貢獻(xiàn)。我堅信本譯本的出版將對我國高校計算機(jī)系的算法教學(xué)起到很大的推動作用。
收起全部↑
朱洪，復(fù)旦大學(xué)計算機(jī)科學(xué)系教授，中國計算機(jī)學(xué)會理論專業(yè)委員會常委，中國人工智能學(xué)會離散數(shù)學(xué)專委會主任，中國密碼學(xué)會理事。 M. H. Alsuwaiyel在沙特阿拉伯的Kin g Fahd University of Petroleum&Minerals（KFUPM，皇家法哈德石油礦業(yè)大學(xué)）完成大學(xué)學(xué)業(yè)，在南加州（USC）大學(xué)獲得計算機(jī)科學(xué)碩士和博士學(xué)位。作者曾任KFUPM的計算機(jī)科學(xué)系主任、工程與計算機(jī)學(xué)院院長。他在沙特阿拉伯有廣泛的學(xué)術(shù)影響，是政府（包括內(nèi)務(wù)部和國防部在內(nèi)）的高級顧問。
第一部分 基本概念和算法導(dǎo)引
第1章 算法分析基本概念
1．1引言
1．2歷史背景
1．3二分搜索
1．4合并兩個已排序的表
1．5選擇排序
1．6插入排序
1．7自底向上合并排序
1．8時間復(fù)雜性
1．9空間復(fù)雜性
1．10最優(yōu)算法
1．11如何估計算法運(yùn)行時間
1．12最壞情況和平均情況的分析
1．13平攤分析
1．14輸入大小和問題實(shí)例
1．15練習(xí)
1．16參考注釋
第2章 數(shù)學(xué)預(yù)備知識
2．1集合、關(guān)系和函數(shù)
2．2證明方法
2．3對數(shù)
2．4底函數(shù)和頂函數(shù)
2．5階乘和二項式系數(shù)
2．6鴿巢原理
2．7和式
2．8遞推關(guān)系
2．9練習(xí)
第3章 數(shù)據(jù)結(jié)構(gòu)
3．1引言
3．2鏈表
3．3圖
3．4樹
3．5根樹
3．6二叉樹
3．7練習(xí)
3．8參考注釋
第4章 堆和不相交集數(shù)據(jù)結(jié)構(gòu)
4．1引言
4．2堆
4．3不相交集數(shù)據(jù)結(jié)構(gòu)
4．4練習(xí)
4．5參考注釋
第二部分 基于遞歸的技術(shù)
第5章 歸納法
5．1引言
5．2兩個簡單的例子
5．3基數(shù)排序
5．4整數(shù)冪
5．5多項式求值（Horner規(guī)則）
5．6生成排列
5．7尋找多數(shù)元素
5．8練習(xí)
5．9參考注釋
第6章 分治
6．1引言
6．2二分搜索
6．3合并排序
6．4分治范式
6．5尋找中項和第k小元素
6．6快速排序
6．7大整數(shù)乘法
6．8矩陣乘法
6．9最近點(diǎn)對問題
6．10練習(xí)
6．11參考注釋
第7章 動態(tài)規(guī)劃
7．1引言
7．2最長公共子序列問題
7．3矩陣鏈相乘
7．4動態(tài)規(guī)劃范式
7．5所有點(diǎn)對的最短路徑問題
7．6背包問題
7．7練習(xí)
7．8參考注釋
第三部分最先割技術(shù)
第8章 貪心算法
8．1引言
8．2最短路徑問題
8．3最小耗費(fèi)生成樹（Kruskal算法）
8．4最小耗費(fèi)生成樹(Prim算法)
8．5文件壓縮
8．6練習(xí)
8．7參考注釋
第9章 圖的遍歷
9．1引言
9．2深度優(yōu)先搜索
9．3深度優(yōu)先搜索的應(yīng)用
9．4廣度優(yōu)先搜索
9．5廣度優(yōu)先搜索的應(yīng)用
9．6練習(xí)
9．7參考注釋第四部分問題的復(fù)雜性
第10章 NP完全問題
10．1引言
10．2P類
10．3NP類
10．4NP完全問題
10．5co?NP類
10．6NPI類
10．7四種類之間的關(guān)系
10．8練習(xí)
10．9參考注釋
第11章 計算復(fù)雜性引論
11．1引言
11．2計算模型：圖靈機(jī)
11．3k帶圖靈機(jī)和時間復(fù)雜性
11．4離線圖靈機(jī)和空間復(fù)雜性
11．5帶壓縮和線性增速
11．6復(fù)雜性類之間的關(guān)系
11．7歸約
11．8完全性
11．9多項式時間層次
11．10練習(xí)
11．11參考注釋
第12章 下界
12．1引言
12．2平凡下界
12．3決策樹模型
12．4代數(shù)決策樹模型
12．5線性時間歸約
12．6練習(xí)
12．7參考注釋第五部分克服困難性
第13章 回溯法
13．1引言
13．23著色問題
13．38皇后問題
13．4一般回溯方法
13．5分支限界法
13．6練習(xí)
13．7參考注釋
第14章 隨機(jī)算法
14．1引言
14．2Las Vegas和Monte Carlo算法
14．3隨機(jī)化快速排序
14．4隨機(jī)化的選擇算法
14．5測試串的相等性
14．6模式匹配
14．7隨機(jī)取樣
14．8素數(shù)性測試
14．9練習(xí)
14．10參考注釋
第15章 近似算法
15．1引言
15．2基本定義
15．3差界
15．4相對性能界
15．5多項式近似方案
15．6完全多項式近似方案
15．7練習(xí)
15．8參考注釋第六部分域指定問題的迭代改進(jìn)
第16章 網(wǎng)絡(luò)流
16．1引言
16．2預(yù)備知識
16．3Ford?Fulkerson方法
16．4最大容量增值
16．5最短路徑增值
16．6 Dinic算法
16．7 MPM算法
16．8練習(xí)
16．9參考注釋
第17章 匹配
17．1引言
17．2預(yù)備知識
17．3網(wǎng)絡(luò)流方法
17．4二分圖的匈牙利樹方法
17．5一般圖中的最大匹配
17．6二分圖的On2．5算法
17．7練習(xí)
17．8參考注釋第七部分計算幾何技術(shù)
第18 章幾何掃描
18．1引言
18．2幾何預(yù)備知識
18．3計算線段的交點(diǎn)
18．4凸包問題
18．5計算點(diǎn)集的直徑
18．6練習(xí)
18．7參考注釋
第19章 Voronoi圖解
19．1引言
19．2最近點(diǎn)Voronoi圖解
19．3Voronoi圖解的應(yīng)用
19．4最遠(yuǎn)點(diǎn)Voronoi圖解
19．5最遠(yuǎn)點(diǎn)Voronoi圖解的應(yīng)用
19．6練習(xí)
19．7參考注釋參考文獻(xiàn)
新書資訊