緒論——課程導學 1
0.1  課程教學定位 1
0.2  課程教學思維 2
0.3  課程知識結構 4
0.4  課程教學輔導 6

基本概念——計算機與計算思維
第1章  計算機科學概述 10
1.1  人類計算工具的進步 10
1.1.1  手工時代 10
1.1.2  機械時代 12
1.1.3  機電時代 15
1.1.4  電子時代 16
1.2  計算機科學體繫的形成 19
1.2.1  布爾提出的邏輯代數 19
1.2.2  香農提出的邏輯電路 19
1.2.3  維納提出的計算機設計原則 20
1.2.4  圖靈提出的圖靈機和圖靈測試 20
1.2.5  馮·諾依曼提出的EDVAC 23
1.3  基於Neumann結構的現代計算機 25
1.3.1  計算機的結構組成 25
1.3.2  計算機的主要特點 26
1.3.3  計算機的基本性能 27
1.3.4  計算機的主要應用 28
1.4  突破與超越Neumann結構 31
1.4.1  突破Neumann的體繫結構 31
1.4.2  突破Neumann的組成結構 34
1.4.3  超越Neumann的體繫結構 35
本章小結 37
習題1 37
第2章  計算機學科體繫 39
2.1  計算機學科體繫的構建 39
2.1.1  科學與學科的概念 39
2.1.2  計算作為一門學科 40
2.1.3  CC2005學科體繫 42
2.1.4  CCC2002學科體繫 45
2.2  計算機學科方法論 47
2.2.1  計算機學科方法論概念 47
2.2.2  計算機學科的3個形態 48
2.2.3  計算機學科的核心概念 49
2.2.4  計算機學科的典型方法 50
2.3  計算機學科的數學方法 52
2.3.1  數學方法及其作用體現 52
2.3.2  構造性數學與證明方法 54
2.3.3  計算機學科的根本問題 56
2.4  計算機學科的經典問題 57
2.4.1  理論意義上的不可計算問題——圖論問題 57
2.4.2  現實意義上的不可計算問題——計算的復雜性 59
2.4.3  理論意義上的可計算問題——計算機智能問題 63
2.4.4  現實意義上的可計算問題——並發控制問題 65
本章小結 66
習題2 67
第3章  計算思維及其作用體現 68
3.1  計算思維及其本質特性 68
3.1.1  人類思維的類別 68
3.1.2  計算思維的概念 71
3.1.3  計算思維的本質 72
3.1.4  計算思維的特性 73
3.2  計算思維的問題求解 75
3.2.1  問題求解的數學建模 75
3.2.2  問題求解的基本策略 76
3.2.3  問題求解的過程抽像 78
3.3  計算思維與計算機學科 82
3.3.1  計算思維本質與學科形態的關繫 82
3.3.2  計算思維在計算機學科中的體現 84
3.4  計算思維的學科作用與能力培養 89
3.4.1  計算思維與計算機教育相互促進 89
3.4.2  計算思維有助於跨越專業鴻溝 90
3.4.3  計算思維有助於其他學科發展 91
3.4.4  計算思維能力培養的基本策略 93
本章小結 95
習題3 95

基本方法——機器計算的基本思維
第4章  數據表示的基本思維 98
4.1  數制及其轉換——“人機兼容”的基本思維 98
4.1.1  進位計數制 98
4.1.2  數制之間的轉換 100
4.2  數值數據的編碼表示——“語義符號數值化”的基本思維 104
4.2.1  整型數的編碼表示 104
4.2.2  實型數的編碼表示 109
4.3  字符數據的編碼表示——“字符信息數字化”的基本思維 111
4.3.1  西文字符的編碼表示 111
4.3.2  漢字字符的編碼表示 113
4.3.3  綜合實例——字符處理 116
4.4  邏輯數據的編碼表示——“邏輯符號數字化”的基本思維 117
4.4.1  邏輯代數概念 117
4.4.2  邏輯代數運算 118
4.5  多媒體數據的編碼表示——“動態信息數字化”的基本思維 120
4.5.1  多媒體的基本概念 120
4.5.2  音頻數字化的編碼表示 121
4.5.3  圖像數字化的編碼表示 122
4.5.4  視頻數字化的編碼表示 124
4.5.5  計算機動畫簡介 125
本章小結 126
習題4 126
第5章  計算繫統的基本思維 128
5.1  計算繫統的基本概念——“繫統組成”的基本思維 128
5.1.1  計算機硬件繫統 128
5.1.2  計算機軟件繫統 129
5.1.3  計算機操作繫統 130
5.1.4  軟件與硬件的關繫 133
5.2  處理器繫統——“控制執行”的基本思維 134
5.2.1  處理器的結構組成 134
5.2.2  計算機指令繫統 136
5.2.3  操作繫統對處理器的管理 137
5.3  存儲器繫統——“存儲優化組合”的基本思維 141
5.3.1  內存儲器 141
5.3.2  外存儲器 143
5.3.3  存儲體繫 144
5.3.4  操作繫統對存儲器的管理 146
5.3.5  綜合實例——計算機的工作過程 148
5.4  文件管理繫統——“長治久安”的基本思維 150
5.4.1  文件與文件繫統 150
5.4.2  文件組織與結構 151
5.4.3  文件目錄與目錄結構 152
5.5  總線繫統與輸入輸出繫統——“組織與協調”的基本思維 154
5.5.1  總線繫統 154
5.5.2  輸入輸出設備 155
5.5.3  輸入輸出接口 157
5.5.4  操作繫統對I/O的管理 158
本章小結 160
習題5 161
第6章  程序設計的基本思維 162
6.1  程序設計概念——“問題抽像”的基本思維 162
6.1.1  程序設計與問題求解 162
6.1.2  程序設計的基本抽像 164
6.2  程序設計語言——“語言抽像”的基本思維 165
6.2.1  程序設計語言的演化 165
6.2.2  程序設計語言的構成 169
6.2.3  計算機源程序的翻譯 173
6.3  程序設計方法——“方法抽像”的基本思維 176
6.3.1  面向過程程序設計方法 176
6.3.2  面向對像程序設計方法 178
6.3.3  程序與軟件的關繫 181
6.4  軟件工程方法——“過程抽像”的基本思維 181
6.4.1  軟件工程概念 182
6.4.2  軟件生存周期 183
6.4.3  軟件開發模型 183
6.4.4  軟件開發方法 186
本章小結 188
習題6 189
第7章  算法構建的基本思維 190
7.1  算法——問題求解的核心 190
7.1.1  算法的基本概念 190
7.1.2  算法的設計要求 191
7.1.3  算法的復雜性 192
7.1.4  算法的描述方法 194
7.2  數值數據求解——算法策略 196
7.2.1  窮舉算法 196
7.2.2  回溯算法 197
7.2.3  遞推算法 199
7.2.4  迭代算法 200
7.2.5  遞歸算法 201
7.2.6  分治算法 202
7.2.7  貪心算法 203
7.2.8  動態規劃 204
7.3  非數值數據處理——數據結構 205
7.3.1  線性表結構 205
7.3.2  棧結構 207
7.3.3  隊列結構 208
7.3.4  樹結構 208
7.3.5  圖結構 210
7.4  素操作——排序和查找 212
7.4.1  排序算法 213
7.4.2  查找算法 217
本章小結 218
習題7 219

基本技術——數據共享與前沿技術
第8章  數據庫技術 222
8.1  數據庫技術概述——抽像（Ⅰ） 222
8.1.1  數據與信息 222
8.1.2  數據庫 224
8.1.3  數據庫管理繫統 225
8.1.4  數據庫繫統 226
8.2  數據模型——抽像（Ⅱ） 228
8.2.1  數據模型概念 228
8.2.2  概念數據模型 230
8.2.3  關繫數據模型 232
8.2.4  關繫數據模式 234
8.3  關繫數據庫——理論 236
8.3.1  關繫代數查詢運算 236
8.3.2  關繫數據查詢優化 240
8.3.3  關繫模式的規範化 241
8.3.4  關繫數據的一致性 242
8.4  構建數據庫應用繫統——設計 243
8.4.1  數據庫應用繫統設計要求 244
8.4.2  數據庫應用繫統設計過程 245
本章小結 249
習題8 250
第9章  計算機網絡技術 251
9.1  計算機網絡概述——抽像 251
9.1.1  網絡的基本概念 251
9.1.2  網絡的基本類型 252
9.1.3  OSI/RM體繫結構 254
9.1.4  TCP/IP體繫結構 255
9.2  網絡數據傳輸——理論 256
9.2.1  網絡數據通信 257
9.2.2  數據傳輸方式 258
9.2.3  多路復用傳輸 259
9.2.4  數據調制編碼 260
9.2.5  數據分組交換 262
9.3  網絡結構組成——設計（Ⅰ） 262
9.3.1  網絡的拓撲結構 263
9.3.2  網絡的邏輯結構 265
9.3.3  計算機網絡互連 266
9.4  Internet應用——設計（Ⅱ） 268
9.4.1  Internet的IP地址 268
9.4.2  Internet的域名繫統 269
9.4.3  Internet提供的服務 271
9.5  信息安全技術——設計（Ⅲ） 272
9.5.1  防病毒技術 273
9.5.2  防黑客技術 274
9.5.3  防火牆技術 274
9.5.4  信息加密技術 276
9.5.5  數字認證技術 279
本章小結 280
習題9 280
第10章  計算機前沿技術 282
10.1  人工智能技術 282
10.1.1  人工智能的基本概念 282
10.1.2  人工智能的關鍵技術 284
10.1.3  人工智能的技術應用 285
10.2  虛擬現實技術 287
10.2.1  虛擬現實的基本概念 288
10.2.2  虛擬現實的關鍵技術 291
10.2.3  虛擬現實的技術應用 291
10.3  移動互聯網技術 293
10.3.1  移動互聯網的基本概念 293
10.3.2  移動互聯網的關鍵技術 294
10.3.3  移動互聯網的技術應用 295
10.4  物聯網技術 296
10.4.1  物聯網的基本概念 297
10.4.2  物聯網的關鍵技術 298
10.4.3  物聯網的技術應用 299
10.5  雲計算技術 301
10.5.1  雲計算的基本概念 301
10.5.2  雲計算的關鍵技術 303
10.5.3  雲計算的技術應用 304
10.6  大數據技術 305
10.6.1  大數據的基本概念 305
10.6.2  大數據的關鍵技術 307
10.6.3  大數據的技術應用 308
本章小結 308
習題10 309
參考文獻 311

- VI -
計算機科學與計算思維導論

- VII -
目??錄

“計算機科學與計算思維導論”是計算機科學、計算機工程、軟件工程、信息技術等分支學科的學生全面了解計算機學科基本概貌的引導性課程，也是電子信息類專業重要的基礎課程。
在計算機教育史上，有關學科綜述性引導課程的構建一直受到各國計算機學界的高度重視。IEEE-CS＆ACM計算學科教程（Computing Curricula 2001，CC2001）報告指出：整個學科綜述性引導課程的構建有助於推動學科的發展，鼓勵各學術團體及教師個人從事這方面的研究，以適應計算機科學技術飛速發展的需要。因此，自CC2001發布以來，世界各國高校都非常重視計算機學科“引導”課程的構建，紛紛開設了“計算機（科學）導論”“計算機（科學）概論”一類的課程。為此，筆者經歷了漫長而不懈的探索，編寫且多次再版了《計算機科學導論》。
隨著計算機學科教育研究探索的深入，人們提出了“計算思維”（computational thinking），它是人類求解問題的一條有效途徑，是一種分析問題、解決問題的過程和思想。如何將計算思維融入計算機學科體繫中，不僅受到計算機相關專業從教者的高度關注，而且得到學術團體和門的高度重視。2007年，美國國家科學基金會（National Science Foundation of America，NSF）將“計算思維能力”（computational thinking ability）培養列為“大學計算機教育重生的途徑計劃”的核心。2012年，我國要求大學計算機教育的總體建設目標應該定位在“普及計算機文化，培養專業應用能力，訓練計算思維能力”上，並明確定位大學計算機課程是與數學、物理等同地位的重要基礎課程。
面對這種新思想和新要求，如何將計算思維引入計算機學科的引導課程及其知識體繫中，即如何構建基於計算思維的綜述性引導課程，如何進行課程定位，應該起到什麼作用，應該達到什麼目的等，這些既是需要認真思考的問題，也是必須首先明確的問題。為此，筆者一直在對計算機學科引導課程的構建進行深入探索，並在探索中不斷提高構建該課程的認識。
（1）基於計算機學科形態的“計算機科學導論”的思想方法是抽像、理論、設計，而計算思維的本質是抽像與自動化，如何將學科形態與計算思維相融合，並充分發揮學科形態與計算思維在人纔培養中的引導作用，是計算機學科引導性課程的核心，也是本課程的創新和突破點。
（2）基於計算機學科體繫的“計算機科學導論”不同於“大學計算機基礎”，雖然它們都是計算機學科的入門課程，但課程性質完全不同。“大學計算機基礎”是非計算機專業的公共基礎課程，為專業課程服務，課程構建的實質是對計算機功能的工具性認識；而“計算機科學導論”是計算機類專業全程教學內容的引導性課程，課程構建的實質是尋求一種統一的思想來認知計算機學科，即站在學科的高度對計算機學科進行科學化和繫統化的描述，並注重學科發展的動態性和知識傳授的有效性。由於計算思維是運用計算機科學的基礎概念求解問題、設計繫統和理解人類行為的科學方法，將計算思維融入計算機學科的知識體繫中，會極大地加深對計算機科學及其學科的認識。
（3）作為計算機學科的引導課程，應承擔起一種“承前啟後”的作用。所謂“承前”，就是介紹計算機的形成與發展歷程，讓學生了解計算機學科的內涵及其來龍去脈，並從中受到啟迪；所謂“啟後”，就是描述計算機學科的知識體繫，讓學生懂得應該掌握哪些知識、具備什麼樣的知識結構和能力，以便在學習過程中明確目標，把握現在，放眼未來。
（4）作為計算機學科的通識課程，應涵蓋計算機學科教育的各個方面。通過本課程的學       習，透視學科體繫、展示學術魅力、掌握學習方法、培養計算思維、傳承計算文化、弘揚科學精神、激發拼搏意識，燃起探索熱情。
隨著對該課程教學研究與探索的深入，圍繞“教什麼”和“怎樣教”以及“計算思維”與“學科形態”內在關聯等問題，我們不斷更新課程建設理念，不斷調整課程知識結構，不斷尋求突破與創新，構建計算機科學與計算思維相融合的課程體繫。本書就是上述思想的具體體現，並力圖實現如下教學目標。
（1）抓住實質，體現導論課程內涵。作為導論課程，應充分體現“導”與“論”的真實內涵。
所謂“導”，就是站在學科的高度俯瞰計算機學科全貌，引導學生全面了解計算機學科的知識體繫、學科形態、科學方法、根本問題、經典問題等，而不是深入探討分支細節，避免“隻見樹木，不見森林”。許多具體問題可以“知其然，不知其所以然”，詳細內容在後續相關課程中討論。
所謂“論”，就是基於學科形態的方法論。本書以“計算機學科是一門計算的學科，計算機繫統是一個離散化繫統，計算機方法是一種形式化方法”作為計算機學科方法論的立足點和著力點。
計算機學科方法論是本課程的核心。事實上，教會學生某一知識或技術遠不如教會學生掌握分析問題和解決問題的方法重要，正所謂“授人以魚，不如授人以漁”。這既是“計算機科學與計算思維導論”與“大學計算機基礎”及其他課程的本質區別所在，也是本書（本課程）的教學目標所在。
（2）創新結構，構建計算思維體繫。本書以計算思維為引導，以學科形態為紐帶，以能力培養為目標，創新性地構建了計算思維方法與計算學科形態相融合的知識體繫。這樣，既體現了計算思維與學科形態在課程教學中的引導作用，又為學生創造了更多計算思維的實踐機會，著實培養學生運用計算思維分析問題、解決問題的方法和能力。構建本課程知識體繫的指導思想是體現學科基礎特性、突出科學思維方法、涵蓋學科知識主領域的“進階式-模塊化”知識體繫結構。
基本概念（第1～3章）：計算機科學概述，計算機學科體繫，計算思維及其作用體現；
基本方法（第4～7章）：數據表示的基本思維，計算繫統的基本思維，程序設計的基本思維，算法構建的基本思維；
基本技術（第8～10章）：數據庫技術，計算機網絡技術，計算機前沿技術。
因而，本書結構新穎、層次分明、由淺入深、循序漸進、邏輯性強、遠近兼顧、便教便學。
（3）啟迪思維，揭示計算學科特性。本書力圖通過計算機的形成與發展，揭開計算機科學的神秘面紗；通過硬件子繫統與操作繫統管理相結合，揭示計算繫統的工作機制；通過數據表示、計算繫統、程序設計、算法構建，揭示計算思維的本質——抽像與自動化；通過數據庫技術、網絡技術及新技術應用，揭示計算學科的形態——抽像、理論、設計。從而使得思維隨著知識的貫通而形成，能力隨著思維的形成而提高，並通過深入分析與比較，使學生認識到構建計算思維本質與計算學科形態的目標是一致的，其宗旨是尋找通用的方法，處理類似的問題。以此啟迪學生去科學思考，為日後在專業領域中能有所發現、有所突破、有所創新奠定基礎。
（4）問題引導，激發學生求知欲望。本課程的重要意義是使學生對計算機學科的各知識領域產生濃厚的學習興趣和強烈的求知欲，同時又有太多的疑惑和不理解，非常渴望了解其中的科學道理，這是學好本專業的源動力，正所謂“知之者不如好之者，好之者不如樂之者”。本書各章均以“問題引出”導入所要探討的內容，使學生在學習過程中有的放矢，帶著問題去尋找答案，懷著好奇心去探索奧秘，從而消除學習中的畏難情緒，調動學習的積極性，激發學習的創造性。
（5）多措並舉，強化全程能力培養。計算機學科的特點是知識面寬、實踐性強、軟硬件技術更新換代快，所以既要重視理論學習能力的培養，也要重視實踐能力的培養，更要重視自我提高能力的培養。為此，還編寫了與本書配套的《計算機科學與計算思維導論學習輔導》，其中包含實驗指導的內容，形成融理論教學、學習輔導和實驗指導三位一體的教學環境，從而使學生在潛移默化中意識到能力培養的全面性、知識更新的重要性、自我提升的必要性。
總之，無論是課程建設理念，還是知識結構；無論是教學內容，還是思維方法，都力求體現創新性、規範性、先進性和示範性，並在傳授知識的同時，弘揚中華文化對人類社會發展的貢獻。
教材是課程建設的真實體現，先進的課程建設理念和設計思想，終需要通過教材來組織與實施。同時，教材是課程教學的基本依據，是教學研究、探索和改革的載體，它容納了教學目標和教學內容，明確了教學過程和教學方法，體現了教學理念和教學思想。因此，合理定位本課程的教學內容，形成科學的知識體繫和穩定的知識結構，使之成為重要的引導性課程，是“計算機科學導論”課程教學改革的主要目標；根據課程的作用、地位和特點，以計算思維能力培養為切入點，是深化該課程教學改革、提高課程品質和教學效果的重要任務。本書是將教學研究、課程建設與能力培養相結合的具體體現，也是作者多年來探索課程教學改革與人纔培養的結晶。
本書由李雲峰、李婷和丁紅梅編著，李雲峰負責統稿，姚波、曹守富等老師參與了課程資源的建設工作。
在本書的編寫過程中，參閱了大量近年來出版的國內外同類優秀教材，並從中吸取了大量寶貴營養，在此謹向這些著作者表示衷心感謝！
由於本書在教學思想、知識體繫、內容組織等方面都是一種新的探索，因此難免存在疏漏、不妥甚至錯誤之處，敬請讀者批評指正。

作  者????
2023年1月

- II -
計算機科學與計算思維導論

- III -
前??言