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