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

定　價(jià)：￥36.00

作　者：	（沙特）阿蘇外耶著，吳偉昶等譯
出版社：	電子工業(yè)出版社
叢編項(xiàng)：
標(biāo)　簽：	計(jì)算機(jī)理論

購買這本書可以去

ISBN：	9787121118531	出版時(shí)間：	2010-10-01	包裝：	平裝
開本：	16開	頁數(shù)：	318	字?jǐn)?shù)：

內(nèi)容簡介

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

作者簡介

暫缺《算法設(shè)計(jì)技巧與分析》作者簡介

圖書目錄

第一部分　基本概念和算法導(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　輸入大小和問題實(shí)例
　1.15　練習(xí)
　1.16　參考注釋
第2章　數(shù)學(xué)預(yù)備知識(shí)
　2.1　集合、關(guān)系和函數(shù)
　2.2　證明方法
　2.3　對數(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è)簡單的例子
　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)對問題
　6.10　練習(xí)
　6.11　參考注釋
第7章　動(dòng)態(tài)規(guī)劃
　7.1　引言
　7.2　最長公共子序列問題
　7.3　矩陣鏈相乘
　7.4　動(dòng)態(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.2　P類
　10.3　NP類
　10.4　NP完全問題
　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著色問題
　13.3　8皇后問題
　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　測試串的相等性
　14.6　模式匹配
　14.7　隨機(jī)取樣
　14.8　素?cái)?shù)性測試
　14.9　練習(xí)
　14.10　參考注釋
第15章　近似算法
　15.1　引言
　15.2　基本定義
　15.3　差界
　15.4　相對性能界
　15.5　多項(xiàng)式近似方案
　15.6　完全多項(xiàng)式近似方案
　15.7　練習(xí)
　15.8　參考注釋第六部分域指定問題的迭代改進(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　凸包問題
　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)