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

內(nèi)容概要

王紅梅、胡明編著的《算法設(shè)計(jì)與分析》將經(jīng)典問題和算法設(shè)計(jì)技術(shù)很好地結(jié)合起來，系統(tǒng)地介紹了算法設(shè)計(jì)技術(shù)及其在經(jīng)典問題中的應(yīng)用。全書共分四部分：第一部分是基礎(chǔ)知識(shí)，包括算法設(shè)計(jì)基礎(chǔ)和算法分析基礎(chǔ)；第二部分是基本的算法設(shè)計(jì)技術(shù)，包括蠻力法、分治法、減治法、動(dòng)態(tài)規(guī)劃法和貪心法；第三部分是基于搜索的算法設(shè)計(jì)技術(shù)，包括回溯法和分支限界法；第四部分是計(jì)算的限制，介紹了問題的復(fù)雜性、近似算法和概率算法。所有問題都用偽代碼給出了算法描述，大多數(shù)問題都給出了C++語言的算法實(shí)現(xiàn)，并且所有程序均在VC++6.0環(huán)境下調(diào)試通過。每章均附有一篇閱讀材料，以通俗易懂的方式介紹了算法領(lǐng)域的一些最新研究成果。
    《算法設(shè)計(jì)與分析》內(nèi)容豐富，深入淺出，結(jié)合應(yīng)用，圖例豐富，可作為高等院校計(jì)算機(jī)專業(yè)本科和研究生學(xué)習(xí)算法設(shè)計(jì)與分析的教材，也可供工程技術(shù)人員和自學(xué)者學(xué)習(xí)參考。

書籍目錄

第一部分 基礎(chǔ)知識(shí)第1章 算法設(shè)計(jì)基礎(chǔ)3  1.1 算法的基本概念3  1.1.1 算法及其重要特性3  1.1.2 算法的描述方法5  1.1.3 算法設(shè)計(jì)的一般過程6  1.2 為什么要學(xué)習(xí)和研究算法7  1.2.1 算法在問題求解中的地位8  1.2.2 算法訓(xùn)練能夠提高計(jì)算思維能力10  1.2.3 算法研究是推動(dòng)計(jì)算機(jī)技術(shù)發(fā)展的關(guān)鍵11  1.3 重要的問題類型12  1.3.1 查找問題12  1.3.2 排序問題12  1.3.3 圖問題13  1.3.4 組合問題13  1.3.5 幾何問題13  閱讀材料--算法研究與圖靈獎(jiǎng)14  習(xí)題1第2章 算法分析基礎(chǔ)17  2.1 算法的時(shí)間復(fù)雜性分析17  2.1.1 輸入規(guī)模與基本語句18  2.1.2 算法的漸進(jìn)分析19  2.1.3 最好、最壞和平均情況20  2.1.4 非遞歸算法的時(shí)間復(fù)雜性分析20  2.1.5 遞歸算法的時(shí)間復(fù)雜性分析22  2.2 算法的空間復(fù)雜性分析23  2.3 最優(yōu)算法23  2.3.1 問題的計(jì)算復(fù)雜性下界24  2.3.2 平凡下界25  2.3.3 判定樹模型25  閱讀材料--算法的實(shí)驗(yàn)分析26  習(xí)題2第二部分 基本的算法設(shè)計(jì)技術(shù)第3章 蠻力法33  3.1 概述33  3.1.1 蠻力法的設(shè)計(jì)思想33  3.1.2 一個(gè)簡(jiǎn)單的例子--百元買百雞問題34  3.2 查找問題中的蠻力法36  3.2.1 順序查找36  3.2.2 串匹配問題37  3.3 排序問題中的蠻力法42  3.3.1 選擇排序42  3.3.2 起泡排序43  3.4 組合問題中的蠻力法44  3.4.1 0/1背包問題44  3.4.2 任務(wù)分配問題45  3.5 圖問題中的蠻力法46  3.5.1 哈密頓回路問題46  3.5.2 TSP問題47  3.6 幾何問題中的蠻力法48  3.6.1 最近對(duì)問題48  3.6.2 凸包問題49  閱讀材料--KMP算法中next值的計(jì)算51  習(xí)題3第4章 分治法55  4.1 概述55  4.1.1 分治法的設(shè)計(jì)思想55  4.1.2 一個(gè)簡(jiǎn)單的例子--數(shù)字旋轉(zhuǎn)方陣57  4.2 排序問題中的分治法59  4.2.1 歸并排序59  4.2.2 快速排序61  4.3 組合問題中的分治法64  4.3.1 最大子段和問題64  4.3.2 棋盤覆蓋問題65  4.4 幾何問題中的分治法67  4.4.1 最近對(duì)問題68  4.4.2 凸包問題71  閱讀材料--遞歸函數(shù)的執(zhí)行過程72  習(xí)題4第5章 減治法77  5.1 概述77  5.1.1 減治法的設(shè)計(jì)思想77  5.1.2 一個(gè)簡(jiǎn)單的例子--兩個(gè)序列的中位數(shù)78  5.2 查找問題中的減治法80  5.2.1 折半查找80  5.2.2 二叉查找樹82  5.2.3 選擇問題84  5.3 排序問題中的減治法86  5.3.1 插入排序86  5.3.2 堆排序88  5.4 組合問題中的減治法90  5.4.1 淘汰賽冠軍問題90  5.4.2 假幣問題91  閱讀材料--假幣問題的復(fù)雜版本93  習(xí)題5第6章 動(dòng)態(tài)規(guī)劃法97  6.1 概述97  6.1.1 多階段決策過程98  6.1.2 動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想99  6.1.3 一個(gè)簡(jiǎn)單的例子--數(shù)塔問題100  6.2 圖問題中的動(dòng)態(tài)規(guī)劃法102  6.2.1 多段圖的最短路徑問題102  6.2.2 多源點(diǎn)最短路徑問題106  6.2.3 TSP問題107  6.3 組合問題中的動(dòng)態(tài)規(guī)劃法109  6.3.1 最長遞增子序列問題109  6.3.2 最長公共子序列問題111  6.3.3 0/1背包問題114  6.4 查找問題中的動(dòng)態(tài)規(guī)劃法116  6.4.1 最優(yōu)二叉查找樹116  6.4.2 近似串匹配問題119  閱讀材料--人工神經(jīng)網(wǎng)絡(luò)121  習(xí)題6第7章 貪心法127  7.1 概述127  7.1.1 貪心法的設(shè)計(jì)思想127  7.1.2 一個(gè)簡(jiǎn)單的例子--埃及分?jǐn)?shù)128  7.2 圖問題中的貪心法129  7.2.1 TSP問題129  7.2.2 圖著色問題132  7.2.3 最小生成樹問題134  7.3 組合問題中的貪心法138  7.3.1 背包問題138  7.3.2 活動(dòng)安排問題140  7.3.3 多機(jī)調(diào)度問題142  閱讀材料--貪心法的正確性證明144  習(xí)題7第三部分 基于搜索的算法設(shè)計(jì)技術(shù)第8章 回溯法151  8.1 概述151  8.1.1 問題的解空間樹151  8.1.2 回溯法的設(shè)計(jì)思想152  8.1.3 回溯法的時(shí)間性能153  8.1.4 一個(gè)簡(jiǎn)單的例子--素?cái)?shù)環(huán)問題154  8.2 圖問題中的回溯法155  8.2.1 圖著色問題155  8.2.2 哈密頓回路問題158  8.3 組合問題中的回溯法160  8.3.1 八皇后問題160  8.3.2 批處理作業(yè)調(diào)度問題163  閱讀材料--遺傳算法166  習(xí)題8第9章 分支限界法171  9.1 概述171  9.1.1 分支限界法的設(shè)計(jì)思想171  9.1.2 分支限界法的時(shí)間性能172  9.1.3 一個(gè)簡(jiǎn)單的例子--圓排列問題173  9.2 圖問題中的分支限界法175  9.2.1 TSP問題175  9.2.2 多段圖的最短路徑問題178  9.3 組合問題中的分支限界法180  9.3.1 0/1背包問題180  9.3.2 任務(wù)分配問題182  9.3.3 批處理作業(yè)調(diào)度問題184  閱讀材料--蟻群算法187  習(xí)題9第四部分 計(jì)算的限制第10章 問題的復(fù)雜性193  10.1 問題的復(fù)雜性分類193  10.1.1 什么是計(jì)算194  10.1.2 可計(jì)算問題與不可計(jì)算問題195  10.1.3 易解問題與難解問題197  10.2 P類問題和NP類問題199  10.2.1 判定問題199  10.2.2 確定性算法與P類問題199  10.2.3 非確定性算法與NP類問題200  10.3 NP完全問題201  10.3.1 問題變換201  10.3.2 NP完全問題的定義202  10.3.3 基本的NP完全問題202  10.3.4 NP完全問題的計(jì)算機(jī)處理203  閱讀材料--Cook定理204  習(xí)題10第11章 近似算法209  11.1 概述209  11.1.1 近似算法的設(shè)計(jì)思想209  11.1.2 一個(gè)簡(jiǎn)單的例子--求π的近似值210    11.2 圖問題中的近似算法211  11.2.1 頂點(diǎn)覆蓋問題211  11.2.2 TSP問題212  11.3 組合問題中的近似算法214  11.3.1 裝箱問題214  11.3.2 子集和問題216  閱讀材料--粒子群算法219  習(xí)題11第12章 概率算法223  12.1 概述223  12.1.1 概率算法的設(shè)計(jì)思想224  12.1.2 隨機(jī)數(shù)發(fā)生器224  12.2 舍伍德型概率算法225  12.2.1 舍伍德型概率算法的設(shè)計(jì)思想225  12.2.2 快速排序226  12.2.3 二叉查找樹227  12.3 拉斯維加斯型概率算法228  12.3.1 拉斯維加斯型概率算法的設(shè)計(jì)思想228  12.3.2 八皇后問題229  12.3.2 整數(shù)因子劃分問題230  12.4 蒙特卡羅型概率算法231  12.4.1 蒙特卡羅型概率算法的設(shè)計(jì)思想231  12.4.2 主元素問題232  12.4.3 素?cái)?shù)測(cè)試問題233  閱讀材料--模擬淬火算法234  習(xí)題12附錄A 名詞索引237參考文獻(xiàn)243

編輯推薦

王紅梅、胡明編著的《算法設(shè)計(jì)與分析》共12章，第1章介紹了算法的基本概念和算法分析方法，第2章從算法的觀點(diǎn)非形式化地介紹了NP完全理論，第3章-第11章分別介紹了蠻力法、分治法、減治法、動(dòng)態(tài)規(guī)劃法、貪心法、回溯法、分支限界法、概率算法和近似算法等算法設(shè)計(jì)技術(shù)，第12章基于圖靈機(jī)計(jì)算模型介紹了計(jì)算復(fù)雜性理論。書中所有問題均給出了若干應(yīng)用實(shí)例，每章還設(shè)有一個(gè)實(shí)驗(yàn)項(xiàng)目，通過設(shè)計(jì)提高學(xué)生創(chuàng)造性思維的培養(yǎng)。每章均附有一篇閱讀材料，以通俗易懂的筆觸介紹了算法領(lǐng)域的一些最新研究成果，保證知識(shí)的先進(jìn)性。書中所有算法均給出了偽代碼，大部分算法還給出了C++描述。在算法介紹上，注重對(duì)問題求解過程的理解，注重算法設(shè)計(jì)思路和分析過程的講解，體現(xiàn)了“授之以漁”的教學(xué)理念。

圖書封面

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

---

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

---