446
《計算機科學導論》一導讀
前 言
Foundations of Computer Science, Third Edition
計算機在我們的日常生活中扮演了一個重要的角色，而且在未來也將一樣。計算機科學是一個充滿了挑戰和發展機遇的年輕學科。計算機網絡將處在地球上每一個角落的我們連接在一起。虛擬現實創造了炫目的三維圖像。宇宙空間探險的成功也部分歸功於計算機的發展。計算機創建的特技效果改變了電影行業。計算機在遺傳學研究中也扮演了一個重要的角色。
本書讀者對象
這本書同時麵向學術的和專業的讀者。本書可以作為感興趣的專業人士的自學指南。作為教材，本書包含一學期（semester）或一學季（quarter）的教學內容，是計算機科學的入門教程。本書是基於美國計算機學會（ACM）推薦的CS0課程設計的。它從廣度上覆蓋了計算機科學所有的領域。其他領域的學生需要對計算機科學有大致的了解時，無論是從本書中選讀部分內容還是通讀全書，都有幫助。
第3版中的改動
在本版中我進行了以下幾類修改。
1.修訂的章節和附錄
針對教學目的，對本書中的兩章和附錄進行了全麵的修訂。
（1）第6章
為了更便於初次接觸計算機網絡的學生進行理解，第6章的內容采用自頂向下的教學方法進行修訂。
（2）第16章
對於第一次接觸計算機科學的學生而言，安全的概念普遍較難接受。該章修訂後的內容更通俗易懂。
（3）附錄F
該附錄修訂後的內容增加了三種計算機語言（C、C++和Java）的一些簡易程序例子。
2.部分章節中的細微變化
基於書評者的建議，部分章節的格式和內容進行了細微的修改，並且部分章節中增加了一些新的技術。
3.章末材料的變化
章末材料主要經曆了以下兩個主要的變化：
每章最後的多選題被刪去了，增加了在線小測驗，這樣無論對老師檢查教學成果，還是學生進行檢驗都方便許多。
每章結尾增加了在線小程序來幫助學生發現一些問題的可視化解決方法。
組織
這本書由18章和8個附錄構成。
1.章節
章節的作用是提供基本的學習材料，但並不是書中的每一個章節都對學生有利用價值。教這門課的老師可以自主選擇教學用的章節。我們會在後麵提供一份教學指南。
2.附錄
附錄的作用是為理解書中討論的概念所需的材料提供一個快速的參照或複習。本書中有8個可供學生參照和學習的附錄。
3.縮略語
本書包含一份縮略語表來幫助快速尋找到對應的術語。
4.術語表
為了使學生熟悉書中使用的術語，本書提供一份廣泛的術語表。
教學法
本書中的部分教學法是為使學生可以非常簡便地理解書中內容而設計的。
1.圖文並茂
本書圖文並茂，而且不使用複雜的公式來展示高深內容。本書附圖超過400幅，以便讀者形象而直觀地了解本書內容。圖片對於解釋構成整體的各組件之間的關係極為重要。對於很多學生來說，這些概念通過圖片相比文字更容易掌握。
2.重點
把重要的概念放在陰影框中以便快速參考和即時注意。
3.範例和應用
在合適的情況下，在書中引入了可以說明概念的例子。
4.算法
第3版增加了幾十個算法，有助於學生熟悉問題求解和編程。
5. UML
本書通篇使用UML圖以使學生熟悉該工具，因為這已經成為業界的實際標準。
6.章末材料
每一章以一係列材料結尾，包括以下部分：
（1）推薦讀物
這部分給出該章推薦書目列表。這些列表也用於參考引用。
（2）小結
每章結尾的小結都包括了對該章中所有內容的概括。小結把該章最重要的內容都整合在一起以便閱讀。
7.練習
每章包括為強化重要概念同時鼓勵學生進行實踐而設計的練習。練習包括四部分內容：小測驗、複習題、練習題和小程序。
（1）小測驗
本書網站上的小測驗提供對概念掌握情況的快速測試。學生可以通過這些小測驗來檢測對所學內容的理解。
（2）複習題
這個部分包括與書中討論到的概念有關的簡單題。本書網站上為學生提供了奇數編號複習題的答案以供核對。
（3）練習題
這一部分包括難度更大的題目，這些題目的求解需要對該章討論的內容有更深層次的理解。我強烈推薦學生去嚐試求解這部分的全部題目。奇數編號練習題的答案也已經公布在了本書網站以便學生進行核對。
（4）小程序
Java小程序是作者編寫並發布在網站上的交互式試驗。這裏的小程序有些用於更好地理解部分練習題的解答，而有些則用於更好地通過實踐理解網絡的概念。小程序是為了簡化對部分範例的理解而專門設計的。
教師資源
本書為教該課程的老師提供完整的以下教學資源。他們可以從本書網站下載。
1.演示文稿
本書網站為教授該課程的老師提供了一係列彩色的、動畫式的幻燈片演示文稿。
2.練習的答案
本書網站為教授該課程的老師提供了所有複習題和練習題的答案。
如何使用本書
本書的章節提供了較大的靈活性組織。我建議以下幾點：
第1～8章內容對理解本書剩下內容而言是必要的。
如果時間允許，可以教授第9～14 章內容。在學季製（quarter）中這些內容可以省去。
第15～18章內容的教授應該基於學生的專業和老師的辨別力進行選擇。
目 錄
第1章 緒論
1.1 圖靈模型
1.2 馮·諾依曼模型
1.3 計算機組成部分
1.4 曆史
1.5 社會問題和道德問題
1.6 計算機科學作為一門學科
1.7 課程綱要
1.8 章末材料
1.9 練習
第2章 數字係統
2.1 引言
2.2 位置化數字係統
2.3 非位置化數字係統
2.4 章末材料
2.5 練習
第3章 數據存
3.1 數據類型
3.2 存儲數字
3.2.1 存儲整數
3.2.2 3種係統的比較
3.3 存儲文本
3.4 存儲音頻
3.4.1 采樣
3.4.2 量化
3.4.3 編碼
3.4.4 聲音編碼標準
3.5 存儲圖像
3.5.1 光柵圖
3.5.2 矢量圖
3.6 存儲視頻
3.7 章末材料
3.8 練習
第4章 數據運算
4.1 邏輯運算
4.1.1 位層次上的邏輯運算
4.1.2 模式層次上的邏輯運算
4.2 移位運算
4.3 算術運算
4.3.1 整數的算術運算
4.3.2 實數的算術運算
4.4 章末材料
4.5 練習
第5章 計算機組成
5.1 引言
5.2 中央處理單元
5.2.1 算術邏輯單
5.2.2 寄存器
5.2.3 控製單元
5.3 主存儲器
5.3.1 地址空間
5.3.2 存儲器的類型
5.3.3 存儲器的層次結構
5.3.4 高速緩衝存儲器
5.4 輸入/輸出子係統
5.4.1 非存儲設備
5.4.2 存儲設備
5.5 子係統的互連
5.5.1 CPU和存儲器的連接
5.5.2 I/O設備的連接
5.5.3 輸入／輸出設備的尋址
5.6 程序執行
5.6.1 機器周期
5.6.2 輸入／輸出操作
5.7 不同的體係結構
5.7.1 CISC
5.7.2 RISC
5.7.3 流水線
5.7.4 並行處理
5.8 簡單計算機
5.8.1 CPU
5.8.2 主存
5.8.3 輸入/輸出子係統
5.8.4 指令集
5.8.5 處理指令
5.8.6 存儲程序和數據
5.8.7 指令周期
5.8.8 另一個例子
5.8.9 可重用性
5.9 章末材料
5.10 練習
第6章 計算機網絡和因特網
6.1 引言
6.1.1 網絡
6.1.2 因特網
6.1.3 硬件和軟件
6.1.4 協議分層
6.1.5 TCP/IP協議族
6.2 應用層
6.2.1 提供服務
6.2.2 應用層模式
6.2.3 標準化客戶機-服務器應用
6.2.4 文件傳輸協議
6.2.5 電子郵件
6.2.6 TELNET
6.2.7 安全外殼
6.2.8 域名係統
6.2.9 端到端模式
6.3 傳輸層
6.3.1 傳輸層服務
6.3.2 傳輸層協議
6.4 網絡層
6.4.1 網絡層提供的服務
6.4.2 網絡層協議
6.5 數據鏈路層
6.5.1 節點和鏈接
6.5.2 局域網
6.5.3 廣域網
6.6 物理層
6.6.1 數據和信號
6.6.2 數字化傳輸
6.6.3 模擬傳輸
6.7 傳輸介質
6.7.1 導向介質
6.7.2 非導向介質：無線
6.8 章末材料
6.9 練習
第7章 操作係統
7.1 引言
7.1.1 操作係統
7.1.2 自舉過程
7.2 演化
7.2.1 批處理係統
7.2.2 分時係統
7.2.3 個人係統
7.2.4 並行係統
7.2.5 分布式係統
7.2.6 實時係統
7.3 組成部分
7.3.1 用戶界麵
7.3.2 內存管理器
7.3.3 進程管理器
7.3.4 文件管理器
7.4 主流操作係統
7.4.1 UNIX
7.4.2 Linux
7.4.3 Windows
7.5 章末材料
7.6 練習
第8章 算法
8.1 概念
8.1.1 非正式定義
8.1.2 定義動作
8.1.3 細化
8.1.4 泛化
8.2 三種結構
8.2.1 順序
8.2.2 判斷
8.2.3 循環
8.3 算法的表示
8.3.1 UML
8.3.2 偽代碼
8.4 更正式的定義
8.4.1 定義良好
8.4.2 明確步驟
8.4.3 產生結果
8.4.4 在有限的時間內終止
8.5 基本算法
8.5.1 求和
8.5.2 乘
8.5.3 最大和最小
8.5.4 排序
8.5.5 查找
8.6 子算法
8.7 遞歸
8.7.1 迭代的定義
8.7.2 遞歸的定義
8.8 章末材料
8.9 練習
第9章 程序設計語言
9.1 演化
9.1.1 機器語言
9.1.2 匯編語言
9.1.3 高級語言
9.2 翻譯
9.2.1 編譯
9.2.2 解釋
9.2.3 翻譯過程
9.3 編程模式
9.3.1 過程式模式
9.3.2 麵向對象模式
9.3.3 函數式模式
9.3.4 說明式模式
9.4 共同概念
9.4.1 標識符
9.4.2 數據類型
9.4.3 語句
9.5 章末材料
9.6 練習
第10章 軟件工程
10.1 軟件生命周期
10.2 分析階段
10.2.1 麵向過程分析
10.2.2 麵向對象分析
10.3 設計階段
10.3.1 麵向過程設計
10.3.2 麵向對象設計
10.4 實現階段
10.4.1 語言的選擇
10.4.2 軟件質量
10.5 測試階段
10.5.1 白盒測試
10.5.2 黑盒測試
10.6 文檔
10.6.1 用戶文檔
10.6.2 係統文檔
10.6.3 技術文檔
10.7 章末材料
10.8 練習
第11章 數據結構197
11.1 數組
11.1.1 數組名與元素名
11.1.2 多維數組
11.1.3 存儲配置
11.1.4 數組操作
11.1.5 數組的應用
11.2 記錄
11.2.1 記錄名與域名
11.2.2 記錄與數組的比較
11.2.3 記錄數組
11.2.4 數組與記錄數組
11.3 鏈表
11.3.1 數組與鏈表
11.3.2 鏈表名與節點名
11.3.3 鏈表操作
11.3.4 鏈表的應用
11.4 章末材料
11.5 練習
第12章 抽象數據類型
12.1 背景
12.1.1 簡單抽象數據類型
12.1.2複雜抽象數據類型
12.1.3 定義
12.1.4 抽象數據類型的模型
12.1.5實現
12.2棧
12.2.1棧的操作
12.2.2棧的抽象數據類型
12.2.3棧的應用
12.2.4棧的實現
12.3隊列
12.3.1隊列的操作
12.3.2隊列抽象數據類型
12.3.3隊列的應用
12.3.4隊列的實現
12.4廣義線性表
12.4.1廣義線性表的操作
12.4.2廣義線性表的抽象數據類型
12.4.3廣義線性表的應用
12.4.4廣義線性表的實現
12.5樹
12.5.1二叉樹
12.5.2二叉樹的操作
12.5.3二叉樹的應用
12.5.4二叉樹的實現
12.5.5二叉搜索樹
12.5.6二叉搜索樹的抽象數據類型
12.5.7二叉搜索樹的實現
12.6圖
12.7章末材料
12.8練習
第13章 文件結構
13.1引言
13.1.1順序存取
13.1.2隨機存取
13.2順序文件
13.3索引文件
13.4散列文件
13.4.1散列方法
13.4.2衝突
13.5目錄
13.6文本文件與二進製文件
13.6.1文本文件
13.6.2二進製文件
13.7章末材料
13.8練習
第14章 數據庫
14.1引言
14.1.1定義
14.1.2數據庫的優點
14.1.3數據庫管理係統
14.2數據庫體係結構
14.2.1內層
14.2.2概念層
14.2.3外層
14.3數據庫模型
14.4關係數據庫模型
14.5關係的操作
14.5.10 差
14.6 數據庫設計
14.6.1 實體關係模型
14.6.2 從E-R圖到關係
14.6.3 規範化
14.7 其他數據庫模型
14.8 章末材料
14.9 練習
第15章 數據壓縮
15.1 引言
15.2 無損壓縮
15.2.1 遊程長度編碼
15.2.2 赫夫曼編碼
15.2.3 Lempel Ziv編碼
15.3 有損壓縮方法
15.3.1 圖像壓縮：JPEG
15.3.2 視頻壓縮：MPEG
15.3.3 音頻壓縮
15.4 章末材料
15.5 練習
第16章 安全
16.1引言
16.1.1安全目標
16.1.2攻擊
16.1.3 服務和技術
16.2 機密性
16.2.1 對稱密鑰密碼術
16.2.2 非對稱密鑰密碼術
16.3 其他安全服務
16.3.1 消息完整性
16.3.2 消息驗證
16.3.3 數字簽名
16.3.4 實體驗證
16.3.5 密鑰管理
16.4 防火牆
16.4.1 包過濾防火牆
16.4.2 代理防火牆
16.5 章末材料
16.6 練習
第17章 計算理論
17.1 引言
17.2 簡單語言
17.2.1 遞增語句
17.2.2 遞減語句
17.2.3 循環語句
17.2.4 簡單語言的威力
17.3 圖靈機
17.3.1 圖靈機組成部件
17.3.2 對簡單語言的模擬
17.3.3 邱奇-圖靈論題
17.4 歌德爾數
17.4.1 表示一個程序
17.4.2 翻譯一個數字
17.5 停機問題
17.6 問題的複雜度
17.6.1 不可解問題
17.6.2 可解問題
17.7 章末材料
17.8 練習
第18章 人工智能
18.1引言
18.1.1 什麼是人工智能
18.1.2 人工智能簡史
18.1.3 圖靈測試
18.1.4 智能體
18.1.5 編程語言
18.2 知識表示
18.2.1 語義網
18.2.2 框架
18.2.3 謂詞邏輯
18.2.4 基於規則的係統
18.3 專家係統
18.3.1 抽取知識
18.3.2 抽取事實
18.3.3 體係結構
18.4 感知
18.4.1 圖像處理
18.4.2 語言理解
18.5 搜索
18.6 神經網絡
18.6.1 生物神經元
18.6.2 感知器
18.6.3 多層網絡
18.6.4 應用
18.7 章末材料
18.8 練習
附錄A Unicode
附錄B UML
附錄C 偽代碼
附錄D 結構圖
附錄E 布爾代數和邏輯電路
附錄F C、C++和Java程序示例
附錄G 數學知識
附錄H 誤差檢測和校正
縮略語
術語表
最後更新：2017-06-21 17:02:31