計算機科學概論（第13版）

第0章 緒 論 1
0.1 算法的作用 2
0.2 計算的歷史 3
0.3 學習大綱 7
0.4 計算機科學的首要主題 8
0.4.1 算法 8
0.4.2 抽象 9
0.4.3 創(chuàng)新 10
0.4.4 數(shù)據(jù) 10
0.4.5 程序設計 10
0.4.6 因特網(wǎng) 11
0.4.7 影響 11
社會問題 12
課外閱讀 13
第 1章 數(shù)據(jù)存儲 14
1.1 位和位存儲 15
1.1.1 布爾運算 15
1.1.2 門和觸發(fā)器 16
1.1.3 十六進制記數(shù)法 19
1.2 主存儲器 20
1.2.1 存儲器結(jié)構(gòu) 20
1.2.2 存儲器容量的度量 21
1.3 海量存儲器 22
1.3.1 磁系統(tǒng) 22
1.3.2 光系統(tǒng) 24
1.3.3 閃存驅(qū)動器 25
1.4 用位模式表示信息 26
1.4.1 文本的表示 26
1.4.2 數(shù)值的表示 27
1.4.3 圖像的表示 28
1.4.4 聲音的表示 29
*1.5 二進制系統(tǒng) 31
1.5.1 二進制記數(shù)法 31
1.5.2 二進制加法 32
1.5.3 二進制中的分數(shù) 33
*1.6 整數(shù)的存儲 34
1.6.1 二進制補碼記數(shù)法 35
1.6.2 二進制補碼記數(shù)法中的加法 36
1.6.3 溢出問題 37
1.6.4 余碼記數(shù)法 37
*1.7 分數(shù)的存儲 39
1.7.1 浮點記數(shù)法 39
1.7.2 截斷誤差 40
*1.8 數(shù)據(jù)與程序設計 43
1.8.1 Python入門 43
1.8.2 你好，Python 43
1.8.3 變量 44
1.8.4 運算符和表達式 45
1.8.5 貨幣轉(zhuǎn)換 46
1.8.6 調(diào)試 47
*1.9 數(shù)據(jù)壓縮 48
1.9.1 通用的數(shù)據(jù)壓縮技術(shù) 48
1.9.2 圖像壓縮 50
1.9.3 音頻和視頻壓縮 51
*1.10 通信差錯 52
1.10.1 奇偶校驗位 52
1.10.2 糾錯碼 53
復習題 55
社會問題 58
課外閱讀 59
第 2章 數(shù)據(jù)操控 60
2.1 計算機體系結(jié)構(gòu) 61
2.1.1 CPU基礎知識 61
2.1.2 存儲程序概念 62
2.2 機器語言 63
2.2.1 指令系統(tǒng) 63
2.2.2 數(shù)據(jù)傳輸類 64
2.2.3 算術(shù)/邏輯類 64
2.2.4 控制類 64
2.2.5 Vole：一種演示用的機器語言 65
2.3 程序執(zhí)行 68
2.3.1 程序執(zhí)行的一個例子 69
2.3.2 程序與數(shù)據(jù) 71
*2.4 算術(shù)/邏輯指令 73
2.4.1 邏輯運算 73
2.4.2 循環(huán)移位運算及移位運算 74
2.4.3 算術(shù)運算 75
*2.5 與其他設備通信 76
2.5.1 控制器的作用 76
2.5.2 直接存儲器存取 77
2.5.3 握手 78
2.5.4 流行的通信媒介 78
2.5.5 通信速率 79
*2.6 數(shù)據(jù)操控編程 80
2.6.1 邏輯運算和移位運算 80
2.6.2 控制結(jié)構(gòu) 81
2.6.3 函數(shù) 82
2.6.4 輸入和輸出 83
2.6.5 馬拉松訓練助手 85
*2.7 其他體系結(jié)構(gòu) 87
2.7.1 流水線 87
2.7.2 多處理器機器 87
復習題 88
社會問題 93
課外閱讀 94
第3章 操作系統(tǒng) 95
3.1 操作系統(tǒng)的歷史 96
3.2 操作系統(tǒng)的體系結(jié)構(gòu) 99
3.2.1 軟件概述 99
3.2.2 操作系統(tǒng)組件 100
3.2.3 系統(tǒng)啟動 102
3.3 協(xié)調(diào)機器的活動 104
3.3.1 進程的概念 104
3.3.2 進程管理 104
*3.4 處理進程間的競爭 106
3.4.1 信號量 106
3.4.2 死鎖 108
3.5 安全性 110
3.5.1 來自外部的攻擊 110
3.5.2 來自內(nèi)部的攻擊 111
復習題 113
社會問題 115
課外閱讀 116
第4章 組網(wǎng)及因特網(wǎng) 117
4.1 網(wǎng)絡基礎 118
4.1.1 網(wǎng)絡分類 118
4.1.2 協(xié)議 119
4.1.3 組合網(wǎng)絡 121
4.1.4 進程間通信的方法 122
4.1.5 分布式系統(tǒng) 124
4.2 因特網(wǎng) 124
4.2.1 因特網(wǎng)體系結(jié)構(gòu) 125
4.2.2 因特網(wǎng)編址 127
4.2.3 因特網(wǎng)應用 129
4.3 萬維網(wǎng) 132
4.3.1 萬維網(wǎng)實現(xiàn) 133
4.3.2 HTML 134
4.3.3 XML 136
4.3.4 客戶端活動和服務器端活動 137
*4.4 因特網(wǎng)協(xié)議 138
4.4.1 因特網(wǎng)軟件的分層方法 138
4.4.2 TCP/IP協(xié)議簇 141
*4.5 簡單的客戶機服務器 143
4.6 網(wǎng)絡安全 146
4.6.1 攻擊的形式 146
4.6.2 防護和對策 148
4.6.3 密碼學 149
4.6.4 網(wǎng)絡安全的法律途徑 151
復習題 153
社會問題 155
課外閱讀 156
第5章 算法 158
5.1 算法的概念 159
5.1.1 非正式的回顧 159
5.1.2 算法的正式定義 159
5.1.3 算法的抽象本質(zhì) 160
5.2 算法的表示 161
5.2.1 原語 161
5.2.2 偽代碼 163
5.3 算法的發(fā)現(xiàn) 167
5.3.1 問題求解的藝術(shù) 167
5.3.2 邁出第 一步 169
5.4 迭代結(jié)構(gòu) 172
5.4.1 順序搜索算法 172
5.4.2 循環(huán)控制 173
5.4.3 插入排序算法 177
5.5 遞歸結(jié)構(gòu) 180
5.5.1 二分搜索算法 181
5.5.2 遞歸控制 185
5.6 效率和正確性 187
5.6.1 算法效率 187
5.6.2 軟件驗證 190
復習題 194
社會問題 198
課外閱讀 199
第6章 程序設計語言 200
6.1 歷史回顧 201
6.1.1 早期程序設計語言 201
6.1.2 機器無關和超越機器無關 203
6.1.3 程序設計范型 204
6.2 傳統(tǒng)的程序設計概念 208
6.2.1 變量和數(shù)據(jù)類型 209
6.2.2 數(shù)據(jù)結(jié)構(gòu) 210
6.2.3 常量和字面量 211
6.2.4 賦值語句 212
6.2.5 控制語句 213
6.2.6 注釋 216
6.3 過程單元 218
6.3.1 函數(shù) 218
6.3.2 參數(shù) 219
6.3.3 有返回值的函數(shù) 222
6.4 語言實現(xiàn) 224
6.4.1 翻譯過程 224
6.4.2 軟件開發(fā)包 230
6.5 面向?qū)ο蟪绦蛟O計 231
6.5.1 類和對象 231
6.5.2 構(gòu)造器 233
6.5.3 附加特性 234
*6.6 程序設計并發(fā)活動 236
*6.7 說明性程序設計 238
6.7.1 邏輯推演 238
6.7.2 Prolog 240
復習題 242
社會問題 245
課外閱讀 246
第7章 軟件工程 247
7.1　軟件工程學科 248
7.2　軟件生命周期 250
7.2.1　周期是個整體 250
7.2.2　傳統(tǒng)的開發(fā)階段 251
7.3　軟件工程方法學 253
7.4　模塊化 254
7.4.1　模塊化實現(xiàn) 255
7.4.2　耦合 257
7.4.3　內(nèi)聚 258
7.4.4　信息隱藏 258
7.4.5　組件 259
7.5　行業(yè)工具 260
7.5.1　較老的工具 261
7.5.2　統(tǒng)一建模語言 261
7.5.3　設計模式 265
7.6　質(zhì)量保證 266
7.6.1　質(zhì)量保證的范圍 266
7.6.2　軟件測試 267
7.7　文檔 268
7.8　人機界面 269
7.9　軟件所有權(quán)和責任 271
復習題 273
社會問題 275
課外閱讀 256
第8章 數(shù)據(jù)抽象 277
8.1 基本數(shù)據(jù)結(jié)構(gòu) 278
8.1.1　數(shù)組和聚合 278
8.1.2　列表、棧和隊列 278
8.1.3　樹 280
8.2　相關概念 281
8.2.1　再談抽象 281
8.2.2　靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu) 282
8.2.3　指針 282
8.3　數(shù)據(jù)結(jié)構(gòu)的實現(xiàn) 283
8.3.1 存儲數(shù)組 283
8.3.2 存儲聚合 285
8.3.3　存儲列表 286
8.3.4　存儲棧和隊列 289
8.3.5　存儲二叉樹 291
8.3.6　操控數(shù)據(jù)結(jié)構(gòu) 293
8.4　一個簡短的案例研究 294
8.5　定制的數(shù)據(jù)類型 298
8.5.1　用戶定義的數(shù)據(jù)類型 298
8.5.2　抽象數(shù)據(jù)類型 299
8.6　類和對象 301
*8.7　機器語言中的指針 302
復習題 304
社會問題 308
課外閱讀 309
第9章 數(shù)據(jù)庫系統(tǒng) 310
9.1　數(shù)據(jù)庫基礎 311
9.1.1　數(shù)據(jù)庫系統(tǒng)的重要性 311
9.1.2　模式的作用 313
9.1.3　數(shù)據(jù)庫管理系統(tǒng) 313
9.1.4　數(shù)據(jù)庫模型 314
9.2　關系模型 315
9.2.1　關系設計中的問題 315
9.2.2　關系運算 318
9.2.3　SQL 321
*9.3　面向?qū)ο髷?shù)據(jù)庫 323
*9.4　維護數(shù)據(jù)庫的完整性 325
9.4.1　提交/回滾協(xié)議 326
9.4.2　鎖定 326
*9.5　傳統(tǒng)的文件結(jié)構(gòu) 328
9.5.1　順序文件 328
9.5.2　索引文件 330
9.5.3　散列文件 331
9.6　數(shù)據(jù)挖掘 334
9.7　數(shù)據(jù)庫技術(shù)的社會影響 335
復習題 337
社會問題 340
課外閱讀 341
第 10章 計算機圖形學 342
10.1　計算機圖形學的范圍 343
10.2　3D圖形學概述 344
10.3　建模 346
10.3.1　單個物體的建模 346
10.3.2　整個場景的建模 350
10.4　渲染 351
10.4.1　光－表面相互作用 351
10.4.2　裁剪、掃描轉(zhuǎn)換和隱藏面消除 353
10.4.3　著色 356
10.4.4　渲染－流水線硬件 357
*10.5　處理全局光照 359
10.5.1　光線跟蹤 359
10.5.2　輻射度 360
10.6　動畫 361
10.6.1　動畫基礎 361
10.6.2　運動學和動力學 362
10.6.3　動畫制作過程 363
復習題 364
社會問題 366
課外閱讀 366
第 11章 人工智能 368
11.1 智能與機器 368
11.1.1 智能體 368
11.1.2 研究方法 369
11.1.3 圖靈測試 370
11.2 感知 371
11.2.1 理解圖像 371
11.2.2 語言處理 373
11.3 推理 376
11.3.1 產(chǎn)生式系統(tǒng) 376
11.3.2 搜索樹 378
11.3.3 啟發(fā)式 379
11.4 其他研究領域 384
11.4.1 知識的表達和處理 384
11.4.2 學習 386
11.4.3 遺傳算法 387
11.5 人工神經(jīng)網(wǎng)絡 388
11.5.1 基本特性 388
11.5.2 訓練人工神經(jīng)網(wǎng)絡 390
11.6 機器人學 392
11.7 后果的思考 395
復習題 396
社會問題 399
課外閱讀 401
第 12章 計算理論 402
12.1 函數(shù)及其計算 403
12.2 圖靈機 404
12.2.1 圖靈機的原理 405
12.2.2 丘奇-圖靈論題 407
12.3 通用程序設計語言 407
12.3.1 Bare Bones語言 408
12.3.2 用Bare Bones語言編程 409
12.3.3 Bare Bones的通用性 410
12.4 一個不可計算的函數(shù) 411
12.4.1 停機問題 411
12.4.2 停機問題的不可解性 413
12.5 問題的復雜性 415
12.5.1 問題復雜性的度量 416
12.5.2 多項式問題與非多項式問題 419
12.5.3 NP問題 420
*12.6 公鑰密碼學 423
12.6.1 模表示法 424
12.6.2 RSA公鑰密碼學 424
復習題 426
社會問題 429
課外閱讀 429
附錄A ASCII碼 431
附錄B 用于處理二進制補碼表示的電路 432
附錄C Vole：一種簡單的機器語言 434
附錄D 高級程序設計語言 436
附錄E 迭代結(jié)構(gòu)與遞歸結(jié)構(gòu)的等價性 438
索引 440