信息技術(shù)教育中的計(jì)算思維信息技術(shù)教育中的計(jì)算思維

……學(xué)會(huì)運(yùn)用計(jì)算思維對(duì)問(wèn)題進(jìn)行識(shí)別、分析、抽象、建模并設(shè)計(jì)系統(tǒng)解決方案……--摘自《高中信息技術(shù)課程標(biāo)準(zhǔn)修訂（草稿）》學(xué)科核心素養(yǎng)總目標(biāo)信息技術(shù)教育中的計(jì)算思維……學(xué)會(huì)運(yùn)用計(jì)算思維對(duì)問(wèn)題進(jìn)行識(shí)別、分析、抽運(yùn)用計(jì)算機(jī)科學(xué)領(lǐng)域的思想方法形成解決問(wèn)題方案的過(guò)程中，所包含的一系列思維活動(dòng)即計(jì)算思維。

具備計(jì)算思維的學(xué)生在信息活動(dòng)中能夠采用計(jì)算機(jī)可以處理的方式界定問(wèn)題，抽象問(wèn)題特征，建立結(jié)構(gòu)模型，合理組織數(shù)據(jù)；通過(guò)判斷、分析與綜合各種信息資源，運(yùn)用算法設(shè)計(jì)解決問(wèn)題的方案；總結(jié)利用計(jì)算機(jī)解決問(wèn)題的過(guò)程與方法，并將其遷移到與其相關(guān)的其他問(wèn)題解決之中。--摘自《高中信息技術(shù)課程標(biāo)準(zhǔn)修訂（草稿）》學(xué)科核心素養(yǎng)部分信息技術(shù)教育中的計(jì)算思維運(yùn)用計(jì)算機(jī)科學(xué)領(lǐng)域的思想方法形成解決問(wèn)題方案“計(jì)算思維”是信息社會(huì)運(yùn)用信息技術(shù)解決問(wèn)題的主要思維方式，作為人類三大科學(xué)思維方式之一，計(jì)算思維對(duì)學(xué)生世界觀、人生觀、價(jià)值觀的形成有著重要影響。計(jì)算思維的本質(zhì)是抽象和自動(dòng)化，在不同的模塊課程中有不同的表現(xiàn)形式。任何一種思維方式從形成到內(nèi)化都需要在解決問(wèn)題的過(guò)程中經(jīng)過(guò)多次運(yùn)用才能逐步完成。教學(xué)時(shí)要在各個(gè)模塊課程中提煉計(jì)算思維的具體表現(xiàn)，將思維過(guò)程設(shè)計(jì)為教學(xué)中每個(gè)范例的主線，每個(gè)實(shí)踐項(xiàng)目的主線，讓學(xué)生在解決不同問(wèn)題的情境中，反復(fù)親歷思維的全過(guò)程，不斷運(yùn)用學(xué)科思維，從而達(dá)到內(nèi)化程度。--摘自《高中信息技術(shù)課程標(biāo)準(zhǔn)修訂（草稿）》教學(xué)建議部分信息技術(shù)教育中的計(jì)算思維“計(jì)算思維”是信息社會(huì)運(yùn)用信息技術(shù)解決問(wèn)題的計(jì)算思維興起的緣由從二十世紀(jì)七十年代中期開始，在諾貝爾物理學(xué)獎(jiǎng)得主KenWilson等人的積極倡導(dǎo)下，基于大規(guī)模并行數(shù)值計(jì)算與模擬的“計(jì)算科學(xué)”（ComputingScience）迅速崛起，并開創(chuàng)了科學(xué)研究的第三種范例（理論、實(shí)驗(yàn)、計(jì)算機(jī)模擬）。計(jì)算科學(xué)協(xié)同其它科學(xué)領(lǐng)域，如基因組工程、生物信息學(xué)、天體物理等，取得了一系列重大突破性進(jìn)展，并受到傳統(tǒng)科學(xué)界的重視和接納。計(jì)算思維興起的緣由從二十世紀(jì)七十年代中期開始，在諾貝爾物理學(xué)1991年，美國(guó)聯(lián)邦政府立法將建立聯(lián)網(wǎng)的大規(guī)模超級(jí)計(jì)算中心（資源）作為保持美國(guó)科學(xué)技術(shù)領(lǐng)先地位的一項(xiàng)重要措施。今天我們所熟悉的一些新技術(shù)，包括大數(shù)據(jù)、數(shù)據(jù)可視化及云計(jì)算等均源自于這場(chǎng)運(yùn)動(dòng)。國(guó)內(nèi)很多大學(xué)數(shù)學(xué)學(xué)院中的“信息與計(jì)算”專業(yè)也是在這個(gè)時(shí)期陸續(xù)出現(xiàn)的。計(jì)算思維興起的緣由1991年，美國(guó)聯(lián)邦政府立法將建立聯(lián)網(wǎng)的大規(guī)模超級(jí)計(jì)算中心（這場(chǎng)運(yùn)動(dòng)對(duì)于“計(jì)算機(jī)科學(xué)”的普及、得到政府決策部門的重視和基金支持起到了一定的推進(jìn)作用，像之前的“人工智能”一樣！但是，由于相對(duì)片面地理解和宣揚(yáng)所謂的“計(jì)算科學(xué)”，也帶來(lái)一些副作用。至今仍有相當(dāng)多的人（包括學(xué)術(shù)界）混淆“計(jì)算科學(xué)”與“計(jì)算機(jī)科學(xué)”或“信息科學(xué)”。計(jì)算思維興起的緣由這場(chǎng)運(yùn)動(dòng)對(duì)于“計(jì)算機(jī)科學(xué)”的普及、得到政府決策部門的重視和基更傳統(tǒng)意義上的計(jì)算機(jī)科學(xué)（ComputerScience，指圍繞計(jì)算現(xiàn)象和計(jì)算對(duì)象的研究）反而受到了冷落甚至質(zhì)疑。進(jìn)入二十一世紀(jì)后，美國(guó)報(bào)考各大學(xué)計(jì)算機(jī)科學(xué)及其相關(guān)專業(yè)的優(yōu)秀學(xué)生數(shù)量開始呈明顯下降趨勢(shì)，高規(guī)格的科研資助力度和水平有所降低。這標(biāo)志學(xué)科的影響力和社會(huì)認(rèn)知度出現(xiàn)了危機(jī)。計(jì)算思維興起的緣由更傳統(tǒng)意義上的計(jì)算機(jī)科學(xué)（ComputerScience，計(jì)算思維興起的緣由計(jì)算機(jī)科學(xué)界開始反思，隨后大力宣揚(yáng)自身學(xué)科的核心價(jià)值。有關(guān)計(jì)算思維的探討和研究就是在這樣的背景下產(chǎn)生的。計(jì)算思維旨在倡導(dǎo)一種所謂的“計(jì)算機(jī)科學(xué)家的思維方式”，以區(qū)別“邏輯（抽象）思維”、“數(shù)學(xué)思維”和“工程化思維”等等這些已為學(xué)術(shù)界普遍認(rèn)同的思維方式，從而提高社會(huì)、學(xué)術(shù)界、學(xué)生及家長(zhǎng)對(duì)學(xué)科的認(rèn)同。計(jì)算思維興起的緣由計(jì)算機(jī)科學(xué)界開始反思，隨后大力宣揚(yáng)自身學(xué)科當(dāng)前比較系統(tǒng)和典型的觀點(diǎn)是由J.Wing（周以真）提出的：

ComputationalThinking,COMMUNICATIONS

OFTHEACM,Vol.49,No.3,March2006J.Wing的觀點(diǎn)對(duì)國(guó)內(nèi)高校的計(jì)算機(jī)教學(xué)頗具影響力。但有關(guān)“什么是計(jì)算思維？”的問(wèn)題仍存爭(zhēng)議。計(jì)算思維興起的緣由當(dāng)前比較系統(tǒng)和典型的觀點(diǎn)是由J.Wing（周以真）提出的：信息技術(shù)教育中的計(jì)算思維ppt課件從算法思維到計(jì)算思維早在二十世紀(jì)五、六十年代，就曾提出算法思維的說(shuō)法，是當(dāng)時(shí)的“算法學(xué)家”們?yōu)闋?zhēng)取將計(jì)算機(jī)科學(xué)從數(shù)學(xué)中獨(dú)立出來(lái)所進(jìn)行的努力。著名計(jì)算機(jī)科學(xué)家D.Knuth（高德納）1985年在《美國(guó)數(shù)學(xué)月刊》（為美國(guó)影響最大、讀者群最廣的數(shù)學(xué)雜志）上發(fā)表了題為“數(shù)學(xué)思維與算法思維”的文章。文章中例舉了十個(gè)例子，說(shuō)明算法思維與數(shù)學(xué)思維解決問(wèn)題的相同和不同之處。從算法思維到計(jì)算思維早在二十世紀(jì)五、六十年代，就曾提出算法思“算法思維”著重強(qiáng)調(diào)在（數(shù)學(xué)）問(wèn)題求解過(guò)程中算法構(gòu)造的核心作用?，F(xiàn)代“計(jì)算思維”的含義比“算法思維”要更廣泛。計(jì)算思維包含了多種抽象層次、發(fā)展算法的數(shù)學(xué)以及對(duì)跨越不同尺度問(wèn)題的算法效率的分析等方面。從算法思維到計(jì)算思維“算法思維”著重強(qiáng)調(diào)在（數(shù)學(xué)）問(wèn)題求解過(guò)程中算法構(gòu)造的核心作（現(xiàn)實(shí)世界中的）問(wèn)題與模型模型現(xiàn)實(shí)世界理論（現(xiàn)實(shí)世界中的）問(wèn)題與模型模型現(xiàn)實(shí)世界理論數(shù)學(xué)模型與數(shù)學(xué)思維數(shù)學(xué)模型數(shù)學(xué)概念數(shù)學(xué)理論抽象自然現(xiàn)象及對(duì)象建模應(yīng)用概念關(guān)聯(lián)結(jié)構(gòu)規(guī)律數(shù)學(xué)模型與數(shù)學(xué)思維數(shù)學(xué)模型數(shù)學(xué)概念數(shù)學(xué)理論抽象自然現(xiàn)象及對(duì)象計(jì)算模型與計(jì)算思維計(jì)算模型計(jì)算概念計(jì)算機(jī)科學(xué)理論抽象自然的及人工的信息處理建模應(yīng)用概念關(guān)聯(lián)結(jié)構(gòu)規(guī)律計(jì)算模型與計(jì)算思維計(jì)算模型計(jì)算概念計(jì)算機(jī)科學(xué)理論抽象自然的及從小處看計(jì)算思維XYffXY數(shù)學(xué)函數(shù)觀點(diǎn)：強(qiáng)調(diào)定義域（輸入）和值域（輸出）的具體形式，淡化對(duì)應(yīng)本身。算法（流程圖）觀點(diǎn)：強(qiáng)調(diào)如何將輸入變換為輸出，淡化對(duì)輸入輸出自身的描述（由數(shù)據(jù)結(jié)構(gòu)來(lái)處理?。?。從小處看計(jì)算思維XYffXY數(shù)學(xué)函數(shù)觀點(diǎn)：強(qiáng)調(diào)定義域（輸入）如何防止非正常用戶破解密碼？常規(guī)的解決方法：使用復(fù)雜的密碼、限制密碼輸入次數(shù)、限制輸入的時(shí)間…關(guān)鍵：防止非法用戶利用計(jì)算機(jī)快速嘗試不同的密碼。計(jì)算思維的解決方法：只有人能做好但計(jì)算機(jī)做不好的。日常應(yīng)用中的計(jì)算思維如何防止非正常用戶破解密碼？日常應(yīng)用中的計(jì)算思維日常應(yīng)用中的計(jì)算思維CAPTCHA=CompletelyAutomatedPublicTuringTeststoTellComputersandHumansApart圖靈測(cè)試的一個(gè)現(xiàn)代的、簡(jiǎn)單的直接應(yīng)用！圖靈測(cè)試的初始目的是給“機(jī)器智能”下一個(gè)定義。這個(gè)小應(yīng)用與圖靈提出“測(cè)試”的本意相差甚遠(yuǎn)。日常應(yīng)用中的計(jì)算思維CAPTCHA=Completely信息技術(shù)教育中的計(jì)算思維ppt課件整數(shù)乘法的計(jì)算問(wèn)題使用標(biāo)準(zhǔn)的乘法算法，兩個(gè)n位整數(shù)相乘的“計(jì)算量”大致上與n2成正比。用計(jì)算理論的術(shù)語(yǔ)說(shuō)：兩個(gè)n位整數(shù)乘法的“計(jì)算復(fù)雜度”為O(n2).例如，兩個(gè)10000位整數(shù)乘法大約需要10000

10000=1010次標(biāo)準(zhǔn)運(yùn)算。對(duì)于“大”整數(shù)（如1010位以上級(jí)別的）的乘法，這個(gè)復(fù)雜程度是不可接受的。關(guān)于算法效率的一個(gè)非平凡例子整數(shù)乘法的計(jì)算問(wèn)題關(guān)于算法效率的一個(gè)非平凡例子1971年，基于著名數(shù)學(xué)家高斯在十九世紀(jì)的一個(gè)古老的思想，計(jì)算機(jī)科學(xué)家們?cè)O(shè)計(jì)出一種快速的乘法算法，其計(jì)算復(fù)雜度為O(nlognloglogn)這個(gè)算法每年節(jié)省的計(jì)算資源價(jià)值數(shù)以百億元！關(guān)于算法效率的一個(gè)非平凡例子1971年，基于著名數(shù)學(xué)家高斯在十九世紀(jì)的一個(gè)古老的思想，計(jì)例如，Web上總共大概有1011個(gè)頁(yè)面，做一次關(guān)鍵詞搜索要做多次1011

1011階矩陣的乘法，這個(gè)計(jì)算量約為1025次標(biāo)準(zhǔn)計(jì)算單位。假設(shè)計(jì)算機(jī)每秒計(jì)算1015次（這已經(jīng)超過(guò)了當(dāng)前最快的計(jì)算機(jī)數(shù)百萬(wàn)倍了），那么做一次搜索就需要大概1010秒。使用快速乘法算法，計(jì)算量大約只有大約1012次！關(guān)于算法效率的一個(gè)非平凡例子例如，Web上總共大概有1011個(gè)頁(yè)面，做一次關(guān)鍵詞搜索要做大問(wèn)題中的計(jì)算思維公鑰密碼學(xué)–素?cái)?shù)判定與大數(shù)分解身份認(rèn)證問(wèn)題–圖著色問(wèn)題（NP難解問(wèn)題）網(wǎng)頁(yè)排名問(wèn)題–稀疏矩陣的計(jì)算大數(shù)據(jù)時(shí)代的個(gè)人隱私保護(hù)大問(wèn)題中的計(jì)算思維公鑰密碼學(xué)–素?cái)?shù)判定與大數(shù)分解用計(jì)算思維解決問(wèn)題的一個(gè)非平凡例子在網(wǎng)絡(luò)上如何向某個(gè)實(shí)體證實(shí)自己的身份？這稱為身份認(rèn)證問(wèn)題。關(guān)于這個(gè)問(wèn)題已經(jīng)有大量的研究和解決方案。用計(jì)算思維解決問(wèn)題的一個(gè)非平凡例子在網(wǎng)絡(luò)上如何向某個(gè)實(shí)體證實(shí)用計(jì)算思維解決問(wèn)題的一個(gè)非平凡例子真正難做到的是：既要證實(shí)身份，同時(shí)不透露與身份有關(guān)的任何有價(jià)值的信息。這能做到嗎？如果不改變觀念，肯定做不到!“隱含假設(shè)”是定勢(shì)思維最常見的現(xiàn)象之一。假設(shè)了驗(yàn)證過(guò)程要一次完成。假設(shè)了一方只能問(wèn)、另一方方只能答。假設(shè)了驗(yàn)證結(jié)果的絕對(duì)性。用計(jì)算思維解決問(wèn)題的一個(gè)非平凡例子真正難做到的是：既要證實(shí)身零知識(shí)認(rèn)證問(wèn)題一方（證明者）在不暴露任何有用信息的前提下，向另一方（驗(yàn)證方）證明她知道一個(gè)秘密。1985年由以色列計(jì)算機(jī)科學(xué)家ShafiGoldwasser等人首先提出。Goldwasser獲得2012年度圖靈獎(jiǎng)。Goldwasser的突破性思想很大程度上基于去掉三個(gè)隱含的不必要假設(shè)。去掉隱含假設(shè)后對(duì)答案的要求有顯著變化。驗(yàn)證過(guò)程不必一次性完成，可以進(jìn)行多步驗(yàn)證，每一步只驗(yàn)證一個(gè)微小的部分。求證方和證明方可以進(jìn)行任意對(duì)話。不強(qiáng)求絕對(duì)的“零”知識(shí)，只要求在每一步“幾乎”是零知識(shí)的，而累積的結(jié)果不隨著步驟的增多而加大。零知識(shí)認(rèn)證問(wèn)題一方（證明者）在不暴露任何有用信息的前提下，向零知識(shí)認(rèn)證問(wèn)題–一個(gè)簡(jiǎn)化的版本證明者A向驗(yàn)證方B證明她有暗道內(nèi)雙面門的某一側(cè)的鑰匙，但不能透露是哪一面的鑰匙（秘密）。兩個(gè)關(guān)鍵因素：重復(fù)及隨機(jī)性！重復(fù)逐漸降低了A恰好蒙對(duì)的可能。這稱為Quisquater-Guillou-Berson零知識(shí)協(xié)議。這是所有可能中最簡(jiǎn)單的情況，因?yàn)樯婕暗闹R(shí)僅有1位。原始論文發(fā)表于1989年，標(biāo)題為“寫給嬰兒的零知識(shí)協(xié)議”。A先進(jìn)入暗道走到岔道處。B進(jìn)入暗道到達(dá)岔道處，同時(shí)A從自己有鑰匙的那一側(cè)到達(dá)門口。B要求A從左側(cè)或右側(cè)出來(lái)。重復(fù)上述步驟，直到B確信A的確有一把鑰匙。入口岔道雙面門零知識(shí)認(rèn)證問(wèn)題–一個(gè)簡(jiǎn)化的版本證明者A向驗(yàn)證方B證明她有零知識(shí)認(rèn)證問(wèn)題A向B證明:她可以使用三種不同的顏色將某個(gè)圖的頂點(diǎn)著色，使得相鄰頂點(diǎn)的顏色不同。這個(gè)問(wèn)題的理論依據(jù)是：你可以快速生成一個(gè)著好色的圖。但反之，給出未著色的圖，沒(méi)有簡(jiǎn)單方法能迅速找出著色。這個(gè)問(wèn)題涉及的知識(shí)可以任意多，而知識(shí)的多少依賴于圖的復(fù)雜程度。零知識(shí)認(rèn)證問(wèn)題A向B證明:她可以使用三種不同的顏色將某個(gè)圖零知識(shí)認(rèn)證問(wèn)題–Goldwasser的解答A準(zhǔn)備三幅著色好的圖，每幅圖之間的差異在于同一個(gè)頂點(diǎn)上的顏色相互替換。B看到翻開頂點(diǎn)的著色情況后退出房間，A再換一張圖重復(fù)前面的步驟。每次B都看到正確的著色結(jié)果，重復(fù)足夠多次后，不得不相信A的確知道如何正確著色。A隨機(jī)選擇其中一幅圖，用紙杯蓋住所有的頂點(diǎn)。B進(jìn)入房間，可一次性任意選擇兩個(gè)相鄰的頂點(diǎn)翻開紙杯查看。零知識(shí)認(rèn)證問(wèn)題–Goldwasser的解答A準(zhǔn)備三幅著色一組人通過(guò)各自擁有的私秘信息共同產(chǎn)生一個(gè)可共享的信息信息，但在過(guò)程中不能向其他人透露出其個(gè)人秘密。協(xié)同共享問(wèn)題協(xié)同作業(yè)在現(xiàn)代網(wǎng)絡(luò)環(huán)境中非常重要，協(xié)同作業(yè)中的隱私信息保密是巨大的難題。三個(gè)人希望計(jì)算出其體重之和，但不希望其他兩人知道自己的體重。這個(gè)能做到嗎？計(jì)算過(guò)程不必一次完成，可以進(jìn)行多步計(jì)算，每步只計(jì)算一個(gè)微小的部分。三方均可以與任意其他人進(jìn)行對(duì)話。不強(qiáng)求絕對(duì)不泄漏，只要求在每步計(jì)算時(shí)，信息極少透露。計(jì)算結(jié)果知識(shí)泄漏的累積不隨步驟的增多而加大。一組人通過(guò)各自擁有的私秘信息共同產(chǎn)生一個(gè)可共享的信息信息，但1.每人隨機(jī)選擇0到1000之間的兩個(gè)數(shù)，然后再選擇出第三個(gè)數(shù)，使得三個(gè)數(shù)之和模1000后恰好是自己的體重。2.每人將隨機(jī)選擇的兩個(gè)數(shù)分別發(fā)送給其他兩人。4.每個(gè)人將三個(gè)人的體重?cái)?shù)相加后再模1000后得到的余數(shù)就是三人的體重之和。3.每人將自己的第三個(gè)數(shù)與接收到的其他人的共享數(shù)相加，并將結(jié)果模1000。協(xié)同共享問(wèn)題1.每人隨機(jī)選擇0到1000之間的兩個(gè)數(shù)，然后再選擇出第三一個(gè)思考題在ATM機(jī)上操作時(shí)需要完整正確輸入密碼。能否不用輸入密碼，就讓ATM機(jī)（驗(yàn)證方）相信你的確知道密碼？這個(gè)過(guò)程有巨大的安全隱患。請(qǐng)你找出其中的主要安全隱患。暫且不考慮是否實(shí)用。一個(gè)思考題在ATM機(jī)上操作時(shí)需要完整正確輸入密碼。能否不用輸計(jì)算思維與數(shù)學(xué)思維的關(guān)系關(guān)注的對(duì)象不同關(guān)注的問(wèn)題不同都有多級(jí)抽象層次數(shù)學(xué)方法是證明或研究算法問(wèn)題的工具計(jì)算思維會(huì)反作用于數(shù)學(xué)（這點(diǎn)非常關(guān)鍵！）計(jì)算的方法也可以成為數(shù)學(xué)研究的工具（數(shù)學(xué)實(shí)驗(yàn)、實(shí)驗(yàn)數(shù)學(xué)）計(jì)算思維與數(shù)學(xué)思維的關(guān)系關(guān)注的對(duì)象不同什么是計(jì)算思維？計(jì)算思維的實(shí)質(zhì)是將問(wèn)題表征為關(guān)于某種計(jì)算模型的信息處理，并在此基礎(chǔ)上尋求問(wèn)題的算法解。依問(wèn)題的情況可能需要發(fā)現(xiàn)新的計(jì)算模型或修改現(xiàn)有的模型。計(jì)算思維對(duì)每個(gè)人來(lái)講都是基本技能，不僅僅是對(duì)計(jì)算機(jī)專家。在人的基本能力構(gòu)成上，除閱讀、書寫、算術(shù)外，還應(yīng)加上計(jì)算（思維）。印刷出版促進(jìn)了閱讀、書寫、算術(shù)能力的普及，而計(jì)算機(jī)促進(jìn)了計(jì)算思維的普及。什么是計(jì)算思維？計(jì)算思維的實(shí)質(zhì)是將問(wèn)題表征為關(guān)于某種計(jì)算模型計(jì)算思維的特征概念化和抽象化-不僅與編程能力有關(guān)，計(jì)算機(jī)科學(xué)也不僅是計(jì)算機(jī)編程?！跋裼?jì)算機(jī)科學(xué)家一樣思考”，其含義比能夠編程要更深刻，需要不同抽象層面的思考。不能靠死記硬背積累-現(xiàn)代社會(huì)中每個(gè)人都必須具備的一種基本技能。計(jì)算思維是人類（而不是計(jì)