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

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

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

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

ComputationalThinking,COMMUNICATIONS

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

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

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