算法設計技巧與分析

前言

算法設計與分析是計算機科學技術(shù)中處于核心地位的一門專業(yè)基礎(chǔ)課，越來越受到重視。本書系統(tǒng)地介紹了一些常用的、經(jīng)典的算法設計技術(shù)，并給出了詳細的復雜性分析。全書分七部分19章，內(nèi)容含有遞歸技術(shù)、分治、動態(tài)規(guī)劃、貪心算法、圖的遍歷等，同時也包括了近年來發(fā)展迅速的近似算法、概率算法和幾何算法，對于NP完全問題等復雜性理論的基礎(chǔ)內(nèi)容，也做了基本的、清楚的描述。本書結(jié)構(gòu)合理，選材適度，陳述簡明易讀，每章附有適量的各種類型練習，沒有過難或研討性題目，適合于教學和自學。出版后已被許多大學選做本科和研究生的教材及參考書。作者M.H.Alsuwaiyel在沙特阿拉伯的King Fahd University of Petroleum & Minerals（KFUPM，皇家法哈德石油礦業(yè)大學）完成大學學業(yè)，在南加州（USC）大學獲得計算機科學碩士和博士學位。作者曾任KFUPM的計算機科學系主任、工程與計算機學院院長。他在沙特阿拉伯有廣泛的學術(shù)影響，是政府（包括內(nèi)務部和國防部在內(nèi)）的高級顧問。本書的翻譯工作是在朱洪教授的主持下進行的，全書主要由吳偉昶、方世昌翻譯，朱洪審校。對于發(fā)現(xiàn)的原書中的錯誤，在翻譯時已做了糾正，主要的錯誤已給予說明。上海應用技術(shù)學院計算機系的教師徐克奇、蔡旖旎、吳曉偉參與了部分翻譯工作。復旦大學計算機系研究生李夷磊、葛啟、謝之易、李鎮(zhèn)堅、王海濤、馬俊、田世俊、張涌、張華、李鎮(zhèn)堅、李夷磊、謝之易等閱讀了本書的大部分譯稿，并提出了許多寶貴的意見。對于他們的幫助表示最衷心的感謝。由于譯者本身的水平，翻譯中難免有錯誤，懇請讀者批評指正。

內(nèi)容概要

本書是國際著名算法專家李德財教授主編的系列叢書Lecture Notes Series on Computing中的一本。本書涵蓋了絕大多數(shù)算法設計中的一般技術(shù)，在表達每一種技術(shù)時，闡述它的應用背景，注意用與其他技術(shù)比較的方法說明它的特征，并提供大量實際問題的例子。本書同時也強調(diào)了對每一種算法的詳細的復雜性分析。全書分七部分19章，從算法設計和算法分析的基本概念和方法入手，先后介紹了遞歸技術(shù)、分治、動態(tài)規(guī)劃、貪心算法、圖的遍歷等技術(shù)，對NP完全問題進行了基本但清楚的討論。對概率算法、近似算法和計算幾何這些近年來發(fā)展迅猛的領(lǐng)域也用一定的篇幅講述了基本內(nèi)容。書中每章后都附有大量的練習題，有利于讀者對書中內(nèi)容的理解和應用。    本書結(jié)構(gòu)簡明，內(nèi)容豐富，適合于作為計算機學科及相關(guān)學科算法課程的教材和參考書，尤其適宜于學過數(shù)據(jù)結(jié)構(gòu)和離散數(shù)學課程之后的算法課程教材。同時也可作為從事算法研究的一本好的入門書。

作者簡介

作者：（沙特）阿蘇外耶（M.H.Alsuwaiyel） 譯者：吳偉昶 方世昌 等 注釋 解說詞：朱洪

書籍目錄

第一部分　基本概念和算法導引第1章　算法分析基本概念　1.1　引言　1.2　歷史背景　1.3　二分搜索　1.4　合并兩個已排序的表　1.5　選擇排序　1.6　插入排序　1.7　自底向上合并排序　1.8　時間復雜性　1.9　空間復雜性　1.10　最優(yōu)算法　1.11　如何估計算法運行時間　1.12　最壞情況和平均情況的分析　1.13　平攤分析　1.14　輸入大小和問題實例　1.15　練習　1.16　參考注釋第2章　數(shù)學預備知識　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　練習第3章　數(shù)據(jù)結(jié)構(gòu)　3.1　引言　3.2　鏈表　3.3　圖　3.4　樹　3.5　根樹　3.6　二叉樹　3.7　練習　3.8　參考注釋第4章　堆和不相交集數(shù)據(jù)結(jié)構(gòu)　4.1　引言　4.2　堆　4.3　不相交集數(shù)據(jù)結(jié)構(gòu)　4.4　練習　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　練習　5.9　參考注釋第6章　分治　6.1　引言　6.2　二分搜索　6.3　合并排序　6.4　分治范式　6.5　尋找中項和第k小元素　6.6　快速排序　6.7　大整數(shù)乘法　6.8　矩陣乘法　6.9　最近點對問題　6.10　練習　6.11　參考注釋第7章　動態(tài)規(guī)劃　7.1　引言　7.2　最長公共子序列問題　7.3　矩陣鏈相乘　7.4　動態(tài)規(guī)劃范式　7.5　所有點對的最短路徑問題　7.6　背包問題　7.7　練習　7.8　參考注釋第三部分　最先割技術(shù)第8章　貪心算法　8.1　引言　8.2　最短路徑問題　8.3　最小耗費生成樹（Kruskal算法）　8.4　最小耗費生成樹（Prim算法）　8.5　文件壓縮　8.6　練習　8.7　參考注釋第9章　圖的遍歷　9.1　引言　9.2　深度優(yōu)先搜索　9.3　深度優(yōu)先搜索的應用　9.4　廣度優(yōu)先搜索　9.5　廣度優(yōu)先搜索的應用　9.6　練習　9.7　參考注釋第四部分問題的復雜性第10章　NP完全問題　10.1　引言　10.2　P類　10.3　NP類　10.4　NP完全問題　10.5　co-NP類　10.6　NPI類　10.7　四種類之間的關(guān)系　10.8　練習　10.9　參考注釋第11章　計算復雜性引論　11.1　引言　11.2　計算模型：圖靈機　11.3　k帶圖靈機和時間復雜性　11.4　離線圖靈機和空間復雜性　11.5　帶壓縮和線性增速　11.6　復雜性類之間的關(guān)系　11.7　歸約　11.8　完全性　11.9　多項式時間層次　11.10　練習　11.11　參考注釋第12章　下界　12.1　引言　12.2　平凡下界　12.3　決策樹模型　12.4　代數(shù)決策樹模型　12.5　線性時間歸約　12.6　練習　12.7　參考注釋第五部分克服困難性第13章　回溯法　13.1　引言　13.2　3著色問題　13.3　8皇后問題　13.4　一般回溯方法　13.5　分支限界法　13.6　練習　13.7　參考注釋第14章　隨機算法　14.1　引言　14.2　Las　Vegas和Monte　Carlo算法　14.3　隨機化快速排序　14.4　隨機化的選擇算法　14.5　測試串的相等性　14.6　模式匹配　14.7　隨機取樣　14.8　素數(shù)性測試　14.9　練習　14.10　參考注釋第15章　近似算法　15.1　引言　15.2　基本定義　15.3　差界　15.4　相對性能界　15.5　多項式近似方案　15.6　完全多項式近似方案　15.7　練習　15.8　參考注釋第六部分域指定問題的迭代改進第16章　網(wǎng)絡流　16.1　引言　16.2　預備知識　16.3　Ford-Fulkerson方法　16.4　最大容量增值　16.5　最短路徑增值　16.6　Dinic算法　16.7　MPM算法　16.8　練習　16.9　參考注釋第17章　匹配　17.1　引言　17.2　預備知識　17.3　網(wǎng)絡流方法　17.4　二分圖的匈牙利樹方法　17.5　一般圖中的最大匹配　17.6　二分圖的On2.5算法　17.7　練習　17.8　參考注釋第七部分計算幾何技術(shù)第18　章幾何掃描　18.1　引言　18.2　幾何預備知識　18.3　計算線段的交點　18.4　凸包問題　18.5　計算點集的直徑　18.6　練習　18.7　參考注釋第19章　Voronoi圖解　19.1　引言　19.2　最近點Voronoi圖解　19.3　Voronoi圖解的應用　19.4　最遠點Voronoi圖解　19.5　最遠點Voronoi圖解的應用　19.6　練習　19.7　參考注釋參考文獻

章節(jié)摘錄

插圖：1.1引言最一般的直覺意義上的算法①就是一個由有限的指令集組成的過程。從可能的輸人集中給這個過程一個輸入，如果系統(tǒng)地執(zhí)行該指令集，那么對于這個特定的輸人，當輸出存在時，就能得到輸出；當沒有輸出時，就什么結(jié)果也得不到?？赡艿妮斎爰侵改茏屧撍惴ńo出一個輸出的所有輸入。如果對于一個特定的輸入有一個輸出，那么就說該算法能用于這一輸入，執(zhí)行該算法能夠得到相應的輸出。我們要求算法對于每一個輸入能停下來，這意味著每一條指令只需要有限的時間，同時每一個輸入的長度是有限的。我們還要求對于一個合法輸人所對應的輸出是惟一的。也就是說當算法從一個特定的輸入開始，多次執(zhí)行同一指令集時，結(jié)果總是相同，從這個意義上講算法是確定的。第14章研究隨機算法時將放寬這一條件。在計算機科學領(lǐng)域，算法設計與分析是十分重要的。正如Donald E.Knuth所說，“計算機科學就是算法的研究”。這沒什么可驚訝的，因為計算機科學的每個領(lǐng)域都高度依賴于有效算法的設計。舉個簡單例子，編譯程序和操作系統(tǒng)不外乎就是具有特定目標的算法的直接實現(xiàn)。本章的目的有兩個：首先介紹一些簡單的算法，特別是與搜索和排序相關(guān)的那一類；其次講述用于算法設計和分析的基本概念。由于算法的“運行時間”這一概念對于設計有效算法是至關(guān)重要的，我們將對它進行深入討論?？傊?，時間是衡量算法有效性的最好測度。我們也會討論其他重要資源的測度，比如一個算法所需要的空間等。本章給出的算法雖然簡單，但它們是解釋一些算法概念的許多例子的基礎(chǔ)。從簡單有用的、在更復雜的算法中被用做構(gòu)件模塊的算法開始，是非常有益的。1.2 歷史背景20世紀早期，尤其在30年代，能否用一種有效的過程（即相當于現(xiàn)在所說的算法）來求解問題受到廣泛關(guān)注。在那時，人們的注意力是放在問題的可解或不可解的分類上，即是否存在有效過程來求解問題。為此，產(chǎn)生了對計算模型的需要。如果應用這個模型能夠建立一個算法來求解這個問題，那么這個問題就被歸人可解的問題類。其中的一些模型是哥德爾（del）的遞歸函數(shù)、丘奇（Church）的入演算、波斯特（Post）的波斯特機和圖靈（luring）的圖靈機。RAM計算模型是作為實際的計算機的理論上的補充被引人的。根據(jù)丘奇的論斷，所有這些模型是等效的，即意味著如果一個問題在其中的一個模型上是可解的，那么對于所有其他的模型，該問題都是可解的。

編輯推薦

《算法設計技巧與分析》是國外計算機科學教材系列

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法設計技巧與分析 PDF格式下載

---