計算與算法導論

第一部分
計算視角
第1章
技術、科學與文化的發(fā)展史 2
1.1
技術創(chuàng)新與人類進化 2
1.1.1
歷史發(fā)展的模式 3
1.1.2
科學領域的范式變遷 3
1.1.3
范式變遷的特點 3
1.2
范式發(fā)展歷史的概述 4
1.2.1
原始部族意識時代 4
1.2.2
字母表和抽象思維的萌芽 4
1.2.3
絕對抽象思維的時代 5
1.2.4
機械的媒體技術 6
1.2.5
“機械”思維的時代 7
1.2.6
電子媒體技術 7
1.3
最近幾十年來技術發(fā)展回顧 8
1.3.1
社會形態(tài)變遷過程描述 8
1.3.2
正在形成中的社會形態(tài)的特征 9
1.3.3
新的社會形態(tài)的中心主題 10
1.4
正在形成中的社會形態(tài) 11
1.4.1
現(xiàn)象的算法概念 12
1.4.2
模擬和實驗的方法 12
1.4.3
得到的啟發(fā) 14
習題 16
第2章
算法模型 18
2.1
什么是算法 18
2.2
好算法的要素 21
2.2.1
精度 21
2.2.2
簡單 21
2.2.3
抽象分級 22
2.3
算法與計算機 24
2.3.1
計算機做什么 24
2.3.2
計算機與二進制數(shù)據(jù) 24
2.3.3
計算機中的抽象分級 25
2.3.4
比較算法與計算機程序 27
2.3.5
比較數(shù)據(jù)與信息 27
2.4
算法組件 28
2.4.1
數(shù)據(jù)結構 28
2.4.2
數(shù)據(jù)操作指令 28
2.4.3
條件表達式 29
2.4.4
控制結構 29
2.4.5
模塊 29
2.5
從計算視角看問題 30
2.5.1
用算法表達式構思行為 30
2.5.2
用過程構思展示行為的東西 30
2.5.3
用不同抽象等級構思算法 30
2.5.4
理解復雜度如何限制算法的有用性 31
2.5.5
撇開其他視角 32
小結 33
習題 34
第二部分
算法工具
第3章
基本數(shù)據(jù)與操作 38
3.1
算法語言 38
3.2
創(chuàng)建簡單變量 39
3.2.1
變量標識符 40
3.3
運算符 40
3.3.1
賦值運算符 40
3.3.2
基本操作 41
3.3.3
輸入/輸出運算符 42
3.4
原子數(shù)據(jù)類型 44
3.4.1
數(shù)字型 44
3.4.2
字符 44
3.4.3
布爾型 45
3.4.4
指針型 45
3.5
復雜數(shù)據(jù)類型 45
3.5.1
字符串 45
3.5.2
其他復雜數(shù)據(jù)類型 46
3.6
變量聲明和初始化 46
3.6.1
數(shù)據(jù)聲明的位置 46
3.6.2
選擇標識符名字 46
3.6.3
初始化變量 46
3.7
固定的數(shù)據(jù) 47
3.7.1
常量 47
3.7.2
文字值 47
3.8
一般規(guī)則 48
3.8.1
算法的一般結構 48
3.8.2
標識符格式 49
3.8.3
類型匹配 49
3.9
算法判定 50
3.9.1
基本判定 50
3.9.2
判定與數(shù)據(jù)類型 51
3.9.3
判定活動 51
3.9.4
復雜判定與布爾操作比較 54
3.9.5
嵌套的判定 56
小結 59
習題 59
第4章
過程抽象的方法 62
4.1
基本思想 62
4.2
根據(jù)什么模塊化 63
4.3
對模塊接口的需要 63
4.3.1
參數(shù) 64
4.3.2
參數(shù)的三種基本類型 64
4.4
模塊的創(chuàng)建和使用 64
4.4.1
創(chuàng)建過程和函數(shù) 65
4.4.2
調用過程和函數(shù) 67
4.4.3
使用多個參數(shù) 68
4.5
參數(shù)表 71
4.6
數(shù)據(jù)作用域 71
4.6.1
作用域的三種有效范圍 72
4.6.2
變量的作用域 72
4.6.3
常量作用域 72
4.7
參數(shù)的類型 73
4.7.1
輸入?yún)?shù) 74
4.7.2
輸出參數(shù) 75
4.7.3
輸入/輸出參數(shù) 78
4.8
較大的范例 80
4.9
過程抽象的重要性 83
4.9.1
編寫算法 83
4.9.2
測試代碼 84
4.9.3
維護代碼 85
4.9.4
重用邏輯 85
4.9.5
在不同算法中重用編碼 87
4.10 遞歸控制 87
4.10.1 遞歸的兩種形式 88
4.10.2 跟蹤遞歸模塊的執(zhí)行 89
4.10.3 用遞歸解決問題 90
4.10.4 使用堆棧來跟蹤代碼 91
4.10.5 遞歸的作用 94
小結 96
習題 97
第5章
數(shù)據(jù)抽象的方法 102
5.1
數(shù)據(jù)的意義 102
5.2
組織多個數(shù)據(jù)塊 103
5.3
記錄 103
5.3.1
創(chuàng)建新的記錄數(shù)據(jù)類型 104
5.3.2
訪問記錄的數(shù)據(jù)域 105
5.4
類型與變量的區(qū)別 105
5.4.1
數(shù)據(jù)類型擴展了語言 105
5.4.2
數(shù)據(jù)類型的作用域 106
5.4.3
用戶自定義數(shù)據(jù)類型的抽象能力 106
5.4.4
匿名數(shù)據(jù)類型 107
5.5
指針 107
5.6
動態(tài)數(shù)據(jù)結構 109
5.7
鏈表 110
5.7.1
鏈表的結構 110
5.7.2
使用指針來訪問節(jié)點 111
5.7.3
使用指針來添加節(jié)點 115
5.7.4
使用指針來刪除節(jié)點 115
5.7.5
導航鏈表 117
5.7.6
遍歷鏈表 117
5.7.7
遞歸鏈表遍歷 117
5.7.8
遞歸鏈表的查找 120
5.7.9
簡化表達式的計算 120
5.7.10 建立鏈表 121
5.7.11 從鏈表中刪除值 124
5.7.12 鏈表特性小結 125
5.8
鏈接數(shù)據(jù)的作用域 125
5.8.1
靜態(tài)與動態(tài)變量 125
5.8.2
在鏈接數(shù)據(jù)的參數(shù)保護中的漏洞 128
5.9
二叉樹 129
5.9.1
遍歷二叉樹 130
5.9.2
二叉查找樹 132
5.9.3
中序遍歷BST 132
5.9.4
前序和后序遍歷 135
5.9.5
查找二叉查找樹 136
5.9.6
添加節(jié)點到BST中 138
5.9.7
從BST中刪除節(jié)點 138
5.10 圖 139
5.11 迭代控制 140
5.12 迭代與遞歸 143
5.13 數(shù)組 144
5.13.1
數(shù)組與鏈表 146
5.13.2
遍歷數(shù)組 146
5.13.3
查找數(shù)組 147
5.13.4
更有效的數(shù)組查找 147
5.14 常量的強大抽象能力 149
5.14.1
易修改性 149
5.14.2
可讀性 150
5.15 創(chuàng)建新數(shù)據(jù)類型的強大抽象能力 150
5.15.1
混合使用原子類型和復雜類型 151
5.15.2
記錄數(shù)組 151
5.15.3
記錄的記錄 154
5.15.4
數(shù)組的數(shù)組 155
小結 157
習題 158
第6章
構造算法的方法 162
6.1
遍歷 162
6.1.1
遍歷線性結構 162
6.1.2
遍歷非線性結構 163
6.1.3
堆棧和隊列 164
6.1.4
廣度優(yōu)先遍歷 167
6.1.5
廣度優(yōu)先遍歷的實現(xiàn) 169
6.2
查找 170
6.2.1
用遍歷實現(xiàn)簡單查找 170
6.2.2
關鍵字域 170
6.2.3
更有效的查找 171
6.3
排序 172
6.4
劃分與求解 173
6.5
優(yōu)化 176
6.5.1
貪心算法 176
6.5.2
動態(tài)編程 179
小結 181
習題 182
第7章
現(xiàn)實世界對象的建模方法 185
7.1
面向對象的范式 185
7.1.1
面向對象方法的優(yōu)勢 186
7.1.2
面向對象方法應具有的特征 186
7.2
實現(xiàn)良好的封裝性 186
7.2.1
過程抽象和數(shù)據(jù)抽象的局限性 187
7.2.2
抽象數(shù)據(jù)類型的概念 187
7.2.3
使用類定義抽象數(shù)據(jù)類型 188
7.2.4
使用對象來創(chuàng)建抽象數(shù)據(jù)類型的實例 190
7.3
類的剖析 190
7.3.1
public部分 192
7.3.2
protected部分 192
7.3.3
類中數(shù)據(jù)的作用域 193
7.3.4
說明 194
7.3.5
聲明和使用對象 194
7.4
類屬參數(shù)和可重用性 195
7.5
跟蹤對象行為的執(zhí)行 197
7.6
復制和克隆操作 198
7.7
實現(xiàn)良好的可適應性 201
7.7.1
繼承和擴展行為 201
7.7.2
重新定義繼承的標識 202
7.7.3
修改public/protected狀態(tài) 204
7.7.4
繼承類型小結 204
7.7.5
解決二義性 205
7.8
實現(xiàn)多態(tài)性 205
7.9
任何事物都是對象 208
小結 213
習題 214
第8章
驗證正確性的方法 218
8.1
Bug和調試 218
8.1.1
二義性 219
8.1.2
語法錯誤 219
8.1.3
語義錯誤 219
8.1.4
邏輯錯誤 221
8.2
證明算法的正確性 223
8.3
驗證法 225
8.4
能做的最重要的事情 225
小結 228
習題 228
第9章
估算成本和復雜度的方法 232
9.1
性能度量 232
9.2
工作度量 234
9.3
所做工作的分析 235
9.4
實際輸入與隨機輸入 236
9.5
增加復雜度 236
9.6
性能和數(shù)據(jù)結構 240
9.7
進一步增加復雜度 241
9.8
估算冒泡排序法的復雜度 243
9.9
合理算法和不合理算法 247
9.10 不合理算法的種類 250
小結 252
習題 252
第三部分
計算的局限性
第10章
并發(fā)與并行 256
10.1
概述：并發(fā)與并行 256
10.1.1
什么是并發(fā) 256
10.1.2
什么是并行 257
10.1.3
兩者之間的混淆 257
10.2
并發(fā) 258
10.2.1
多道程序設計 258
10.2.2
多重處理 258
10.2.3
多任務 258
10.2.4
分布式系統(tǒng) 259
10.3
并發(fā)中的問題 259
10.3.1
保護 259
10.3.2
公平性 259
10.3.3
死鎖 260
10.3.4
并發(fā)問題的總結 261
10.4
并行 261
10.5
并行的局限 263
10.5.1
處理器的固定數(shù)量 263
10.5.2
額外開銷 264
10.5.3
依賴 264
10.5.4
優(yōu)先順序 268
小結 271
習題 271
第11章
問題復雜度的層次 274
11.1
問題復雜度 274
11.2
開放式問題和閉合式問題 275
11.3
簡單問題和復雜問題 275
11.4
跨越界限的問題 276
11.5
NP完全問題 276
11.6
證明、預言和確定性 277
11.6.1
證明 278
11.6.2
預言 278
11.6.3
確定性與非確定性 279
11.7
NP完全問題和復雜問題 279
11.8
不可判定問題 279
11.8.1
不可判定問題的證明 281
小結 282
習題 283
第12章
計算與算法的歷史 285
12.1
原始范式 285
12.2
抽象的出現(xiàn) 285
12.3
完全抽象的范式 286
12.4
機械裝置的出現(xiàn) 286
12.5
機械論思想的范式 286
12.6
實時連接的出現(xiàn) 287
12.7
互聯(lián)過程范式 287
12.8
未來趨勢 288