計算思維導論

1、計算思維導論計算思維導論 第第1 1講講 - - 象計算機科學家一樣思考象計算機科學家一樣思考20142014年年0909月月2323日日本課程的目的 （你有兩周時間可以決定是否繼續(xù)上這門課）試圖回答幾個問題：什么是思維?什么是計算思維?計算思維能帶給“我”什么?你別指望：通過聽這門課，在你的筆記本上（如果你有記筆記的習慣的話）會記下上述問題的答案。這個課只是希望引導你去想答案我不敢說我知道什么是計算思維?！吧险n”的幾個境界最低境界：“以己之昏昏，使人昭昭”中級境界：“把自己的知識成功地傳遞給學生”高級境界：傳道 - “道可道，非常道；名可名，非常名”關于考試考試的幾個境界：最低境界：證明你考

2、過了低級境界：證明你背過了中級境界：證明你學過了高級境界：證明你想過了我只想證明你想過了。根據(jù)教務管理部門要求：第一堂課上提醒同學兩周之內可以決定是否選本課程。以上三張ppt試圖幫組你做決定。下面言歸正傳。競爭優(yōu)勢的軟件基礎技能知識能力意識意識為什么要提出這個概念?However, despite the dizzying speed with which some of the technological innovations become obsolete and are replaced by new ones, the fundamentals of the science of c

3、omputation, and hence many of the basic concepts that are considered important in a computer science curriculum, change slowly, if at all.It would appear that anyone associated with computers ought to be aware of thesetopics, and not only those who have decided to spend three or four years gettinga

4、particular kind of academic diploma. Moreover, given that a revolution is indeed taking place before our very eyes, many of these topics, and the special ways of thinking that go with them, ought to be available to the enquiring person even if that person is not directly associated with a computer a

5、t all.本課程教學參考書:David Harel: Algorithmics - the Spirit of Computing, 3rd ed, Pearson Education, 2004 (有高教社影印版)試圖給出定義/CompThink/papers/TheLinkWing.pdf美國卡內基-梅隆大學教授Jeannette M. Wing(周以真)領導世界上可能是唯一的”計算思維研究中心”, 并大力推動這一概念被認可。以下內容摘自她的文章：Computational Thinking: What and Why? Link Magazine

6、, 2010思維: 做法 意識 “無”意識從玩牌的習慣性動作, 到計算機算法設計策略, 這條路并不遙遠.注意：1. 對于“問題”, 我們應該有廣義的理解2. 問題求解包括“定義問題”和“解決問題”兩個層面一個例子 “渡河問題”問題問題：人、狼、羊、菜用一條只能同時載兩位的小船渡河，“狼羊”、“羊菜”不能在無人在場時共處，當然只有人能駕船。圖模型圖模型：頂點表示“原岸的狀態(tài)”，兩點之間有邊當且僅當一次合理的渡河“操作”能夠實現(xiàn)該狀態(tài)的轉變。起始狀態(tài)是“人狼羊菜”，結束狀態(tài)是“空”?！霸试S狀態(tài)”只有10個。問題的解問題的解：找到一條從起始狀態(tài)到結束狀態(tài)的盡可能短的通路?？?成功成功)人羊狼菜人狼菜

7、人羊狼人羊菜狼菜狼菜人羊羊問題編碼上述關系可以用一個布爾矩陣表示： 0000010000000001110000000010100000000110000000001111000000000110000000010100000000111000000000100000它也可以表示成一個“數(shù)”：1000000000111000000010100000000110或者，也可以表示成符號串：16#28#2#6#3#768#384#320#112#32一切皆編碼反其意而用之： 計算無疆歷史上的一個黑色幽默我們用計算機干什么？模擬：自然現(xiàn)象社會現(xiàn)象人造現(xiàn)象通信：跨越空間跨越時間控制抽象物理世界虛擬世界走

8、向物理世界與虛擬世界的無縫連接走向物理世界與虛擬世界的無縫連接問題抽象問題抽象算法核心概念：數(shù)學模型、表示、實現(xiàn)、轉換算法是計算思維的核心概念:方法層: 算法表示層: 編程實現(xiàn)層: 機器這差不多也就是計算機科學的主要內容了問題抽象的分層映射應用領域的對象與關系數(shù)學對象與關系描述數(shù)據(jù)結構與狀態(tài)轉換操作過程與效果分析求解系統(tǒng)抽象系統(tǒng)抽象平臺核心概念：系統(tǒng)模型、功能邏輯、接口、實現(xiàn)系統(tǒng)抽象的分層映射系統(tǒng)目標與子目標分解功能模塊與接口狀態(tài)轉換與功能映射配置與效果設計實現(xiàn)數(shù)據(jù)抽象數(shù)據(jù)抽象解釋核心概念：信息形態(tài)、信息組織、存儲、檢索與利用數(shù)據(jù)抽象的分層映射物理世界的對象描述抽象數(shù)據(jù)類型數(shù)據(jù)類型編碼與標準化

9、編碼解釋再舉一個例子 企業(yè)的工資表處理數(shù)據(jù)抽象：編碼 數(shù)據(jù)記錄 數(shù)據(jù)庫問題抽象：處理單個員工的相關記錄處理任意有限多個員工的不同記錄（同樣的處理方法）系統(tǒng)抽象：應用界面：某種形式的“窗口”邏輯電路支撐 系統(tǒng)軟件支撐 數(shù)據(jù)庫支撐 應用程序支撐計算思維與計算環(huán)境計算環(huán)境的三大變革:海量數(shù)據(jù)資源 無盡的寶藏拓展的無線網(wǎng)絡 無限的舞臺智能化的設計與生產能力 無邊的法力Big Bang計算環(huán)境的革命為你 不管你是從事那個領域的工作 提供了無限的創(chuàng)新機遇, 就靠計算思維來發(fā)現(xiàn)了。本課程的ROADMAP9.23: 陳道蓄，象計算機科學家一樣思考 數(shù)字化與計算思維9.30: 錢柱中，抽象數(shù)據(jù)類型 從數(shù)學模型到

10、計算模型 10.7: 陳道蓄，算法方法 如何讓計算機高效正確地解決問題10.14: 陳道蓄，模擬 - 計算機如何改變科學、技術與工程 生命、社會10.21: 陶先平，模擬 - 計算機如何改變科學、技術與工程 - 地球，物質科學10.28: 陶先平，互聯(lián)與搜索 - 計算機網(wǎng)絡如何改變我們的工作與學習11.4: 錢柱中，網(wǎng)絡計算與服務 計算機網(wǎng)絡如何改變我們的社會11.11: 錢柱中，計算的代價和局限 什么是難問題？不可解問題?11.18: 陳道蓄，并行與隨機 突破限制11.25: 陶先平，人工智能 神話與現(xiàn)實1.2: 陶先平，數(shù)據(jù)挖掘 海量帶來質變12.9: 陶先平，計算技術的濫用 計算的風險 課后作業(yè)閱讀Computational Thinking: What and Why?