第1章-計(jì)算機(jī)與計(jì)算思維

1、1,大學(xué)計(jì)算機(jī)基礎(chǔ)上課信息,第一大班：經(jīng)濟(jì)11~14 講課：周一 7、8節(jié) 周四1、2節(jié) 上機(jī)：周四 9、10節(jié)（19：00~21：00）第二大班: 經(jīng)濟(jì)15~18 講課：周一5、6節(jié) 周四5、6節(jié) 上機(jī)：周四7、8節(jié),機(jī)器安排,2,,教師： 賈應(yīng)智 E-Mail: ying.zhi.jia@stu.xjtu.edu.cn交作業(yè)服務(wù)器：ftp://202.117.207

2、.198 用戶(hù)名：student 口令：ctec,3,第1章 計(jì)算機(jī)與計(jì)算思維,《大學(xué)計(jì)算機(jī)基礎(chǔ)》,4,本章提要,計(jì)算意義與計(jì)算思維計(jì)算科學(xué)方法概論可計(jì)算性與計(jì)算過(guò)程計(jì)算思維的跨學(xué)科交融計(jì)算機(jī)學(xué)科的核心概念與問(wèn)題求解,計(jì)算思維的技能科學(xué)思維邏輯思維算法思維效率思維創(chuàng)新思維倫理思維,5,計(jì)算思維（Computational thinking,CT）由美國(guó) Carnegie Mellon 大學(xué)計(jì)算機(jī)科學(xué)教授周以真女

3、士于2006年提出她認(rèn)為，計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問(wèn)題求解、系統(tǒng)設(shè)計(jì)、以及人類(lèi)行為理解等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)計(jì)算思維代表著一種普遍的態(tài)度和一類(lèi)普適的技能，每一個(gè)人都應(yīng)熱心于它的學(xué)習(xí)和運(yùn)用,6,是概念化的抽象思維而不只是程序設(shè)計(jì)是基本的而不是死記硬背的技能是人的而不是計(jì)算機(jī)的思維方式是數(shù)學(xué)和工程思維的互補(bǔ)與融合是思想而不是人造品面向所有的人和所有地方關(guān)注依舊亟待理解和解決的智力上極有挑戰(zhàn)性并且

4、引人入勝的科學(xué)問(wèn)題,計(jì)算思維的特征,7,Computation 是可用數(shù)學(xué)表示的任何形式的信息處理的概念，它包括簡(jiǎn)單的計(jì)算和人的思維（human thinking）所以，計(jì)算思維無(wú)論是由人或機(jī)器執(zhí)行，都是建立在計(jì)算處理的能力和限制之上的Computing 意味著任何面向目標(biāo)的需要、受益于和創(chuàng)造計(jì)算機(jī)的活動(dòng),包括用于廣泛目的的軟件和硬件系統(tǒng)的設(shè)計(jì)、建造；各種信息的處理、規(guī)范和管理；用計(jì)算機(jī)開(kāi)展的科研活動(dòng)；使計(jì)算機(jī)系統(tǒng)具有智能行

5、為；創(chuàng)建和使用通信和娛樂(lè)媒體；尋找和收集與任何目的有關(guān)的信息等,Computation vs. Computing,8,本章涉及的“計(jì)算”包含了computation和computing的內(nèi)容對(duì)于計(jì)算機(jī)基礎(chǔ)學(xué)習(xí)而言，了解計(jì)算思維的宏觀特性，對(duì)于個(gè)人專(zhuān)業(yè)發(fā)展具有重要意義,計(jì)算思維的宏觀結(jié)構(gòu),9,通過(guò)網(wǎng)絡(luò)可以求解的問(wèn)題信息查詢(xún)交流與溝通資源的發(fā)布與共享,計(jì)算思維的網(wǎng)絡(luò)化,10,移動(dòng)通信與地理信息系統(tǒng)的結(jié)合，產(chǎn)生了新的計(jì)算模式：與

6、位置有關(guān)的計(jì)算利用GPS定位，可以找到周邊的服務(wù)設(shè)施通過(guò)移動(dòng)信號(hào)基站，發(fā)現(xiàn)客戶(hù)所需要的服務(wù)：天氣、旅游、購(gòu)物等,計(jì)算思維的移動(dòng)化,移動(dòng)通訊設(shè)備的廣泛應(yīng)用，催生了諸多新型的商業(yè)應(yīng)用模式,11,計(jì)算思維的信息化促進(jìn)了政務(wù)、商務(wù)、教育和社會(huì)的信息化小學(xué)校園的門(mén)禁系統(tǒng)與移動(dòng)通信結(jié)合，產(chǎn)生學(xué)生在校、離校信息服務(wù)信用卡消費(fèi)信息與移動(dòng)通信和因特網(wǎng)結(jié)合，產(chǎn)生實(shí)時(shí)消費(fèi)報(bào)告和無(wú)紙化賬單報(bào)告校園一卡通,計(jì)算思維的信息化,12,中國(guó)經(jīng)濟(jì)發(fā)展正在向服務(wù)

7、型經(jīng)濟(jì)轉(zhuǎn)型計(jì)算機(jī)科學(xué)與技術(shù)及信息技術(shù)則是現(xiàn)代服務(wù)型經(jīng)濟(jì)發(fā)展的根本保障Software as a service (SaaS)和服務(wù)計(jì)算（service computing）正在引起關(guān)注,計(jì)算思維的服務(wù)化,云計(jì)算模型示意,13,計(jì)算思維的智能化促進(jìn)了交通管理的智能化、業(yè)務(wù)流程的智能化、電子服務(wù)的智能化電子服務(wù)和社會(huì)生活的智能化的需求反過(guò)來(lái)促進(jìn)計(jì)算思維智能化的進(jìn)一步發(fā)展,計(jì)算思維的智能化,智能化能夠緩解交通擁堵？,14,計(jì)算思維從計(jì)算

8、理論、計(jì)算技術(shù)、計(jì)算工程、計(jì)算工具、計(jì)算服務(wù)和計(jì)算應(yīng)用的轉(zhuǎn)化就是計(jì)算思維的工程化計(jì)算思維的工程化促進(jìn)了諸如計(jì)算機(jī)、手機(jī)、平板電腦等計(jì)算工具和系統(tǒng)的發(fā)展，后者反過(guò)來(lái)促進(jìn)了計(jì)算思維的工程化,計(jì)算思維的工程化,15,計(jì)算思維的人性化促進(jìn)了人－機(jī)交互的人性化、計(jì)算工具的人性化和社會(huì)的進(jìn)步計(jì)算和信息技術(shù)對(duì)人類(lèi)產(chǎn)生的負(fù)面影響同樣不可小視信息社會(huì)中的“宅人”數(shù)碼相機(jī) vs.膠片工業(yè)數(shù)字印刷 vs. 鉛字印刷,計(jì)算思維的人性化,人性化設(shè)計(jì) 筆

9、記本電腦支架,16,層次化源于社會(huì)組織和分工計(jì)算思維的層次包括計(jì)算理論思維、計(jì)算技術(shù)思維、計(jì)算工程思維、計(jì)算工具思維、計(jì)算服務(wù)思維和計(jì)算應(yīng)用思維六個(gè)層次思維組成 它們分別對(duì)應(yīng)計(jì)算理論、計(jì)算技術(shù)、計(jì)算工程、計(jì)算工具、計(jì)算服務(wù)和計(jì)算應(yīng)用每個(gè)層次上的思維都至少包含許多不同的思維過(guò)程、思維模式和思維規(guī)律,計(jì)算思維的層次化,17,結(jié)構(gòu)化源于軟件開(kāi)發(fā)的結(jié)構(gòu)化系統(tǒng)分析、結(jié)構(gòu)化設(shè)計(jì)和結(jié)構(gòu)化程序設(shè)計(jì)重要的案例計(jì)算機(jī)體系結(jié)構(gòu)多核CPUGPGP

10、U（通用圖形處理器）網(wǎng)絡(luò)體系結(jié)構(gòu)ISO/OSI 參考模型TCP/IP模型,計(jì)算思維的結(jié)構(gòu)化,Intel Core 2 Duo Processor,18,計(jì)算思維源于并服務(wù)于由計(jì)算理論、計(jì)算技術(shù)、計(jì)算工程、計(jì)算工具、計(jì)算服務(wù)和計(jì)算應(yīng)用構(gòu)成的計(jì)算思維生存周期這一生存周期以計(jì)算理論為始點(diǎn)，以計(jì)算應(yīng)用為終點(diǎn),計(jì)算思維的過(guò)程化,19,計(jì)算意義與計(jì)算思維小結(jié),“計(jì)算思維”是面向所有的人，所有學(xué)科的，應(yīng)當(dāng)具有普適性，但這種普適的內(nèi)部是有差異的

11、計(jì)算機(jī)科學(xué)是新興學(xué)科，其內(nèi)容日新月異，以及人的智力水于有高低之分，人們已掌握的計(jì)算機(jī)知識(shí)各有差異，不同人的計(jì)算思維具有很大差別，因此計(jì)算思維具有層次性只要具有思維品質(zhì)中的獨(dú)創(chuàng)性，就能創(chuàng)造性地解決問(wèn)題不同層次上的計(jì)算機(jī)思維均可得到同質(zhì)性的發(fā)展,20,科學(xué)界一般認(rèn)為，科學(xué)方法分為理論、實(shí)驗(yàn)和計(jì)算三大類(lèi)與三大科學(xué)方法相對(duì)的是三大科學(xué)思維，理論思維以數(shù)學(xué)為基礎(chǔ)，實(shí)驗(yàn)思維以物理等學(xué)科為基礎(chǔ)，計(jì)算思維以計(jì)算機(jī)科學(xué)為基礎(chǔ),21,理論源于數(shù)學(xué)，

12、理論思維支撐著所有的學(xué)科領(lǐng)域。正如數(shù)學(xué)一樣，定義是理論思維的靈魂，定理和證明則是它的精髓公理化方法是最重要的理論思維方法，科學(xué)界一般認(rèn)為，公理化方法是世界科學(xué)技術(shù)革命推動(dòng)的源頭。,理論思維,22,實(shí)驗(yàn)思維方法可以分為以下三個(gè)步驟：①先提取出從現(xiàn)象中獲得的直觀認(rèn)識(shí)的主要部分，用最簡(jiǎn)單的數(shù)學(xué)形式表示出來(lái)，以建立量的概念； ②再由此試用數(shù)學(xué)方法導(dǎo)出另一易于實(shí)驗(yàn)證實(shí)的數(shù)量關(guān)系；③然后通過(guò)實(shí)驗(yàn)證實(shí)這種數(shù)量關(guān)系對(duì)于實(shí)驗(yàn)思維來(lái)說(shuō)，最為重要的

13、事情就是設(shè)計(jì)、制造實(shí)驗(yàn)儀器和追求理想的實(shí)驗(yàn)環(huán)境,實(shí)驗(yàn)思維,23,計(jì)算思維最根本的內(nèi)容，即其本質(zhì)是抽象（Abstraction）與自動(dòng)化（Automation）計(jì)算思維中的抽象完全超越物理的時(shí)空觀，并完全用符號(hào)來(lái)表示，其中，數(shù)字抽象只是其中的一類(lèi)特例計(jì)算思維中的抽象最終是要能夠利用機(jī)器的一步步自動(dòng)執(zhí)行。為了確保機(jī)器的自動(dòng)化，就需要在抽象的過(guò)程中進(jìn)行精確和嚴(yán)格的符號(hào)標(biāo)記和建模還要求計(jì)算機(jī)系統(tǒng)或軟件系統(tǒng)生產(chǎn)廠家能夠向公眾提供各種不同抽象

14、層次之間的翻譯工具,計(jì)算思維,24,計(jì)算機(jī)科學(xué)在本質(zhì)上源自數(shù)學(xué)思維，因?yàn)橄袼械目茖W(xué)一樣，它的形式化基礎(chǔ)建筑于數(shù)學(xué)之上計(jì)算機(jī)科學(xué)又從本質(zhì)上源自工程思維，因?yàn)槲覀兘ㄔ斓氖悄軌蚺c實(shí)際世界互動(dòng)的系統(tǒng)，基本計(jì)算設(shè)備的限制迫使計(jì)算機(jī)科學(xué)家必須計(jì)算性地思考，而不能只是數(shù)學(xué)性地思考構(gòu)建虛擬世界的自由使我們能夠超越物理世界的各種系統(tǒng)數(shù)學(xué)和工程思維的互補(bǔ)與融合很好的體現(xiàn)在抽象、理論和設(shè)計(jì)三個(gè)學(xué)科形態(tài)（或過(guò)程）上,計(jì)算機(jī)科學(xué)的“源”與“流”,25,計(jì)

15、算理論是研究使用計(jì)算機(jī)解決計(jì)算問(wèn)題的數(shù)學(xué)理論有三個(gè)核心領(lǐng)域：自動(dòng)機(jī)理論、可計(jì)算性理論和計(jì)算的復(fù)雜性理論自動(dòng)機(jī)將離散數(shù)學(xué)系統(tǒng)的構(gòu)造，作用和關(guān)系作為研究對(duì)象的數(shù)學(xué)理論（描述通用計(jì)算機(jī)計(jì)算能力的圖靈機(jī)模型）可計(jì)算性理論的中心問(wèn)題是建立計(jì)算的數(shù)學(xué)模型，進(jìn)而研究哪些是可計(jì)算的，哪些是不可計(jì)算的計(jì)算的復(fù)雜性理論研究算法的時(shí)間復(fù)雜性和空間復(fù)雜性,26,計(jì)算機(jī)學(xué)科的方法論有三個(gè)過(guò)程：抽象、理論和自動(dòng)化設(shè)計(jì)及實(shí)現(xiàn)最根本的問(wèn)題在于：?jiǎn)栴}如何進(jìn)行描

16、述？哪些部分能夠被自動(dòng)化？如何進(jìn)行自動(dòng)化描述？建立物理符號(hào)系統(tǒng)并對(duì)其實(shí)施等價(jià)變換是計(jì)算機(jī)學(xué)科進(jìn)行問(wèn)題描述和求解的重要手段?！翱尚行浴彼蟮摹靶问交奔捌洹半x散特征”使得數(shù)學(xué)成為重要的工具而計(jì)算模型無(wú)論從方法還是工具等方面，都表現(xiàn)出它在計(jì)算機(jī)上科學(xué)中的重要作用（參見(jiàn)1.3節(jié)）,計(jì)算機(jī)學(xué)科的方法論的三個(gè)過(guò)程,27,科學(xué)：關(guān)于自然、社會(huì)和思維的發(fā)展與變化規(guī)律的知識(shí)體系，其核心是發(fā)現(xiàn)技術(shù)：根據(jù)實(shí)踐經(jīng)驗(yàn)和科學(xué)原理而發(fā)展形成的各種工藝操作

17、方法、技能和技巧，其核心是發(fā)明工程：將科學(xué)原理應(yīng)用到生產(chǎn)實(shí)踐中，是某種形式的科學(xué)應(yīng)用，其核心是建造,現(xiàn)代科技工作者的素養(yǎng),我們所使用的工具影響著我們的思維方式和思維習(xí)慣，從而也將深刻地影響著我們的思維能力 Edsger Dijkstra,28,霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的字母）進(jìn)行編碼變長(zhǎng)編碼表通過(guò)評(píng)估來(lái)源符號(hào)出現(xiàn)概率的方法得到的，概率高的字母用較短的編碼，出現(xiàn)概率低的則用較

18、長(zhǎng)的編碼使編碼之后的字符串的平均長(zhǎng)度、期望值降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的,四個(gè)狀態(tài)的霍夫曼編碼過(guò)程,29,設(shè)信號(hào)源為X={ 、a、e、I、m、t、c、h、r }。對(duì)應(yīng)的概率為 p= { 0.22、0.22、0.14、0.07、0.07、0.07、0.07、0.07、0.07 },試給出該信源的霍夫曼編碼方案。解： 若傳送一個(gè)串字符串“I am a teacher”，共14個(gè)字符。若用ASCII傳送，每個(gè)字符8位，共

19、需112位。該字符串中有9個(gè)不同的符號(hào)，至少需要4位二進(jìn)制才能表示，這樣傳送該字符串也要56位。若用計(jì)算的Huffman編碼，只需要42位。,霍夫曼編碼舉例,︺,30,霍夫曼編碼過(guò)程,可以得到：　a的編碼00 e的編碼 111 I的編碼1101 m的編碼1100 t的編碼1011 c的編碼 1010 h的編碼1001 r的編碼 1000原字符串（二進(jìn)制）長(zhǎng)度：= 11

20、2（14×8）位Huffman編碼長(zhǎng)度： = 42位 （01 00 111 1101 1100 1011 1010 1001 1000）,,31,在數(shù)論中，反運(yùn)算的問(wèn)題往往是極難求解的，或者說(shuō)極難計(jì)算的離散對(duì)數(shù)和整數(shù)因式分解問(wèn)題就屬于困難的計(jì)算數(shù)論問(wèn)題如果給出兩個(gè)素?cái)?shù)p和q，要求兩者的乘積，即使p和q很大，那計(jì)算它們的乘積仍然是可行的但反過(guò)來(lái)，給出N，要求p和q就極為困難了

21、利用反計(jì)算的難度，對(duì)數(shù)據(jù)進(jìn)行加密，是現(xiàn)代密碼學(xué)的基礎(chǔ)計(jì)算機(jī)通訊中的公開(kāi)密鑰加密算法，就是利用了數(shù)論的這個(gè)原理,32,密鑰舉例：,在馬丁?加德納的《數(shù)學(xué)游戲》一書(shū)中，報(bào)告了1977年由RSA（Rivest,shamir和Adleman）懸賞100美元求解對(duì)一個(gè)密鑰的破解問(wèn)題。給出一對(duì)整數(shù)（e,N）作為公開(kāi)鑰，e=9007，N是一個(gè)隨機(jī)的129位數(shù)11438162575788886766923577997614661201021829

22、67212423625625618429357069352457338978305971235639587058989075147599290026878543541經(jīng)過(guò)它加密后得到的密文C是96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013399055182994515578

23、15154問(wèn)C加密前的明文是什么？,33,問(wèn)題結(jié)論,這個(gè)問(wèn)題在1994年4月2日，即相隔了17年之后由迪里克?阿特金斯（Derek Atkins），邁克爾?克拉弗（Michael Graff）和阿爾金?K?廉斯特拉（Arjen K?Lenstra），帕爾?雷蘭德（Panl Leyland）解出，他們對(duì)上述的N成功地進(jìn)行因式分解，它的兩素因子是： 3490529510847650949147849619903898133417

24、764638493387843990820577 和 3276913299326670954996198819083446143177642967991941539798288533在得到了p和q后，從密文計(jì)算明文的障礙就被克服了，這個(gè)明文是20080500130070903002315180419000118050019172105011309190800151919090618010705它是：THE MAGIC

25、 WORDS ARE SQUEAMISH OSSIFRAGE（這些魔術(shù)般的詞是魚(yú)鷹。）,34,生物信息學(xué)是一門(mén)新興交叉學(xué)科，其發(fā)展的標(biāo)志便是大量生命科學(xué)數(shù)據(jù)的快速積累以及為處理這些復(fù)雜數(shù)據(jù)而設(shè)計(jì)的新算法的不斷涌現(xiàn)最常用的數(shù)據(jù)結(jié)構(gòu)主要包括四種類(lèi)型：1) 字符串結(jié)構(gòu)，表示DNA，RNA和氨基酸序列；2) 樹(shù)結(jié)構(gòu)，表示各種生物有機(jī)體的系統(tǒng)進(jìn)化樹(shù)；3) 三維空間點(diǎn)和連接集合結(jié)構(gòu)，表示蛋白質(zhì)的三維結(jié)構(gòu)；4) 圖結(jié)構(gòu)，表示代謝和信號(hào)傳導(dǎo)通

26、路,35,計(jì)算科學(xué)中許多仿生計(jì)算算法都是受到生物學(xué)中群體行為的啟發(fā)而模仿設(shè)計(jì)出來(lái)的例如，計(jì)算科學(xué)中的神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、演化算法、蟻群算法、協(xié)同進(jìn)化算法、粒子群算法、生物免疫算法以及突現(xiàn)計(jì)算算法等計(jì)算機(jī)病毒的概念與行為也是模仿自然界中的生物病毒行為提出來(lái)的，同樣具有潛伏性、流行性、傳播性、自復(fù)制性、變異性和適應(yīng)性等特點(diǎn),,,36,計(jì)算機(jī)學(xué)科的核心概念是ACM/IEEE-CS制定的CC1991報(bào)告首次提出的，是具有普遍性、持久性的

27、重要思想、原則和方法，核心概念具有如下基本特征：（1）在學(xué)科及各分支學(xué)科中普遍出現(xiàn)；（2）在理論、抽象和設(shè)計(jì)的各個(gè)層面上都有很多示例；（3）在理論上具有可延展和變形的作用，在技術(shù)上有高度的獨(dú)立性,37,通過(guò)將一個(gè)對(duì)象（或事物）與其某種屬性相聯(lián)系，從而使抽象的概念具體化的過(guò)程將一個(gè)進(jìn)程與一個(gè)處理機(jī)、一個(gè)變量與其類(lèi)型或值分別聯(lián)系起來(lái)這種聯(lián)系的建立，實(shí)際上就是建立了某種約束在數(shù)據(jù)庫(kù)中的不同表之間建立“關(guān)系”和參照完整性，就是用約束

28、關(guān)系來(lái)保證數(shù)據(jù)的完整性。,CS核心概念-綁定（Binding）,38,指隨著問(wèn)題規(guī)模的增長(zhǎng)使問(wèn)題的復(fù)雜性呈非線性增加的效應(yīng)這種非線性增加的效應(yīng)是區(qū)分和選擇各種現(xiàn)有方法和技術(shù)的重要因素幾十萬(wàn)考生的高考成績(jī)排序，須認(rèn)真選擇排序算法氣候變暖對(duì)全球經(jīng)濟(jì)的影響，仿真與模擬,CS核心概念-大問(wèn)題的復(fù)雜性（Complexity of Large Problems）,39,對(duì)一個(gè)想法或問(wèn)題進(jìn)行形式化、特征化、可視化思維的方法數(shù)據(jù)流圖和E-R圖

29、等都屬于概念模型，而邏輯理論、開(kāi)關(guān)理論和計(jì)算理論中的模型大都屬于形式模型UML，統(tǒng)一建模語(yǔ)言是軟件工程中的重要工具和方法,CS核心概念-概念和形式模型（Conceptual and Format Models）,40,一致性包括用于形式說(shuō)明的一組公理的一致性、事實(shí)和理論的一致性，以及一種語(yǔ)言或接口設(shè)計(jì)的內(nèi)部一致性例如，由于計(jì)算機(jī)資源的部署原因，服務(wù)器的網(wǎng)絡(luò)地址可能發(fā)生變化，但由于用戶(hù)訪問(wèn)的是域名地址，只要保證正確的映射關(guān)系，網(wǎng)絡(luò)地址

30、的變化不會(huì)影響用戶(hù)訪問(wèn)，這就是一致性在發(fā)揮作用,CS核心概念-一致性和完備性（Consistency and Completeness），,41,關(guān)于時(shí)間、空間、人力和財(cái)力等資源消耗的度量在計(jì)算機(jī)軟硬件的設(shè)計(jì)中，要充分考慮某種預(yù)期果達(dá)到的效率，以及一個(gè)給定的實(shí)現(xiàn)過(guò)程較之替代的實(shí)現(xiàn)過(guò)程的效率例如，原用于圖形顯示的圖形處理器（GPU），現(xiàn)廣泛應(yīng)用于數(shù)據(jù)密集型的高性能計(jì)算場(chǎng)合（GPGPU，通用圖形處理器），而這種應(yīng)用可以大大節(jié)省高性能處理

31、中的成本和能源消耗,CS核心概念-效率（Efficiency）,42,指系統(tǒng)的結(jié)構(gòu)、狀態(tài)、特征、行為和功能等隨著時(shí)間的推移而發(fā)生的更改從CLI（命令行界面）到GUI（圖形用戶(hù)界面），是計(jì)算機(jī)應(yīng)用方式演化的里程碑；而瀏覽器的出現(xiàn)，結(jié)束了桌面系統(tǒng)一統(tǒng)天下的局面最容易使用戶(hù)受到困擾的是軟件無(wú)止境的演化，從而預(yù)見(jiàn)和適應(yīng)計(jì)算機(jī)系統(tǒng)的演化,CS核心概念-演化（Evolution）,43,所謂科學(xué)思維最基本的內(nèi)容是沒(méi)有證據(jù)就不要求急于下結(jié)論：遵

32、循科學(xué)的方法來(lái)建立新的知識(shí)無(wú)論這些知識(shí)只是對(duì)日常生活中的現(xiàn)象，或是學(xué)科的前沿發(fā)現(xiàn),44,邏輯思維是從已知的些微（但非常重要的）信息中推導(dǎo)出盡可能多的信息，而不要輕易下結(jié)論新的信息收集必須按照確定的規(guī)程，你不能僅僅因?yàn)樾疫\(yùn)的而走對(duì)路,計(jì)算思維的技能-邏輯思維,數(shù)獨(dú)問(wèn)題求解,45,有些問(wèn)題是一次性的，但解決這些問(wèn)題的方案，則可以不斷發(fā)展在同類(lèi)問(wèn)題一再出現(xiàn)時(shí)，算法思維就可以介入。沒(méi)有必要重新每次從頭思考，而是采用每次都行之有效的解決方案

33、囚徒困境（prisoner's dilemma）是博弈論的非零和博弈中具代表性的例子，反映個(gè)人最佳選擇并非團(tuán)體最佳選擇雖然困境本身只屬模型性質(zhì)，但現(xiàn)實(shí)中的價(jià)格競(jìng)爭(zhēng)、環(huán)境保護(hù)等方面，也會(huì)頻繁出現(xiàn)類(lèi)似情況,計(jì)算思維的技能-算法思維,46,算法思維案例：囚徒困境,兩個(gè)罪犯準(zhǔn)備搶劫銀行，但作案前失手被擒。警方懷疑他們意圖搶劫，苦干證據(jù)只夠起訴非法持有槍械，于是將其分開(kāi)審訊。 為離間雙方，警方分別對(duì)兩人說(shuō)：若都保持沉默(“合作”)

34、，則一同入獄1年；若是互相檢舉(互相“背叛”)，則一同入獄5年若你認(rèn)罪并檢舉對(duì)方(“背叛”對(duì)方)，他保持沉默，他入人獄10年，你可以獲釋(反之亦然) 結(jié)果兩人都選擇了招供（最希望的結(jié)果）。,47,情況分析,孤立地看，這是最符合個(gè)體利益的“理性”選擇。以A為例：若B招供，A自己招供獲刑5年，不招供獲刑10年；若B不招供，自己招供可以免刑，不招供獲刑1年。兩種情況下，選擇招供都更有利，事實(shí)上卻比兩人都拒不招供的結(jié)果糟。 由囚徒困境

35、可知，公共生活中，如果每個(gè)人都從眼前利益、個(gè)人利益出發(fā)，結(jié)果會(huì)對(duì)整體的利益(間接對(duì)個(gè)人的利益)造成傷害。,48,為解決“囚徒困境”難題，美國(guó)曾組織競(jìng)賽，要求參賽者根據(jù)“重復(fù)囚徒困境”(雙方不止一次相遇，“背叛”可能在以后遭到報(bào)復(fù))來(lái)設(shè)計(jì)程序。 將程序輸入計(jì)算機(jī)反復(fù)互相博弈，以最終得分評(píng)估優(yōu)劣(雙方合作各得3分；雙方背叛各得1分；一方合作一方背叛，合作方得0分，背叛方得5分)；有些程序采用“隨機(jī)”對(duì)策；有些采用“永遠(yuǎn)背叛”對(duì)策；有

36、些采用“永遠(yuǎn)合作”對(duì)策； 結(jié)果，加拿大多倫多大學(xué)的阿納托爾·拉帕波特教授的“一報(bào)還一報(bào)”策略?shī)Z得了最高分。,49,我方在第一次相遇時(shí)選擇“合作”，之后就采取對(duì)方上一次的選擇。這意味著： 在對(duì)方每一次背叛后，我方就“以牙還牙”，也背叛一次； 對(duì)方每一次合作后，我方就“以德報(bào)德”一次；《論語(yǔ)·憲問(wèn)》中，有人問(wèn)孔子：“以德報(bào)怨，何如?”孔子反問(wèn)：“何以報(bào)德?以直報(bào)怨，以德報(bào)德。 該策略有別于“善良”的“永遠(yuǎn)合作”

37、或“邪惡”的“永遠(yuǎn)背叛”對(duì)策，及對(duì)方一旦“不忠”，我方就不再給機(jī)會(huì)，長(zhǎng)久對(duì)抗的策略。,50,如果你選擇“永遠(yuǎn)背叛”策略，你或許會(huì)在第一局拿到最高分，但之后的各局可能都只能拿到低分，最后雖然可能“戰(zhàn)勝”不少對(duì)手，但由于總分很低，最終難逃被淘汰出局的命運(yùn)。 所以除非很難與對(duì)方再次相遇，不用擔(dān)心其日后的反應(yīng)，才可選擇對(duì)抗與背叛； 而在長(zhǎng)期互動(dòng)、博弈的關(guān)系中，“一報(bào)還一報(bào)”是最佳策略：它是善意的，從不首先背叛；它不迂腐，不管過(guò)去相處多好，仍

38、然對(duì)背叛有反應(yīng)；它是寬容的，不因一次背叛而選擇玉石俱焚。,51,計(jì)算機(jī)科學(xué)家效率觀念有非常精確的定義，通用的方式是討論如何盡量減少使用的資源來(lái)完成任務(wù)可減少資源各有不同，但最重要的往往是'時(shí)間‘重要的是尋找某種途徑，保證能夠任務(wù)完成而且使用盡可能少的步驟,計(jì)算思維的技能-效率思維,紅綠球的換位游戲，如何使完成步驟最少？,52,計(jì)算機(jī)科學(xué)家是進(jìn)行系統(tǒng)集成的專(zhuān)家不只是應(yīng)用今天的技術(shù)，而且還創(chuàng)造明天的技術(shù)什么是當(dāng)今世界的10名

39、大的創(chuàng)新？互聯(lián)網(wǎng)，手機(jī)，個(gè)人計(jì)算機(jī)，光纖，電子郵件，衛(wèi)星導(dǎo)航系統(tǒng)，記憶存儲(chǔ)磁盤(pán)，數(shù)碼相機(jī)和RFID標(biāo)簽計(jì)算機(jī)科學(xué)家則將它們組合在一起，構(gòu)建新的系統(tǒng)并滿(mǎn)足社會(huì)的需求“需要發(fā)掘用戶(hù)需要但無(wú)從表達(dá)的需求 –喬布斯”—實(shí)際上是創(chuàng)造用戶(hù)的需求,計(jì)算思維的技能-創(chuàng)新思維,53,任何新技術(shù)都是一把雙刃劍+現(xiàn)代計(jì)算機(jī)系統(tǒng)的成是帶來(lái)對(duì)數(shù)字信息進(jìn)行分析、處理和共享的便利-也存在大量負(fù)面的影響例如，如何處理創(chuàng)建電子商務(wù)客戶(hù)聯(lián)機(jī)檔案的便利性與隱私問(wèn)

40、題之間的平衡，是當(dāng)代信息系統(tǒng)引發(fā)的倫理問(wèn)題之一,計(jì)算思維的技能-倫理思維,54,弄清事實(shí)界定沖突或困境并識(shí)別有關(guān)的更高序列上的價(jià)值理念確定利益相關(guān)者理性的選擇解決方案確認(rèn)解決方案可能帶來(lái)的后果,倫理分析過(guò)程,55,計(jì)算思維是在計(jì)算學(xué)科與其他學(xué)科思想方法的交互中發(fā)展的，比如許多算法的思想來(lái)源于人類(lèi)對(duì)特定學(xué)科研究對(duì)象的認(rèn)識(shí)，又反過(guò)來(lái)作用于這些學(xué)科和更多學(xué)科的發(fā)展從計(jì)算思維的內(nèi)涵上講，它闡述計(jì)算的基本思想和方法，究其根源這些思想和方

41、法均來(lái)自人類(lèi)的共同智慧，不但有助于計(jì)算學(xué)科中問(wèn)題的求解，也與人類(lèi)在其他領(lǐng)域工作和生活中解決問(wèn)題的方法相通,本章小結(jié),56,周以真．計(jì)算思維．中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊[J].2007，3(11)．王飛躍．從計(jì)算思維到計(jì)算文化[J]．中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊．2007，3(11)．董榮勝．計(jì)算機(jī)科學(xué)導(dǎo)論——思想與方法[M]．高等教育出版社，2007．董榮勝，古天龍．計(jì)算機(jī)科學(xué)與技術(shù)方法論[M]．人民郵電出版社，2002．張曉如，張?jiān)佘S. 再談?dòng)?jì)

42、算機(jī)思維[J]. 計(jì)算機(jī)教育 2010董榮勝，古天龍．計(jì)算思維與計(jì)算機(jī)方法論[J]．計(jì)算機(jī)科學(xué)，2009，36(1)：1—4．王樹(shù)林，黃德雙，駱嘉偉，“計(jì)算科學(xué)與生命科學(xué)的相互交融與相互啟示，”計(jì)算機(jī)科學(xué)[J]，2008年11月專(zhuān)輯, vol.35, no.11, pp.31-35.孫兆豪, 孫俊卿, 郭喜鳳. 論計(jì)算思維和計(jì)算機(jī)思維 [BS/OL] http://www.gljpkc.com/jsjkxdl/fushe5-2.a