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

內(nèi)容概要

為了適應(yīng)培養(yǎng)21世紀(jì)計(jì)算機(jī)人才的需要，結(jié)合我國高等院校教育工作的現(xiàn)狀，立足培養(yǎng)學(xué)生能跟上國際計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展水平，更新教學(xué)內(nèi)容和教學(xué)方法，本書以算法設(shè)計(jì)策略為知識單元，系統(tǒng)地介紹計(jì)算機(jī)算法的設(shè)計(jì)方法與分析技巧，以期為計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的學(xué)生提供廣泛而堅(jiān)實(shí)的計(jì)算機(jī)算法基礎(chǔ)知識。
    本書內(nèi)容豐富，觀點(diǎn)新穎，理論聯(lián)系實(shí)際。采用Java語言描述算法，簡明清晰、結(jié)構(gòu)緊湊，可讀性強(qiáng)。本書可以作為高等院校計(jì)算機(jī)專業(yè)本科生和研究生學(xué)習(xí)計(jì)算機(jī)算法設(shè)計(jì)的教材，也可供廣大工程技術(shù)人員和自學(xué)讀者學(xué)習(xí)參考。

書籍目錄

第1章 算法引論1.1 算法與程序1.2 表達(dá)算法的抽象機(jī)制1.3 描述算法1.4 算法復(fù)雜性分析小結(jié)習(xí)題第2章 遞歸與分治策略2.1 速歸的概念2.2 分治法的基本思想2.3 二分搜索技術(shù)2.4 大整數(shù)的乘法2.5 Strassen矩陣乘法2.6 棋盤覆蓋2.7 合并排序2.8 快速排序2.9 線性時間選擇2.10 最接近點(diǎn)對問題2.11 循環(huán)賽日程表小結(jié)習(xí)題第3章 動態(tài)規(guī)劃3.1 矩陣連乘問題3.2 動態(tài)規(guī)劃算法的基本要素3.3 最長公共子序列3.4 凸多邊形最優(yōu)三角剖分3.5 多邊形游戲3.6 圖像壓縮3.7 電路布線3.8 流水作業(yè)調(diào)度3.9 0-1背包問題3.10 最優(yōu)二叉搜索樹小結(jié)習(xí)題第4章 貪心算法4.1 活動安排問題4.2 貪心算法的基本要素4.2.1 貪心選擇性質(zhì)4.2.2 最優(yōu)子結(jié)構(gòu)性質(zhì)4.2.3 貪心算法與動態(tài)規(guī)劃算法的差異4.3 最優(yōu)裝載4.4 哈夫曼編碼4.4.1 前綴碼4.4.2 構(gòu)造哈夫曼編碼4.4.3 哈夫曼算法的正確性4.5 單源最短路徑4.5.1 算法基本思想4.5.2 算法的正確性和計(jì)算復(fù)雜性4.6 最小生成樹4.6.1 最小生成樹性質(zhì)4 6.2 Prim算法4.6.3 Kruskal算法4.7 多機(jī)調(diào)度問題4.8 貪心算法的理論基礎(chǔ)4.8.1 擬陣4.8.2 帶權(quán)擬陣的貪心算法4.8.3 任務(wù)時間表問題小結(jié)習(xí)題第5章 回溯法5.1 回溯法的算法框架5.1.1 問題的解空間5.1.2 回溯法的基本思想5.1.3 遞歸回溯5.1.4 迭代回溯5.1.5 子集樹與排列樹5.2 裝載問題5.3 批處理作業(yè)調(diào)度5.4 符號三角形問題5.5 n后問題5.6 0-1背包問題5.7 最大團(tuán)問題5.8 圖的m著色問題5.9 旅行售貨員問題5.10 圓排列問題5.11 電路板排列問題5.12 連續(xù)郵資問題5.13 回溯法的效率分析小結(jié)習(xí)題第6章 分支限界法6.1 分支限界法的基本思想6.2 單源最短路徑問題6.3 裝載問題6.4 布線問題6.5 0-1背包問題6.6 最大團(tuán)問題6.7 旅行售貨員問題6.8 電路板排列問題6.9 批處理作業(yè)調(diào)度小結(jié)習(xí)題第7章 概率算法7.1 隨機(jī)數(shù)7.2 數(shù)值概率算法7.2.1 用隨機(jī)投點(diǎn)法計(jì)算л值7.2.2 計(jì)算定積分7.2.3 解非線性方程組7.3 舍伍德算法7.3.1 線性時間選擇算法7.3.2 跳躍表7.4 拉斯維加斯算法7.4.1 n后問題7.4.2 整數(shù)因子分解7.5 蒙特卡羅算法7.5.1 蒙特卡羅算法的基本思想7.5.2 主元素問題7.5.3 素?cái)?shù)測試小結(jié)習(xí)題第8章 NP完全性理論8.1 計(jì)算模型8.1.1 隨機(jī)存取機(jī)RAM8.1.2 隨機(jī)存取存儲程序機(jī)RASP8.1.3 RAM模型的變形與簡化8.1.4 圖靈機(jī)8.1.5 圖靈機(jī)模型與RAM模型的關(guān)系8.1.6 問題變換與計(jì)算復(fù)雜性歸約8.2 P類與NP類問題8.2.1 非確定性圖靈機(jī)8.2.2 P類與NP類語言8.2.3 多項(xiàng)式時間驗(yàn)證8.3 NP完全問題8.3.1 多項(xiàng)式時間變換8.3.2 Cook定理8.4 一些典型的NP完全問題8.4.1 合取范式的可滿足性問題8.4.2 3元合取范式的可滿足性問題8.4.3 團(tuán)問題8.4.4 頂點(diǎn)覆蓋問題8.4.5 子集和問題8.4.6 哈密頓回路問題8.4.7 旅行售貨員問題小結(jié)習(xí)題第9章 近似算法9.1 近似算法的性能9.2 頂點(diǎn)覆蓋問題的近似算法9.3 旅行售貨員問題近似算法9.3.1 具有三角不等式性質(zhì)的旅行售貨員問題9.3.2 一般的旅行售貨員問題9.4 集合覆蓋問題的近似算法9.5 子集和問題的近似算法9.5.1 子集和問題的指數(shù)時間算法9.5.2 子集和問題的完全多項(xiàng)式時間近似格式小結(jié)習(xí)題第10章 算法優(yōu)化策略10.1 算法設(shè)計(jì)策略的比較與選擇10.1.1 最大子段和問題的簡單算法10.1.2 最大子段和問題的分治算法10.1.3 最大子段和問題的動態(tài)規(guī)劃算法10.1.4 最大子段和問題與動態(tài)規(guī)劃算法的推廣10.2 動態(tài)規(guī)劃加速原理10.2.1 貨物儲運(yùn)問題10.2.2 算法及其優(yōu)化10.3 問題的算法特征10.3.1 貪心策略10.3.2 對貪心策略的改進(jìn)10.3.3 算法三部曲10.3.4 算法實(shí)現(xiàn)10 3.5 算法復(fù)雜性10.4 優(yōu)化數(shù)據(jù)結(jié)構(gòu)10.4.1 帶權(quán)區(qū)間最短路問題10.4.2 算法設(shè)計(jì)思想10.4.3 算法實(shí)現(xiàn)方案10.4.4 并查集10.4.5 可并優(yōu)先隊(duì)列10.5 優(yōu)化搜索策略小結(jié)習(xí)題參考文獻(xiàn)

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

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

---