本書(shū)介紹了算法的概念，算法分析的基本理論、過(guò)程和方法以及算法設(shè)計(jì)的基本策略。主要內(nèi)容包括算法概述、算法效率分析基礎(chǔ)、蠻力法、分治法、分治策略變體——減治策略和變治策略、動(dòng)態(tài)規(guī)劃、時(shí)空權(quán)衡技術(shù)、貪心算法、回溯法和分支限界法、NP完全性理論等。本書(shū)最后對(duì)ACM競(jìng)賽精選案例進(jìn)行了分析和講解。
根據(jù)教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)對(duì)高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)人才專業(yè)能力構(gòu)成與培養(yǎng)的主題的闡述，計(jì)算機(jī)專業(yè)人才的專業(yè)基本能力包括計(jì)算思維能力、算法設(shè)計(jì)與分析能力、程序設(shè)計(jì)與實(shí)現(xiàn)能力、系統(tǒng)能力。算法是系統(tǒng)工作的基礎(chǔ)，作為一名優(yōu)秀的計(jì)算機(jī)專業(yè)人才，關(guān)鍵是建立算法的概念，具備算法設(shè)計(jì)與分析的能力。
本教材按照“算法基本知識(shí)—經(jīng)典算法思想—算法應(yīng)用實(shí)踐”的順序進(jìn)行了內(nèi)容的組織及編寫(xiě)。讀者通過(guò)閱讀算法基礎(chǔ)部分，可了解算法的由來(lái)及其發(fā)展過(guò)程，理解算法的含義及問(wèn)題分類，掌握算法的分析表示方法及算法效率的評(píng)價(jià)手段。面對(duì)日益復(fù)雜的問(wèn)題，可將算法分為蠻力法、分治法及其變體算法、動(dòng)態(tài)規(guī)劃、時(shí)空權(quán)衡、貪心算法、回溯和分支限界法等幾種。在經(jīng)典算法思想部分，基本按照“算法思想—算法特點(diǎn)—算法實(shí)例—效率分析”的體例分別描述了各種算法，目的是使讀者能夠深入淺出地理解并掌握算法，能夠分析并比較相同問(wèn)題采用不同算法時(shí)的效率。為了提高讀者的算法應(yīng)用能力，本書(shū)結(jié)合ACM競(jìng)賽，從中選取了12個(gè)競(jìng)賽題目，例如果園籬笆問(wèn)題、旅游預(yù)算問(wèn)題等，并對(duì)各類問(wèn)題進(jìn)行了分析和討論，加強(qiáng)了讀者理論和實(shí)踐相結(jié)合的意識(shí)。
全書(shū)共分為11章。
第1章介紹算法的概念、由來(lái)與發(fā)展，對(duì)基本問(wèn)題類型、數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)要闡述。然后介紹算法求解的框架和步驟。
第2章介紹算法效率分析基礎(chǔ)。介紹算法分析的框架、三種漸進(jìn)符號(hào)和基本效率類型。然后介紹針對(duì)非遞歸算法和遞歸算法的數(shù)學(xué)分析方法。
第3章介紹蠻力法。它是解決問(wèn)題的最直接的方法，基于問(wèn)題的描述和所涉及的概念、定義直接求解。
第4章介紹分治法。分治法是問(wèn)題求解采用的最常用的算法策略之一，非常重要。
第5章介紹分治策略的變體。介紹了分治法的兩種變形： 減治和變治策略，并通過(guò)實(shí)例介紹這兩種策略在實(shí)際中的應(yīng)用。
第6章介紹動(dòng)態(tài)規(guī)劃算法。以實(shí)例詳述動(dòng)態(tài)規(guī)劃的算法思想、特點(diǎn)和求解問(wèn)題的方法步驟。
第7章介紹時(shí)空權(quán)衡技術(shù)。介紹犧牲時(shí)間效率換取空間效率和犧牲空間效率換取時(shí)間效率的算法設(shè)計(jì)方法。
第8章介紹貪心算法。它也是非常重要的算法策略，且效率較高。介紹了幾種典型的采用貪心算法求解最優(yōu)問(wèn)題的方法。
第9章介紹搜索算法。介紹回溯法和分支限界法，這兩種算法適宜解決數(shù)據(jù)量較大且難解的問(wèn)題。
第10章介紹NP完全性理論。簡(jiǎn)單介紹了NP完全性理論，以引起讀者進(jìn)一步學(xué)習(xí)和研究的興趣。
第11章精心挑選了12道ACM競(jìng)賽題目，對(duì)各問(wèn)題進(jìn)行了分析和講解，并在電子資源中提供了程序清單，以供讀者學(xué)習(xí)和參考。
本教材可以作為計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程等專業(yè)本科生及研究生的教材使用，同時(shí)也可作為有關(guān)專業(yè)軟件開(kāi)發(fā)人員的參考書(shū)。
本教材由師智斌等編著，其中師智斌編寫(xiě)了第1章，
井超編寫(xiě)了第2、5、6章，王東編寫(xiě)了第3章，靳雁霞編寫(xiě)了第4章，梁志劍編寫(xiě)了第7章，雷海衛(wèi)編寫(xiě)了第8~10章，秦品樂(lè)編寫(xiě)了第11章。本教材還參閱了大量國(guó)內(nèi)外專家、學(xué)者發(fā)表的著作、論文，在此向這些同行們表示衷心的感謝！
由于編者水平有限，書(shū)稿雖數(shù)次修改，仍會(huì)有不妥甚至錯(cuò)誤之處，誠(chéng)盼專家和廣大讀者不吝指正。聯(lián)系方法： 電子郵件1637350520@qq.com。
編者
2014年6月
第1章 緒論
1.1 什么是算法
1.1.1 算法的由來(lái)
1.1.2 算法的發(fā)展
1.1.3 算法的例子
1.2 重要的問(wèn)題類型
1.2.1 排序
1.2.2 查找
1.2.3 字符串匹配
1.2.4 圖問(wèn)題
1.2.5 組合問(wèn)題
1.2.6 幾何問(wèn)題
1.2.7 數(shù)值問(wèn)題
1.3 基本數(shù)據(jù)結(jié)構(gòu)
1.3.1 線性結(jié)構(gòu)
1.3.2 樹(shù)結(jié)構(gòu)
1.3.3 圖結(jié)構(gòu)
1.3.4 集合
1.3.5 數(shù)據(jù)的物理結(jié)構(gòu)
1.4 算法問(wèn)題求解基礎(chǔ)
1.4.1 算法求解框架
1.4.2 算法設(shè)計(jì)步驟
1.5 算法的表示
1.6 為什么學(xué)習(xí)算法
總結(jié)
習(xí)題1
第2章 算法效率分析基礎(chǔ)
2.1 算法分析框架
2.1.1 算法分析概述
2.1.2 算法正確性分析
2.1.3 時(shí)空效率分析
2.1.4 算法分析過(guò)程
2.2 漸進(jìn)符號(hào)和基本效率類型
2.2.1 三種漸進(jìn)符號(hào)
2.2.2 漸進(jìn)符號(hào)的特性
2.2.3 基本效率類型
2.3 非遞歸算法的數(shù)學(xué)分析方法
2.4 遞歸算法的數(shù)學(xué)分析
2.4.1 遞歸算法的數(shù)學(xué)分析方法
2.4.2 斐波那契數(shù)列
2.5 算法的其他分析方法
總結(jié)
習(xí)題2
第3章 蠻力法
3.1 概述
3.2 排序問(wèn)題
3.2.1 選擇排序
3.2.2 冒泡排序
3.3 查找問(wèn)題
3.3.1 順序查找
3.3.2 字符串匹配
3.4 幾何問(wèn)題
3.4.1 最近對(duì)問(wèn)題
3.4.2 凸包問(wèn)題
3.5 組合問(wèn)題
3.5.1 旅行商問(wèn)題
3.5.2 背包問(wèn)題
總結(jié)
習(xí)題3
第4章 分治法
4.1 概述
4.2 分治法的基本策略及步驟
4.2.1 分治法的基本策略
4.2.2 分治法的基本步驟
4.3 排序問(wèn)題
4.3.1 合并排序
4.3.2 快速排序
4.4 查找問(wèn)題
4.4.1 折半查找
4.4.2 二叉樹(shù)遍歷及其相關(guān)特性
4.5 數(shù)值計(jì)算問(wèn)題
4.5.1 大整數(shù)乘法
4.5.2 Strassen矩陣乘法
4.6 幾何問(wèn)題
4.6.1 用分治法解最近對(duì)問(wèn)題
4.6.2 用分治法解凸包問(wèn)題
4.7 分析分治法在安排循環(huán)賽中的應(yīng)用
總結(jié)
習(xí)題4
第5章 分治策略變體——減治策略和變治策略
5.1 減治策略
5.1.1 插入排序
5.1.2 拓?fù)渑判?br />
5.1.3 生成組合對(duì)象的算法
5.1.4 減常因子算法
5.1.5 減可變規(guī)模算法
5.2 變治策略
5.2.1 排序問(wèn)題
5.2.2 平衡查找樹(shù)
5.2.3 霍納法則和二進(jìn)制冪
5.2.4 問(wèn)題化簡(jiǎn)
總結(jié)
習(xí)題5
第6章 動(dòng)態(tài)規(guī)劃
6.1 概述
6.2 算法特點(diǎn)
6.2.1 備忘錄方法
6.2.2 最優(yōu)化原理
6.2.3 求解步驟
6.3 矩陣連乘問(wèn)題
6.4 最長(zhǎng)公共子序列
6.5 0-1背包問(wèn)題
6.6 最大子段和
6.7 最優(yōu)二叉查找樹(shù)
總結(jié)
習(xí)題6
第7章 時(shí)空權(quán)衡技術(shù)
7.1 時(shí)空權(quán)衡策略
7.2 計(jì)數(shù)排序
7.3 字符串匹配
7.4 散列法
總結(jié)
習(xí)題7
第8章 貪心算法
8.1 概述
8.1.1 貪心算法的基本要素
8.1.2 貪心算法的求解過(guò)程
8.2 活動(dòng)安排問(wèn)題
8.3 背包問(wèn)題
8.4 最小生成樹(shù)問(wèn)題
8.4.1 Prim算法
8.4.2 Kruskal算法
8.5 單源(點(diǎn))最短路徑問(wèn)題
8.6 哈夫曼編碼
總結(jié)
習(xí)題8
第9章 回溯法和分支限界法
9.1 回溯法
9.1.1 概述
9.1.2 子集和問(wèn)題
9.1.3 n皇后問(wèn)題
9.1.4 哈密頓回路
9.1.5 裝載問(wèn)題
9.2 分支限界法
9.2.1 概述
9.2.2 0-1背包問(wèn)題
9.2.3 任務(wù)分配問(wèn)題
9.2.4 多段圖的最短路徑問(wèn)題
9.2.5 旅行商問(wèn)題
總結(jié)
習(xí)題9
第10章 NP完全性理論
10.1 判定問(wèn)題和最優(yōu)化問(wèn)題
10.2 P類問(wèn)題
10.3 NP類問(wèn)題
10.4 NP完全問(wèn)題
10.5 典型的NP完全問(wèn)題
10.6 其他NP完全問(wèn)題
10.7 NP完全問(wèn)題的計(jì)算機(jī)處理
總結(jié)
習(xí)題10
第11章 案例精選
11.1 果園籬笆問(wèn)題
11.2 空中飛行管理問(wèn)題
11.3 去數(shù)問(wèn)題
11.4 極差問(wèn)題
11.5 最優(yōu)合并問(wèn)題
11.6 在棋盤中實(shí)現(xiàn)從初始布局到目標(biāo)布局的轉(zhuǎn)變
11.7 商店購(gòu)物問(wèn)題
11.8 旅游預(yù)算問(wèn)題
11.9 防衛(wèi)導(dǎo)彈問(wèn)題
11.10 釣魚(yú)問(wèn)題
11.11 胖男孩問(wèn)題
11.12 護(hù)衛(wèi)隊(duì)問(wèn)題
參考文獻(xiàn)
書(shū)單推薦
