計(jì)算與算法導(dǎo)論

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