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

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

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

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

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

5、。 計算哲學(xué)、計算語言學(xué)、生命計算、計算化學(xué)、計算哲學(xué)、計算語言學(xué)、生命計算、計算化學(xué)、 計算社會學(xué)、計算人類學(xué)。計算社會學(xué)、計算人類學(xué)。 問題的提出 計算無處不在計算無處不在計算新時代計算新時代 最初發(fā)明計算機(jī)的動機(jī)，在于計算機(jī)運(yùn)算能力的應(yīng)用，如科學(xué)、最初發(fā)明計算機(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)用范圍就延伸至教育、休閑以及國 計民生各個方面。計民生各個方面。 問題的提出 計算方法和模型使我們敢于去處

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

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

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

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

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

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

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

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

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

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

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

17、序、查詢、發(fā)送及傳輸信息）。 不插電的計算機(jī)科學(xué)的內(nèi)容 二進(jìn)制數(shù)和“比特” 用二進(jìn)制數(shù)來存取數(shù)據(jù) 從比特到字母 從比特到圖像 壓縮信息 檢測錯誤 不插電的計算機(jī)科學(xué)的內(nèi)容 介紹： 保存數(shù)據(jù)是計算機(jī)首先要完成的事情 二進(jìn)制是所有計算機(jī)的數(shù)據(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ī)

18、技術(shù)中一種常用的度量單位，非0即1 ，且容易實(shí)現(xiàn)； 從小比特可到大數(shù)字。 1.二進(jìn)制數(shù)和“比特” 二進(jìn)制數(shù)字游戲 1.二進(jìn)制數(shù)和“比特” 互動： 準(zhǔn)備卡片 你留意到卡片的規(guī)律沒有? 如果向左側(cè)繼續(xù)增加一張卡片,這張卡片需要畫幾個點(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表示多少? 這些卡片一共有多少個比特? 1.二進(jìn)制數(shù)和“比特” 用任意符號代表二進(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ī)中的“大”數(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ù)表示一個十進(jìn)制數(shù)（轉(zhuǎn)換）？如何用二進(jìn)制數(shù)表示一個十進(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ī) 介紹介紹“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ī)中存儲的任何數(shù)據(jù)（文檔、電子郵件、網(wǎng)頁、圖片、音樂、計算機(jī)中存儲的任何數(shù)據(jù)（文檔、電子郵件、網(wǎng)頁、圖片、音樂、 視頻）都是二進(jìn)制視頻）都是二進(jìn)制 比特代表字母比特代表字母-編碼和解碼編碼和解碼 3.從比特到字母 游戲：儲藏室謎題游戲：儲藏室謎題 3.從比特到字母 游戲：傳音游戲游戲：傳音游戲 像像modemmodem一樣用聲音發(fā)送一樣用聲音發(fā)送emailemail 3.從比特到字母 介紹介紹 比特可以表示字母、圖像，如：ASCII

22、碼或Unicode碼來存儲字符； 比特表示像素存儲圖像。 像素（pixel） 4.從比特到圖像 最簡單的黑白圖像中,每個像素只有兩種值:黑或白,如下 面字母a的放大圖。 當(dāng)計算機(jī)存儲這樣的圖片時,它只需記錄圖像中哪些是黑 點(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)：記錄每個白色或黑色連續(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ù)的單詞 計算壓縮前后字符數(shù)計算壓縮前后字符數(shù) 計算壓縮率計算壓縮率 5.壓縮信息 游戲：文字的壓縮游戲：文字的壓縮 尋找重復(fù)的

24、單詞尋找重復(fù)的單詞-The, Rain, tter, pa,The Rain, -The, Rain, tter, pa,The Rain, Pitter patterPitter patter 計算壓縮前后字符數(shù)計算壓縮前后字符數(shù)-96/39-96/39 計算壓縮率計算壓縮率-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ò)展：自指向代碼 對于對于“Banana”Banana”該如何分解？該如何分解？ Ban(2,3)Ban(2,3) 對于對于“mississippimississippi”該如何分解？該如何分解？ miss(3,4)ppi 5.壓縮信息 介紹介紹 在數(shù)據(jù)的存儲、傳輸、處理時會產(chǎn)生錯誤在數(shù)據(jù)的存儲、傳輸、處理時會產(chǎn)生錯誤 如何能檢測甚至自動修復(fù)錯誤如何能檢測甚至自動修復(fù)錯誤 奇偶校驗(yàn)奇偶校驗(yàn) 6.

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

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

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

29、為偶數(shù)嗎？ 不能 6.發(fā)現(xiàn)更多的錯誤 你能做到翻動3張卡片，但不被檢測出來嗎？ 不能 翻動4張卡片，但不被檢測出來嗎？ 可以，只要挑選兩行和兩列，翻轉(zhuǎn)位于行和列交叉處的四張卡片。 6.發(fā)現(xiàn)更多的錯誤 錯誤數(shù)量錯誤數(shù)量可以檢測出可以檢測出可以糾錯可以糾錯 1YesYes 2或3YesNo 4NoNo 6.發(fā)現(xiàn)更多的錯誤 奇偶校驗(yàn)的特殊用法 奇偶校驗(yàn)陣列 RAID磁盤陣列 6.發(fā)現(xiàn)更多的錯誤 每本書在封底都有一個10位或13位的編號，稱為國際標(biāo)準(zhǔn) 書號（ISBN）。 ISBN的最后一位數(shù)字稱為計算機(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檢測 如果兩個數(shù)字顛倒了, 0-13-191991-4? 你能找出只改變其中一個數(shù)字,并保證最后的校驗(yàn)碼不變 的方法嗎? 不能 6.ISBN檢測 13位編碼