算法設計與分析

內容概要

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

書籍目錄

第一部分 基礎知識第1章 算法設計基礎3  1.1 算法的基本概念3  1.1.1 算法及其重要特性3  1.1.2 算法的描述方法5  1.1.3 算法設計的一般過程6  1.2 為什么要學習和研究算法7  1.2.1 算法在問題求解中的地位8  1.2.2 算法訓練能夠提高計算思維能力10  1.2.3 算法研究是推動計算機技術發(fā)展的關鍵11  1.3 重要的問題類型12  1.3.1 查找問題12  1.3.2 排序問題12  1.3.3 圖問題13  1.3.4 組合問題13  1.3.5 幾何問題13  閱讀材料--算法研究與圖靈獎14  習題1第2章 算法分析基礎17  2.1 算法的時間復雜性分析17  2.1.1 輸入規(guī)模與基本語句18  2.1.2 算法的漸進分析19  2.1.3 最好、最壞和平均情況20  2.1.4 非遞歸算法的時間復雜性分析20  2.1.5 遞歸算法的時間復雜性分析22  2.2 算法的空間復雜性分析23  2.3 最優(yōu)算法23  2.3.1 問題的計算復雜性下界24  2.3.2 平凡下界25  2.3.3 判定樹模型25  閱讀材料--算法的實驗分析26  習題2第二部分 基本的算法設計技術第3章 蠻力法33  3.1 概述33  3.1.1 蠻力法的設計思想33  3.1.2 一個簡單的例子--百元買百雞問題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 任務分配問題45  3.5 圖問題中的蠻力法46  3.5.1 哈密頓回路問題46  3.5.2 TSP問題47  3.6 幾何問題中的蠻力法48  3.6.1 最近對問題48  3.6.2 凸包問題49  閱讀材料--KMP算法中next值的計算51  習題3第4章 分治法55  4.1 概述55  4.1.1 分治法的設計思想55  4.1.2 一個簡單的例子--數(shù)字旋轉方陣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 最近對問題68  4.4.2 凸包問題71  閱讀材料--遞歸函數(shù)的執(zhí)行過程72  習題4第5章 減治法77  5.1 概述77  5.1.1 減治法的設計思想77  5.1.2 一個簡單的例子--兩個序列的中位數(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  閱讀材料--假幣問題的復雜版本93  習題5第6章 動態(tài)規(guī)劃法97  6.1 概述97  6.1.1 多階段決策過程98  6.1.2 動態(tài)規(guī)劃法的設計思想99  6.1.3 一個簡單的例子--數(shù)塔問題100  6.2 圖問題中的動態(tài)規(guī)劃法102  6.2.1 多段圖的最短路徑問題102  6.2.2 多源點最短路徑問題106  6.2.3 TSP問題107  6.3 組合問題中的動態(tài)規(guī)劃法109  6.3.1 最長遞增子序列問題109  6.3.2 最長公共子序列問題111  6.3.3 0/1背包問題114  6.4 查找問題中的動態(tài)規(guī)劃法116  6.4.1 最優(yōu)二叉查找樹116  6.4.2 近似串匹配問題119  閱讀材料--人工神經網(wǎng)絡121  習題6第7章 貪心法127  7.1 概述127  7.1.1 貪心法的設計思想127  7.1.2 一個簡單的例子--埃及分數(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 活動安排問題140  7.3.3 多機調度問題142  閱讀材料--貪心法的正確性證明144  習題7第三部分 基于搜索的算法設計技術第8章 回溯法151  8.1 概述151  8.1.1 問題的解空間樹151  8.1.2 回溯法的設計思想152  8.1.3 回溯法的時間性能153  8.1.4 一個簡單的例子--素數(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è)調度問題163  閱讀材料--遺傳算法166  習題8第9章 分支限界法171  9.1 概述171  9.1.1 分支限界法的設計思想171  9.1.2 分支限界法的時間性能172  9.1.3 一個簡單的例子--圓排列問題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 任務分配問題182  9.3.3 批處理作業(yè)調度問題184  閱讀材料--蟻群算法187  習題9第四部分 計算的限制第10章 問題的復雜性193  10.1 問題的復雜性分類193  10.1.1 什么是計算194  10.1.2 可計算問題與不可計算問題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完全問題的計算機處理203  閱讀材料--Cook定理204  習題10第11章 近似算法209  11.1 概述209  11.1.1 近似算法的設計思想209  11.1.2 一個簡單的例子--求π的近似值210    11.2 圖問題中的近似算法211  11.2.1 頂點覆蓋問題211  11.2.2 TSP問題212  11.3 組合問題中的近似算法214  11.3.1 裝箱問題214  11.3.2 子集和問題216  閱讀材料--粒子群算法219  習題11第12章 概率算法223  12.1 概述223  12.1.1 概率算法的設計思想224  12.1.2 隨機數(shù)發(fā)生器224  12.2 舍伍德型概率算法225  12.2.1 舍伍德型概率算法的設計思想225  12.2.2 快速排序226  12.2.3 二叉查找樹227  12.3 拉斯維加斯型概率算法228  12.3.1 拉斯維加斯型概率算法的設計思想228  12.3.2 八皇后問題229  12.3.2 整數(shù)因子劃分問題230  12.4 蒙特卡羅型概率算法231  12.4.1 蒙特卡羅型概率算法的設計思想231  12.4.2 主元素問題232  12.4.3 素數(shù)測試問題233  閱讀材料--模擬淬火算法234  習題12附錄A 名詞索引237參考文獻243

編輯推薦

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

圖書封面

評論、評分、閱讀與下載

---

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

---