第一講 計算思維概述

計算思維計算機教研室—周旭ComputationalThinking計算不再只和計算機有關(guān)，它和我們的生活息息相關(guān)。一、計算改變了什么？二、什么是計算？三、什么是計算思維？計算思維引言一、計算改變了什么計算改變了科學(xué)家的思考方式計算生物學(xué)改變著生物學(xué)家的思考方式數(shù)學(xué)機械化改變著數(shù)學(xué)家的思考方式計算博弈理論改變著經(jīng)濟學(xué)家的思考方式社會計算改變社會學(xué)家的思考方式計算生物學(xué)改變著生物學(xué)家的思考方式最典型的案例：人類的基因工程----耗時10年，耗資數(shù)百億美元。散彈槍算法提出來后，用于基因測序----耗時幾天，耗資千把美元就能測一個基因。（因為大量的繁雜的工作由計算機完成，大大解放了生物學(xué)家，從而改變著生物學(xué)家的思考方式）數(shù)學(xué)機械化改變著數(shù)學(xué)家的思考方式數(shù)學(xué)機械化，就是刻板化和規(guī)格化。---吳方法（吳文?。?shù)學(xué)問題的機械化，就是要求在運算或證明過程中，每前進一步之后，都有一個確定的、必須選擇的下一步，這樣沿著一條有規(guī)律的、刻板的道路，一直達到結(jié)論。吳文俊-中科院資深院士吳先生創(chuàng)立了初等幾何定理證明的機械化方法，國際上稱“吳方法”，首次實現(xiàn)了高效的幾何定理的機器證明。計算博弈理論改變著經(jīng)濟學(xué)家思考方式博弈論指的是研究人與人之間行為互動的一般理論。所謂社會，就是互動。1943年，馮?諾依曼《博弈論和經(jīng)濟行為》著作首次介紹了博弈論。博弈論：兩人以上參與，雙方通過不同策略相互競爭的游戲。博弈：一方采用的策略會對另一方的行為產(chǎn)生影響。計算思想在諾貝獎獲獎理論中占到70%以上的比例。社會計算改變社會學(xué)家的思考方式根據(jù)社會科學(xué)理論，以計算技術(shù)為工具，可以：研究人類社會的組成、關(guān)系、結(jié)構(gòu)、層次、行為、運動等問題；研究社會媒體，促進社會人群的交流與合作。一、計算改變了什么計算改變了工作方式數(shù)字化會議數(shù)字化醫(yī)療數(shù)字化教學(xué)數(shù)字化制造數(shù)字化會議數(shù)字化醫(yī)療數(shù)字化教學(xué)數(shù)字化制造美國學(xué)者尼葛洛龐帝在其1996年出版的《數(shù)字化生存》一書中提出的，按照他的解釋，計算不再只與計算機有關(guān)，它決定我們的生存。13尼葛洛龐帝（Negroponte）為美國麻省理工學(xué)院教授及媒體實驗室的創(chuàng)辦人。西方媒體推崇他為電腦和傳播科技領(lǐng)域最具影響力的大師之一，1996年7月被《時代》周刊列為當(dāng)代最重要的未來學(xué)家之一。計算改變了世界二、什么是計算計算的定義：計算是指運用事先規(guī)定的規(guī)則，將一組數(shù)值變換為另一(所需的)數(shù)值的過程。對某一類問題，如能找到一組確定的規(guī)則，當(dāng)給出這類問題中的任一具體問題后，按規(guī)則可以完全機械地在有限步內(nèi)求出結(jié)果，則說這類問題是可計算的。這種規(guī)則就是算法。猜數(shù)游戲：有自然數(shù)1--1000，隨機選取其中的一個數(shù)，請大家猜數(shù)?；卮?0次是與否，就可以猜出該數(shù)字。開始游戲?qū)嶋H問題設(shè)計算法編程實現(xiàn)二分查找法3.計算思維的特征計算工具與思維方式的相互影響家迪科斯徹：我們使用的工具影響著我們的思維方式和思維習(xí)慣，從而也將深刻地影響著我們的思維能力。計算思維是各個專業(yè)求解問題的基本途徑。3.計算思維的特征計算思維的定義“計算思維”是美國卡內(nèi)基梅隆大學(xué)周以真教授提出的一種理論。周以真認為：計算思維是運用計算機科學(xué)的基礎(chǔ)概念去求解問題、設(shè)計系統(tǒng)和理解人類行為，它涵蓋了計算機科學(xué)的一系列思維活動。周以真（英文名JeannetteM.Wing，），美國計算機科學(xué)家?？▋?nèi)基-梅隆大學(xué)教授。美國國家自然基金會計算與信息科學(xué)工程部助理部長。ACM和IEEE會士。

問題求解中的計算思維系統(tǒng)設(shè)計問題求解人類行為理解建立問題模型選擇算法編程實現(xiàn)有一座城市需要鋪路，不僅每棟房子都能沿著鋪好的道路到達其他所有的房子，而且用的石磚最少。設(shè)有三棟房子和三條路，哪些路是必須要鋪上石磚的？鋪路問題如果是5棟房子？12345B3C3E1D3A122問題建模圖論中最小路徑算法警察抓小偷警察局抓了a，b，c，d四名偷竊嫌疑犯，其中只有一人是小偷，審訊記錄如下：A說：我不是小偷B說：c是小偷C說：小偷肯定是dD說：c在冤枉人四個人中，三個人說的是真話，一個人說的是假話，請問誰是小偷？問題分析1依次假設(shè)每個人是小偷的情況一一代入四句供詞2依次檢驗“四個人中三個人說真話，一個人說假話”是否成立3如果成立，小偷找到數(shù)學(xué)建模將a,b,c,d四個人進行編號為1,2,3,4。用變量x存放小偷的編號。依次將x=1,x=2,x=3,x=4代入問題系統(tǒng)，檢驗“三真一假”是否成立。計算1A說：我不是小偷2B說：c是小偷3C說：小偷肯定是d4D說：c在冤枉人5三真一假1X≠11or02X=31or03X=41or04X≠41or053編程實現(xiàn)Forx=1to4If(x<>1+(x=3)+(x=4)+(x<>4)=3)thenPrintxNextx百元買白雞公雞每只5元，母雞每只3元，小雞一元3只，一百元買一百只雞，問有幾種買法？問題分析：X+Y+Z=1005X+3Y+Z/3=100編程計算思維能夠反映人類思維活動，高效執(zhí)行。For

x=1to100Fory=1to100Z=100-x-yIf5*x+3*y+z/3=100thenPrintx,y,zEndifNextforNextfor計算機解題方法計算機解決問題步驟：理解問題，尋找解決問題的條件；從問題抽象出適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計解決這個數(shù)學(xué)模型的算法；按照算法編寫程序，并調(diào)試、測試、運行程序，得到最終解答。問題發(fā)現(xiàn)問題分析問題預(yù)見問題解決問題系統(tǒng)設(shè)計中的計算思維將系統(tǒng)中的變換過程映射為符號變換——形式化，然后就可以用計算機進行處理。系統(tǒng)設(shè)計問題求解人類行為理解重要理論計算思維的本質(zhì)：抽象、自動化（程序、算法）計算思維能力：建立起利用計算機技術(shù)解決問題的思路，并理解問題的可求解性。問題抽象、模型建立、算法設(shè)計、實現(xiàn)抽象自動化囚徒困境——博弈策略建模囚徒困境問題描述警方逮捕了A、B兩名嫌疑犯，但沒有足夠證據(jù)指控二人有罪。于是警方分開囚禁嫌疑犯，并向雙方提供以下相同的選擇（如表所示）：（1）如果一人認罪并檢控對方（背叛），而對方保持沉默，則此人將獲釋，沉默者將判監(jiān)禁10年。（2）如果二人都保持沉默（合作），則二人同樣判監(jiān)1年。（3）如果二人都互相檢舉（背叛），則二人同樣判監(jiān)8年。策略A沉默（合作）A認罪（背叛）B沉默（合作）二人同服刑1年A即時獲釋；B服刑10年B認罪（背叛）A服刑10年；B即時獲釋A和B二人同服刑8年囚徒困境——博弈策略建模囚徒的策略選擇困境兩名囚徒的選擇：（1）若對方沉默，背叛會讓我獲釋，所以我會選擇背叛。（2）若對方背叛我，我也要指控對方才能得到較低刑期，所以選擇背叛。結(jié)果：兩人都選擇背叛，結(jié)果二人服刑8年。如果兩個囚徒合作保持沉默，總體利益會更高。而兩個囚徒追求個人利益，選擇背叛時，總體利益較低。這就是困境所在。囚徒困境——博弈策略建模囚徒困境的數(shù)學(xué)建模（1）策略的符號化將囚徒各種選擇獲得的收益和支付轉(zhuǎn)換為數(shù)值，獲得表所示符號表。符號分數(shù)英文中文說明T5Temptation背叛收益單獨背叛成功所得R3Reward合作報酬共同合作所得P1Punishment背叛懲罰共同背叛所得S0Suckers受騙支付被單獨背叛所獲囚徒困境——博弈策略建模（2）建立收益和支付矩陣根據(jù)以下規(guī)則確定博弈雙方的收益和支付：一人背叛，一人合作時，背叛者得5分（背叛收益），合作者得0分（受騙支付）；二人都合作時，雙方各得3分（合作報酬）；二人都背叛時，各得1分（背叛懲罰）。從表可見：5>3>1>0，得出：T>R>P>S。囚徒的收益和支付矩陣以符號表示的策略策略A合作A背叛策略A合作A背叛B合作A=3，B=3A=5，B=0B合作R，RT，SB背叛A=0，B=5A=1，B=1B背叛S，TP，P符號分數(shù)T5R3P1S0囚徒困境——博弈策略建模（3）建立數(shù)學(xué)模型A=R，B=R時，A=3，B=3；A=T，B=S時，A=5，B=0；A=S，B=T時，A=0，B=5；A=P，B=P時，A=1，B=1。囚徒困境——博弈策略建模【案例】生活中的“囚徒困境”現(xiàn)象。幼兒園小朋友互相分享玩具（給他玩，不給他玩）；夫妻雙方對家庭的態(tài)度（忠誠，背叛）；公共衛(wèi)生的維持（不扔垃圾，亂扔垃圾）；老板與下屬的關(guān)系（信任，不信任）；商場上的君子協(xié)定（不違約，違約）；競爭對手的價格戰(zhàn)（不降價，降價）；國家之間的對抗（和平，戰(zhàn)爭）等。雖然括號內(nèi)的前者選擇是大家想要達到的目標，但自私的結(jié)果往往是大家要接受后者。囚徒困境——博弈策略建模石頭剪刀布游戲的博弈模型石頭剪刀布是一種相互制約的多元博弈游戲，它是最平衡的游戲。石頭剪刀布不具備數(shù)學(xué)上的傳遞性（a>b，b>c時，則a>c）。石頭剪刀布游戲規(guī)則絕對平衡，簡單明了，沒有任何規(guī)則漏洞。游戲過程充滿了“心理博弈”，單次輸贏取決于運氣，多次比賽的話，贏家一定是個心理博弈的高手。對石頭剪刀布游戲建立數(shù)學(xué)模型。如表3-4所示。博弈矩陣乙石頭剪刀布甲石頭01-1剪刀-101布1-10囚徒困境——博弈策略建?！景咐刻锛少愸R的博弈。博弈矩陣齊王田忌勝者第1場上等馬下等馬齊王第2場中等馬上等馬田忌第3場下等馬中等馬田忌人類行為理解中的計算思維計算思維不僅能夠反映人類思維活動，還能夠通過計算手段來研究人類的行為。系統(tǒng)設(shè)計問題求解人類行為理解醫(yī)學(xué)中的計算思維計算思維1）多臟器衰竭2）心血管和腦血管同時梗塞3）復(fù)雜疑難癥的治療方案的總體設(shè)計計算思維（構(gòu)造思維）的培養(yǎng)，將有助于臨床醫(yī)生提出“整體構(gòu)架設(shè)計解決方案”的治療方案。計算思維的特性1概念化，不是程序化。抽象多層次思維計算機科學(xué)不是計算機編程。像計算機科學(xué)家那樣去思維意味著遠遠不止能為計算機編程。它要求能夠在抽象的多個層次上思維。計算思維的特性2基礎(chǔ)的，不是機械的技能。現(xiàn)代社會每個人都必須掌握的技能基礎(chǔ)的技能是每一個人為了在現(xiàn)代社會中發(fā)揮職能所必須掌握的。生搬硬套之機械的技能意味著機械的重復(fù)。計算思維的特性3人的，不是計算機的思維。人類賦予計算機以激情創(chuàng)造性的使用計算機計算思維是人類求解問題的一條途徑，人類聰穎且富有想象力，人類賦予計算機以激情。配置了計算設(shè)備，就能用自己的智慧去解決那些計算時代之前不敢嘗試的問題。計算思維的特性4數(shù)學(xué)和工程思維的互補與融合。計算機科學(xué)在本質(zhì)上源自數(shù)學(xué)思維，構(gòu)建虛擬世界的自由使我們能夠超越物理世界去打造各種系統(tǒng)。計算思維的特性5是思想，不是人造品。面向所有的人，所有地方不只是我們生產(chǎn)的軟件、硬件等人造品