計(jì)算思維-概念、特征與啟示樊磊首都師范大學(xué)教育技術(shù)系u@計(jì)算思維興起的緣由從二十世紀(jì)七十年代中期開(kāi)始，在諾貝爾物理學(xué)獎(jiǎng)得主KenWilson等人的積極倡導(dǎo)下，基于大規(guī)模并行數(shù)值計(jì)算與模擬的“計(jì)算科學(xué)”（ComputingScience）開(kāi)創(chuàng)了科學(xué)研究的第三種范例（理論、實(shí)驗(yàn)、計(jì)算機(jī)模擬）。計(jì)算科學(xué)協(xié)同其它科學(xué)領(lǐng)域（如基因組工程、天體物理等等）取得了一系列重要的突破性進(jìn)展，受到傳統(tǒng)科學(xué)界的重視和接納。1991年，美國(guó)聯(lián)邦政府立法將建立聯(lián)網(wǎng)的大規(guī)模超級(jí)計(jì)算中心（資源）作為保持美國(guó)科學(xué)技術(shù)領(lǐng)先地位的一項(xiàng)重要措施。今天我們所熟悉的大數(shù)據(jù)、可視化及云計(jì)算等等均源自于這場(chǎng)運(yùn)動(dòng)。國(guó)內(nèi)很多大學(xué)數(shù)學(xué)學(xué)院中的“信息與計(jì)算”專業(yè)也是在這個(gè)時(shí)期出現(xiàn)的。這場(chǎng)運(yùn)動(dòng)對(duì)于“計(jì)算機(jī)科學(xué)”的普及和得到政府決策部門(mén)的重視起到了一定的推進(jìn)作用（像之前的“人工智能”一樣?。?。由于相對(duì)片面地理解和宣揚(yáng)所謂的“計(jì)算科學(xué)”，也帶來(lái)很多副作用，至今學(xué)術(shù)界仍有相當(dāng)多的人混淆“計(jì)算科學(xué)”與“計(jì)算機(jī)科學(xué)”（或“信息科學(xué)”）。計(jì)算思維興起的緣由更傳統(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ù)量開(kāi)始呈明顯下降趨勢(shì)，高規(guī)格科研資助的力度和水平降低，這標(biāo)志學(xué)科的影響力和社會(huì)認(rèn)知度出現(xiàn)了危機(jī)。計(jì)算機(jī)科學(xué)界開(kāi)始再次反思并宣揚(yáng)自身學(xué)科的核心價(jià)值，有關(guān)計(jì)算思維的探討和研究就是在這樣的背景下產(chǎn)生的。計(jì)算思維興起的緣由從算法思維到計(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é)思維與算法思維”的文章。“算法思維”著重強(qiáng)調(diào)在（數(shù)學(xué)）問(wèn)題求解過(guò)程中算法（構(gòu)造?。┑暮诵淖饔谩，F(xiàn)代“計(jì)算思維”的含義比“算法思維”要廣泛得多，包含了多種抽象層次、發(fā)展算法的數(shù)學(xué)以及跨越不同尺度問(wèn)題的算法效率問(wèn)題的分析等方面。模型與（現(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ī)律計(jì)算模型與計(jì)算思維計(jì)算模型計(jì)算概念計(jì)算機(jī)科學(xué)理論抽象自然的及人工的信息處理建模應(yīng)用概念關(guān)聯(lián)結(jié)構(gòu)規(guī)律小問(wèn)題中的計(jì)算思維CAPTCHA=CompletelyAutomatedPublicTuringTeststoTellComputersandHumansApart圖靈測(cè)試的一個(gè)現(xiàn)代簡(jiǎn)單直接應(yīng)用！圖靈測(cè)試的目的是給機(jī)器“智能”下一個(gè)定義，這個(gè)小小的應(yīng)用與圖靈提出“測(cè)試”的本意相差甚遠(yuǎn)。整數(shù)乘法的計(jì)算量問(wè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ù)雜程度是不可接受的（為什么？）。1971年，基于Gauss在十九世紀(jì)的一個(gè)古老的思想，由計(jì)算機(jī)科學(xué)家們?cè)O(shè)計(jì)的快速乘法算法，其計(jì)算復(fù)雜度為O(nlognloglogn)這個(gè)算法每年節(jié)省的計(jì)算資源價(jià)值數(shù)以百億元！小問(wèn)題中的計(jì)算思維小問(wèn)題中的計(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)處理！）。大問(wèn)題中的計(jì)算思維素?cái)?shù)判定與大數(shù)分解–公鑰密碼學(xué)圖著色問(wèn)題（NP難解問(wèn)題）–身份認(rèn)證（零知識(shí)協(xié)議）稀疏矩陣計(jì)算–PageRank值（網(wǎng)頁(yè)排名）量子力學(xué)的范疇基礎(chǔ)零知識(shí)協(xié)議所謂零知識(shí)認(rèn)證協(xié)議指：一方（證明者）在不暴露有可能危及秘密的任何信息前提下，向另一方（驗(yàn)證方）證明她知道一個(gè)秘密。零知識(shí)協(xié)議在1985年由以色列計(jì)算機(jī)科學(xué)家ShafiGoldwasser等人提出。ShafiGoldwasser圖著色與零知識(shí)協(xié)議圖的3-著色問(wèn)題：任給一個(gè)圖，設(shè)計(jì)一種方案，使用3種顏色著色圖中的各個(gè)節(jié)點(diǎn)，使得任意相鄰兩個(gè)節(jié)點(diǎn)（有邊相連的節(jié)點(diǎn)）的顏色不同。3-圖著色問(wèn)題是一個(gè)NP難解問(wèn)題，簡(jiǎn)單地說(shuō)，就是沒(méi)有快速算法能對(duì)任何給定的圖完成3-著色。但反過(guò)來(lái)可以快速生成3-著色的圖！圖著色與零知識(shí)協(xié)議協(xié)同計(jì)算一組人通過(guò)其各自擁有的私秘信息（如年齡、體重等）共同計(jì)算出一個(gè)共享的信息，但在計(jì)算過(guò)程中不透露出個(gè)人的秘密。例如：Alice,Bob,Carol想計(jì)算他們的體重之和，但都不希望別人知道自己的體重。協(xié)同計(jì)算1.每人隨機(jī)選擇0到1000之間的兩個(gè)數(shù)，然后再選擇出第三個(gè)數(shù)，使得三個(gè)數(shù)之和模1000后恰好是自己的體重。2.每人將隨機(jī)選擇的兩個(gè)數(shù)分別發(fā)送給其他兩人。4.每個(gè)人將三個(gè)人的數(shù)相加后再模1000后的余數(shù)就是三人的體重之和。3.每人將自己的第三個(gè)數(shù)與接收到的其他人的共享數(shù)相加，并將結(jié)果模1000。計(jì)算思維與數(shù)學(xué)思維的關(guān)系關(guān)注的對(duì)象不同關(guān)注的問(wèn)題不同都有多級(jí)抽象層次使用數(shù)學(xué)方法來(lái)證明或研究算法問(wèn)題計(jì)算思維會(huì)反作用于數(shù)學(xué)（這點(diǎn)非常關(guān)鍵！）指數(shù)運(yùn)算、邏輯推理和化簡(jiǎn)法則

(am)n=amn.

p

(q

r)

p

q

r.兩者的共同點(diǎn)是什么？參見(jiàn)：樊磊等，利用計(jì)算直覺(jué)理解抽象數(shù)學(xué)概念，黑龍江高教研究，2005年。計(jì)算思維對(duì)數(shù)學(xué)的反作用什么是計(jì)算思維？計(jì)算思維的實(shí)質(zhì)是將問(wèn)題表征為關(guān)于某種計(jì)算模型的信息處理，并在此基礎(chǔ)上尋求問(wèn)題的算法解。依問(wèn)題的情況可能需要發(fā)現(xiàn)新的計(jì)算模型或修改現(xiàn)有的模型。計(jì)算思維對(duì)每個(gè)人都是基本技能，不僅僅是對(duì)計(jì)算機(jī)科學(xué)家。在兒童的基本分析能力的構(gòu)成上，除閱讀、書(shū)寫(xiě)、算術(shù)外，還應(yīng)加上計(jì)算（思維）。印刷出版促進(jìn)了閱讀、書(shū)寫(xiě)、算術(shù)能力的普及，而計(jì)算機(jī)則將促進(jìn)計(jì)算思維的普及。計(jì)算思維的特征概念化和抽象化-不僅與編程能力有關(guān)，計(jì)算機(jī)科學(xué)也不僅是計(jì)算機(jī)編程。“像計(jì)算機(jī)科學(xué)家一樣思考”，其含義比能夠編程要更深刻，需要不同抽象層面的思考。不能靠死記硬背積累-現(xiàn)代社會(huì)中每個(gè)人都必須具備的一種基本技能。計(jì)算思維是人類解決問(wèn)題的（而不是計(jì)算機(jī)的）一種思維方式，它不是試圖讓人類像計(jì)算機(jī)一樣思考。計(jì)算思維的特征與數(shù)學(xué)思維和工程思維互補(bǔ)。計(jì)算思維是思想，不是制品。它不僅是我們生活中已經(jīng)隨處可見(jiàn)的軟件和硬件制品，而是我們用以處理和求解問(wèn)題、管理日常事務(wù)、與他人通信及交互的“計(jì)算概念”框架。人人可用、處處可用。計(jì)算機(jī)思維是指導(dǎo)計(jì)算機(jī)科學(xué)教育家、研究者、實(shí)踐者的大一統(tǒng)視界，將會(huì)與人類思維密切集成（就像我們的數(shù)學(xué)與工程思維能力一樣）。計(jì)算機(jī)科學(xué)與信息科學(xué)計(jì)算機(jī)科學(xué)是對(duì)自然和人工現(xiàn)象中的信息處理基本性質(zhì)的研究，而計(jì)算機(jī)是進(jìn)行這類研究的基本工具，因此也是研究對(duì)象之一。信息處理存在于自然（上帝造的）世界和人造世界，因此計(jì)算機(jī)科學(xué)的研究兼具數(shù)學(xué)和自然科學(xué)的特征，是數(shù)學(xué)、工程和科技的有機(jī)合體。在主要?dú)W洲國(guó)家，與“計(jì)算機(jī)科學(xué)”（ComputerScience）“差不多”相對(duì)等的詞是“信息科學(xué)”（Informatics）。Computing一詞也經(jīng)常用來(lái)指“計(jì)算機(jī)科學(xué)”，但其有同時(shí)包容ComputerScience和ComputingScience的含義。計(jì)算機(jī)科學(xué)的核心價(jià)值在于計(jì)算能夠做些什么（計(jì)算理論）、如何做（算法）、能做多好（