計(jì)算機(jī)科學(xué)概論（原書(shū)第2版）

第一部分  基  礎(chǔ)  篇
第1章  全景圖        1
1.1  計(jì)算系統(tǒng)        1
1.1.1  計(jì)算系統(tǒng)的分層        2
1.1.2  抽象        3
1.2  計(jì)算的歷史        5
1.2.1  計(jì)算硬件的簡(jiǎn)史        5
1.2.2  計(jì)算軟件的簡(jiǎn)史        11
1.2.3  預(yù)言        14
1.3  計(jì)算工具和計(jì)算學(xué)科        15
小結(jié)        16
練習(xí)        17
思考題        19
第二部分  信  息  層
第2章  二進(jìn)制數(shù)值和記數(shù)系統(tǒng)        21
2.1  數(shù)字分類        21
2.2  自然數(shù)        22
2.2.1  位置記數(shù)法        22
2.2.2  二進(jìn)制、八進(jìn)制和十六進(jìn)制        25
2.2.3  其他記數(shù)系統(tǒng)中的運(yùn)算        26
2.2.4  以2的冪為基數(shù)的記數(shù)系統(tǒng)        26
2.2.5  把十進(jìn)制數(shù)轉(zhuǎn)換成其他數(shù)制的數(shù)        28
2.2.6  二進(jìn)制數(shù)值和計(jì)算機(jī)        29
小結(jié)        30
練習(xí)        31
思考題        33
第3章  數(shù)據(jù)表示法        34
3.1  數(shù)據(jù)和計(jì)算機(jī)        34
3.1.1  模擬信息和數(shù)字信息        35
3.1.2  二進(jìn)制表示法        36
3.2  數(shù)字?jǐn)?shù)據(jù)的表示法        38
3.2.1  負(fù)數(shù)表示法        38
3.2.2  實(shí)數(shù)表示法        40
3.3  文本表示法        42
3.3.1  ASCII字符集        43
3.3.2  Unicode字符集        43
3.3.3  文本壓縮        44
3.4  音頻信息表示法        47
3.4.1  音頻格式        48
3.4.2  MP3音頻格式        48
3.5  圖像和圖形的表示法        49
3.5.1  顏色表示法        49
3.5.2  數(shù)字化圖像和圖形        50
3.5.3  圖形的矢量表示法        51
3.6  視頻表示法        52
小結(jié)        53
練習(xí)        54
思考題        57
第三部分  硬  件  層
第4章  門(mén)和電路        59
4.1  計(jì)算機(jī)和電學(xué)        59
4.2  門(mén)        61
4.2.1  非門(mén)        61
4.2.2  與門(mén)        62
4.2.3  或門(mén)        62
4.2.4  異或門(mén)        63
4.2.5  與非門(mén)和或非門(mén)        63
4.2.6  門(mén)處理回顧        64
4.2.7  具有更多輸入的門(mén)        64
4.3  門(mén)的構(gòu)造        65
4.4  電路        66
4.4.1  組合電路        67
4.4.2  加法器        69
4.4.3  多路復(fù)用器        71
4.5  存儲(chǔ)器電路        71
4.6  集成電路        72
4.7  CPU芯片        73
小結(jié)        73
練習(xí)        74
思考題        77
第5章  計(jì)算部件        78
5.1  獨(dú)立的計(jì)算機(jī)部件        78
5.2  存儲(chǔ)程序的概念        80
5.2.1  von Neumann體系結(jié)構(gòu)        81
5.2.2  讀取-執(zhí)行周期        85
5.2.3  RAM和ROM        86
5.2.4  二級(jí)存儲(chǔ)設(shè)備        87
5.2.5  觸摸屏        90
5.3  非von Neumann體系結(jié)構(gòu)        91
5.4  廣告解析        92
小結(jié)        92
練習(xí)        94
思考題        96
第四部分  程序設(shè)計(jì)層
第6章  問(wèn)題求解和算法設(shè)計(jì)        97
6.1  問(wèn)題求解        97
6.1.1  如何解決問(wèn)題        98
6.1.2  計(jì)算機(jī)問(wèn)題求解        101
6.1.3  執(zhí)行算法        103
6.1.4  開(kāi)發(fā)算法        104
6.2  自頂向下設(shè)計(jì)        104
6.2.1  一個(gè)通用的實(shí)例        105
6.2.2  一個(gè)計(jì)算機(jī)實(shí)例        106
6.2.3  方法總結(jié)        110
6.2.4  測(cè)試算法        110
6.3  面向?qū)ο笤O(shè)計(jì)        112
6.3.1  面向?qū)ο?nbsp;       112
6.3.2  類之間的關(guān)系        113
6.3.3  面向?qū)ο笤O(shè)計(jì)方法        114
6.3.4  一個(gè)通用的實(shí)例        117
6.3.5  一個(gè)計(jì)算機(jī)實(shí)例        118
6.4  幾個(gè)重要思想        121
6.4.1  信息隱蔽        121
6.4.2  抽象        122
6.4.3  事物命名        123
6.4.4  程序設(shè)計(jì)語(yǔ)言        123
6.4.5  測(cè)試        124
小結(jié)        124
練習(xí)        125
思考題        128
第7章  低級(jí)程序設(shè)計(jì)語(yǔ)言        129
7.1  計(jì)算機(jī)操作        129
7.2  抽象的分層        130
7.3  機(jī)器語(yǔ)言        130
7.4  一個(gè)程序?qū)嵗?nbsp;       135
7.4.1  問(wèn)題和算法        135
7.4.2  程序        136
7.5  匯編語(yǔ)言        139
7.5.1  Pep/7匯編語(yǔ)言        140
7.5.2  具有分支的程序        144
7.6  其他的重要思想        145
小結(jié)        148
練習(xí)        149
思考題        151
第8章  高級(jí)程序設(shè)計(jì)語(yǔ)言        152
8.1  翻譯過(guò)程        152
8.1.1  編譯器        152
8.1.2  解釋器        153
8.2  程序設(shè)計(jì)語(yǔ)言的范型        155
8.3  命令式語(yǔ)言的功能性        156
8.3.1  Boolean表達(dá)式        156
8.3.2  強(qiáng)類型化        158
8.3.3  輸入/輸出結(jié)構(gòu)        161
8.3.4  控制結(jié)構(gòu)        163
8.3.5  復(fù)合數(shù)據(jù)類型        174
8.4  面向?qū)ο笳Z(yǔ)言的功能性        177
8.4.1  封裝        177
8.4.2  繼承        178
8.4.3  多態(tài)性        178
小結(jié)        178
練習(xí)        180
思考題        184
第9章  抽象數(shù)據(jù)類型和算法        185
9.1  抽象數(shù)據(jù)類型        185
9.2  實(shí)現(xiàn)        186
9.2.1  基于數(shù)組的實(shí)現(xiàn)        186
9.2.2  鏈?zhǔn)綄?shí)現(xiàn)        187
9.3  列表        189
9.3.1  列表的基礎(chǔ)操作        189
9.3.2  其他列表操作        192
9.4  排序        192
9.4.1  選擇排序        193
9.4.2  冒泡排序法        194
9.4.3  快速排序        195
9.5  二分檢索法        199
9.6  棧和隊(duì)列        200
9.6.1  棧        201
9.6.2  隊(duì)列        202
9.6.3  實(shí)現(xiàn)        202
9.7  樹(shù)        202
9.7.1  二叉樹(shù)        203
9.7.2  二叉檢索樹(shù)        204
9.7.3  其他操作        207
9.7.4  圖        208
9.8  程序設(shè)計(jì)庫(kù)        209
小結(jié)        209
練習(xí)        210
思考題        213
第五部分  操作系統(tǒng)層
第10章  操作系統(tǒng)        215
10.1  操作系統(tǒng)的角色        215
10.1.1  內(nèi)存、進(jìn)程和CPU管理        216
10.1.2  批處理        217
10.1.3  分時(shí)操作        218
10.1.4  其他OS要素        219
10.2  內(nèi)存管理        219
10.2.1  單塊內(nèi)存管理        220
10.2.2  分區(qū)內(nèi)存管理        221
10.2.3  頁(yè)式內(nèi)存管理        222
10.3  進(jìn)程管理        224
10.3.1  進(jìn)程狀態(tài)        224
10.3.2  進(jìn)程控制塊        225
10.4  CPU調(diào)度        225
10.4.1  先到先服務(wù)        226
10.4.2  最短作業(yè)優(yōu)先        227
10.4.3  循環(huán)調(diào)度法        227
小結(jié)        228
練習(xí)        230
思考題        234
第11章  文件系統(tǒng)和目錄        235
11.1  文件系統(tǒng)        235
11.1.1  文本文件和二進(jìn)制文件        236
11.1.2  文件類型        236
11.1.3  文件操作        237
11.1.4  文件訪問(wèn)        238
11.1.5  文件保護(hù)        239
11.2  目錄        240
11.2.1  目錄樹(shù)        240
11.2.2  路徑名        241
11.3  磁盤(pán)調(diào)度        244
11.3.1  先到先服務(wù)磁盤(pán)調(diào)度法        245
11.3.2  最短尋道時(shí)間優(yōu)先磁盤(pán)調(diào)度法        245
11.3.3  SCAN磁盤(pán)調(diào)度法        246
小結(jié)        246
練習(xí)        247
思考題        250
第六部分  應(yīng)用程序?qū)?br />第12章  信息系統(tǒng)        251
12.1  信息管理        251
12.2  電子制表軟件        252
12.2.1  電子數(shù)據(jù)表公式        253
12.2.2  循環(huán)引用        257
12.2.3  電子數(shù)據(jù)表分析        257
12.3  數(shù)據(jù)庫(kù)管理系統(tǒng)        258
12.3.1  關(guān)系模型        259
12.3.2  關(guān)系        260
12.3.3  結(jié)構(gòu)化查詢語(yǔ)言        262
12.3.4  數(shù)據(jù)庫(kù)設(shè)計(jì)        263
小結(jié)        264
練習(xí)        265
思考題        268
第13章  人工智能        269
13.1  思維機(jī)        269
13.1.1  圖靈測(cè)試        270
13.1.2  AI問(wèn)題的各個(gè)方面        271
13.2  知識(shí)表達(dá)        271
13.2.1  語(yǔ)義網(wǎng)絡(luò)        272
13.2.2  檢索樹(shù)        274
13.3  專家系統(tǒng)        276
13.4  神經(jīng)網(wǎng)絡(luò)        278
13.4.1  生物神經(jīng)網(wǎng)絡(luò)        278
13.4.2  人工神經(jīng)網(wǎng)絡(luò)        279
13.5  自然語(yǔ)言處理        280
13.5.1  語(yǔ)音合成        281
13.5.2  語(yǔ)音識(shí)別        282
13.5.3  自然語(yǔ)言理解        283
13.6  機(jī)器人學(xué)        283
13.6.1  感知-規(guī)劃-執(zhí)行范型        285
13.6.2  包孕體系結(jié)構(gòu)        285
13.6.3  物理部件        286
小結(jié)        288
練習(xí)        289
思考題        291
第14章  模擬和其他應(yīng)用程序        292
14.1  什么是模擬        292
14.1.1  復(fù)雜系統(tǒng)        292
14.1.2  模型        293
14.1.3  構(gòu)造模型        293
14.1.4  排隊(duì)系統(tǒng)        294
14.1.5  氣象模型        297
14.1.6  其他模型        300
14.1.7  必要的計(jì)算能力        300
14.2  圖形和計(jì)算機(jī)輔助設(shè)計(jì)        301
14.3  嵌入式系統(tǒng)        302
小結(jié)        303
練習(xí)        304
思考題        306
第七部分  通  信  層
第15章  網(wǎng)絡(luò)        307
15.1  連網(wǎng)        307
15.1.1  網(wǎng)絡(luò)的類型        308
15.1.2  Internet連接        310
15.1.3  包交換        312
15.1.4  GPS尋寶        313
15.2  開(kāi)放式系統(tǒng)和協(xié)議        313
15.2.1  開(kāi)放式系統(tǒng)        313
15.2.2  網(wǎng)絡(luò)協(xié)議        314
15.2.3  TCP/IP        314
15.2.4  高層協(xié)議        315
15.2.5  MIME類型        316
15.2.6  防火墻        316
15.3  網(wǎng)絡(luò)地址        317
小結(jié)        319
練習(xí)        321
思考題        323
第16章  萬(wàn)維網(wǎng)        324
16.1  Web簡(jiǎn)介        324
16.1.1  搜索引擎        325
16.1.2  即時(shí)消息        326
16.1.3  cookie        326
16.2  HTML        327
16.2.1  基本的HTML格式        329
16.2.2  圖像和鏈接        330
16.3  交互式Web頁(yè)        331
16.3.1  Java小程序        332
16.3.2  Java服務(wù)器頁(yè)        332
16.4  XML        333
小結(jié)        336
練習(xí)        337
思考題        340
第八部分  總      結(jié)
第17章  計(jì)算的限制        341
17.1  硬件        341
17.1.1  算術(shù)運(yùn)算的限制        341
17.1.2  通信的限制        346
17.2  軟件        347
17.2.1  軟件的復(fù)雜度        347
17.2.2  當(dāng)前提高軟件質(zhì)量的方法        348
17.2.3  臭名昭著的軟件錯(cuò)誤        351
17.3  問(wèn)題        352
17.3.1  算法比較        353
17.3.2  圖靈機(jī)        357
17.3.3  停機(jī)問(wèn)題        360
17.3.4  算法分類        361
小結(jié)        363
練習(xí)        364
思考題        366
部分練習(xí)答案        368
術(shù)語(yǔ)表        410
參考文獻(xiàn)        428