計算機科學(xué)概論（原書第5版）

目　錄
Computer Science Illuminated, Fifth Edition
出版者的話
譯者序
前言
第一部分　基礎(chǔ)篇
第1章　全景圖 2
1.1　計算系統(tǒng) 2
1.1.1　計算系統(tǒng)的分層 3
1.1.2　抽象 4
1.2　計算的歷史 5
1.2.1　計算硬件簡史 5
1.2.2　計算軟件簡史 12
1.2.3　預(yù)言 16
1.3　計算工具與計算學(xué)科 16
小結(jié) 18
道德問題：the Tenth Strand 18
練習(xí) 19
思考題 20
第二部分　信息層
第2章　二進制數(shù)值與記數(shù)系統(tǒng) 22
2.1　數(shù)字與計算 22
2.2　位置記數(shù)法 23
2.2.1　二進制、八進制和十六進制 26
2.2.2　其他記數(shù)系統(tǒng)中的運算 27
2.2.3　以2的冪為基數(shù)的記數(shù)系統(tǒng) 27
2.2.4　把十進制數(shù)轉(zhuǎn)換成其他數(shù)制的數(shù) 29
2.2.5　二進制數(shù)值與計算機 29
小結(jié) 31
道德問題：the Tenth Strand的知識單元 31
練習(xí) 33
思考題 34
第3章　數(shù)據(jù)表示法 35
3.1　數(shù)據(jù)與計算機 35
3.1.1　模擬數(shù)據(jù)與數(shù)字?jǐn)?shù)據(jù) 36
3.1.2　二進制表示法 38
3.2　數(shù)字?jǐn)?shù)據(jù)表示法 39
3.2.1　負(fù)數(shù)表示法 39
3.2.2　實數(shù)表示法 42
3.3　文本表示法 44
3.3.1　ASCII字符集 45
3.3.2　Unicode字符集 45
3.3.3　文本壓縮 46
3.4　音頻數(shù)據(jù)表示法 49
3.4.1　音頻格式 50
3.4.2　MP3音頻格式 50
3.5　圖像與圖形表示法 51
3.5.1　顏色表示法 51
3.5.2　數(shù)字化圖像與圖形 52
3.5.3　圖形的矢量表示法 53
3.6　視頻表示法 53
小結(jié) 55
道德問題：道德準(zhǔn)則 55
練習(xí) 56
思考題 58
第三部分　硬件層
第4章　門和電路 60
4.1　計算機和電學(xué) 60
4.2　門 62
4.2.1　非門 62
4.2.2　與門 63
4.2.3　或門 63
4.2.4　異或門 64
4.2.5　與非門和或非門 64
4.2.6　門處理回顧 65
4.2.7　具有更多輸入的門 65
4.3　門的構(gòu)造 66
4.4　電路 67
4.4.1　組合電路 68
4.4.2　加法器 70
4.4.3　多路復(fù)用器 71
4.5　存儲器電路 72
4.6　集成電路 73
4.7　CPU芯片 73
小結(jié) 74
道德問題：這些違反道德規(guī)范嗎？ 74
練習(xí) 75
思考題 77
第5章　計算部件 78
5.1　獨立的計算機部件 78
5.2　存儲程序的概念 82
5.2.1　馮·諾伊曼體系結(jié)構(gòu) 82
5.2.2　讀取-執(zhí)行周期 87
5.2.3　RAM和ROM 88
5.2.4　二級存儲設(shè)備 89
5.2.5　觸摸屏 92
5.3　嵌入式系統(tǒng) 93
5.4　并行體系結(jié)構(gòu) 94
5.4.1　并行計算 94
5.4.2　并行硬件分類 95
小結(jié) 96
道德問題：數(shù)字鴻溝 96
練習(xí) 97
思考題 98
第四部分　程序設(shè)計層
第6章　低級程序設(shè)計語言與偽代碼 102
6.1　計算機操作 102
6.2　機器語言 103
6.3　一個程序?qū)嵗? 108
6.3.1　手工模擬 109
6.3.2　Pep/8模擬程序 109
6.4　匯編語言 111
6.4.1　Pep/8匯編語言 112
6.4.2　匯編器指令 112
6.4.3　Hello程序的匯編語言版本 113
6.4.4　一個新程序 113
6.4.5　具有分支的程序 115
6.4.6　具有循環(huán)的程序 116
6.5　表達算法 118
6.5.1　偽代碼的功能 118
6.5.2　執(zhí)行偽代碼算法 121
6.5.3　寫偽代碼算法 123
6.5.4　翻譯偽代碼算法 124
6.6　測試 125
小結(jié) 126
道德問題：版權(quán)與軟件盜版 127
練習(xí) 127
思考題 129
第7章　問題求解與算法設(shè)計 130
7.1　如何解決問題 130
7.1.1　提出問題 130
7.1.2　尋找熟悉的情況 132
7.1.3　分治法 132
7.1.4　算法 133
7.1.5　計算機問題求解過程 133
7.1.6　方法總結(jié) 134
7.1.7　測試算法 135
7.2　有簡單參數(shù)的算法 135
7.2.1　帶有選擇的算法 135
7.2.2　帶有循環(huán)的算法 136
7.3　復(fù)雜變量 139
7.3.1　數(shù)組 139
7.3.2　記錄 140
7.4　搜索算法 141
7.4.1　順序搜索 141
7.4.2　有序數(shù)組中的順序搜索 141
7.4.3　二分檢索 142
7.5　排序 144
7.5.1　選擇排序 144
7.5.2　冒泡排序 145
7.5.3　插入排序 147
7.6　遞歸算法 147
7.6.1　子程序語句 148
7.6.2　遞歸階乘 149
7.6.3　遞歸二分檢索 149
7.6.4　快速排序 150
7.7　幾個重要思想 153
7.7.1　信息隱蔽 153
7.7.2　抽象 154
7.7.3　事物命名 155
7.7.4　測試 155
小結(jié) 155
道德問題：開源軟件 156
練習(xí) 157
思考題 159
第8章　抽象數(shù)據(jù)類型與子程序 160
8.1　抽象數(shù)據(jù)類型 160
8.2　棧 161
8.3　隊列 161
8.4　列表 162
8.5　樹 164
8.5.1　二叉樹 164
8.5.2　二叉檢索樹 165
8.5.3　其他操作 169
8.6　圖 169
8.6.1　創(chuàng)建圖 171
8.6.2　圖算法 171
8.7　子程序 176
8.7.1　參數(shù)傳遞 177
8.7.2　值參與引用參數(shù) 178
小結(jié) 180
道德問題：工作場所監(jiān)視 180
練習(xí) 181
思考題 183
第9章　面向?qū)ο笤O(shè)計與高級程序設(shè)計語言 184
9.1　面向?qū)ο蠓椒? 184
9.1.1　面向?qū)ο? 185
9.1.2　設(shè)計方法 185
9.1.3　一個計算機示例 187
9.2　翻譯過程 189
9.2.1　編譯器 190
9.2.2　解釋器 190
9.3　程序設(shè)計語言的范型 192
9.3.1　命令式范型 192
9.3.2　聲明式范型 193
9.4　高級程序設(shè)計語言的功能性 194
9.4.1　布爾表達式 194
9.4.2　數(shù)據(jù)歸類 196
9.4.3　輸入/輸出結(jié)構(gòu) 199
9.4.4　控制結(jié)構(gòu) 200
9.5　面向?qū)ο笳Z言的功能性 204
9.5.1　封裝 204
9.5.2　類 205
9.5.3　繼承 206
9.5.4　多態(tài) 207
9.6　過程設(shè)計與面向?qū)ο笤O(shè)計的區(qū)別 207
小結(jié) 208
道德問題：惡作劇與詐騙 209
練習(xí) 210
思考題 212
第五部分　操作系統(tǒng)層
第10章　操作系統(tǒng) 214
10.1　操作系統(tǒng)的角色 214
10.1.1　內(nèi)存、進程與CPU管理 216
10.1.2　批處理 216
10.1.3　分時 217
10.1.4　其他OS要素 218
10.2　內(nèi)存管理 218
10.2.1　單塊內(nèi)存管理 219
10.2.2　分區(qū)內(nèi)存管理 220
10.2.3　頁式內(nèi)存管理 221
10.3　進程管理 223
10.3.1　進程狀態(tài) 223
10.3.2　進程控制塊 224
10.4　CPU調(diào)度 224
10.4.1　先到先服務(wù) 225
10.4.2　最短作業(yè)優(yōu)先 226
10.4.3　輪詢法 226
小結(jié) 227
道德問題：醫(yī)療隱私——健康保險攜帶與責(zé)任法案 228
練習(xí) 229
思考題 231
第11章　文件系統(tǒng)和目錄 232
11.1　文件系統(tǒng) 232
11.1.1　文本文件和二進制文件 233
11.1.2　文件類型 233
11.1.3　文件操作 234
11.1.4　文件訪問 235
11.1.5　文件保護 236
11.2　目錄 237
11.2.1　目錄樹 237
11.2.2　路徑名 239
11.3　磁盤調(diào)度 241
11.3.1　先到先服務(wù)磁盤調(diào)度法 242
11.3.2　最短尋道時間優(yōu)先磁盤調(diào)度法 242
11.3.3　SCAN磁盤調(diào)度法 242
小結(jié) 243
道德問題：選擇加入和選擇退出 243
練習(xí) 244
思考題 246
第六部分　應(yīng)用程序?qū)?br />第12章　信息系統(tǒng) 248
12.1　信息管理 248
12.2　電子制表軟件 249
12.2.1　電子數(shù)據(jù)表公式 250
12.2.2　循環(huán)引用 254
12.2.3　電子數(shù)據(jù)表分析 254
12.3　數(shù)據(jù)庫管理系統(tǒng) 255
12.3.1　關(guān)系模型 256
12.3.2　關(guān)系 257
12.3.3　結(jié)構(gòu)化查詢語言 258
12.3.4　數(shù)據(jù)庫設(shè)計 260
12.4　電子商務(wù) 261
小結(jié) 262
道德問題：從競選來看政治與網(wǎng)絡(luò) 262
練習(xí) 263
思考題 265
第13章　人工智能 266
13.1　思維機 266
13.1.1　圖靈測試 267
13.1.2　AI問題的各個方面 268
13.2　知識表示 268
13.2.1　語義網(wǎng) 268
13.2.2　檢索樹 271
13.3　專家系統(tǒng) 273
13.4　神經(jīng)網(wǎng)絡(luò) 275
13.4.1　生物神經(jīng)網(wǎng)絡(luò) 275
13.4.2　人工神經(jīng)網(wǎng)絡(luò) 276
13.5　自然語言處理 277
13.5.1　語音合成 277
13.5.2　語音識別 278
13.5.3　自然語言理解 279
13.6　機器人學(xué) 280
13.6.1　感知-規(guī)劃-執(zhí)行范型 280
13.6.2　包孕體系結(jié)構(gòu) 282
13.6.3　物理部件 283
小結(jié) 283
道德問題：從民眾來看政治與網(wǎng)絡(luò) 284
練習(xí) 284
思考題 286
第14章　模擬、圖形學(xué)、游戲和其他應(yīng)用 287
14.1　什么是模擬 287
14.1.1　復(fù)雜系統(tǒng) 287
14.1.2　模型 288
14.1.3　構(gòu)造模型 288
14.2　特殊模型 289
14.2.1　排隊系統(tǒng) 289
14.2.2　氣象模型 292
14.2.3　計算生物學(xué) 295
14.2.4　其他模型 295
14.2.5　必要的計算能力 296
14.3　計算機圖形學(xué) 296
14.3.1　光的工作原理 297
14.3.2　物體形狀 298
14.3.3　光模擬 298
14.3.4　復(fù)雜對象的建模 299
14.3.5　讓物體動起來 303
14.4　游戲 304
14.4.1　游戲的歷史 304
14.4.2　創(chuàng)建虛擬世界 305
14.4.3　游戲設(shè)計與開發(fā) 305
14.4.4　游戲編程 306
小結(jié) 307
道德問題：游戲成癮 307
練習(xí) 308
思考題 309
第七部分　通信層
第15章　網(wǎng)絡(luò) 312
15.1　連網(wǎng) 312
15.1.1　網(wǎng)絡(luò)的類型 313
15.1.2　Internet連接 315
15.1.3　包交換 317
15.2　開放式系統(tǒng)與協(xié)議 318
15.2.1　開放式系統(tǒng) 318
15.2.2　網(wǎng)絡(luò)協(xié)議 319
15.2.3　TCP/IP 319
15.2.4　高層協(xié)議 320
15.2.5　MIME類型 321
15.2.6　防火墻 321
15.3　網(wǎng)絡(luò)地址 322
15.4　云計算 324
小結(jié) 325
道德問題：社交網(wǎng)絡(luò)的影響 326
練習(xí) 327
思考題 328
第16章　萬維網(wǎng) 329
16.1　Web簡介 329
16.1.1　搜索引擎 331
16.1.2　即時消息 331
16.1.3　博客 331
16.1.4　cookie 332
16.2　HTML 333
16.2.1　基本的HTML格式 335
16.2.2　圖像與鏈接 335
16.2.3　HTML5 337
16.3　交互式網(wǎng)頁 337
16.3.1　Java小程序 337
16.3.2　Java服務(wù)器頁 338
16.4　XML 339
16.5　社交網(wǎng)絡(luò) 341
小結(jié) 342
道德問題：賭博與互聯(lián)網(wǎng) 344
練習(xí) 344
思考題 346
第17章　計算機安全 347
17.1　各級安全 347
17.2　阻止未授權(quán)訪問 349
17.2.1　密碼 349
17.2.2　驗證碼 351
17.2.3　指紋分析 352
17.3　惡意代碼 352
17.3.1　殺毒軟件 353
17.3.2　安全攻擊 353
17.4　密碼學(xué) 355
17.5　保護你的在線信息 357
17.5.1　安全與可移動設(shè)備 359
17.5.2　維基解密 359
小結(jié) 360
道德問題：博客 361
練習(xí) 362
思考題 363
第八部分　總結(jié)
第18章　計算的限制 366
18.1　硬件 366
18.1.1　算術(shù)運算的限制 366
18.1.2　部件的限制 370
18.1.3　通信的限制 371
18.2　軟件 372
18.2.1　軟件的復(fù)雜度 372
18.2.2　當(dāng)前提高軟件質(zhì)量的方法 373
18.2.3　臭名昭著的軟件錯誤 376
18.3　問題 377
18.3.1　算法比較 377
18.3.2　圖靈機 382
18.3.3　停機問題 384
18.3.4　算法分類 386
小結(jié) 387
道德問題：Therac-25災(zāi)難剖析 387
練習(xí) 388
思考題 389
參考文獻 390
索引 396