計(jì)算思維與不插電的計(jì)算機(jī)

1、計(jì)算思維/“不插電”的計(jì)算機(jī)科學(xué) CS4HS中小學(xué)師資培訓(xùn)項(xiàng)目 計(jì)算思維 1.問題的提出問題的提出 2.什么是計(jì)算思維什么是計(jì)算思維 3.3.計(jì)算思維可以做什么計(jì)算思維可以做什么 4.4.計(jì)算思維的兩個(gè)計(jì)算思維的兩個(gè)A A 5.5.衡量計(jì)算思維中抽象的衡量計(jì)算思維中抽象的 標(biāo)準(zhǔn)標(biāo)準(zhǔn) 6.6.計(jì)算思維的主要應(yīng)用計(jì)算思維的主要應(yīng)用 7.7.計(jì)算思維的影響計(jì)算思維的影響 8.8.大膽展望大膽展望 9.9.計(jì)算思維是什么，不是計(jì)算思維是什么，不是 什么什么 10.10.計(jì)算思維如何應(yīng)用于我計(jì)算思維如何應(yīng)用于我 國目前的教育國目前的教育 計(jì)算思維 Jeannette M. Wing (Jeannette

2、 M. Wing (周以真周以真) ) Computational Thinking (Jeannette M.Wing)曾任美國卡內(nèi)基-梅隆大學(xué) （CMU）計(jì)算機(jī)科學(xué)系主任，現(xiàn)任美國國家基金會(huì) （NSF）計(jì)算機(jī)和信息科學(xué)與工程部（CISE）主任。 于1983年在美國麻省理工學(xué)院（MIT）獲得計(jì)算機(jī) 科學(xué)博士學(xué)位。主要研究方向?yàn)椴⑿蟹植际较到y(tǒng)的 規(guī)范和認(rèn)證以及編程語言。目前主要研究提升軟件 系統(tǒng)安全性技術(shù)的設(shè)計(jì)和評(píng)價(jià)方法。周教授是ACM 和IEEE會(huì)士。 問題的提出 什么是計(jì)算什么是計(jì)算 數(shù)的加減乘除； 方程的求解、函數(shù)的微分積分等； 計(jì)算還包括定理的證明推導(dǎo)； 計(jì)算的本質(zhì)是什么？計(jì)算的本質(zhì)是

3、什么？ 1930年代，由于哥德爾（K.Godel，1906-1978）、丘奇 (A.Church，1903-1995)、圖靈(A.M.TUI-ing，1912-1954)等數(shù)學(xué) 家的工作，人們才弄清楚什么是計(jì)算的本質(zhì)，以及什么是可計(jì)算 的、什么是不可計(jì)算的等根本性問題。 計(jì)算就是依據(jù)一定的法則對(duì)有關(guān)符號(hào)串的變換過程 計(jì)算的本質(zhì)就是遞歸計(jì)算的本質(zhì)就是遞歸 問題的提出 計(jì)算無處不在計(jì)算無處不在計(jì)算概念的泛化計(jì)算概念的泛化 隨著計(jì)算機(jī)日益廣泛而深刻的運(yùn)用，計(jì)算這個(gè)原本專門的數(shù)學(xué)概隨著計(jì)算機(jī)日益廣泛而深刻的運(yùn)用，計(jì)算這個(gè)原本專門的數(shù)學(xué)概 念已經(jīng)泛化到了人類的整個(gè)知識(shí)領(lǐng)域，并上升為一種極為普適的念已經(jīng)泛

4、化到了人類的整個(gè)知識(shí)領(lǐng)域，并上升為一種極為普適的 科學(xué)概念和哲學(xué)概念，成為人們認(rèn)識(shí)事物、研究問題的一種新視科學(xué)概念和哲學(xué)概念，成為人們認(rèn)識(shí)事物、研究問題的一種新視 角、新觀念和新方法。角、新觀念和新方法。 計(jì)算無處不在計(jì)算無處不在計(jì)算的世界觀和方法論計(jì)算的世界觀和方法論 計(jì)算的觀念正在滲透到宇宙學(xué)、物理學(xué)、生物學(xué)乃至社會(huì)科學(xué)等計(jì)算的觀念正在滲透到宇宙學(xué)、物理學(xué)、生物學(xué)乃至社會(huì)科學(xué)等 諸多領(lǐng)域。諸多領(lǐng)域。 計(jì)算不但已經(jīng)成為人們認(rèn)識(shí)自然、生命、思維和社會(huì)的一種普遍計(jì)算不但已經(jīng)成為人們認(rèn)識(shí)自然、生命、思維和社會(huì)的一種普遍 方法，而且正在試圖成為一種全新的世界觀。方法，而且正在試圖成為一種全新的世界觀

5、。 計(jì)算哲學(xué)、計(jì)算語言學(xué)、生命計(jì)算、計(jì)算化學(xué)、計(jì)算哲學(xué)、計(jì)算語言學(xué)、生命計(jì)算、計(jì)算化學(xué)、 計(jì)算社會(huì)學(xué)、計(jì)算人類學(xué)。計(jì)算社會(huì)學(xué)、計(jì)算人類學(xué)。 問題的提出 計(jì)算無處不在計(jì)算無處不在計(jì)算新時(shí)代計(jì)算新時(shí)代 最初發(fā)明計(jì)算機(jī)的動(dòng)機(jī)，在于計(jì)算機(jī)運(yùn)算能力的應(yīng)用，如科學(xué)、最初發(fā)明計(jì)算機(jī)的動(dòng)機(jī)，在于計(jì)算機(jī)運(yùn)算能力的應(yīng)用，如科學(xué)、 工程等運(yùn)算；工程等運(yùn)算； 后來數(shù)據(jù)處理的發(fā)展也帶來商業(yè)的應(yīng)用；后來數(shù)據(jù)處理的發(fā)展也帶來商業(yè)的應(yīng)用； 近年多媒體及網(wǎng)絡(luò)的普及，應(yīng)用范圍就延伸至教育、休閑以及國近年多媒體及網(wǎng)絡(luò)的普及，應(yīng)用范圍就延伸至教育、休閑以及國 計(jì)民生各個(gè)方面。計(jì)民生各個(gè)方面。 問題的提出 計(jì)算方法和模型使我們敢于去處

6、理那些原本無法 由任何個(gè)人獨(dú)自完成的問題求解和系統(tǒng)設(shè)計(jì)。 什么是計(jì)算思維 計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念去求解問 題、設(shè)計(jì)系統(tǒng)和理解人類的行為。它包括了涵蓋 計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)。 計(jì)算思維可以做什么 每個(gè)人的基本技能每個(gè)人的基本技能 計(jì)算和計(jì)算機(jī)對(duì)計(jì)算思維如同印刷出版對(duì)3R（Reading, wRiting, and aRithmetic3R） 計(jì)算機(jī)科學(xué)的成果正在成為我們解決問題的方法 問題的難易程度 尋找最優(yōu)解 資源約束 環(huán)境 近似解 隨機(jī)化 容錯(cuò) 計(jì)算思維就是通過約簡、嵌入、轉(zhuǎn)化和仿真等方法， 把一個(gè)看來困難的問題重新闡釋成一個(gè)我們知道怎樣解決 的問題。 計(jì)算思維可以做

7、什么 是一種遞歸思維。 是并行處理。 是代碼和數(shù)據(jù)的相互轉(zhuǎn)化。 是類型檢查。 命名規(guī)則。 間接尋址和程序調(diào)用。 是評(píng)價(jià)方法準(zhǔn)確性、效率、美學(xué)、簡潔、優(yōu)雅。 計(jì)算思維可以做什么 抽象和分解抽象和分解 描述龐雜的任務(wù)或者設(shè)計(jì)巨大復(fù)雜的系統(tǒng) 隱藏系統(tǒng)內(nèi)部的實(shí)現(xiàn)細(xì)節(jié) 適應(yīng)將來的改變（預(yù)取、緩存） 計(jì)算思維可以做什么 是按照預(yù)防、保護(hù)及通過冗余、容錯(cuò)、糾錯(cuò)的方式從最壞是按照預(yù)防、保護(hù)及通過冗余、容錯(cuò)、糾錯(cuò)的方式從最壞 情形恢復(fù)的一種思維。情形恢復(fù)的一種思維。 避免死鎖 計(jì)算思維可以做什么 是是啟發(fā)式推理啟發(fā)式推理的方法的方法 規(guī)劃 學(xué)習(xí) 調(diào)度 搜索 策略 權(quán)衡 計(jì)算思維可以做什么 舉例 早晨上班前把當(dāng)天

8、需要的東西放進(jìn)背包-預(yù)置和緩 存 路上丟了錢包沿走過的路尋找-回推 什么時(shí)候停止租車自己買一輛-在線算法 超市付帳時(shí)應(yīng)當(dāng)去排哪個(gè)隊(duì)-多服務(wù)器系統(tǒng)的性能 模型 停電時(shí)電話仍然可用-失敗的無關(guān)性和設(shè)計(jì)的冗余 性 完全自動(dòng)的大眾圖靈測試如何區(qū)分計(jì)算機(jī)和人類- 人工智能和計(jì)算代理程序 計(jì)算思維的兩個(gè)A A AbstractionAbstraction（抽象）（抽象） 計(jì)算思維是抽象化的過程。（與數(shù)學(xué)類似） 計(jì)算思維同時(shí)在多個(gè)抽象層次上同時(shí)進(jìn)行。 計(jì)算思維定義層次之間的關(guān)系。 AutomationAutomation（自動(dòng)化）（自動(dòng)化） 計(jì)算思維的思考方式是：使抽象層次及其關(guān)系機(jī)械化。機(jī)械化的 可行性是

9、由精確和嚴(yán)格的符號(hào)和模型所保證。 在下面是一些“機(jī)器”（人或計(jì)算機(jī)，虛擬或?qū)嶋H的）。 衡量計(jì)算思維中抽象的標(biāo)準(zhǔn) 有效性有效性 速度 空間 能力 正確性正確性 做正確的事 做事（停機(jī)問題） 其他其他 簡單和優(yōu)美 有用性 可修改性 可維護(hù)性 花費(fèi) 計(jì)算思維的主要應(yīng)用 關(guān)注于抽象和概念化的事物關(guān)注于抽象和概念化的事物 復(fù)雜性：可計(jì)算性問題 算法：性能、近似值、隨機(jī)化、優(yōu)化 數(shù)據(jù)：數(shù)據(jù)結(jié)構(gòu) 抽象機(jī)器：自動(dòng)機(jī)、狀態(tài)機(jī) 結(jié)構(gòu)設(shè)計(jì)：分解、組合、模塊化、分層抽象化 語言學(xué)：句法、語義、語法 推理：正確性、邏輯、類型、證明、排錯(cuò) 控制：遞歸、循環(huán)、條件、判斷、并行、分布 通訊：同步、異步、廣播、p2p、客戶機(jī)、

10、服務(wù)器、共享內(nèi)存、消息傳遞 外界約束：容錯(cuò)、可靠性、動(dòng)力 不關(guān)注于不關(guān)注于 計(jì)算機(jī)一般應(yīng)用：word、excel、上網(wǎng) 如何編程 計(jì)算思維的影響： - -單學(xué)科中應(yīng)用多種方法 生物學(xué)：生物學(xué)： 鳥槍算法 vs 基因測序 語言中的字符串 vs DNA序列 布爾網(wǎng)絡(luò) vs 生物網(wǎng)絡(luò) 進(jìn)程演算 vs 分子間相互作用 電路 vs 自動(dòng)調(diào)節(jié)的細(xì)胞 狀態(tài)圖 vs 發(fā)育遺傳學(xué) 計(jì)算思維的影響：機(jī)器學(xué)習(xí) - -一種方法應(yīng)用于多學(xué)科 天文學(xué)：天文學(xué)： 探索星系：機(jī)器學(xué)習(xí) 超大量多維數(shù)據(jù)分析：KD-tree 醫(yī)學(xué)：醫(yī)學(xué)： 藥物研制 疾病診斷 疾病治療 計(jì)算思維的影響：機(jī)器學(xué)習(xí) - -一種方法應(yīng)用于多學(xué)科 氣象學(xué)：

11、氣象學(xué)： 氣候現(xiàn)象的形成研究 計(jì)算思維的影響：機(jī)器學(xué)習(xí) - -一種方法應(yīng)用于多學(xué)科 神經(jīng)科學(xué)：神經(jīng)科學(xué)： 運(yùn)用機(jī)器學(xué)習(xí)研究語言 計(jì)算思維的影響：機(jī)器學(xué)習(xí) - -一種方法應(yīng)用于多學(xué)科 信用卡 超市 金融行業(yè) 娛樂領(lǐng)域 體育 計(jì)算思維的影響：機(jī)器學(xué)習(xí) - -一種方法應(yīng)用于多學(xué)科 化學(xué)：化學(xué)： 原子計(jì)算 化學(xué)反應(yīng)中的算法 計(jì)算思維的影響： - -對(duì)于其他領(lǐng)域 數(shù)學(xué)：數(shù)學(xué)： E8的破解 18人，4年，77小時(shí)，600億 四色定理證明 計(jì)算思維的影響： - -對(duì)于其他領(lǐng)域 工程學(xué)：工程學(xué)： 電氣學(xué) 機(jī)械 航空 宇航 計(jì)算思維的影響： - -對(duì)于其他領(lǐng)域 社會(huì)：社會(huì)： 經(jīng)濟(jì) 法律 人文 地球?qū)W 計(jì)算思維的

12、影響： - -對(duì)于其他領(lǐng)域 大膽展望：計(jì)算思維不僅對(duì)于其他領(lǐng)域的科學(xué)家，而且對(duì)大膽展望：計(jì)算思維不僅對(duì)于其他領(lǐng)域的科學(xué)家，而且對(duì) 每個(gè)人都適用每個(gè)人都適用。 普適計(jì)算是昨天的夢想，今天的現(xiàn)實(shí)。 計(jì)算思維是今天的夢想，明天的現(xiàn)實(shí)。 大膽展望 概念化，不是程序化概念化，不是程序化 計(jì)算機(jī)科學(xué)不是計(jì)算機(jī)編程 追求抽象的多個(gè)層次上思維 計(jì)算思維是什么，不是什么 根本的，不是刻板的技能根本的，不是刻板的技能 根本技能意味著每個(gè)人必須掌握 刻板技能意味著機(jī)械的重復(fù) -具有諷刺 意味的是，當(dāng)計(jì)算機(jī)像人類一樣思考之后，思維可就真的 變成機(jī)械的了。 計(jì)算思維是什么，不是什么 是人的，不是計(jì)算機(jī)的思維方式是人的，

13、不是計(jì)算機(jī)的思維方式 聰穎 想象力 激情 計(jì)算機(jī)只是實(shí)現(xiàn)人類智慧的工具 計(jì)算思維是什么，不是什么 數(shù)學(xué)和工程思維的互補(bǔ)與融合數(shù)學(xué)和工程思維的互補(bǔ)與融合 本質(zhì)上源自數(shù)學(xué)思維（形式化基礎(chǔ)） 本質(zhì)上源自工程思維（面向?qū)嶋H） 以虛擬世界超越物理世界 計(jì)算思維是什么，不是什么 是思想，不是人造物是思想，不是人造物 非物理實(shí)體 接近和求解問題 日常生活 交流和互動(dòng) 無處不在 計(jì)算思維是什么，不是什么 計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué)不是不是計(jì)算機(jī)編程計(jì)算機(jī)編程 智力上的挑戰(zhàn)和引人入勝的科學(xué)問題依舊亟待理解和解決 計(jì)算機(jī)科學(xué)和其他任何科學(xué)沒有沖突只有互相促進(jìn) 計(jì)算思維是什么，不是什么 計(jì)算思維如何應(yīng)用于我國目前的教育

14、在哪些階段引入計(jì)算思維在哪些階段引入計(jì)算思維 小學(xué) 初中 高中 大學(xué) 大學(xué)之后 在哪些課程中引入在哪些課程中引入 計(jì)算無所不在、像計(jì)算機(jī)科學(xué)家那樣思考 計(jì)算語言學(xué)、計(jì)算生物學(xué)、計(jì)算經(jīng)濟(jì)學(xué)、計(jì)算天文學(xué)。 用什么樣的方法引入用什么樣的方法引入 不插電的計(jì)算機(jī)科學(xué) 教學(xué)與生活的關(guān)系教學(xué)與生活的關(guān)系 對(duì)教師的培養(yǎng)對(duì)教師的培養(yǎng) 參考資料 REU Sites PI Meeting,Arlington, VA,March 13, 2009, Jeannette M. Wing 不插電的計(jì)算機(jī)科學(xué)的背景 不插電的計(jì)算機(jī)科學(xué)的內(nèi)容 不插電的計(jì)算機(jī)科學(xué)的內(nèi)涵 實(shí)現(xiàn)“不插電”學(xué)習(xí)計(jì)算機(jī)科學(xué)的教學(xué)方法 二、不插電的計(jì)

15、算機(jī)科學(xué)（1 1）-內(nèi)容提要 計(jì)算機(jī)無處不在，無處不用； 中小學(xué)生有必要探尋、領(lǐng)悟計(jì)算機(jī)的原理及其解決問題的 精妙思想； 通過游戲教學(xué)將抽象、復(fù)雜的計(jì)算機(jī)原理形象化、簡單化， 使學(xué)生們了解計(jì)算機(jī)工作的基本原理； 培養(yǎng)學(xué)生們的“計(jì)算思維”，開發(fā)他們解決問題的方法， 自我獲取知識(shí)的能力。 CS Unplugged的背景 不插電的計(jì)算機(jī)科學(xué)是一系列免費(fèi)的學(xué)習(xí)活動(dòng)， Unplugged通過使用卡片、串珠、蠟燭等，穿插有大量的 活動(dòng)，參與一些游戲及謎題，達(dá)到學(xué)習(xí)計(jì)算機(jī)科學(xué)的目的。 這些活動(dòng)向?qū)W生介紹了計(jì)算機(jī)科學(xué)中的很多概念，像二進(jìn) 制數(shù)， 排序算法 以及 數(shù)據(jù)壓縮等，不使用計(jì)算機(jī)，學(xué) 生可以學(xué)到計(jì)算機(jī)科

16、學(xué)中的很多思想。 不插電的計(jì)算機(jī)科學(xué)適合于各個(gè)年齡階段的人，從孩子到 老人，從城市到鄉(xiāng)村。在世界各地，人們使用不插電的計(jì) 算機(jī)科學(xué)已經(jīng)超過15年了，無論是在教室、科學(xué)中心、家 里，甚至是在公園里，Unplungged 可以作為假日活動(dòng)來 進(jìn)行。 CS Unplugged的背景 為了滿足人們的需要，計(jì)算機(jī)會(huì)在內(nèi)部處理兩類事情： 計(jì)算機(jī)會(huì)存儲(chǔ)數(shù)據(jù)計(jì)算機(jī)會(huì)存儲(chǔ)數(shù)據(jù) 數(shù)據(jù)是計(jì)算機(jī)工作時(shí)處理的原材料對(duì)象，計(jì)算機(jī)會(huì)將內(nèi) 部數(shù)據(jù)轉(zhuǎn)換為人們可以理解的信息（如：數(shù)字、詞語和圖 像）。 計(jì)算機(jī)通過一系列指令對(duì)數(shù)據(jù)進(jìn)行處理計(jì)算機(jī)通過一系列指令對(duì)數(shù)據(jù)進(jìn)行處理 通過這些指令（即算法）使得計(jì)算機(jī)能夠解決許多問題 （如：排

17、序、查詢、發(fā)送及傳輸信息）。 不插電的計(jì)算機(jī)科學(xué)的內(nèi)容 二進(jìn)制數(shù)和“比特” 用二進(jìn)制數(shù)來存取數(shù)據(jù) 從比特到字母 從比特到圖像 壓縮信息 檢測錯(cuò)誤 不插電的計(jì)算機(jī)科學(xué)的內(nèi)容 介紹： 保存數(shù)據(jù)是計(jì)算機(jī)首先要完成的事情 二進(jìn)制是所有計(jì)算機(jī)的數(shù)據(jù)儲(chǔ)存形式 這來源于計(jì)算機(jī)內(nèi)存中晶體管的“開”“關(guān)”狀態(tài) 1.二進(jìn)制數(shù)和“比特” 游戲：二進(jìn)制卡片游戲：二進(jìn)制卡片 游戲目的游戲目的 掌握比特(bit)非0即1 ，二進(jìn)制的性質(zhì)以及二進(jìn)制與數(shù)字之間的轉(zhuǎn) 換規(guī)律。 游戲內(nèi)容游戲內(nèi)容 通過學(xué)生手持卡片的翻轉(zhuǎn)反面和正面，代替比特的 “0”、“1” 變化；通過人數(shù)的變化，說明二進(jìn)制的性質(zhì)。 游戲結(jié)果游戲結(jié)果 比特是計(jì)算機(jī)

18、技術(shù)中一種常用的度量單位，非0即1 ，且容易實(shí)現(xiàn)； 從小比特可到大數(shù)字。 1.二進(jìn)制數(shù)和“比特” 二進(jìn)制數(shù)字游戲 1.二進(jìn)制數(shù)和“比特” 互動(dòng)： 準(zhǔn)備卡片 你留意到卡片的規(guī)律沒有? 如果向左側(cè)繼續(xù)增加一張卡片,這張卡片需要畫幾個(gè)點(diǎn)? 1.二進(jìn)制數(shù)和“比特” 數(shù)字6如何表示? 1.二進(jìn)制數(shù)和“比特” 數(shù)字0-9如何表示? 任何數(shù)字能用不止一種方法來表示嗎? 5張卡片能表示的最大數(shù)字是多少? 能表示的最小數(shù)字是多少? 1.二進(jìn)制數(shù)和“比特” 二進(jìn)制01001表示多少? 這些卡片一共有多少個(gè)比特? 1.二進(jìn)制數(shù)和“比特” 用任意符號(hào)代表二進(jìn)制中的0和1 1.二進(jìn)制數(shù)和“比特” 擴(kuò)展： 進(jìn)制的概念 理

19、解十進(jìn)制和二進(jìn)制 1.二進(jìn)制數(shù)和“比特” 擴(kuò)展： 生日蛋糕 Born August 2, 1971 1.二進(jìn)制數(shù)和“比特” 介紹： 雖然比特很小，但計(jì)算機(jī)中的“大”數(shù)字也是由比特組成 只要是有兩種狀態(tài)的都可以表示比特 用手也可以表示二進(jìn)制數(shù) 2.用二進(jìn)制數(shù)來存取數(shù)據(jù) 游戲：二進(jìn)制數(shù)的性質(zhì)游戲：二進(jìn)制數(shù)的性質(zhì) 二進(jìn)制數(shù)的相加？二進(jìn)制數(shù)的相加？ 二進(jìn)制數(shù)的成倍擴(kuò)大？二進(jìn)制數(shù)的成倍擴(kuò)大？ 固定位數(shù)的二進(jìn)制表示的最大數(shù)？固定位數(shù)的二進(jìn)制表示的最大數(shù)？ 如何用二進(jìn)制數(shù)表示一個(gè)十進(jìn)制數(shù)（轉(zhuǎn)換）？如何用二進(jìn)制數(shù)表示一個(gè)十進(jìn)制數(shù)（轉(zhuǎn)換）？ 2.用二進(jìn)制數(shù)來存取數(shù)據(jù) 擴(kuò)展：擴(kuò)展： 什么是千字節(jié)（什么是千字節(jié)（K

20、ilobyteKilobyte） 為什么為什么1 1千字節(jié)千字節(jié)=1024=1024字節(jié)字節(jié) 介紹兆字節(jié)（介紹兆字節(jié)（MegabyteMegabyte）、吉字節(jié)（）、吉字節(jié)（GigabyteGigabyte）、太字節(jié)）、太字節(jié) （terabyteterabyte）、拍字節(jié)（）、拍字節(jié)（PetabytePetabyte） 介紹能表示兩種狀態(tài)的電子設(shè)備介紹能表示兩種狀態(tài)的電子設(shè)備 晶體管晶體管 電容器電容器 磁盤、磁帶磁盤、磁帶 光盤光盤 介紹介紹2424位彩色位彩色 介紹介紹10001000兆連接兆連接 介紹介紹32/6432/64位計(jì)算機(jī)位計(jì)算機(jī) 介紹介紹“128128位位SSLSSL加密加密

21、” 介紹介紹8 8進(jìn)制、進(jìn)制、1616進(jìn)制進(jìn)制 2.用二進(jìn)制數(shù)來存取數(shù)據(jù) 擴(kuò)展：讀心術(shù)擴(kuò)展：讀心術(shù) 2.用二進(jìn)制數(shù)來存取數(shù)據(jù) 1 2 3 4 5 6 介紹介紹 計(jì)算機(jī)中存儲(chǔ)的任何數(shù)據(jù)（文檔、電子郵件、網(wǎng)頁、圖片、音樂、計(jì)算機(jī)中存儲(chǔ)的任何數(shù)據(jù)（文檔、電子郵件、網(wǎng)頁、圖片、音樂、 視頻）都是二進(jìn)制視頻）都是二進(jìn)制 比特代表字母比特代表字母-編碼和解碼編碼和解碼 3.從比特到字母 游戲：儲(chǔ)藏室謎題游戲：儲(chǔ)藏室謎題 3.從比特到字母 游戲：傳音游戲游戲：傳音游戲 像像modemmodem一樣用聲音發(fā)送一樣用聲音發(fā)送emailemail 3.從比特到字母 介紹介紹 比特可以表示字母、圖像，如：ASCII

22、碼或Unicode碼來存儲(chǔ)字符； 比特表示像素存儲(chǔ)圖像。 像素（pixel） 4.從比特到圖像 最簡單的黑白圖像中,每個(gè)像素只有兩種值:黑或白,如下 面字母a的放大圖。 當(dāng)計(jì)算機(jī)存儲(chǔ)這樣的圖片時(shí),它只需記錄圖像中哪些是黑 點(diǎn)哪些是白點(diǎn),也就是比特的組合。 4.從比特到圖像 0 1 1 1 00 1 1 1 0 ？ 0 0 0 0 10 0 0 0 1 1 0 0 0 11 0 0 0 1 0 1 1 1 10 1 1 1 1 1 0 0 0 11 0 0 0 1 4.從比特到圖像 游程編碼(RLE)：記錄每個(gè)白色或黑色連續(xù)區(qū)域的長度。 4.從比特到圖像-圖像壓縮 1,3,1 4,1 1,4 0

23、,1,3,1 0,1,3,1 1,4 游戲：圖像解碼 4.從比特到圖像-圖像壓縮 游戲：圖像解碼 4.從比特到圖像-圖像壓縮 游戲：圖像編碼 4.從比特到圖像-圖像壓縮 4.從比特到圖像-圖像壓縮 4.從比特到圖像-圖像壓縮 擴(kuò)展：從比特到圖像的實(shí)例-噴墨打印機(jī) 介紹介紹 壓縮不但可以減小體積還可以加快運(yùn)行或傳輸速度 游程編碼可以壓縮黑白圖像 LZ算法 5.壓縮信息 游戲：文字的壓縮游戲：文字的壓縮 5.壓縮信息 游戲：文字的壓縮游戲：文字的壓縮 尋找重復(fù)的單詞尋找重復(fù)的單詞 計(jì)算壓縮前后字符數(shù)計(jì)算壓縮前后字符數(shù) 計(jì)算壓縮率計(jì)算壓縮率 5.壓縮信息 游戲：文字的壓縮游戲：文字的壓縮 尋找重復(fù)的

24、單詞尋找重復(fù)的單詞-The, Rain, tter, pa,The Rain, -The, Rain, tter, pa,The Rain, Pitter patterPitter patter 計(jì)算壓縮前后字符數(shù)計(jì)算壓縮前后字符數(shù)-96/39-96/39 計(jì)算壓縮率計(jì)算壓縮率-41%-41% 5.壓縮信息 游戲：文字的壓縮游戲：文字的壓縮 在實(shí)際應(yīng)用中需要標(biāo)記指針在實(shí)際應(yīng)用中需要標(biāo)記指針 5.壓縮信息 Pitter patter Pitter pa(7,4) 游戲：文字的解壓縮游戲：文字的解壓縮 恢復(fù)一首缺詞少字的詩歌恢復(fù)一首缺詞少字的詩歌“Pease porridge”Pease porr

25、idge” 5.壓縮信息 游戲：文字的解壓縮游戲：文字的解壓縮 恢復(fù)一首缺詞少字的詩歌恢復(fù)一首缺詞少字的詩歌“Pease porridge”Pease porridge” 5.壓縮信息 擴(kuò)展：自指向代碼擴(kuò)展：自指向代碼 對(duì)于對(duì)于“Banana”Banana”該如何分解？該如何分解？ Ban(2,3)Ban(2,3) 對(duì)于對(duì)于“mississippimississippi”該如何分解？該如何分解？ miss(3,4)ppi 5.壓縮信息 介紹介紹 在數(shù)據(jù)的存儲(chǔ)、傳輸、處理時(shí)會(huì)產(chǎn)生錯(cuò)誤在數(shù)據(jù)的存儲(chǔ)、傳輸、處理時(shí)會(huì)產(chǎn)生錯(cuò)誤 如何能檢測甚至自動(dòng)修復(fù)錯(cuò)誤如何能檢測甚至自動(dòng)修復(fù)錯(cuò)誤 奇偶校驗(yàn)奇偶校驗(yàn) 6.

26、檢測錯(cuò)誤 游戲目的游戲目的 掌握計(jì)算機(jī)中檢驗(yàn)數(shù)據(jù)錯(cuò)誤的奇偶校驗(yàn)。 游戲內(nèi)容游戲內(nèi)容 準(zhǔn)備36張卡片，保證每張卡片正反兩面的圖案和顏色不同。學(xué)生 任意擺放其中25張卡片,你增加一行和一列。然后你背過身去，讓學(xué) 生任意翻轉(zhuǎn)一張卡片。 游戲結(jié)果游戲結(jié)果 您可以猜出學(xué)生翻轉(zhuǎn)的是那一張卡片。使學(xué)生掌握計(jì)算機(jī)中是如 何檢驗(yàn)數(shù)據(jù)錯(cuò)誤的。 6.檢測錯(cuò)誤 翻卡街頭魔術(shù) 6.檢測錯(cuò)誤 玩法： 讓學(xué)生將卡片放在桌子上,并由他決定每張卡片放置的正 反。 接著，你可以增加幾張卡片。 讓學(xué)生翻轉(zhuǎn)一張卡片，你總能告訴他哪一張卡片是被翻過 的。 訣竅就在你所增加的幾張卡片。 6.檢測錯(cuò)誤 圖中每行有多少張白色的卡片？ 左下方

27、最后兩張應(yīng)該是什么顏 色的卡片？ 規(guī)律在那里？ 每行每列白色卡片數(shù)量均為偶數(shù)。 6.檢測錯(cuò)誤 右圖中卡片組合中，每行和每列的 白色卡片，開始均為偶數(shù)？記下現(xiàn) 在各行上白色卡片的總數(shù)。 哪一行白色卡片的總數(shù)不再為偶數(shù) 了呢？ 記下每列白色卡片總數(shù)。 哪一列白色卡片的總數(shù)不再為偶數(shù) 了呢？ 你能判斷出是哪張卡片被翻動(dòng)過? 6.檢測錯(cuò)誤 這些被放置的卡片就好比計(jì)算機(jī)中 的比特(0或1),而0和1的組合代表了 數(shù)字、字母或圖像。那些新增加的 卡片我們稱之為奇偶校驗(yàn)位。計(jì)算 機(jī)就是通過在數(shù)據(jù)中添加奇偶校驗(yàn) 位來保證數(shù)據(jù)不被隨意修改。 利用類似奇偶校驗(yàn)的方法，可以保 護(hù)計(jì)算機(jī)中幾乎所有的數(shù)據(jù)。 6.檢測錯(cuò)

28、誤 當(dāng)發(fā)生一系列錯(cuò)誤時(shí)，什么情況下 計(jì)算機(jī)能利用奇偶校驗(yàn)位來檢測并 修正錯(cuò)誤。 圖中開始每行每列的白色數(shù)均為偶 數(shù)，但有兩張卡片已經(jīng)翻過了。 哪幾行哪幾列處于錯(cuò)誤狀態(tài)？ 我們能檢測到錯(cuò)誤發(fā)生了，但無法修復(fù) 它們。 6.發(fā)現(xiàn)更多的錯(cuò)誤 如果計(jì)算機(jī)接收到一條信息中，提示它可能存在兩個(gè)比特 的錯(cuò)誤，那么此時(shí)計(jì)算機(jī)如何處理？ 如果同時(shí)發(fā)生兩處錯(cuò)誤，你無法確定哪個(gè)是出錯(cuò)的比特，你必須 讓發(fā)送人重新再發(fā)送一次消息。 但有時(shí)如磁盤上的數(shù)據(jù)無法重新發(fā)送，所以糾錯(cuò)也是很重要的。 試著用幾張卡片排列成滿足奇偶檢驗(yàn)原理的陣列（保證每 行和每列的白色卡片均為偶數(shù)）。你能在翻動(dòng)兩張卡片后， 保持每行和每列白色卡片總數(shù)仍

29、為偶數(shù)嗎？ 不能 6.發(fā)現(xiàn)更多的錯(cuò)誤 你能做到翻動(dòng)3張卡片，但不被檢測出來嗎？ 不能 翻動(dòng)4張卡片，但不被檢測出來嗎？ 可以，只要挑選兩行和兩列，翻轉(zhuǎn)位于行和列交叉處的四張卡片。 6.發(fā)現(xiàn)更多的錯(cuò)誤 錯(cuò)誤數(shù)量錯(cuò)誤數(shù)量可以檢測出可以檢測出可以糾錯(cuò)可以糾錯(cuò) 1YesYes 2或3YesNo 4NoNo 6.發(fā)現(xiàn)更多的錯(cuò)誤 奇偶校驗(yàn)的特殊用法 奇偶校驗(yàn)陣列 RAID磁盤陣列 6.發(fā)現(xiàn)更多的錯(cuò)誤 每本書在封底都有一個(gè)10位或13位的編號(hào)，稱為國際標(biāo)準(zhǔn) 書號(hào)（ISBN）。 ISBN的最后一位數(shù)字稱為計(jì)算機(jī)校驗(yàn)碼。 2007年1月開始，圖書統(tǒng)一開始使用13位的ISBN。 10位編碼原理: 第一位數(shù)字乘以1

30、0,第二位數(shù)字乘以9,一直到第9位數(shù)字乘以2，將 它們相加的總和除以11，記下余數(shù)。11-余數(shù)為校驗(yàn)碼。 校驗(yàn)碼值為10，用X代替。 6.ISBN檢測 ISBN 0-13-911991-4 (0 10) + (1 9) + (3 8) + (9 7) + (1 6)+ (1 5) + (9 4) + (9 3) + (1 2) = 172 172 11 = 15 remainder 7 11 7 = 4 6.ISBN檢測 ISBN 0-14-911991-4 (0 10) + (1 9) + (4 8) + (9 7) + (1 6)+ (1 5) + (9 4) + (9 3) + (1 2) = 180 180 11 = 16 remainder 4 11 4 = 7 6.ISBN檢測 如果兩個(gè)數(shù)字顛倒了, 0-13-191991-4? 你能找出只改變其中一個(gè)數(shù)字,并保證最后的校驗(yàn)碼不變 的方法嗎? 不能 6.ISBN檢測 13位編碼