信息技術教育中的計算思維課件

信息技術教育中的計算思維信息技術教育中的計算思維

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

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

ComputationalThinking,COMMUNICATIONS

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

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

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