計算機科學概論

第0章  簡介                  
 0. 1  算法的研究                  
 0. 2  計算機的起源                  
 0. 3  算法的科學                  
 0. 4  抽象的角色                  
 0. 5  社會的反作用                  
 0. 6  社會問題                  
 0. 7  課外閱讀                  
 第一部分  計算機體系結構                  
 第1章  數(shù)據(jù)存儲                  
 1. 1  位與它們的存儲                  
 1. 1. 1  門與觸發(fā)器                  
 1. 1. 2  其他存儲技術                  
 1. 1. 3  十六進制表示法                  
 1. 2  主存儲器                  
 1. 2. 1  存儲器結構                  
 1. 2. 2  度量主存容量                  
 1. 3  大容量存儲器                  
 1. 3. 1  磁盤                  
 1. 3. 2  光盤(CD)                  
 1. 3. 3  磁帶                  
 1. 3. 4  文件存儲與檢索                  
 1. 4  以二進制編碼表示數(shù)據(jù)                  
 1. 4. 1  文本的表示                  
 1. 4. 2  數(shù)字值的表示                  
 1. 4. 3  圖像的表示                  
 1. 4. 4  音頻的表示                  
 1. 5  二進制系統(tǒng)                  
 1. 5. 1  二進制加法                  
 1. 5. 2  二進制中的分數(shù)                  
 1. 6  整數(shù)的存儲                  
 1. 6. 1    進制補碼表示法                  
 1. 6. 2  余碼                  
 1. 7  小數(shù)的存儲                  
 1. 7. 1  浮點記數(shù)法                  
 1. 7. 2  截斷誤差                  
 1. 8  數(shù)據(jù)壓縮                  
 1. 8. 1  普通數(shù)據(jù)壓縮技術                  
 1. 8. 2  圖像的壓縮                  
 1. 9  通信錯誤                  
 1. 9. 1  奇偶校驗位                  
 1. 9. 2  錯誤糾正碼                  
 1. 10  本章復習題                  
 1. 11  社會問題                  
 1. 12  課外閱讀                  
 第2章  數(shù)據(jù)操作                  
 2. 1  計算機體系結構                  
 2. 2  機器語言                  
 2. 2. 1  指令系統(tǒng)                  
 2. 2. 2  一種說明性的機器語言                  
 2. 3  程序的執(zhí)行                  
 2. 3. 1  程序執(zhí)行的一個例子                  
 2. 3. 2  程序與數(shù)據(jù)                  
 2. 4  算術邏輯指令                  
 2. 4. 1  邏輯運算                  
 2. 4. 2  循環(huán)移位操作                  
 2. 4. 3  算術操作                  
 2. 5  與其他設備的通信                  
 2. 5. 1  通信控制器                  
 2. 5. 2  數(shù)據(jù)傳輸速率                  
 2. 6  其他體系結構                  
 2. 6. 1  流水線                  
 2. 6. 2  多處理器計算機                  
 2. 7  本章復習題                  
 2. 8  社會問題                  
 2. 9  課外閱讀                  
 第二部分  軟  件                  
 第3章  操作系統(tǒng)與網(wǎng)絡                  
 3. 1  操作系統(tǒng)的變革                  
 3. 1. 1  單處理器系統(tǒng)                  
 3. 1. 2  多處理器系統(tǒng)                  
 3. 2  操作系統(tǒng)體系結構                  
 3. 2. 1  軟件概覽                  
 3. 2. 2  操作系統(tǒng)的組成                  
 3. 2. 3  系統(tǒng)啟動                  
 3. 3  協(xié)調機器活動                  
 3. 3. 1  進程的概念                  
 3. 3. 2  進程管理                  
 3. 3. 3  客戶/服務器模型                  
 3. 4  進程間的競爭處理                  
 3. 4. 1  旗語                  
 3. 4. 2  死鎖                  
 3. 5  網(wǎng)絡                  
 3. 5. 1  網(wǎng)絡基礎                  
 3. 5. 2  聯(lián)網(wǎng)                  
 3. 6  網(wǎng)絡協(xié)議                  
 3. 6. 1  控制傳輸協(xié)議                  
 3. 6. 2  互聯(lián)網(wǎng)軟件的分層結構                  
 3. 6. 3  TCP／IP協(xié)議族                  
 3. 7  安全                  
 3. 8  本章復習題                  
 3. 9  社會問題                  
 3. 10  課外閱讀                  
 第4章  算法                  
 4. 1  算法的概念                  
 4. 1. 1  概覽                  
 4. 1. 2  算法的正式定義                  
 4. 1. 3  算法的抽象本質                  
 4. 2  算法表示                  
 4. 2. 1  原語                  
 4. 2. 2  偽碼                  
 4. 3  算法發(fā)現(xiàn)    4. 3. 1  解決問題的技巧                  
 4. 3. 2  進入問題                  
 4. 4  迭代結構                  
 4. 4. 1  順序查找法                  
 4. 4. 2  循環(huán)控制                  
 4. 4. 3  插入排序法                  
 4. 5  遞歸結構                  
 4. 5. 1  分查找法                  
 4. 5. 2  遞歸控制                  
 4. 6  效率和正確性                  
 4. 6. 1  算法效率                  
 4. 6. 2  軟件確認                  
 4. 7  本章復習題                  
 4. 8  社會問題                  
 4. 9  課外閱讀                  
 第5章  程序設計語言                  
 5. 1  歷史回顧                  
 5. 1. 1  早期程序設計語言                  
 5. 1. 2  機器獨立性及其超越                  
 5. 1. 3  程序設計范型                  
 5. 2  傳統(tǒng)的程序設計概念                  
 5. 2. 1  變量和數(shù)據(jù)類型                  
 5. 2. 2  數(shù)據(jù)結構                  
 5. 2. 3  常數(shù)和文字                  
 5. 2. 4  賦值語句                  
 5. 2. 5  控制語句                  
 5. 2. 6  注釋                  
 5. 3  過程單元                  
 5. 3. 1  過程                  
 5. 3. 2  參數(shù)                  
 5. 3. 3  函數(shù)                  
 5. 3. 4  輸入／輸出語句                  
 5. 4  語言的執(zhí)行                  
 5. 4. 1  翻譯進程                  
 5. 4. 2  連接與加載                  
 5. 4. 3  軟件開發(fā)包                  
 5. 5  面向對象程序設計                  
 5. 5. 2  構造函數(shù)                  
 5. 5. 3  附加特性                  
 5. 6  程序設計的并發(fā)行為                  
 5. 7  聲明程序設計                  
 5. 7. 1  邏輯推演                  
 5. 7. 2  Prolog                  
 5. 8  本章復習題                  
 5. 9  社會問題                  
 5. 10  課外閱讀                  
 第6章  軟件工程                  
 6. 1  軟件工程學科                  
 6. 2  軟件生命周期                  
 6. 2. 1  作為整體的周期                  
 6. 2. 2  傳統(tǒng)開發(fā)階段                  
 6. 2. 3  趨勢                  
 6. 3  模塊化                  
 6. 3. 1  模塊的實現(xiàn)                  
 6. 3. 2  耦合                  
 6. 3. 3  聚合                  
 6. 4  設計方法學                  
 6. 4. 1  自頂向下與自底向上                  
 6. 4. 2  設計模式                  
 6. 4. 3  開放源碼運動                  
 6. 5  專業(yè)工具                  
 6. 6  測試                  
 6. 7  文檔                  
 6. 8  軟件的所有權和責任                  
 6. 9  本章復習題                  
 6. 10  社會問題                  
 6. 11  課外閱讀                  
 第三部分  數(shù)據(jù)組織                  
 第7章  數(shù)據(jù)結構                  
 7. 1  數(shù)據(jù)結構基礎                  
 7. 1. 1  抽象                  
 7. 1. 2  靜態(tài)與動態(tài)結構的比較                  
 7. 1. 3  指針                  
 7. 2  數(shù)組                  
 7. 3  表                  
 7. 3. 1  鄰接表                  
 7. 3. 2  鏈接表                  
 7. 3. 3  抽象概念表                  
 7. 4  堆棧                  
 7. 4. 1  回溯                  
 7. 4. 2  棧的實現(xiàn)                  
 7. 5  隊列                  
 7. 6  樹                  
 7. 6. 1  樹的實現(xiàn)                  
 7. 6. 2  二叉樹包                  
 7. 7  自定義數(shù)據(jù)類型                  
 7. 7. 1  用戶定義類型                  
 7. 7. 2  類                  
 7. 8  機器語言中的指針                  
 7. 9  本章復習題                  
 7. 10  社會問題                  
 7. 11  課外閱讀                  
 第8章  文件結構                  
 8. 1  操作系統(tǒng)的任務                  
 8. 2  順序文件                  
 8. 2. 1  順序文件的處理                  
 8. 2. 2  文本文件                  
 8. 2. 3  編程概念                  
 8. 3  索引                  
 8. 3. 1  索引的原理                  
 8. 3. 2  編程概念                  
 8. 4  散列                  
 8. 4. 1  一個特殊的散列系統(tǒng)                  
 8. 4. 2  分配問題                  
 8. 4. 3  編程思想                  
 8. 5  本章復習題                  
 8. 6  社會問題                  
 8. 7  課外閱讀                  
 第9章  數(shù)據(jù)庫結構                  
 9. 1  概論                  
 9. 2  數(shù)據(jù)庫的分層實現(xiàn)                  
 9. 2. 1  數(shù)據(jù)庫管理系統(tǒng)                  
 9. 2. 2  數(shù)據(jù)庫模型                  
 9. 3  關系模型                  
 9. 3. 1  關系的設計                  
 9. 3. 2  關系操作                  
 9. 3. 3  執(zhí)行的問題                  
 9. 3. 4  SQL                  
 9. 4  面向對象的數(shù)據(jù)庫                  
 9. 5  維持數(shù)據(jù)完整性                  
 9. 5. 1  提交／回滾協(xié)議                  
 9. 5. 2  鎖                  
 9. 6  數(shù)據(jù)庫技術的社會影響                  
 9. 7  本章復習題                  
 9. 8  社會問題                  
 9. 9  課外閱讀                  
 第四部分  機器的潛力                  
 第10章  人工智能                  
 10. 1  智能與計算機                  
 10. 1. 1  執(zhí)行與仿真                  
 10. 1. 2  圖靈測試                  
 10. 1. 3  “8數(shù)碼問題”機器                  
 10. 2  圖像識別                  
 10. 3  推理                  
 10. 3. 1  產生式系統(tǒng)                  
 10. 3. 2  搜索樹                  
 10. 3. 3  啟發(fā)式搜索                  
 10. 4  人工神經(jīng)網(wǎng)絡                  
 10. 4. 1  基本概念                  
 10. 4. 2  一個特殊的應用                  
 10. 4. 3  聯(lián)想記憶                  
 10. 5  遺傳算法                  
 10. 6  其他研究領域                  
 10. 6. 1  語言處理                  
 10. 6. 2  機器人                  
 10. 6. 3  數(shù)據(jù)庫系統(tǒng)                  
 10. 6. 4  專家系統(tǒng)                  
 10. 7  考慮的問題                  
 10. 8  本章復習題                  
 10. 9  社會問題                  
 10. 10  課外閱讀                  
 第11章  計算理論                  
 11. 1  函數(shù)與計算                  
 11. 2  圖靈機                  
 11. 2. 1  圖靈機的基本原理                  
 11. 2. 2  Church-Turing論題                  
 11. 3  通用編程語言                  
 11. 3. 1  原語言                  
 11. 3. 2  利用原語言編程                  
 11. 3. 3  原語言的通用性                  
 11. 4  不可計算的函數(shù)                  
 11. 4. 1  停機問題                  
 11. 4. 2  停機問題的不可解性                  
 11. 5  問題復雜度                  
 11. 5. 1  衡量一個問題的復雜度                  
 11. 5. 2  多項式對非多項式的問題                  
 11. 5. 3  NP問題                  
 11. 6  公鑰加密系統(tǒng)                  
 11. 6. 1  通過背包問題加密                  
 11. 6. 2  模運算                  
 11. 6. 3  返回加密                  
 11. 7  本章復習題                  
 11. 8  社會問題                  
 11. 9  課外閱讀                  
 第五部分  附  錄                  
 附錄A  ASCII                  
 附錄B  二進制補碼的操作電路                  
 附錄C  一個簡單的機器語言                  
 附錄D  高級程序設計語言示例                  
 附錄E  迭代與遞歸結構的等價性                  
 附錄F  “問題與練習”答案                  
 詞匯表