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

第0章  導(dǎo)引   1
 0.1  算法的作用   1
 0.2  計(jì)算機(jī)器的由來   3
 0.3  算法的科學(xué)   7
 0.4  抽象   8
 0.5  學(xué)習(xí)綱要   9
 0.6  社會(huì)影響   11
 社會(huì)議題   11
 課外閱讀   13
 第1章  數(shù)據(jù)存儲(chǔ)   14
 1.1  位和它們的存儲(chǔ)   14
 1.1.1  布爾運(yùn)算   14
 1.1.2  門和觸發(fā)器   16
 1.1.3  其他存儲(chǔ)技術(shù)   19
 1.1.4  十六進(jìn)制記數(shù)法   19
 1.2  主存儲(chǔ)器   22
 1.2.1  存儲(chǔ)器結(jié)構(gòu)   22
 1.2.2  存儲(chǔ)器容量的度量   23
 1.3  大容量存儲(chǔ)器   24
 1.3.1  磁盤   25
 1.3.2  光盤   26
 1.3.3  磁帶   27
 1.3.4  文件存儲(chǔ)和檢索   28
 1.4  用位模式表示信息   30
 1.4.1  文本的表示   30
 1.4.2  數(shù)值的表示   31
 1.4.3  圖像的表示   32
 1.4.4  聲音的表示   33
 *1.5  二進(jìn)制系統(tǒng)   35
 1.5.1  二進(jìn)制記數(shù)法   35
 1.5.2  二進(jìn)制加法   37
 1.5.3  二進(jìn)制中的小數(shù)   38
 *1.6  整數(shù)的儲(chǔ)存   40
 1.6.1  二進(jìn)制補(bǔ)碼記數(shù)法   40
 1.6.2  二進(jìn)制余碼記數(shù)法   43
 *1.7  小數(shù)的儲(chǔ)存   45
 1.7.1  浮點(diǎn)記數(shù)法   46
 1.7.2  截?cái)嗾`差   48
 *1.8  數(shù)據(jù)壓縮   50
 1.8.1  通用數(shù)據(jù)壓縮技術(shù)   50
 1.8.2  圖像的壓縮   53
 *1.9  通信差錯(cuò)   54
 1.9.1  奇偶校驗(yàn)位   55
 1.9.2  差錯(cuò)糾正碼   56
 本章復(fù)習(xí)題   58
 社會(huì)議題   64
 課外閱讀   65
 第2章  數(shù)據(jù)操作   66
 2.1  計(jì)算機(jī)體系結(jié)構(gòu)   66
 2.2  機(jī)器語言   69
 2.2.1  指令系統(tǒng)   69
 2.2.2  示例性的機(jī)器語言   71
 2.3  程序的執(zhí)行   74
 2.3.1  程序執(zhí)行的一個(gè)例子   75
 2.3.2  程序與數(shù)據(jù)   78
 *2.4  算術(shù)/邏輯指令   81
 2.4.1  邏輯運(yùn)算   81
 2.4.2  循環(huán)移位和移位運(yùn)算   82
 2.4.3  算術(shù)運(yùn)算   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  多處理器計(jì)算機(jī)   91
 本章復(fù)習(xí)題   92
 社會(huì)議題   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)啟動(dòng)   109
 3.3  協(xié)調(diào)機(jī)器的活動(dòng)   110
 3.3.1  進(jìn)程的概念   110
 3.3.2  進(jìn)程管理   111
 *3.4  處理進(jìn)程間的競(jìng)爭(zhēng)   113
 3.4.1  信標(biāo)   113
 3.4.2  死鎖   115
 *3.5  安全性   117
 本章復(fù)習(xí)題   119
 社會(huì)議題   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  遠(yuǎn)程登錄   134
 4.3  萬維網(wǎng)   135
 4.3.1  萬維網(wǎng)實(shí)現(xiàn)   136
 4.3.2  HTML. 138
 4.3.3  XML. 140
 4.3.4  動(dòng)態(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
 社會(huì)議題   156
 課外閱讀   158
 第5章  算法   159
 5.1  算法的概念   159
 5.1.1  簡(jiǎn)單的回顧   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  軟件檢驗(yàn)   195
 本章復(fù)習(xí)題   200
 社會(huì)議題   207
 課外閱讀   208
 第6章  程序設(shè)計(jì)語言   209
 6.1  歷史回顧   209
 6.1.1  早幾代語言   209
 6.1.2  獨(dú)立于機(jī)器, 超越機(jī)器   212
 6.1.3  程序設(shè)計(jì)范型   213
 6.2  傳統(tǒng)的程序設(shè)計(jì)概念   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  語言實(shí)現(xiàn)   234
 6.4.1  翻譯過程   234
 6.4.2  連接和裝入   240
 6.4.3  軟件開發(fā)包   241
 *6.5  面向?qū)ο蟪绦蛟O(shè)計(jì)   243
 6.5.1  類和對(duì)象   243
 6.5.2  構(gòu)造函數(shù)   245
 6.5.3  其他特色   246
 *6.6  并發(fā)活動(dòng)的程序設(shè)計(jì)   248
 *6.7  說明型程序設(shè)計(jì)   251
 6.7.1  邏輯演繹   251
 6.7.2  Prolog. 254
 本章復(fù)習(xí)題   256
 社會(huì)議題   262
 課外閱讀   263
 第7章  軟件工程   265
 7.1  軟件工程學(xué)科   265
 7.2  軟件生命周期   267
 7.2.1　周期是個(gè)整體   267
 7.2.2　傳統(tǒng)的開發(fā)階段   268
 7.2.3　當(dāng)今趨勢(shì)   270
 7.3　模塊化   271
 7.3.1　模塊實(shí)現(xiàn)   271
 7.3.2　耦合   273
 7.3.3　內(nèi)聚性   275
 7.4  設(shè)計(jì)方法論   277
 7.4.1　自頂向下和自底向上   277
 7.4.2　設(shè)計(jì)模式   277
 7.4.3　開放源開發(fā)技術(shù)   278
 7.5　行業(yè)工具   280
 7.6  測(cè)試   283
 7.7　文檔編制   284
 7.8  軟件所有權(quán)和責(zé)任   286
 本章復(fù)習(xí)題   288
 社會(huì)議題   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)和動(dòng)態(tài)結(jié)構(gòu)   295
 8.1.4　指針   296
 8.2  數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)   297
 8.2.1　同構(gòu)型數(shù)組的存儲(chǔ)   297
 8.2.2　列表的存儲(chǔ)   299
 8.2.3　堆棧和隊(duì)列的存儲(chǔ)   301
 8.2.4　二叉樹的存儲(chǔ)   304
 8.2.5　數(shù)據(jù)結(jié)構(gòu)的操作   306
 8.3  一個(gè)簡(jiǎn)短案例的研究   308
 8.4  定制的數(shù)據(jù)類型   313
 8.4.1　用戶自定義數(shù)據(jù)類型   313
 8.4.2　抽象數(shù)據(jù)類型   314
 *8.5  類和對(duì)象   316
 *8.6  機(jī)器語言中的指針   318
 本章復(fù)習(xí)題   320
 社會(huì)議題   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è)計(jì)的問題   333
 9.2.2　關(guān)系運(yùn)算   337
 9.2.3　SQL. 341
 *9.3　面向?qū)ο髷?shù)據(jù)庫   343
 *9.4　維護(hù)數(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ù)的社會(huì)影響   357
 本章復(fù)習(xí)題   359
 社會(huì)議題   365
 課外閱讀   366
 第10章  人工智能   367
 10.1  智能與機(jī)器   367
 10.1.1　智能動(dòng)原體   367
 10.1.2  性能還是模擬   369
 10.1.3　圖靈測(cè)試   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　一個(gè)特定應(yīng)用   386
 10.4.3　聯(lián)想記憶   389
 10.5  遺傳算法   393
 10.6  其他研究領(lǐng)域   396
 10.6.1　語言處理   396
 10.6.2　機(jī)器人學(xué)   399
 10.6.3　數(shù)據(jù)庫系統(tǒng)   399
 10.6.4　專家系統(tǒng)   402
 10.7  后果的思考   403
 本章復(fù)習(xí)題   405
 社會(huì)議題   411
 課外閱讀   412
 第11章  計(jì)算理論   413
 11.1  函數(shù)及其計(jì)算   413
 11.2  圖靈機(jī)   415
 11.2.1　圖靈機(jī)原理   415
 11.2.2　丘奇-圖靈論題   417
 11.3  萬用程序設(shè)計(jì)語言   418
 11.3.1　Bare Bones（基本要素）語言   419
 11.3.2　用Bare Bones語言編程   421
 11.3.3　Bare Bones的萬用性   422
 11.4  一個(gè)不可計(jì)算的函數(shù)   424
 11.4.1　停機(jī)問題   424
 11.4.2　停機(jī)問題的不可解性   426
 11.5  問題的復(fù)雜性   429
 11.5.1　問題復(fù)雜性的度量   429
 11.5.2　多項(xiàng)式問題與非多項(xiàng)式問題   432
 11.5.3　不確定多項(xiàng)式問題   435
 *11.6  公鑰密碼學(xué)   437
 11.6.1　模表示法   438
 11.6.2　RSA公鑰密碼學(xué)   439
 本章復(fù)習(xí)題   441
 社會(huì)議題   446
 課外閱讀   447
 附錄A  ASCII代碼   448
 附錄B  處理補(bǔ)碼的電路   449
 附錄C  一個(gè)簡(jiǎn)單的機(jī)器語言   452
 附錄D  高級(jí)語言程序示例   454
 附錄E  迭代結(jié)構(gòu)與遞歸結(jié)構(gòu)的等價(jià)   461
 附錄F  問題與練習(xí)答案   463