第一講 計(jì)算思維概述

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

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

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