計算機科學概論（原書第2版）

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