第0章 導引 1
0.1 算法的作用 1
0.2 計算機器的由來 3
0.3 算法的科學 7
0.4 抽象 8
0.5 學習綱要 9
0.6 社會影響 11
社會議題 11
課外閱讀 13
第1章 數(shù)據存儲 14
1.1 位和它們的存儲 14
1.1.1 布爾運算 14
1.1.2 門和觸發(fā)器 16
1.1.3 其他存儲技術 19
1.1.4 十六進制記數(shù)法 19
1.2 主存儲器 22
1.2.1 存儲器結構 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ù)據壓縮 50
1.8.1 通用數(shù)據壓縮技術 50
1.8.2 圖像的壓縮 53
*1.9 通信差錯 54
1.9.1 奇偶校驗位 55
1.9.2 差錯糾正碼 56
本章復習題 58
社會議題 64
課外閱讀 65
第2章 數(shù)據操作 66
2.1 計算機體系結構 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ù)據 78
*2.4 算術/邏輯指令 81
2.4.1 邏輯運算 81
2.4.2 循環(huán)移位和移位運算 82
2.4.3 算術運算 84
2.5 與其他設備的通信 85
2.5.1 通信與控制器 85
2.5.2 數(shù)據通信速率 88
*2.6 其他體系結構 90
2.6.1 流水線 90
2.6.2 多處理器計算機 91
本章復習題 92
社會議題 99
課外閱讀 100
第3章 操作系統(tǒng) 101
3.1 操作系統(tǒng)的發(fā)展 101
3.2 操作系統(tǒng)的體系結構 104
3.2.1 軟件綜述 105
3.2.2 操作系統(tǒng)的組件 106
3.2.3 系統(tǒng)啟動 109
3.3 協(xié)調機器的活動 110
3.3.1 進程的概念 110
3.3.2 進程管理 111
*3.4 處理進程間的競爭 113
3.4.1 信標 113
3.4.2 死鎖 115
*3.5 安全性 117
本章復習題 119
社會議題 122
課外閱讀 123
第4章 組網和因特網 124
4.1 網絡基礎 124
4.1.1 網絡分類 124
4.1.2 客戶/服務器模式 126
4.1.3 分布式系統(tǒng) 129
4.2 因特網 130
4.2.1 因特網體系結構 130
4.2.2 因特網編址 131
4.2.3 電子郵件 133
4.2.4 文件傳輸協(xié)議 134
4.2.5 遠程登錄 134
4.3 萬維網 135
4.3.1 萬維網實現(xiàn) 136
4.3.2 HTML. 138
4.3.3 XML. 140
4.3.4 動態(tài)網頁 142
*4.4 網絡協(xié)議 144
4.4.1 傳輸權的控制 144
4.4.2 因特網軟件分層方法 146
4.4.3 TCP/IP協(xié)議組 150
4.5 安全性 151
本章復習題 154
社會議題 156
課外閱讀 158
第5章 算法 159
5.1 算法的概念 159
5.1.1 簡單的回顧 159
5.1.2 算法的形式定義 160
5.1.3 算法的抽象本質 161
5.2 算法的表示 162
5.2.1 原語 162
5.2.2 偽代碼 164
5.3 算法的發(fā)現(xiàn) 169
5.3.1 問題求解的藝術 169
5.3.2 跨入門檻 171
5.4 循環(huán)結構 175
5.4.1 順序查找算法 176
5.4.2 循環(huán)控制 177
5.4.3 插入排序算法 180
5.5 遞歸結構 185
5.5.1 二分查找算法 185
5.5.2 遞歸控制 190
5.6 有效性和正確性 191
5.6.1 算法的有效性 192
5.6.2 軟件檢驗 195
本章復習題 200
社會議題 207
課外閱讀 208
第6章 程序設計語言 209
6.1 歷史回顧 209
6.1.1 早幾代語言 209
6.1.2 獨立于機器, 超越機器 212
6.1.3 程序設計范型 213
6.2 傳統(tǒng)的程序設計概念 217
6.2.1 變量和數(shù)據類型 218
6.2.2 數(shù)據結構 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 面向對象程序設計 243
6.5.1 類和對象 243
6.5.2 構造函數(shù) 245
6.5.3 其他特色 246
*6.6 并發(fā)活動的程序設計 248
*6.7 說明型程序設計 251
6.7.1 邏輯演繹 251
6.7.2 Prolog. 254
本章復習題 256
社會議題 262
課外閱讀 263
第7章 軟件工程 265
7.1 軟件工程學科 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 內聚性 275
7.4 設計方法論 277
7.4.1 自頂向下和自底向上 277
7.4.2 設計模式 277
7.4.3 開放源開發(fā)技術 278
7.5 行業(yè)工具 280
7.6 測試 283
7.7 文檔編制 284
7.8 軟件所有權和責任 286
本章復習題 288
社會議題 291
課外閱讀 292
第8章 數(shù)據抽象 293
8.1 數(shù)據結構基礎 293
8.1.1 基本數(shù)據結構 293
8.1.2 抽象 294
8.1.3 靜態(tài)結構和動態(tài)結構 295
8.1.4 指針 296
8.2 數(shù)據結構的實現(xiàn) 297
8.2.1 同構型數(shù)組的存儲 297
8.2.2 列表的存儲 299
8.2.3 堆棧和隊列的存儲 301
8.2.4 二叉樹的存儲 304
8.2.5 數(shù)據結構的操作 306
8.3 一個簡短案例的研究 308
8.4 定制的數(shù)據類型 313
8.4.1 用戶自定義數(shù)據類型 313
8.4.2 抽象數(shù)據類型 314
*8.5 類和對象 316
*8.6 機器語言中的指針 318
本章復習題 320
社會議題 327
課外閱讀 328
第9章 數(shù)據庫系統(tǒng) 329
9.1 數(shù)據庫原理 329
9.1.1 模式的作用 329
9.1.2 數(shù)據庫管理系統(tǒng) 331
9.1.3 數(shù)據庫模型 332
9.2 關系模型 333
9.2.1 關系設計的問題 333
9.2.2 關系運算 337
9.2.3 SQL. 341
*9.3 面向對象數(shù)據庫 343
*9.4 維護數(shù)據庫的完整性 345
9.4.1 提交/轉返協(xié)議 346
9.4.2 鎖定 347
*9.5 傳統(tǒng)的文件結構 348
9.5.1 順序文件 348
9.5.2 索引文件 351
9.5.3 散列文件 352
9.6 數(shù)據挖掘 355
9.7 數(shù)據庫技術的社會影響 357
本章復習題 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 產生式系統(tǒng) 374
10.3.2 搜索樹 376
10.3.3 試探法 378
10.4 人工神經網絡 383
10.4.1 基本特性 384
10.4.2 一個特定應用 386
10.4.3 聯(lián)想記憶 389
10.5 遺傳算法 393
10.6 其他研究領域 396
10.6.1 語言處理 396
10.6.2 機器人學 399
10.6.3 數(shù)據庫系統(tǒng) 399
10.6.4 專家系統(tǒng) 402
10.7 后果的思考 403
本章復習題 405
社會議題 411
課外閱讀 412
第11章 計算理論 413
11.1 函數(shù)及其計算 413
11.2 圖靈機 415
11.2.1 圖靈機原理 415
11.2.2 丘奇-圖靈論題 417
11.3 萬用程序設計語言 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 問題的復雜性 429
11.5.1 問題復雜性的度量 429
11.5.2 多項式問題與非多項式問題 432
11.5.3 不確定多項式問題 435
*11.6 公鑰密碼學 437
11.6.1 模表示法 438
11.6.2 RSA公鑰密碼學 439
本章復習題 441
社會議題 446
課外閱讀 447
附錄A ASCII代碼 448
附錄B 處理補碼的電路 449
附錄C 一個簡單的機器語言 452
附錄D 高級語言程序示例 454
附錄E 迭代結構與遞歸結構的等價 461
附錄F 問題與練習答案 463