計(jì)算機(jī)算法基礎(chǔ)

前言
教學(xué)建議
第1章  概述
1.1  算法與數(shù)據(jù)結(jié)構(gòu)及程序的關(guān)系
1.1.1  什么是算法
1.1.2  算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系
1.1.3  算法與程序的關(guān)系
1.1.4  選擇排序的例子
1.1.5  算法的偽碼表示
1.2  算法復(fù)雜度分析
1.2.1  算法復(fù)雜度的度量
1.2.2  算法復(fù)雜度與輸入數(shù)據(jù)規(guī)模的關(guān)系
1.2.3  輸入數(shù)據(jù)規(guī)模的度量模型
1.2.4  算法復(fù)雜度分析中的兩個(gè)簡(jiǎn)化假設(shè)
1.2.5  最好情況、最壞情況和平均情況的復(fù)雜度分析
1.3  函數(shù)增長(zhǎng)漸近性態(tài)的比較
1.3.1  三種比較關(guān)系及O、Ω、Θ記號(hào)
1.3.2  表示算法復(fù)雜度的常用函數(shù)
1.4  算法復(fù)雜度與問(wèn)題復(fù)雜度的關(guān)系
1.4.1  問(wèn)題復(fù)雜度是算法復(fù)雜度的下界
1.4.2  問(wèn)題復(fù)雜度與最佳算法
1.4.3  易處理問(wèn)題和難處理問(wèn)題
習(xí)題
第2章  分治法
2.1  分治法原理
2.1.1  二元搜索的例子
2.1.2  表示復(fù)雜度的遞推關(guān)系
2.2  遞推關(guān)系求解
2.2.1  替換法
2.2.2  序列求和法和遞歸樹(shù)法
2.2.3  常用序列和公式
2.2.4  主方法求解
習(xí)題
第3章  基于比較的排序算法
3.1  插入排序
3.1.1  插入排序的算法
3.1.2  插入排序算法的復(fù)雜度分析
3.1.3  插入排序的優(yōu)缺點(diǎn)
3.2  合并排序
3.2.1  合并算法及其復(fù)雜度
3.2.2  合并排序的算法及其復(fù)雜度
3.2.3  合并排序的優(yōu)缺點(diǎn)
3.3  堆排序
3.3.1  堆的數(shù)據(jù)結(jié)構(gòu)
3.3.2  堆的修復(fù)算法及其復(fù)雜度
3.3.3  為輸入數(shù)據(jù)建堆
3.3.4  堆排序算法
3.3.5  堆排序算法的復(fù)雜度
3.3.6  堆排序算法的優(yōu)缺點(diǎn)
3.3.7  堆用作優(yōu)先隊(duì)列
3.4  快排序
3.4.1  快排序算法
3.4.2  快排序算法最壞情況復(fù)雜度
3.4.3  快排序算法平均情況復(fù)雜度
3.4.4  快排序算法最好情況復(fù)雜度
3.4.5  快排序算法優(yōu)缺點(diǎn)
習(xí)題
第4章  不基于比較的排序算法
4.1  比較排序的下界
4.1.1  決策樹(shù)模型及最壞情況下界
4.1.2  二叉樹(shù)的外路徑總長(zhǎng)與平均情況下界
4.1.3  二叉樹(shù)的全路徑總長(zhǎng)及堆排序最好情況下界
4.2  不基于比較的線性時(shí)間排序算法
4.2.1  計(jì)數(shù)排序
4.2.2  基數(shù)排序
4.2.3  桶排序
習(xí)題
第5章  中位數(shù)和任一順序數(shù)的選擇
5.1  問(wèn)題定義
5.2  最大數(shù)和最小數(shù)的選擇
5.2.1  最大和最小順序數(shù)的選擇算法及其復(fù)雜度
5.2.2  同時(shí)找出最大數(shù)和最小數(shù)的算法
5.3  線性時(shí)間找出任一順序數(shù)的算法
5.3.1  最壞情況復(fù)雜度為O（n）的算法
5.3.2  平均情況復(fù)雜度為O（n）的算法
5.4  找出k個(gè)最大順序數(shù)的算法
5.4.1  一個(gè)理論聯(lián)系實(shí)際的問(wèn)題
5.4.2  利用堆來(lái)找k個(gè)最大的順序數(shù)的算法
5.4.3  利用錦標(biāo)賽樹(shù)來(lái)找k個(gè)最大順序數(shù)的算法
習(xí)題
第6章  動(dòng)態(tài)規(guī)劃
6.1  動(dòng)態(tài)規(guī)劃的基本原理
6.2  矩陣連乘問(wèn)題
6.3  最長(zhǎng)公共子序列問(wèn)題
6.4  最佳二元搜索樹(shù)
6.5  多級(jí)圖及其應(yīng)用
6.6  最長(zhǎng)遞增子序列問(wèn)題
習(xí)題
第7章  貪心算法
7.1  最佳郵局設(shè)置問(wèn)題
7.2  最佳活動(dòng)安排問(wèn)題
7.3  哈夫曼編碼問(wèn)題
7.3.1  前綴碼
7.3.2  最佳前綴碼——哈夫曼編碼
7.4  最佳加油計(jì)劃問(wèn)題
習(xí)題
第8章  圖的周游算法
8.1  圖的表示
8.1.1  鄰接表
8.1.2  鄰接矩陣
8.2  廣度優(yōu)先搜索及應(yīng)用
8.2.1  廣度優(yōu)先搜索策略
8.2.2  廣度優(yōu)先搜索算法及距離樹(shù)
8.2.3  無(wú)向圖的二著色問(wèn)題
8.3  深度優(yōu)先搜索及應(yīng)用
8.3.1  深度優(yōu)先搜索策略
8.3.2  深度優(yōu)先搜索算法和深度優(yōu)先樹(shù)
8.3.3  深度優(yōu)先搜索算法舉例和圖中邊的分類(lèi)
8.3.4  拓?fù)渑判?br />8.3.5  無(wú)回路有向圖中最長(zhǎng)路徑問(wèn)題及應(yīng)用
8.3.6  有向圖的強(qiáng)連通分支的分解
8.3.7  無(wú)向圖的雙連通分支的分解
習(xí)題
第9章  圖的最小支撐樹(shù)
9.1  計(jì)算最小支撐樹(shù)的一個(gè)通用的貪心算法策略
9.2  Kruskal算法
9.3  Prim算法
習(xí)題
第10章  單源最短路徑
10.1  Dijkstra算法
10.2  Bellman-Ford算法
習(xí)題
第11章  網(wǎng)絡(luò)流
11.1  網(wǎng)絡(luò)模型和最大網(wǎng)絡(luò)流問(wèn)題
11.2  網(wǎng)絡(luò)中流與割的關(guān)系
11.2.1  網(wǎng)絡(luò)中的割及其容量
11.2.2  剩余網(wǎng)絡(luò)和增廣路徑
11.2.3  最大流最小割定理
11.3  Ford-Fulkerson方法
11.3.1  Ford-Fulkerson的通用方法
11.3.2  Edmonds-Karp算法
11.3.3  Dinic算法
11.3.4  0-1網(wǎng)絡(luò)的最大流問(wèn)題
11.4  二部圖的匹配問(wèn)題
11.4.1  用網(wǎng)絡(luò)流求二部圖的最大匹配算法
11.4.2  Philip-Hall婚配定理
11.4.3  Birkhoff-vonNeuman定理
11.5  推進(jìn)-重標(biāo)號(hào)算法簡(jiǎn)介
11.5.1  預(yù)流和高度函數(shù)
11.5.2  在剩余圖中對(duì)頂點(diǎn)的兩個(gè)操作
11.5.3  推進(jìn)-重標(biāo)號(hào)算法的初始化
11.5.4  推進(jìn)-重標(biāo)號(hào)的通用算法
習(xí)題
第12章  計(jì)算幾何基礎(chǔ)
12.1  平面線段及相互關(guān)系
12.1.1  向量的點(diǎn)積和叉積
12.1.2  平面線段的相互關(guān)系
12.2  平掃線技術(shù)和線段相交的確定
12.2.1  平掃線的狀態(tài)
12.2.2  用平掃線確定線段相交的算法
12.3  平面點(diǎn)集的凸包
12.3.1  Graham掃描法
12.3.2  Jarvis行進(jìn)法
12.4  最近點(diǎn)對(duì)問(wèn)題
習(xí)題
第13章  字符串匹配
13.1  一個(gè)樸素的字符串匹配算法
13.2  Rabin-Karp算法
13.3  基于有限狀態(tài)自動(dòng)機(jī)的匹配算法
13.3.1  有限狀態(tài)自動(dòng)機(jī)簡(jiǎn)介
13.3.2  字符串匹配自動(dòng)機(jī)
13.3.3  基于有限狀態(tài)自動(dòng)機(jī)的串匹配算法
13.4  Knuth-Morris-Pratt（KMP）算法
13.4.1  模式的前綴函數(shù)
13.4.2  KMP算法的偽碼
習(xí)題
第14章  NP完全問(wèn)題
14.1  預(yù)備知識(shí)
14.1.1  圖靈機(jī)
14.1.2  符號(hào)集和編碼對(duì)計(jì)算復(fù)雜度的影響
14.1.3  判斷型問(wèn)題和優(yōu)化型問(wèn)題及其關(guān)系
14.1.4  判斷型問(wèn)題的形式語(yǔ)言表示
14.1.5  多項(xiàng)式關(guān)聯(lián)和多項(xiàng)式歸約
14.2  P和NP語(yǔ)言類(lèi)
14.2.1  非確定圖靈機(jī)和NP語(yǔ)言類(lèi)
14.2.2  多項(xiàng)式檢驗(yàn)算法和NP類(lèi)語(yǔ)言
14.3  NP完全語(yǔ)言類(lèi)和NP完全問(wèn)題
14.3.1  第一個(gè)NPC問(wèn)題
14.3.2  若干著名NPC問(wèn)題的證明
習(xí)題
第15章  近似算法
15.1  近似算法的性能評(píng)價(jià)
15.2  頂點(diǎn)覆蓋問(wèn)題
15.3  貨郎擔(dān)問(wèn)題
15.3.1  滿足三角不等式關(guān)系的貨郎擔(dān)問(wèn)題
15.3.2  無(wú)三角不等式關(guān)系的一般貨郎擔(dān)問(wèn)題
15.4  集合覆蓋問(wèn)題
15.5  MAX-3-SAT問(wèn)題
15.6  加權(quán)的頂點(diǎn)覆蓋問(wèn)題
15.7  子集和問(wèn)題
15.7.1  一個(gè)保證最優(yōu)解的指數(shù)型算法
15.7.2  子集和問(wèn)題的一個(gè)完全多項(xiàng)式近似機(jī)制
15.8  鴻溝定理和不可近似性
15.8.1  鴻溝定理
15.8.2  任務(wù)均勻分配問(wèn)題
習(xí)題
第16章  窮舉搜索
16.1  搜索問(wèn)題及方法的描述
16.2  回溯法
16.2.1  回溯法的通用算法
16.2.2  n皇后問(wèn)題
16.2.3  子集和問(wèn)題
16.2.4  回溯法的效率估計(jì)
16.3  分支限界法
16.3.1  分支限界法解n皇后問(wèn)題
16.3.2  0/1背包問(wèn)題
16.4  博弈樹(shù)和α-β剪枝
16.4.1  博弈樹(shù)及其評(píng)估的方法
16.4.2  α-β剪枝法
習(xí)題
附錄紅黑樹(shù)
參考文獻(xiàn)