電腦科學概論（第13版） Computer Science An Overview

J. Glenn Brookshear 世界闻名的计算机科学教育家。他在1975年获得新墨西哥州立大学博士后，创办了Marquette大学的计算机科学学位项目，并在该校任教至今。他的主要研究方向是计算理论。除了本书之外，他还著有《Theory of Computationr: Formal Languages, Automata, and Complexity》。

 

第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 創新 10

0.4.4 數據 10

0.4.5 程序設計 10

0.4.6 因特網 11

0.4.7 影響 11

社會問題 12

課外閱讀 13

第 1章 數據存儲 14

1.1 位和位存儲 15

1.1.1 布爾運算 15

1.1.2 門和觸發器 16

1.1.3 十六進制記數法 19

1.2 主存儲器 20

1.2.1 存儲器結構 20

1.2.2 存儲器容量的度量 21

1.3 海量存儲器 22

1.3.1 磁系統 22

1.3.2 光系統 24

1.3.3 快閃內存驅動器 25

1.4 用位模式表示信息 26

1.4.1 文本的表示 26

1.4.2 數值的表示 27

1.4.3 圖像的表示 28

1.4.4 聲音的表示 29

*1.5 二進制系統 31

1.5.1 二進制記數法 31

1.5.2 二進制加法 32

1.5.3 二進制中的分數 33

*1.6 整數的存儲 34

1.6.1 二進制補碼記數法 35

1.6.2 二進制補碼記數法中的加法 36

1.6.3 溢出問題 37

1.6.4 餘碼記數法 37

*1.7 分數的存儲 39

1.7.1 浮點記數法 39

1.7.2 截斷誤差 40

*1.8 數據與程序設計 43

1.8.1 Python入門 43

1.8.2 你好，Python 43

1.8.3 變量 44

1.8.4 運算符和表達式 45

1.8.5 貨幣轉換 46

1.8.6 調試 47

*1.9 數據壓縮 48

1.9.1 通用的數據壓縮技術 48

1.9.2 圖像壓縮 50

1.9.3 音頻和視頻壓縮 51

*1.10 通信差錯 52

1.10.1 奇偶校驗位 52

1.10.2 糾錯碼 53

復習題 55

社會問題 58

課外閱讀 59

第 2章 數據操控 60

2.1 電腦體系結構 61

2.1.1 CPU基礎知識 61

2.1.2 存儲程序概念 62

2.2 機器語言 63

2.2.1 指令系統 63

2.2.2 數據傳輸類 64

2.2.3 算術/邏輯類 64

2.2.4 控制類 64

2.2.5 Vole：一種演示用的機器語言 65

2.3 程序執行 68

2.3.1 程序執行的一個例子 69

2.3.2 程序與數據 71

*2.4 算術/邏輯指令 73

2.4.1 邏輯運算 73

2.4.2 循環移位運算及移位運算 74

2.4.3 算術運算 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 數據操控編程 80

2.6.1 邏輯運算和移位運算 80

2.6.2 控制結構 81

2.6.3 函數 82

2.6.4 輸入和輸出 83

2.6.5 馬拉松訓練助手 85

*2.7 其他體系結構 87

2.7.1 流水線 87

2.7.2 多處理器機器 87

復習題 88

社會問題 93

課外閱讀 94

第3章 操作系統 95

3.1 操作系統的歷史 96

3.2 操作系統的體系結構 99

3.2.1 軟件概述 99

3.2.2 操作系統組件 100

3.2.3 系統啟動 102

3.3 協調機器的活動 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 來自內部的攻擊 111

復習題 113

社會問題 115

課外閱讀 116

第4章 組網及因特網 117

4.1 網絡基礎 118

4.1.1 網絡分類 118

4.1.2 協議 119

4.1.3 組合網絡 121

4.1.4 進程間通信的方法 122

4.1.5 分佈式系統 124

4.2 因特網 124

4.2.1 因特網體系結構 125

4.2.2 因特網編址 127

4.2.3 因特網應用 129

4.3 萬維網 132

4.3.1 萬維網實現 133

4.3.2 HTML 134

4.3.3 XML 136

4.3.4 客戶端活動和服務器端活動 137

*4.4 因特網協議 138

4.4.1 因特網軟件的分層方法 138

4.4.2 TCP/IP協議簇 141

*4.5 簡單的客戶機服務器 143

4.6 網絡安全 146

4.6.1 攻擊的形式 146

4.6.2 防護和對策 148

4.6.3 密碼學 149

4.6.4 網絡安全的法律途徑 151

復習題 153

社會問題 155

課外閱讀 156

第5章 算法 158

5.1 算法的概念 159

5.1.1 非正式的回顧 159

5.1.2 算法的正式定義 159

5.1.3 算法的抽象本質 160

5.2 算法的表示 161

5.2.1 原語 161

5.2.2 偽代碼 163

5.3 算法的發現 167

5.3.1 問題求解的藝術 167

5.3.2 邁出第 一步 169

5.4 迭代結構 172

5.4.1 順序搜索算法 172

5.4.2 循環控制 173

5.4.3 插入排序算法 177

5.5 遞歸結構 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 傳統的程序設計概念 208

6.2.1 變量和數據類型 209

6.2.2 數據結構 210

6.2.3 常量和字面量 211

6.2.4 賦值語句 212

6.2.5 控制語句 213

6.2.6 註釋 216

6.3 過程單元 218

6.3.1 函數 218

6.3.2 參數 219

6.3.3 有返回值的函數 222

6.4 語言實現 224

6.4.1 翻譯過程 224

6.4.2 軟件開發包 230

6.5 面向對象程序設計 231

6.5.1 類和對象 231

6.5.2 構造器 233

6.5.3 附加特性 234

*6.6 程序設計並發活動 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　傳統的開發階段 251

7.3　軟件工程方法學 253

7.4　模塊化 254

7.4.1　模塊化實現 255

7.4.2　耦合 257

7.4.3　內聚 258

7.4.4　信息隱藏 258

7.4.5　組件 259

7.5　行業工具 260

7.5.1　較老的工具 261

7.5.2　統一建模語言 261

7.5.3　設計模式 265

7.6　質量保證 266

7.6.1　質量保證的範圍 266

7.6.2　軟件測試 267

7.7　文檔 268

7.8　人機界面 269

7.9　軟件所有權和責任 271

復習題 273

社會問題 275

課外閱讀 256

第8章 數據抽象 277

8.1 基本數據結構 278

8.1.1　數組和聚合 278

8.1.2　列表、棧和隊列 278

8.1.3　樹 280

8.2　相關概念 281

8.2.1　再談抽象 281

8.2.2　靜態結構與動態結構 282

8.2.3　指針 282

8.3　數據結構的實現 283

8.3.1 存儲數組 283

8.3.2 存儲聚合 285

8.3.3　存儲列表 286

8.3.4　存儲棧和隊列 289

8.3.5　存儲二叉樹 291

8.3.6　操控數據結構 293

8.4　一個簡短的案例研究 294

8.5　定製的數據類型 298

8.5.1　用戶定義的數據類型 298

8.5.2　抽象數據類型 299

8.6　類和對象 301

*8.7　機器語言中的指針 302

復習題 304

社會問題 308

課外閱讀 309

第9章 數據庫系統 310

9.1　數據庫基礎 311

9.1.1　數據庫系統的重要性 311

9.1.2　模式的作用 313

9.1.3　數據庫管理系統 313

9.1.4　數據庫模型 314

9.2　關系模型 315

9.2.1　關系設計中的問題 315

9.2.2　關系運算 318

9.2.3　SQL 321

*9.3　面向對象數據庫 323

*9.4　維護數據庫的完整性 325

9.4.1　提交/回滾協議 326

9.4.2　鎖定 326

*9.5　傳統的文件結構 328

9.5.1　順序文件 328

9.5.2　索引文件 330

9.5.3　散列文件 331

9.6　數據挖掘 334

9.7　數據庫技術的社會影響 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　裁剪、掃描轉換和隱藏面消除 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 產生式系統 376

11.3.2 搜索樹 378

11.3.3 啟發式 379

11.4 其他研究領域 384

11.4.1 知識的表達和處理 384

11.4.2 學習 386

11.4.3 遺傳算法 387

11.5 人工神經網絡 388

11.5.1 基本特性 388

11.5.2 訓練人工神經網絡 390

11.6 機器人學 392

11.7 後果的思考 395

復習題 396

社會問題 399

課外閱讀 401

第 12章 計算理論 402

12.1 函數及其計算 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 一個不可計算的函數 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 迭代結構與遞歸結構的等價性 438

索引 440