算法設(shè)計(jì)技巧與分析

前言

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

內(nèi)容概要

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

作者簡(jiǎn)介

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

書籍目錄

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

章節(jié)摘錄

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

編輯推薦

《算法設(shè)計(jì)技巧與分析》是國(guó)外計(jì)算機(jī)科學(xué)教材系列

圖書封面

圖書標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法設(shè)計(jì)技巧與分析 PDF格式下載

---