新聞一
本課程是“計算機科學導論”國家級精品課程的MOOC版本，本課程將課程的結構建立在計算學科認知模型的基礎上，并以計算機科學的內容為背景，在學科思想與方法層面上對學生認知計算學科進行導引，借助大量案例，著力提高學生在復雜問題的分析和求解，系統設計，以及人類行為理解方面的計算思維能力。
—— 課程團隊
課程概述
本課程是計算機類專業學生入學學習的第一門計算機基礎必修課，它構建在計算學科認知模型的基礎上，并以計算機科學的內容為背景，從學科思想與方法層面對計算學科進行導引，著力提高學生的計算思維能力。本課程來源于ACM教育委員會對“整個計算學科綜述性導引”課程構建的要求，即用嚴密的方式將學生引入計算學科各個富有挑戰性的領域之中。本課程為學生正確認知計算學科提供方法，為今后深入學習計算機課程作鋪墊。
授課目標
本課程要求學生了解計算學科的認知模型；學科的基本問題；學科抽象、理論和設計三個形態；學科中的核心概念、數學方法、系統科學方法，以及社會和職業問題等內容。“復雜”這個詞貫穿本課程的始終，要求學生通過大量案例的訓練，初步掌握運用計算機科學的基礎概念控制和降低復雜工程問題的思想與方法。
課程大綱
一、緒論
1.主要內容
（1）計算學科的定義；
（2）計算學科的根本問題；
（3）“計算機科學導論”課程的構建問題；
（4）計算學科認知模型——計算學科二維定義矩陣；
（5）計算思維與計算機科學導論。
2.基本要求
（1）了解計算學科的定義；
（2）了解計算學科的根本問題，即“能行性”問題；
（3）了解“計算機科學導論”課程構建問題提出的背景和意義；
（4）了解計算學科認知模型——計算學科二維定義矩陣提出的背景和意義；
（5）了解計算思維與計算機科學導論的關系。
3.重點、難點
重點：計算學科的根本問題，計算學科二維定義矩陣，計算思維與計算機科學導論。
難點：計算學科二維定義矩陣。
二、計算學科的基本問題
1.主要內容
（1）對問題進行抽象的典型實例——哥尼斯堡七橋問題；
（2）漢諾塔問題；
（3）停機問題；
（4）證比求易算法；
（5）P＝NP？；
（6）RSA公開密鑰密碼系統；
（7）旅行商問題與組合爆炸問題；
（8）找零問題、背包問題與貪婪算法；
（9）GOTO語句與程序設計中的結構問題；
（10）哲學家共餐問題與計算機系統中的軟硬件資源的管理；
（11）兩軍問題與計算機網絡；
（12）圖靈測試與“中文屋子”；
（13）計算機中的博弈問題。
2.基本要求
（1）能夠將一般的回路問題抽象成歐拉回路或者哈密爾頓回路問題，并對是否存在回路進行判定；
（2）初步掌握遞歸算法的構造，能夠分析求解漢諾塔問題的時間復雜度（
）；
（3）通過停機問題理解不可計算問題；
（4）理解順序算法和并行算法，并獲得 “證比求易（verifying is easier than finding solutions）”這個元認知知識；
（5）區分P類問題和NP類問題，了解計算機技術發展中“P=NP?”問題提出的背景和意義；
（6）構建一個簡單的RSA公開密鑰密碼系統，在該密碼系統下進行信息的加密和解密；
（7）通過旅行商問題了解組合爆炸問題；
（8）理解簡單的啟發式算法，應用啟發式的貪婪算法求解背包問題；
（9）理解程序結構設計的重要性，了解計算機技術發展中“GOTO語句有害”這一觀點提出的背景和意義；
（10）能夠對計算機資源管理的互斥問題進行簡單分析；
（11）通過案例可以對網絡協議的復雜性和微妙性進行簡單分析，認知處理復雜系統所采用的分層抽象策略，了解使用該策略控制和降低系統復雜程度的重要作用；
（12）了解圖靈對“機器思維”的定義，了解計算機技術發展中圖靈測試提出的背景和意義，了解強人工智能與弱人工智能的不同，了解計算機技術發展中西爾勒中文屋子提出的背景和意義；
（13）通過計算機博弈問題初步了解人工智能領域研究工作的進展。
3.重點、難點
重點：漢諾塔問題，證比求易算法，P=NP?問題，RSA公開密鑰密碼系統，停機問題，找零問題、背包問題與貪婪算法，分支和循環結構的簡單程序。
難點：漢諾塔問題的算法設計。
三、計算學科中的3個學科形態
1.主要內容
（1）一個關于“學生選課”的例子；
（2）抽象、理論和設計3個學科形態；
（3）自然語言與形式語言；
（4）圖靈機的特征及其工作原理；
（5）馮·諾依曼計算機及基于馮·諾依曼計算機的Vcomputer實例；
（6）機器指令與匯編語言及基于Vcomputer機器的簡單程序設計；
（7）虛擬機的層次結構及其意義和作用；
（8）高級語言、應用語言和自然語言的形式化問題。
2.基本要求
（1）初步掌握簡單數據庫系統的建模方法，實現客觀世界到信息世界的抽象，了解建模在控制和降低軟件復雜性方面的重要作用；將模型與實現綁定在一起，構建簡單的關系數據庫系統，對系統復雜性隨實體和屬性數量的增加而呈非線性增加有一個初步的了解；
（2）理解學科內容劃分的背景和意義；
（3）通過實例加深對自然語言和形式語言的理解；
（4）理解提出通用計算機“圖靈機”的背景與意義；
（5）理解計算機技術發展中馮·諾依曼計算機產生的背景與意義；加深對存儲程序式計算機結構的理解，理解“程序與數據同樣看待”這一思想的背景和重要意義；
（6）能夠對計算機指令系統的兩種設計思路進行簡單評價；能夠使用Vcomputer進行簡單的機器指令和匯編指令的程序設計；
（7）理解控制復雜系統和降低其復雜程度的分層抽象策略，將該策略與虛擬機綁定在一起，理解虛擬機的重要作用；
（8）了解高級語言中有關抽象、理論和設計形態的主要內容，進一步理解這種劃分的重要作用；應用語言及第四代語言的概念，教學目標-將第四代語言與軟件生產效率綁定在一起，理解第四代語言的重要作用；了解計算機技術發展中語法形式化的背景和意義。
3.重點、難點
重點：E-R圖的簡單繪制，計算學科的三個學科形態（抽象，理論和設計）的區別，基于Vcomputer機器的程序設計；
難點：計算學科的三個學科形態（抽象，理論和設計）的區別，基于Vcomputer機器的程序設計。
四、計算學科中的核心概念
1.主要內容
（1）算法的基本知識；
（2）算法的四種表示方法；
（3）算法的分析；
（4）常見的兩類算法：搜索與排序；
（5）數據結構及基于Vcomputer機器的數據結構；
（6）程序、軟件和硬件的定義；
（7）數據的存儲及表示；
（8）CC1991報告提取的12個核心概念。
2.基本要求
（1）了解算法的歷史和簡單的算法實例；了解算法的非形式化定義和算法的重要特性；了解算法的形式化定義；
（2）使用自然語言、流程圖和偽代碼描述算法，了解計算機程序設計語言對算法的描述方法；
（3）初步掌握大O記號估算簡單算法時間復雜度的方法；
（4）能夠應用折半搜索算法和歸并排序算法求解實際問題；通過排序網絡加深對并行計算的理解；了解計算機技術發展中Google與云計算產生的背景和影響；了解DARPA網絡挑戰賽的背景和影響；
（5）將數據結構的表示與Vcomputer機器綁定在一起，理解數據結構與機器的關系；了解線性表、棧和隊列的定義、表示方法和基本操作；了解數組的定義、表示方法和基本操作，將數組存儲和機器綁定在一起，進一步理解程序與機器的關系；了解樹、二叉樹和圖的定義、表示方法和基本操作；了解線性表的存儲結構及其表示方式；了解廣義表的鏈式存儲結構及其表示方式；了解二叉樹的存儲結構及其表示方式；了解圖的存儲結構及其表示方式；
（6）了解程序、軟件和硬件的基本概念；
（7）加深學生對于進制轉換的理解；了解“模”系統中，負數的表示方法及其運算；了解字符和字符串的表示方法；了解漢字在計算機內部的表示方法；了解計算機內表示圖像的兩種方法（位圖和矢量圖）；了解正弦音波的產生過程；
（8）記憶12個核心概念。
3.重點、難點
重點：算法的歷史（含歐幾里得算法教學實驗），求解1+2+3+…+100的算法，求解調和級數的算法（含教學實驗），求解斐波那契數列的算法，漢諾塔算法的時間復雜度分析，常見的兩類算法：搜索與排序，基于排序網絡對一組數進行排序，Vcomputer機器的數據結構，補碼與模運算；
難點：求解斐波那契數列的算法，漢諾塔算法的時間復雜度分析，Vcomputer機器的數據結構，補碼與模運算。
五、計算學科中的數學方法
1.主要內容
（1）數學的基本特征及數學方法的作用；
（2）計算學科中常用的數學概念和術語（集合，函數和關系，代數系統（含群、環、格、布爾代數，布爾代數與數字邏輯電路）；定義、定理和證明，必要條件和充分條件）；
（3）證明方法（直接證明和間接證明、反證法、歸納法、構造性證明）；
（4）遞歸和迭代；
（5）隨機數和蒙特卡羅方法；
（6）公理化方法簡介；
（7）形式化方法簡介。
2.基本要求
（1）通過求解2的平方根的海倫算法，了解數學與計算機科學學科的區別；了解數學的基本特征及數學方法的作用；
（2）理解集合的概念、描述方法和基本運算；在認知等價類這個概念本質的基礎上，理解網絡的層次結構、馮·諾依曼計算機、虛擬機、分割、政企分開、傳染病人隔離等類似的各種控制和降低非良好結構系統（問題）復雜程度的劃分策略；解代數系統中的環、格和布爾代數之間的關系；了解定義、定理和證明的不同之處；能夠在集合論的基礎上采用必要條件和充分條件分析實際問題，了解分層抽象對控制軟件系統復雜性的必要性；
（3）了解直接證明法和間接證明法；通過海倫算法求解2的平方根，用數學歸納法證明2的平方根是無理數，進一步理解數學與計算機科學的不同；
（4）將遞歸與數學歸納法綁定在一起，了解它們的區別和聯系；通過實例進一步加深對遞歸概念的理解；
（5）了解產生偽隨機數的方法；通過蒙特卡羅方法求解無序數列的現實問題；
（6）了解公理化方法的重要作用；了解公理化方法的基本要素；掌握構建公理化體系的基本方法；
（7）了解形式系統的局限性。
3.重點、難點
重點：等價類，必要條件和充分條件，蒙特卡洛方法的應用
難點：等價類，蒙特卡洛方法的應用
六、計算學科中的系統科學方法
1.主要內容
（1）系統科學與系統科學方法；
（2）人固有能力的局限性以及使用工具后產生力量的案例；
（3）復雜性的可操作性定義（含實例）及軟件系統的復雜性；
（4）軟件開發的系統化方法需要遵循的基本原則；
（5）使用系統方法的思考。
2.基本要求
（1）將布爾代數與數字邏輯電路綁定在一起，理解系統同構的性質和作用；通過5個小實例理解計算學科處理復雜系統采用的分層抽象策略，能夠將該策略與等價類綁定在一起，知曉采用該策略控制和降低復雜系統的數學思想；了解系統科學尊遵循的一般原則及常見的幾種系統科學方法；
（2）認知人固有能力的局限性，知曉采用系統科學方法控制和降低復雜性的重要作用；
（3）通過實例從程序員的角度認知復雜性；認知軟件系統開發的難點在于對其概念結構（概念模型）的規格、設計和測試；
（4）認知軟件開發這類特殊工程設計的復雜性；
（5）要求學生能將系統方法和軟件研制的復雜性，以及抽象層次和人類分工的概念綁定在一起，能用系統方法中的結構和層次兩個概念理解引入系統方法的目的之所在（降低和控制軟件系統的復雜性）。
3.重點、難點
重點：系統同構，理解系統基本概念的5個實例，人固有能力的局限性以及使用工具后產生力量的案例，復雜性的可操作性定義，《人月神話》對軟件復雜性的分析，使用系統方法的目的。
難點：系統同構，復雜性的可操作性定義，使用系統方法的目的。
七、社會和職業的問題
1.主要內容
（1）道德分析的方法（Kitchener的5條道德原則）；
（2）職業和道德責任（基于協議的職業化本質；有效的檢舉行為）；
（3）基于計算機系統的風險和責任；
（4）團隊工作；
（5）知識產權；
（6）隱私和公民自由（基于Web的隱私保護技術）。
2.基本要求
（1）了解道德選擇的一般步驟（算法），培養學生道德分析的職業習慣；
（2）能夠從協議（模型）的角度理解職業化的本質，培養學生未來工作之后的職業精神；要求學生從過程的角度，區分什么是有效檢舉，什么不是，要求學生了解檢舉泛濫的危害，掌握有效檢舉的步驟（算法），培養學生進行有效檢舉的職業觀念；
（3）要求學生在系統的設計過程中能夠充分考慮經濟、環境、法律、安全、健康、倫理等影響因素，培養學生未來從事專業工作的倫理規范；通過“Therac-25”事件案例分析計算機系統的風險，在設計安全至上的應用系統的時候，要充分考慮系統出現故障時，危害如何降至最低；
（4）了解團隊最重要的特征（運作機制），了解提高團隊業績的兩種常用方法（團隊制和單一領導制），了解團隊合作的困難。補充“小團隊的敏捷開發案例”，了解這種實際使用并受到支持的特定軟件開發方法，將經常交付、反思改進、滲透式交流、個人安全、焦點、與專家用戶建立方便的聯系、配有自動測試的技術環境等7個屬性與小團隊綁定在一起，了解卓越小團隊成功的特征，為未來從事專業工作進行團隊合作打下基礎；
（5）了解知識產權的定義和重要作用；
（6）了解信息安全與隱私保護的相關技術。
3.重點、難點
重點：Kitchener的5條道德原則，基于“協議”的職業化本質，軟件工程師的倫理規范，有效的檢舉行為，“Therac-25”事件，團隊合作（含溝通）。
難點：軟件工程師的倫理規范，有效的檢舉行為，團隊合作（含溝通）。
八、探討與展望
1.主要內容
（1）計算本質的認識歷史；
（2）程序設計在計算學科中的地位；
（3）難度、復雜度與能力；
（4）SOLO分類法與淺層學習和深度學習；
（5）注意力。
2.基本要求
（1）了解計算本質的認識歷史；
（2）了解程序設計在計算學科中的地位；
（3）掌握難度、復雜度與能力的關系；
（4）掌握SOLO分類法與淺層學習和深度學習的關系；
（5）了解注意力對學習和工作的重要作用。
3.重點、難點
重點： Bloom分類法，SOLO分類法，難度、復雜度與能力。
難點：難度、復雜度與能力。
預備知識
無
證書要求
設置“合格”（達到60分）、“優秀”（達到80分）兩檔課程標準。
參考資料
推薦教材：
1.董榮勝.計算機科學導論—思想與方法（第3版）.高等教育出版社,2015.07
2.董榮勝.計算思維的結構. 人民郵電出版社, 2017.08
參考教材：
1.董榮勝，古天龍.計算機科學與技術方法論.人民郵電出版社,2002
2.陳國良.大學計算機—計算思維視角（第2版）.高等教育出版社,2014
3.李廉.大學計算機教程—從計算到計算思維.高等教育出版社,2016
4.J.Glenn Brookshear著，劉藝等譯.計算機科學概論（第11版）,人民郵電出版社,2011
5.趙致琢.計算科學導論（第三版）.科學出版社,2004
國家精品課程“計算機科學導論”網站：https://jpkc.guet.edu.cn/jsjkxdl/index.asp
常見問題
Q1：“計算機科學導論”課程是否比一門常見的計算機專業課程更為重要？
A1: 美國國家科學基金會的“重建多樣性（Rebuilding the Mosaic）”報告認為，在處理幾乎所有領域出現的新問題時，均需要使用和管理大規模的數據集。解決這些新問題，需要創造性地設計以數據為中心的問題解決方案，以及應用計算和計算機工具進行跨學科的研究。
為了應對以上需求，“計算機科學導論”課程的作用已逐步超出一門常見的計算機專業課程。這門課程越來越大的作用包括：
（1）它不僅需要為未來的計算機科學家和從業人員打下基礎，而且還要激發學生對計算機科學的興趣、動員和吸引新的學生加入計算機科學；
（2）此外，它還要為其他專業的學生提供計算思維的方法和計算機科學方面的技能；
（3）它甚至還要為未來講授計算機科學的K-12教員提供培訓。
摘自：Soh L K, Shell D F, Ingraham E, et al. Learning through computational creativity[J]. Communications of the ACM, 2015, 58(8):33-35
Q2：Bloom分類法和SOLO分類法降低了課程評估的復雜程度，為課程的開發提供了基本的依據。老師能用兩個本課程的案例來佐證一下嗎？
A2：Bloom分類法將人類思維的復雜程度劃分為6個水平層次（記憶、理解、應用、分析、評估、創造），并認為這6個層次不是累積層次，即前一個層次不是后一個層次的基礎，這一結論動搖了只有扎實的基礎才能進行較高層次思維的論斷，使人們可以在較短的時間內盡快進入到分析，評估和創造等較高層次的思維階段。至于，記不住的知識可以查，不會的知識可以有針對性的在思維的過程中補。這一論斷有重要的應用價值。本課程有大量的案例可以佐證，下面給出第2章的兩個案例：
（1）案例1：漢諾塔問題。在沒有介紹算法基礎知識的情況下，在第2章的學習中，就讓學生將數學歸納法與求解漢諾塔的遞歸算法綁定在一起，要求學生掌握簡單遞歸算法的構建。
（2）案例2：RSA公開密鑰密碼系統。在學生沒有任何密碼學基礎知識的情況下，在第2章的學習中，要求學生初步掌握RSA公開密鑰密碼系統的構建，這也是Bloom分類法和SOLO分類法的一個成功應用案例。
Q3：如何控制和降低“復雜問題”是本課程關注的重要內容，“復雜”這個關鍵詞貫穿于本課程的始終，這個關鍵詞正是國際工程教育專業認證的核心。請問，“計算機科學導論”課程各章節中的案例是如何支撐專業認證對本科生的12條畢業要求的？
A3：
【第1章】計算學科的認知問題是一個引發激烈爭論的復雜問題。本章借助案例“計算學科的認知模型——計算學科二維定義矩陣”對計算學科的認知問題進行分析，降低了問題分析的復雜程度，符合“畢業要求2：問題分析”中要求在構建模型降低問題復雜程度的基礎上，對復雜問題進行分析的要求。
注：本課程有大量符合“畢業要求”的具體案例，正是這些案例證明了本課程對復雜工程問題的處理是有方法的，再加上嚴格的訓練就可以確保合格畢業生的質量。
【第2章】計算問題的復雜性體現在時間和空間兩個方面。本章借助案例“漢諾塔問題”、“證比求易算法”、“阿姆達定律”認知計算復雜性。在此基礎上，構建“輕量級”的RSA公開密鑰密碼系統，符合“畢業要求3：設計/開發解決方案”中設計滿足特定需求系統的要求。
【第3章】如何將客觀世界中的一類問題抽象到信息世界是復雜計算系統中的一個工程問題。本章借助案例“學生選課”，要求學生掌握簡單的數據庫應用系統的建模方法，理解實例屬性的約束條件，實現客觀世界到信息世界的抽象，了解系統復雜性隨實體和屬性數量的增加而呈非線性增加
的結果。借助案例“圖靈機”、“馮諾依曼計算機”，加深對存儲程序式計算機結構的理解，了解“程序與數據同樣看待”這一思想的背景和重要意義。借助案例“虛擬機”和“Vcomputer機器”理解采用分層抽象降低和控制復雜系統的重要作用。符合“畢業要求1：工程知識”中將專業知識用于解決復雜工程問題的要求。
【第4章】數據結構與算法是復雜軟件系統的基礎。本章將數據結構與Vcomputer機器綁定在一起，降低了計算機軟件系統理解的復雜性，符合“畢業要求1：工程知識”中將專業知識用于解決復雜工程問題的要求。
【第5章】計算機科學基礎概念建立在數學集合概念的基礎上，如何將集合中的元素變為有序，是降低軟件系統復雜性的關鍵。本章借助“等價類”這個數學概念，要求學生將等價類與抽象層次這個計算思維中的重要概念綁定在一起，理解分層抽象、網絡的層次結構、馮·諾依曼計算機、虛擬機、分割、政企分開、傳染病人隔離等類似的各種控制和降低非良好結構系統（問題）復雜程度的劃分策略及在計算學科工程實踐中的巨大作用，符合“畢業要求1：工程知識”將數學知識用于解決復雜工程問題的要求。
本章還要求將將公理化方法與形式模型（形式化的公理體系）的構建綁定在一起，了解形式系統的局限性，掌握構建形式系統的基本方法，符合“畢業要求4：研究”中采用科學方法解決復雜工程問題的要求。
【第6章】軟件的復雜度是軟件生產的主要困難。本章將控制計算機軟硬件系統復雜度的分層抽象思想與數學中的等價類綁定在一起，對軟件復雜性進行分析，符合“畢業要求2：問題分析”應用數學、自然科學和工程科學的基本原理，識別、表達、并通過文獻研究分析復雜工程問題，以獲得有效結論的要求。
【第7章】本章采用計算機科學的思想與方法對學科的職業規范進行分析。比如，采用算法的思想培養學生道德分析的職業習慣；從協議（模型）的角度理解職業化的本質，培養學生的職業精神；從過程的角度，區分什么是有效檢舉，什么不是，要求學生了解檢舉泛濫的危害，掌握有效檢舉的步驟（算法），培養學生進行有效檢舉的職業觀念。符合“畢業要求8：職業規范”中對遵守工程職業道德和規范，履行責任的要求。
本章借助案例“Therac-25”事件分析計算機系統的風險，在設計安全至上的應用系統的時候，要充分考慮系統出現故障時，危害如何降至最低。符合“畢業要求6：工程與社會”中專業工程實踐和復雜工程問題解決方法對社會、健康、安全的影響，并理解應承擔的責任。
本章要求學生了解團隊最重要的特征（運作機制），了解提高團隊業績的兩種常用方法（團隊制和單一領導制），了解團隊合作的困難，學習“小團隊的敏捷開發案例”，了解這種實際使用并受到支持的特定軟件開發方法，為未來從事專業工作進行團隊合作打下基礎。符合“畢業要求9：個人與團隊”中能夠在多學科背景下的團隊中承擔個體、團隊成員以及負責人的角色的要求。
本章借助案例“小團隊的敏捷開發案例”，了解這種實際使用并受到支持的特定軟件開發方法，將經常交付、反思改進、滲透式交流（溝通）、個人安全、焦點、與專家用戶建立方便的聯系（溝通）、配有自動測試的技術環境等7個屬性與小團隊綁定在一起，了解卓越小團隊成功的特征，在項目的開發過程中認知溝通的重要性。符合“畢業要求10：溝通”的要求。
【第8章】通過實例認知注意力，了解養成良好的思維習慣的重要性，為終身學習奠定認知基礎；了解難度，復雜度與能力的不同，了解Bloom分類法的研究背景和意義，為終身學習奠定認知基礎；區分淺層學習和深度學習，為終身學習奠定認知基礎。符合“畢業要求12：終身學習”的要求，讓學生在未來的學習和工作中終身受益。