第1章計算機科學概貌1
1.1計算機科學領域現狀1
1.2計算機科學的發展脈絡8
1.2.1巴貝奇問題——如何構建計算機9
1.2.2布什問題——如何使用計算機11
1.2.3圖靈問題——如何構建智能應用13
1.2.4計算機科學的3個奇妙之處17
1.3計算思維的特征22
1.3.1離散化與數字化22
1.3.2計算機的馮·諾依曼模型24
1.3.3計算機科學解題思路26
1.3.4對計算思維的10種理解38
1.4科學計算的創新故事43
1.4.1地球繫統數值模擬的創新故事43
1.4.2蛋白質結構預測的創新故事44
1.5習題47
第2章程序的設計與執行50
2.1如何表示數和字符50
2.2初識計算機編程55
2.2.1編寫第一個Go程序56
2.2.2初識數據類型59
2.2.3運算流與簡單控制流62
2.2.4初識模塊化編程66
2.3初識計算機設計73
2.3.1斐波那契計算機的硬件74
2.3.2斐波那契計算機的軟件74
2.3.3斐波那契計算機的狀態轉移75
2.4計算機程序的創新故事852.4.1Ada的故事: 第一個計算機程序85
2.4.2霍爾悖論: 快速排序程序為什麼難以理解88
2.5習題89
第3章邏輯思維94
3.1布爾邏輯94
3.1.1命題邏輯94
3.1.2謂詞邏輯108
3.2圖靈機模型110
3.2.1定理機器證明與吳方法110
3.2.2有窮自動機111
3.2.3圖靈機112
3.2.4邱奇圖靈論題117
3.2.5悖論與不完備定理118
3.3計算邏輯的創新故事119
3.3.1布爾的故事119
3.3.2圖靈的故事122
3.4習題123
◆計算機科學導論——以計算思維為舟目錄第4章算法思維127
4.1什麼是算法127
4.2算法思維的要點129
4.2.1分治算法範式129
4.2.2其他算法範式136
4.3算法的創新故事144
4.3.1算法復雜度的故事144
4.3.2平穩復雜度146
4.4習題148
第5章繫統思維152
5.1繫統思維一覽152
5.1.1周到性153
5.1.2整體性155
5.1.3應對復雜性158
5.2抽像化161
5.2.1抽像三性質161
5.2.2數據抽像164
5.2.3文件與文件繫統173
5.2.4控制抽像181
5.2.5模塊抽像186
5.2.6（）操作繫統簡介191
5.3模塊化191
5.3.1邏輯門與組合電路192
5.3.2信息隱藏原理193
5.3.3時序電路198
5.4無縫銜接204
5.4.1揚雄周期原理204
5.4.2電路的無縫銜接: 寬進嚴出原理實例211
5.4.3指令的無縫銜接: 馮·諾依曼窮舉原理實例213
5.4.4阿姆達爾定律214
5.5計算繫統的創新故事216
5.5.1IBM S/360216
5.5.2關繫數據庫220
5.6習題223
第6章網絡思維229
6.1初識互聯網230
6.1.1初識萬維網編程230
6.1.2網絡名詞術語233
6.1.3網絡思維的價值235
6.2連通性238
6.2.1名字空間238
6.2.2網絡拓撲243
6.3協議棧245
6.3.1分組交換246
6.3.2互聯網協議棧247
6.4專業素養254
6.4.1性能意識254
6.4.2安全意識258
6.4.3專業規範264
6.5網絡的創新故事266
6.5.1第一個計算機網絡266
6.5.2因特網與萬維網268
6.5.3大數據計算273
6.5.4臭蟲與病毒274
6.6習題279
第7章計算機學科展望284
7.1學科研究對像與研究問題285
7.1.1研究對像285
7.1.2研究方法285
7.1.3格雷12問題287
7.1.4主要進步288
7.2學科演變與主要研究方向293
7.2.1學科演化樹293
7.2.2計算機科學與技術296
7.2.3新型計算機300
致謝303
附錄A計算機科學技術中常用的倍數和分數304
參考文獻306

本書以計算思維為主線介紹計算機科學的入門知識，主要針對一年級本科生的“計算機科學導論”“大學計算機基礎”“計算概論”課程。本書的撰寫考慮了全球發展趨勢與中國的實際情況，具備下述4個特點。
(1) 強調計算思維。本書試圖突出計算機科學最本質的特征: 計算機科學是研究計算過程的科學，計算過程是通過操作數字符號變換信息的過程。最本質的解決問題方法是計算思維，包括邏輯思維、算法思維、繫統思維和網絡思維。
(2) 強調基礎知識。本書並不追求覆蓋眾多新概念，而是突出計算機科學不過時的最基礎的入門知識點，並將它們組織成對計算思維的10個理解: 自動執行、正確性、通用性、構造性、復雜度、抽像化、模塊化、無縫銜接、連通性、協議棧。
(3) 鼓勵主動學習。本書的設計鼓勵學生主動學習，但教師講解與課堂互動有利於揭示要點難點、提高學習效率。本書還提供了動手動腦的課程實驗，對應於邏輯、算法、繫統和網絡4部分內容。
(4) 鼓勵勝任力教育。本書參考了ACM/IEEECS在2021年發布的《計算課程體繫規範》（CC2020）。為了實踐CC2020倡導的勝任力教育理念，本書實踐了“高德納測試”，並花了不少篇幅講解計算機領域的真實創新故事，讓同學們了解前人如何通過計算思維認識世界、提出問題、解決問題。
一、 致謝
本書的構思、寫作、實踐優化持續了10年，主要的難點是如何體現計算思維。作者要感謝北京大學李曉明教授，他多年來一直鼓勵和敦促我們寫一本計算機科學導論教科書。感謝時任美國國家科學基金會副主任的周以真（Jeannette Wing）博士，她多次與我們討論了計算思維要點。感謝加州大學伯克利分校的Richard Karp教授，他多次與我們討論計算透鏡思想與計算過程要點。感謝中國科技大學陳國良教授與合肥工業大學李廉教授，以及大學計算機基礎課程教學指導委員會。這些老師花了很多精力在中國推動計算思維改革，為本書提供了很多同行經驗。感謝北京大學的張銘教授向我們解讀ACM/IEEECS《計算課程體繫規範》，她是CC2020的15 位指導委員會成員之一。
特別感謝中國科學院大學的同學們，他們是本書的第一批讀者，也是本書作為教科書的計算機科學導論課程的第一批實踐者。感謝中國科學院計算技術研究所的博士生朝魯、李春典、趙永威、李振營、俞子舒、李奉治、郭泓銳，他們擔任了課程的助教並幫助撰寫了課程實驗內容。感謝中國科學院大學的李思悅、呂星宇、董可昕同學，他們為本書的創造性學習內容提供了案例。
本書引用了業界的大量素材，在此一並致謝。我們要感謝開源社區，尤其是LAMP（Linux、Apache、MySQL、PHP/Perl/Python）社區。感謝學術社區，尤其是ACM、IEEECS、CCF。ACM（Association for Computing Machinery）與IEEECS（IEEE Computer Society）是全球最大的計算機科學技術領域的國際學術社區。CCF（中國計算機學會）有10萬多名會員，是全球第二大的計算機學會。它們的旗艦雜志分別是Communications of the ACM、IEEE Computer以及《中國計算機學會通訊》。
我們還要感謝眾多的公司和機構，本書合理使用了它們的素材（例如公司名稱、技術和產品名稱、logo），這些名稱和標志都是這些公司的知識產權。這些公司包括亞馬遜、AMD、蘋果、AT&T、百度、思科、Docker、Meta、通用電氣、谷歌、紅帽、華為、IBM、英特爾、聯想、領英、龍芯、微軟、甲骨文、曙光、騰訊、W3C、小米等。南京信息高鐵研究院提供了算力資源。
特別致謝斯坦福大學計算機繫榮休教授(Professor Emeritus)高德納老師（Donald Knuth），他長期關心中國計算機教育。這位85歲高齡的碼農今天還在科教一線精力充沛地工作，撰寫教科書、設計算法、編程序、寫論文。他在2020年再次強調: “我是否理解某項知識的終極測試，是看我能否向計算機講解清楚。”本書將他的觀點稱為“高德納測試”，用於指導教學。
二、 課程網站
本書包含課件、實驗課件、部分習題答案、程序源碼和其他教學工具，可掃描如下二維碼查看。
配套資源信息
三、 說明
書中標注有三個星號（）的是進階內容。

徐志偉孫曉明2023年秋於北京中關村◆計算機科學導論——以計算思維為舟學習目標和學習方法
我們使用“本課程”指稱使用本書作為教科書或參考書的“計算機科學導論”或“大學計算機基礎”課程。本課程面向所有專業的一年級本科生，以計算思維為主線，學習計算機科學的最基礎的入門知識。那麼，什麼是計算思維？什麼是計算機科學的最基礎的入門知識？如何知道是否掌握了這些知識？
計算機科學不僅提供一種科技工具、一套知識體繫，更重要的是提供了一種從信息變換角度有效地解決問題的思維方式，這就是作為計算機科學主線的計算思維Wing J. Computational thinking［J］. Communications of ACM. 2006,49 (3): 3335. 。計算思維也是計算機專業人士解決問題的思維方式，其要點是精準地描述計算過程，並使用計算過程認識世界、改造世界、定義問題、解決問題。
一、 教學目標
本課程針對所有專業的一年級本科生，在一學期學完計算機科學導論，達成3個目標。
(1) 掌握基本詞彙。掌握計算機科學的基本詞彙，能夠與計算機同行進行入門級的交流。例如，訪問網站時輸入的“http://cs101.ucas.edu.cn/中文”是什麼意思？ 什麼是計算機的“馮·諾依曼模型”？
(2) 理解基礎知識點。能夠用至少一個實例描述下列基本概念的要點: 抽像計算機、真實計算機、計算機應用、數字符號、抽像、算法、作品、指數增長、計算的極限、智能。在此基礎上，領悟對計算思維的10個理解。
(3) 提升勝任力。提升《計算課程體繫規範》(CC2020)倡導的勝任力ACM, IEEECS. Computing Curricula 2020: Paradigms for Global Computing Education. https://www.acm.org/binaries/content/assets/education/curricularecommendations/cc2020.pdf.。課程專門安排了讓同學們融會貫通基礎知識點、創造性實現個人作品的實驗。
1. 基本詞彙
(1) 數（number）也稱為數值（value）。計算機科學將所有事物表示為數並對其操作，從輸入數值產生輸出數值。
(2) 數位（digit）是表示數值的基本數字。我們最熟悉的是十進制數位（decimal digit）。例如，十進制數279有三個十進制數位，分別是2、7、9三個數字，它們合起來代表二百七十九這個數值。
(3) 比特（bit或binary digit）是二進制數位，即取值為0或1的數位。例如，二進制數1110有4比特，分別是1、1、1、0。二進制數1110等價的十進制數是14。
(4) 數字符號（digital symbol）是可由一個或多個比特表示的記號，用於表示一個抽像或具體的事物。每個數字符號本質上都會表示為一個二進制數。
(5) 字（word）。計算機處理數值的基本單位，所需比特數稱為字長（word length）。例如，在64位計算機中，一次加法是64比特的加法。
(6) 字節（byte）特指8比特構成的數字符號。
(7) 字符（character）是一類特殊的數字符號，表示某種文明的文本（text）。本書重點關注兩類字符集: 表示英文文本的ASCII字符集，包含A、b、7、$等字符；以及表示全球文本的Unicode字符集，包含A、⊙、、中、。
(8) 算法（algorithm）是一組有窮的規則，給出求解問題的數字符號操作步驟序列。
(9) 程序（program）是算法的編程語言表示，也就是說，程序是采用某種計算機語言表示的算法。代碼（code）是指一部分程序，可大到包括整個程序。軟件（software）包括程序及說明程序的文檔。
(10) 數據（data）是一組數字符號。當程序或數據被持續存放在計算機中時，它們被稱為文件（file）。持續存儲是指，當計算機斷電後，文件不會丟失。
(11) 數據類型（data type）是特定類型的數據在計算機中的表示及其操作規則。本書主要關注5種數據類型: 布爾值、整數、字符、數組、切片。
(12) 控制抽像（control abstraction）說明多個操作的順序。本書主要關注5種控制抽像: 運算優先級、串行順序、條件判斷、循環、函數調用（包括遞歸調用）。
(13) 計算機（computer）包括抽像計算機（如圖靈機）和真實計算機（如筆記本計算機）。
(14) 繫統（system）主要是指計算機（如筆記本計算機）。也用於指稱計算機應用繫統（如微信繫統）、計算機的部件子繫統或由多臺計算機組成的計算機網絡繫統。
◆計算機科學導論——以計算思維為舟學習目標和學習方法2. 基礎知識點集合
美國科學院和工程院設立的“計算機科學基礎問題委員會”在2004年撰寫了《計算機科學基礎報告》National Research Council Committee on Fundamentals of Computer Science. Computer Science: Reflections on the Field［M］. The National Academies Press, Washington D.C., 2004. ，歸納了計算機科學的基礎知識點集合，如下框所示。本課程以此報告為基礎，添加了計算機領域概貌介紹和創新故事等內容。《計算機科學基礎報告》的基礎知識點
計算機科學是研究計算機及其能干什麼的一門學科。它研究“抽像計算機的能力與局限，真實計算機的構造與特征，以及用於求解問題的無數計算機應用”。
報告還總結了計算機科學具有的一些本質特點。
(1) 計算機科學涉及符號及其操作。
(2) 計算機科學關注多種抽像的創造和操作。
(3) 計算機科學創造並研究算法。
(4) 計算機科學創造各種人工制品，尤其是不受物理定律限制的作品。
(5) 計算機科學利用並應對指數增長。
(6) 計算機科學探索計算能力的基本極限。
(7) 計算機科學關注與人類智能相關的復雜的、解析的、理性的活動。

本課程設計的一個考慮是: 針對大學所有專業的一年級本科生，包括沒有任何計算機編程經驗的學生，在一學期學完計算機科學導論。因此，不能簡單地羅列討論一個面面俱到的知識點集合，而應該繫統地取舍和組織內容。
例如，本書使用了抽像棧（a stack of abstraction layers）概念（表1），幫助同學們融會貫通計算思維知識點。不隻是停留在如何設計算法解決排序問題或斐波那契數列問題，而是貫穿從算法到電路實現的全棧，下沉到如何用高級語言程序和彙編語言指令實現循環，直到布爾電路層面。這使得同學們從單純的計算機用戶變成了計算機設計者，有利於提升技能到創造層次。這就像語文課要求同學們不隻是能夠讀文章，還能夠寫文章。為了避免煩瑣細節，組合電路和時序電路層面隻考慮加法。掌握了做加法的原理，就可推廣到做減法、乘法、除法，乃至實現各種組合電路和時序電路。表1抽像棧概念示意
3. 勝任力本位教育
ACM與IEEECS在2021年聯合發布了《計算課程體繫規範》。它由全球20多個計算機學會（包括中國計算機學會）的專家共同制定。這個規範有兩個當代特色值得重視。
(1) 教育理念從知識本位教育（knowledgebased education）轉向勝任力本位教育（competencybased education），其中:
勝任力=知識 技能 品行
Competency=Knowledge Skills Dispositions
(2) 認知技能采納了教育學中的布魯姆教育目標六等級（Blooms Taxonomy），即記憶、理解、應用、分析、評估和創造，如圖1所示。
圖1布魯姆教育目標六等級(2001年修訂版)
本課程倡導將布魯姆教育目標從記憶等級提升到創造等級，品行方面鼓勵想像力。
參考勝任力本位教育理念，本課程的教育目標還可歸納為表2所示。其中，期望同學們對基礎知識點的掌握50%達到創造等級，25%達到理解等級。品行不是簡單的“如何做人”，而是鼓勵計算思維的想像力、熱情與責任心。在此基礎上領悟對計算思維的10個理解。表2本課程的教育目標勝任力(Competency)知識(Knowledge)技能(Skills)品行(Dispositions)針對問題求解和創造性表達的勝任力抽像計算機、真實計算機、計算機應用、數字符號、抽像、算法、人工制品、指數增長、計算能力的基本極限、人類智能相關的活動50% 創造
(Create)
25% 理解
(Understand)
25% 記憶
(Remember)想像力
(Imagination)
熱情
(Passion)
責任心
(Responsibility)二、 教學方法〖*2〗1. 知行合一的主動學習方法本課程融合了當代計算機科學教育理念，提倡知行合一的主動學習方法。本書在闡述狹義的計算機科學知識之外，還用不少篇幅講述創新故事，並通過動手動腦的課程實驗，鼓勵同學們創造性地學習。這種方法有利於提升同學們的學習主動性，有利於實踐勝任力本位教育。這種主動學習方法不同於高中學習，對本科一年級同學具有一定挑戰性，需要教學團隊實踐“有溫度的”教學。本書的內容組織考慮了教學的主動性與溫度。
通過知行合一的主動學習方式，同學們能夠達到表3的學習目標。可以看出，它們覆蓋了《計算機科學基礎報告》的基本要點。續表表3學完本書後同學們能夠達到的學習目標《計算機科學基礎報告》
的基本要點知行合一的學習目標舉例抽像計算機實現二進制串行加法器的圖靈機真實計算機在筆記本計算機上編寫執行簡單程序解決問題計算機應用信息隱藏應用程序數字符號從比特、字節、數、字符、圖像到網頁的各種數字符號；從加、減、乘、除到賦值語句的各種操作符號抽像布爾變量、整數、字符、數組、切片等數據抽像；順序、條件判斷、循環、函數調用、遞歸等控制抽像；組合電路、時序電路、指令流水線等硬件抽像；指令、進程、程序等軟件抽像算法高德納算法定義；分治算法、動態規劃算法、快速排序算法人工制品動態網頁個人作品指數增長“P與NP”的基本概念；摩爾定律計算能力的基本極限圖靈可計算性，邱奇圖靈命題，停機問題；哥德爾不完備定理人類智能相關的活動布爾邏輯，演繹推理2. 高德納測試
在2020年2月的一次科技媒體訪談中，高德納老師提出了一個終極測試。他說: “我是否理解某項知識的終極測試，是看我能否向計算機講解清楚。”為了避免斷章取義，我們列出完整的英文原文段落: The ultimate test of whether I understand something is if I can explain it to a computer. I can say something to you and youll nod your head, but Im not sure that I explained it well. But the computer doesnt nod its head. It repeats back exactly what I tell it. In most of life, you can bluff, but not with computers.DAgostino S. The Computer Scientist Who Cant Stop Telling Stories. Quanta Magazine. 2020,(4). https://www.quantamagazine.org/computerscientistdonaldknuthcantstoptellingstories20200416.
本書將他的觀點稱為高德納測試（Knuths Test）。這是將布魯姆教育目標貫徹到計算機教育的一個絕妙測試，為同學們提供了一個實用的教育學工具，可用於檢測自己是否掌握了某項知識或能力: 看自己能否向計算機講清楚。
如何向計算機講清楚一項知識或能力呢？本質上是通過比特精準的計算過程。下面列出3種具體途徑。
(1) 計算機程序。將該項知識或能力具像為計算機程序，在計算機上正確地執行程序，提供典型的輸入數據，返回期望的結果。例如，某位同學測試自己是否掌握“個人作品”相關知識和能力，一個途徑是該同學開發一個動態網頁，在計算機上運行起來，體現創造性表達。在此過程中，如果同學誤解了網頁相關的HTML、CSS或JavaScript知識，程序往往會出現期望之外的行為，計算機會報錯。
(2) 思想實驗（thought experiment）。與計算機程序途徑很像，隻是“計算機”變成了同學自己的大腦（或“心”）。同學自己通過“心算”，當然也可以輔之以紙和筆，在自己心中執行任意一個具體的計算過程。例如，測試是否掌握了“遞歸”概念，即遞歸函數調用，可在自己心中執行任意一個具體的遞歸計算過程，例如快速排序。這個途徑的要點是，“心”必須裝扮成一臺計算機，每一步隻能執行明確的步驟，響應明確的指令，使用精準的輸入，產生精準的輸出結果。
(3) 結對實驗（pairing experiment）。與計算機程序途徑很像，隻是“計算機”變成了另一個同學或助教。這個途徑的要點是，另一個同學必須裝扮成一臺計算機，每一步隻能執行明確的步驟。有時，一個同學也可以扮演這兩個角色: 本人和“另一個同學”。
高德納測試可用於測試布魯姆教育目標六等級的各個等級。下面列出對應“記憶”“理解”“創造”3個等級的教學建議和高德納測試，並舉例說明。注意，這些等級總地來講是逐漸包含關繫，高等級包含了低等級的教學要求。
(1) 記憶等級: 這是最低等級。針對每個概念或方法，每個同學能夠較為精準地重述，並舉一個教科書或課堂講授提到過的實例說明。
高德納測試例子: 可通過習題、考題、實驗重現該概念或方法，並通過比特精準的計算過程，測試出重現結果是否與正確答案契合。
(2) 理解等級: 針對每個概念或方法，每個同學能夠較為精準地解釋它，動手動腦闡述一個具體實例，並能夠舉一反三，應用到講過的問題實例的變種。
高德納測試例子: 本書要求同學們使用圖靈機實現加法器；在此過程中，同學們應該理解了使用圖靈機求解問題的入門知識，從而能夠自行實現本書沒有闡述過的圖靈機減法器。
(3) 創造等級: 掌握了課程相關的勝任力，即“知識 技能 品行”，並能夠應用到新場景，定義新問題、自學新知識、提出新觀點、實現新作品。這裡的關鍵是“新”，是教科書或課堂講授沒有提到過的。
高德納測試例子: 本課程的個人作品實驗體現了高德納測試。同學們需要無中生有地創造、構思並設計作品，在計算機上實現為動態網頁，分享給全班同學。同學們需要將Go語言編程知識遷移到網頁設計的新場景中，自學個人作品需要的網頁設計和編程的新知識。教學團隊會介紹少量入門網頁編程知識，並提供動態網頁實例庫和答疑幫助。
三、 一年級本科生創造性學習實例
下面列舉中國科學院大學的一年級本科生創造性學習的3個真實例子，進一步顯示布魯姆教育目標的“創造”等級和高德納測試。這些實例都是同學們自己想像出來的。
【實例1】呂星宇的“活體U盤”。
本課程的信息隱藏實驗要求將一個英文文本文件隱藏到一個圖像文件中。在完成信息隱藏實驗的實踐中，中國科學院大學計算機專業的呂星宇同學發現: 中文文本文件也可以被隱藏和復原！他的好奇心和探索導致他提出