一、課程名稱（中英文）
中文名稱:算法設(shè)計(jì)與分析
英文名稱:Algorithms Design and Analysis
二、課程性質(zhì)
專(zhuān)業(yè)方向課選修
三、學(xué)時(shí)
總學(xué)時(shí):48（理論學(xué)時(shí):32學(xué)時(shí)；實(shí)驗(yàn)學(xué)時(shí):16學(xué)時(shí)）
四、主要教學(xué)內(nèi)容
第1章 緒論 1
1.1 什么是算法 2
習(xí)題1.1 6
1.2 算法問(wèn)題求解基礎(chǔ) 7
1.2.1 理解問(wèn)題 8
1.2.2 了解計(jì)算設(shè)備的性能 8
1.2.3 在精確解法和近似解法之間做出選擇 9
1.2.4 算法的設(shè)計(jì)技術(shù) 9
1.2.5 確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu) 9
1.2.6 算法的描述 10
1.2.7 算法的正確性證明 10
1.2.8 算法的分析 11
1.2.9 為算法寫(xiě)代碼 12
習(xí)題1.2 13
1.3 重要的問(wèn)題類(lèi)型 14
1.3.1 排序 15
1.3.2 查找 16
1.3.3 字符串處理 16
1.3.4 圖問(wèn)題 16
1.3.5 組合問(wèn)題 17
1.3.6 幾何問(wèn)題 17
1.3.7 數(shù)值問(wèn)題 18
習(xí)題1.3 18
1.4 基本數(shù)據(jù)結(jié)構(gòu) 20
1.4.1 線性數(shù)據(jù)結(jié)構(gòu) 20
1.4.2 圖 22
1.4.3 樹(shù) 25
1.4.4 集合與字典 28
習(xí)題1.4 29
小結(jié) 30
第2章 算法效率分析基礎(chǔ) 32
2.1 分析框架 33
2.1.1 輸入規(guī)模的度量 33
2.1.2 運(yùn)行時(shí)間的度量單位 34
2.1.3 增長(zhǎng)次數(shù) 35
2.1.4 算法的最優(yōu)、最差和平均效率 36
2.1.5 分析框架概要 38
習(xí)題2.1 39
2.2 漸近符號(hào)和基本效率類(lèi)型 40
2.2.1 非正式的介紹 40
2.2.2 符號(hào)O 41
2.2.3 符號(hào) 42
2.2.4 符號(hào) 42
2.2.5 漸近符號(hào)的有用特性 43
2.2.6 利用極限比較增長(zhǎng)次數(shù) 44
2.2.7 基本的效率類(lèi)型 45
習(xí)題2.2 46
2.3 非遞歸算法的數(shù)學(xué)分析 48
習(xí)題2.3 52
2.4 遞歸算法的數(shù)學(xué)分析 54
習(xí)題2.4 59
2.5 例題:計(jì)算第n個(gè)斐波那契數(shù) 62
習(xí)題2.5 65
2.6 算法的經(jīng)驗(yàn)分析 66
習(xí)題2.6 69
2.7 算法可視法 70
小結(jié) 73
第3章 蠻力法 75
3.1 選擇排序和冒泡排序 76
3.1.1 選擇排序 76
3.1.2 冒泡排序 77
習(xí)題3.1 78
3.2 順序查找和蠻力字符串匹配 80
3.2.1 順序查找 80
3.2.2 蠻力字符串匹配 81
習(xí)題3.2 82
3.3 最近對(duì)和凸包問(wèn)題的蠻力算法 83
3.3.1 最近對(duì)問(wèn)題 83
3.3.2 凸包問(wèn)題 84
習(xí)題3.3 87
3.4 窮舉查找 89
3.4.1 旅行商問(wèn)題 89
3.4.2 背包問(wèn)題 90
3.4.3 分配問(wèn)題 91
習(xí)題3.4 93
3.5 深度優(yōu)先查找和廣度優(yōu)先查找 94
3.5.1 深度優(yōu)先查找 94
3.5.2 廣度優(yōu)先查找 96
習(xí)題3.5 98
小結(jié) 100
第4章 減治法 101
4.1 插入排序 103
習(xí)題4.1 105
4.2 拓?fù)渑判?106
習(xí)題4.2 109
4.3 生成組合對(duì)象的算法 111
4.3.1 生成排列 111
4.3.2 生成子集 113
習(xí)題4.3 114
4.4 減常因子算法 115
4.4.1 折半查找 116
4.4.2 假幣問(wèn)題 117
4.4.3 俄式乘法 118
4.4.4 約瑟夫斯問(wèn)題 119
習(xí)題4.4 120
4.5 減可變規(guī)模算法 122
4.5.1 計(jì)算中值和選擇問(wèn)題 122
4.5.2 插值查找 125
4.5.3 二叉查找樹(shù)的查找和插入 126
4.5.4 拈游戲 127
習(xí)題4.5 128
小結(jié) 129
第5章 分治法 131
5.1 合并排序 133
習(xí)題5.1 135
5.2 快速排序 136
習(xí)題5.2 140
5.3 二叉樹(shù)遍歷及其相關(guān)特性 141
習(xí)題5.3 143
5.4 大整數(shù)乘法和Strassen矩陣乘法 144
5.4.1 大整數(shù)乘法 145
5.4.2 Strassen矩陣乘法 146
習(xí)題5.4 148
5.5 用分治法解最近對(duì)問(wèn)題和凸包問(wèn)題 149
5.5.1 最近對(duì)問(wèn)題 149
5.5.2 凸包問(wèn)題 151
習(xí)題5.5 153
小結(jié) 154
第6章 變治法 155
6.1 預(yù)排序 156
習(xí)題6.1 158
6.2 高斯消去法 160
6.2.1 LU分解 164
6.2.2 計(jì)算矩陣的逆 165
6.2.3 計(jì)算矩陣的行列式 166
習(xí)題6.2 167
6.3 平衡查找樹(shù) 168
6.3.1 AVL樹(shù) 169
6.3.2 2-3樹(shù) 173
習(xí)題6.3 174
6.4 堆和堆排序 175
6.4.1 堆的概念 176
6.4.2 堆排序 180
習(xí)題6.4 181
6.5 霍納法則和二進(jìn)制冪 182
6.5.1 霍納法則 182
6.5.2 二進(jìn)制冪 184
習(xí)題6.5 186
6.6 問(wèn)題化簡(jiǎn) 187
6.6.1 求最小公倍數(shù) 188
6.6.2 計(jì)算圖中的路徑數(shù)量 189
6.6.3 優(yōu)化問(wèn)題的化簡(jiǎn) 189
6.6.4 線性規(guī)劃 190
6.6.5 簡(jiǎn)化為圖問(wèn)題 192
習(xí)題6.6 193
小結(jié) 194
第7章 時(shí)空權(quán)衡 196
7.1 計(jì)數(shù)排序 197
習(xí)題7.1 199
7.2 字符串匹配中的輸入增強(qiáng)技術(shù) 200
7.2.1 Horspool算法 201
7.2.2 Boyer-Moore算法 204
習(xí)題7.2 207
7.3 散列法 209
7.3.1 開(kāi)散列(分離鏈) 210
7.3.2 閉散列(開(kāi)式尋址) 211
習(xí)題7.3 213
7.4 B樹(shù) 214
習(xí)題7.4 217
小結(jié) 218
第8章 動(dòng)態(tài)規(guī)劃 219
8.1 三個(gè)基本例子 220
習(xí)題8.1 224
8.2 背包問(wèn)題和記憶功能 226
8.2.1 背包問(wèn)題 226
8.2.2 記憶化 227
習(xí)題8.2 229
8.3 最優(yōu)二叉查找樹(shù) 230
習(xí)題8.3 234
8.4 Warshall算法和Floyd算法 235
8.4.1 Warshall算法 235
8.4.2 計(jì)算完全最短路徑的Floyd算法 238
習(xí)題8.4 241
小結(jié) 242
第9章 貪婪技術(shù) 243
9.1 Prim算法 245
習(xí)題9.1 249
9.2 Kruskal算法 250
習(xí)題9.2 255
9.3 Dijkstra算法 256
習(xí)題9.3 259
9.4 哈夫曼樹(shù)及編碼 260
習(xí)題9.4 264
小結(jié) 265
第10章 迭代改進(jìn) 266
10.1 單純形法 267
10.1.1 線性規(guī)劃的幾何解釋 267
10.1.2 單純形法概述 270
10.1.3 單純形法其他要點(diǎn) 275
習(xí)題10.1 276
10.2 最大流量問(wèn)題 278
習(xí)題10.2 285
10.3 二分圖的最大匹配 286
習(xí)題10.3 291
10.4 穩(wěn)定婚姻問(wèn)題 292
習(xí)題10.4 295
小結(jié) 296
第11章 算法能力的極限 297
11.1 如何求下界 298
11.1.1 平凡下界 298
11.1.2 信息論下界 299
11.1.3 敵手下界 299
11.1.4 問(wèn)題化簡(jiǎn) 300
習(xí)題11.1 302
11.2 決策樹(shù) 302
11.2.1 排序的決策樹(shù) 303
11.2.2 查找有序數(shù)組的決策樹(shù) 305
習(xí)題11.2 306
11.3 P、NP和NP完全問(wèn)題 308
11.3.1 P和NP問(wèn)題 308
11.3.2 NP完全問(wèn)題 311
習(xí)題11.3 314
11.4 數(shù)值算法的挑戰(zhàn) 316
習(xí)題11.4 322
小結(jié) 323
第12章 超越算法能力的極限 325
12.1 回溯法 325
12.1.1 n皇后問(wèn)題 326
12.1.2 哈密頓回路問(wèn)題 328
12.1.3 子集和問(wèn)題 328
12.1.4 一般性說(shuō)明 329
習(xí)題12.1 331
12.2 分支界限法 332
12.2.1 分配問(wèn)題 332
12.2.2 背包問(wèn)題 335
12.2.3 旅行商問(wèn)題 336
習(xí)題12.2 338
12.3 NP困難問(wèn)題的近似算法 339
12.3.1 旅行商問(wèn)題的近似算法 340
12.3.2 背包問(wèn)題的近似算法 349
習(xí)題12.3 352
12.4 解非線性方程的算法 353
12.4.1 平分法 355
12.4.2 試位法 357
12.4.3 牛頓法 358
習(xí)題12.4 360
小結(jié) 361
跋 363
附錄A 算法分析的實(shí)用公式 366
附錄B 遞推關(guān)系簡(jiǎn)明指南 369
課程簡(jiǎn)介
Course Introduction
教學(xué)隊(duì)伍Teaching Members
相關(guān)課程Correlative
Courses
