計算機科學(xué)概論（第八版）

第0章  導(dǎo)引   1
 0.1  算法的作用   1
 0.2  計算機器的由來   3
 0.3  算法的科學(xué)   7
 0.4  抽象   8
 0.5  學(xué)習(xí)綱要   9
 0.6  社會影響   11
 社會議題   11
 課外閱讀   13
 第1章  數(shù)據(jù)存儲   14
 1.1  位和它們的存儲   14
 1.1.1  布爾運算   14
 1.1.2  門和觸發(fā)器   16
 1.1.3  其他存儲技術(shù)   19
 1.1.4  十六進制記數(shù)法   19
 1.2  主存儲器   22
 1.2.1  存儲器結(jié)構(gòu)   22
 1.2.2  存儲器容量的度量   23
 1.3  大容量存儲器   24
 1.3.1  磁盤   25
 1.3.2  光盤   26
 1.3.3  磁帶   27
 1.3.4  文件存儲和檢索   28
 1.4  用位模式表示信息   30
 1.4.1  文本的表示   30
 1.4.2  數(shù)值的表示   31
 1.4.3  圖像的表示   32
 1.4.4  聲音的表示   33
 *1.5  二進制系統(tǒng)   35
 1.5.1  二進制記數(shù)法   35
 1.5.2  二進制加法   37
 1.5.3  二進制中的小數(shù)   38
 *1.6  整數(shù)的儲存   40
 1.6.1  二進制補碼記數(shù)法   40
 1.6.2  二進制余碼記數(shù)法   43
 *1.7  小數(shù)的儲存   45
 1.7.1  浮點記數(shù)法   46
 1.7.2  截斷誤差   48
 *1.8  數(shù)據(jù)壓縮   50
 1.8.1  通用數(shù)據(jù)壓縮技術(shù)   50
 1.8.2  圖像的壓縮   53
 *1.9  通信差錯   54
 1.9.1  奇偶校驗位   55
 1.9.2  差錯糾正碼   56
 本章復(fù)習(xí)題   58
 社會議題   64
 課外閱讀   65
 第2章  數(shù)據(jù)操作   66
 2.1  計算機體系結(jié)構(gòu)   66
 2.2  機器語言   69
 2.2.1  指令系統(tǒng)   69
 2.2.2  示例性的機器語言   71
 2.3  程序的執(zhí)行   74
 2.3.1  程序執(zhí)行的一個例子   75
 2.3.2  程序與數(shù)據(jù)   78
 *2.4  算術(shù)/邏輯指令   81
 2.4.1  邏輯運算   81
 2.4.2  循環(huán)移位和移位運算   82
 2.4.3  算術(shù)運算   84
 2.5  與其他設(shè)備的通信   85
 2.5.1  通信與控制器   85
 2.5.2  數(shù)據(jù)通信速率   88
 *2.6  其他體系結(jié)構(gòu)   90
 2.6.1  流水線   90
 2.6.2  多處理器計算機   91
 本章復(fù)習(xí)題   92
 社會議題   99
 課外閱讀   100
 第3章  操作系統(tǒng)   101
 3.1  操作系統(tǒng)的發(fā)展   101
 3.2  操作系統(tǒng)的體系結(jié)構(gòu)   104
 3.2.1  軟件綜述   105
 3.2.2  操作系統(tǒng)的組件   106
 3.2.3  系統(tǒng)啟動   109
 3.3  協(xié)調(diào)機器的活動   110
 3.3.1  進程的概念   110
 3.3.2  進程管理   111
 *3.4  處理進程間的競爭   113
 3.4.1  信標   113
 3.4.2  死鎖   115
 *3.5  安全性   117
 本章復(fù)習(xí)題   119
 社會議題   122
 課外閱讀   123
 第4章  組網(wǎng)和因特網(wǎng)   124
 4.1  網(wǎng)絡(luò)基礎(chǔ)   124
 4.1.1  網(wǎng)絡(luò)分類   124
 4.1.2  客戶/服務(wù)器模式   126
 4.1.3  分布式系統(tǒng)   129
 4.2  因特網(wǎng)   130
 4.2.1  因特網(wǎng)體系結(jié)構(gòu)   130
 4.2.2  因特網(wǎng)編址   131
 4.2.3  電子郵件   133
 4.2.4  文件傳輸協(xié)議   134
 4.2.5  遠程登錄   134
 4.3  萬維網(wǎng)   135
 4.3.1  萬維網(wǎng)實現(xiàn)   136
 4.3.2  HTML. 138
 4.3.3  XML. 140
 4.3.4  動態(tài)網(wǎng)頁   142
 *4.4  網(wǎng)絡(luò)協(xié)議   144
 4.4.1  傳輸權(quán)的控制   144
 4.4.2  因特網(wǎng)軟件分層方法   146
 4.4.3  TCP/IP協(xié)議組   150
 4.5  安全性   151
 本章復(fù)習(xí)題   154
 社會議題   156
 課外閱讀   158
 第5章  算法   159
 5.1  算法的概念   159
 5.1.1  簡單的回顧   159
 5.1.2  算法的形式定義   160
 5.1.3  算法的抽象本質(zhì)   161
 5.2  算法的表示   162
 5.2.1  原語   162
 5.2.2  偽代碼   164
 5.3  算法的發(fā)現(xiàn)   169
 5.3.1  問題求解的藝術(shù)   169
 5.3.2  跨入門檻   171
 5.4  循環(huán)結(jié)構(gòu)   175
 5.4.1  順序查找算法   176
 5.4.2  循環(huán)控制   177
 5.4.3  插入排序算法   180
 5.5  遞歸結(jié)構(gòu)   185
 5.5.1  二分查找算法   185
 5.5.2  遞歸控制   190
 5.6  有效性和正確性   191
 5.6.1  算法的有效性   192
 5.6.2  軟件檢驗   195
 本章復(fù)習(xí)題   200
 社會議題   207
 課外閱讀   208
 第6章  程序設(shè)計語言   209
 6.1  歷史回顧   209
 6.1.1  早幾代語言   209
 6.1.2  獨立于機器, 超越機器   212
 6.1.3  程序設(shè)計范型   213
 6.2  傳統(tǒng)的程序設(shè)計概念   217
 6.2.1  變量和數(shù)據(jù)類型   218
 6.2.2  數(shù)據(jù)結(jié)構(gòu)   220
 6.2.3  常量和直接量   222
 6.2.4  賦值語句   223
 6.2.5  控制語句   224
 6.2.6  注解   226
 6.3  過程單元   227
 6.3.1  過程   227
 6.3.2  參數(shù)   229
 6.3.3  函數(shù)   232
 6.4  語言實現(xiàn)   234
 6.4.1  翻譯過程   234
 6.4.2  連接和裝入   240
 6.4.3  軟件開發(fā)包   241
 *6.5  面向?qū)ο蟪绦蛟O(shè)計   243
 6.5.1  類和對象   243
 6.5.2  構(gòu)造函數(shù)   245
 6.5.3  其他特色   246
 *6.6  并發(fā)活動的程序設(shè)計   248
 *6.7  說明型程序設(shè)計   251
 6.7.1  邏輯演繹   251
 6.7.2  Prolog. 254
 本章復(fù)習(xí)題   256
 社會議題   262
 課外閱讀   263
 第7章  軟件工程   265
 7.1  軟件工程學(xué)科   265
 7.2  軟件生命周期   267
 7.2.1　周期是個整體   267
 7.2.2　傳統(tǒng)的開發(fā)階段   268
 7.2.3　當今趨勢   270
 7.3　模塊化   271
 7.3.1　模塊實現(xiàn)   271
 7.3.2　耦合   273
 7.3.3　內(nèi)聚性   275
 7.4  設(shè)計方法論   277
 7.4.1　自頂向下和自底向上   277
 7.4.2　設(shè)計模式   277
 7.4.3　開放源開發(fā)技術(shù)   278
 7.5　行業(yè)工具   280
 7.6  測試   283
 7.7　文檔編制   284
 7.8  軟件所有權(quán)和責(zé)任   286
 本章復(fù)習(xí)題   288
 社會議題   291
 課外閱讀   292
 第8章  數(shù)據(jù)抽象   293
 8.1  數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)   293
 8.1.1　基本數(shù)據(jù)結(jié)構(gòu)   293
 8.1.2　抽象   294
 8.1.3　靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu)   295
 8.1.4　指針   296
 8.2  數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)   297
 8.2.1　同構(gòu)型數(shù)組的存儲   297
 8.2.2　列表的存儲   299
 8.2.3　堆棧和隊列的存儲   301
 8.2.4　二叉樹的存儲   304
 8.2.5　數(shù)據(jù)結(jié)構(gòu)的操作   306
 8.3  一個簡短案例的研究   308
 8.4  定制的數(shù)據(jù)類型   313
 8.4.1　用戶自定義數(shù)據(jù)類型   313
 8.4.2　抽象數(shù)據(jù)類型   314
 *8.5  類和對象   316
 *8.6  機器語言中的指針   318
 本章復(fù)習(xí)題   320
 社會議題   327
 課外閱讀   328
 第9章  數(shù)據(jù)庫系統(tǒng)   329
 9.1　數(shù)據(jù)庫原理   329
 9.1.1　模式的作用   329
 9.1.2　數(shù)據(jù)庫管理系統(tǒng)   331
 9.1.3　數(shù)據(jù)庫模型   332
 9.2　關(guān)系模型   333
 9.2.1　關(guān)系設(shè)計的問題   333
 9.2.2　關(guān)系運算   337
 9.2.3　SQL. 341
 *9.3　面向?qū)ο髷?shù)據(jù)庫   343
 *9.4　維護數(shù)據(jù)庫的完整性   345
 9.4.1　提交/轉(zhuǎn)返協(xié)議   346
 9.4.2　鎖定   347
 *9.5　傳統(tǒng)的文件結(jié)構(gòu)   348
 9.5.1　順序文件   348
 9.5.2　索引文件   351
 9.5.3　散列文件   352
 9.6  數(shù)據(jù)挖掘   355
 9.7  數(shù)據(jù)庫技術(shù)的社會影響   357
 本章復(fù)習(xí)題   359
 社會議題   365
 課外閱讀   366
 第10章  人工智能   367
 10.1  智能與機器   367
 10.1.1　智能動原體   367
 10.1.2  性能還是模擬   369
 10.1.3　圖靈測試   370
 10.2　理解圖像   371
 10.3  推理   374
 10.3.1　產(chǎn)生式系統(tǒng)   374
 10.3.2　搜索樹   376
 10.3.3　試探法   378
 10.4  人工神經(jīng)網(wǎng)絡(luò)   383
 10.4.1　基本特性   384
 10.4.2　一個特定應(yīng)用   386
 10.4.3　聯(lián)想記憶   389
 10.5  遺傳算法   393
 10.6  其他研究領(lǐng)域   396
 10.6.1　語言處理   396
 10.6.2　機器人學(xué)   399
 10.6.3　數(shù)據(jù)庫系統(tǒng)   399
 10.6.4　專家系統(tǒng)   402
 10.7  后果的思考   403
 本章復(fù)習(xí)題   405
 社會議題   411
 課外閱讀   412
 第11章  計算理論   413
 11.1  函數(shù)及其計算   413
 11.2  圖靈機   415
 11.2.1　圖靈機原理   415
 11.2.2　丘奇-圖靈論題   417
 11.3  萬用程序設(shè)計語言   418
 11.3.1　Bare Bones（基本要素）語言   419
 11.3.2　用Bare Bones語言編程   421
 11.3.3　Bare Bones的萬用性   422
 11.4  一個不可計算的函數(shù)   424
 11.4.1　停機問題   424
 11.4.2　停機問題的不可解性   426
 11.5  問題的復(fù)雜性   429
 11.5.1　問題復(fù)雜性的度量   429
 11.5.2　多項式問題與非多項式問題   432
 11.5.3　不確定多項式問題   435
 *11.6  公鑰密碼學(xué)   437
 11.6.1　模表示法   438
 11.6.2　RSA公鑰密碼學(xué)   439
 本章復(fù)習(xí)題   441
 社會議題   446
 課外閱讀   447
 附錄A  ASCII代碼   448
 附錄B  處理補碼的電路   449
 附錄C  一個簡單的機器語言   452
 附錄D  高級語言程序示例   454
 附錄E  迭代結(jié)構(gòu)與遞歸結(jié)構(gòu)的等價   461
 附錄F  問題與練習(xí)答案   463