計(jì)算機(jī)與計(jì)算思維

《計(jì)算機(jī)與計(jì)算思維》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)與計(jì)算思維（56頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,*,*,*,大學(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ī)器安排,1,,,教師： 賈應(yīng)智,,,E-Mail: ying.zhi.,,交作業(yè)服務(wù)器：,,,用戶名：student 口令：ctec,2,,第,1,章 計(jì)算機(jī)與計(jì)算思維,《大學(xué)計(jì)算機(jī)基礎(chǔ)》,3,,本章提要,計(jì)算意義與計(jì)算思維,,計(jì)算

2、科學(xué)方法概論,,可計(jì)算性與計(jì)算過(guò)程,,計(jì)算思維的跨學(xué)科交融,,計(jì)算機(jī)學(xué)科的核心概念與問(wèn)題求解,計(jì)算思維的技能,,科學(xué)思維,,邏輯思維,,算法思維,,效率思維,,創(chuàng)新思維,,倫理思維,4,,計(jì)算思維（Computational thinking,CT）由美國(guó) Carnegie Mellon 大學(xué)計(jì)算機(jī)科學(xué)教授周以真女士于2006年提出,,她認(rèn)為，計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行,問(wèn)題求解,、,系統(tǒng)設(shè)計(jì),、以及,人類行為理解,等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列,思維活動(dòng),,計(jì)算思維代表著,一種普遍的態(tài)度,和,一類普適的技能,，每一個(gè)人都應(yīng)熱心于它的學(xué)習(xí)和運(yùn)用,5,,是,概念化的抽象思維而,不只是

3、,程序設(shè)計(jì),,是,基本的而,不是,死記硬背的技能,,是,人的而,不是,計(jì)算機(jī)的思維方式,,是,數(shù)學(xué)和工程思維的互補(bǔ)與融合,,是,思想而,不是,人造品,,面向,所有的人和所有地方,,關(guān)注依舊亟待理解和解決的智力上極有挑戰(zhàn)性并且引人入勝的科學(xué)問(wèn)題,計(jì)算思維,的,特征,6,,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è)

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

5、到周邊的服務(wù)設(shè)施,,通過(guò)移動(dòng)信號(hào)基站，發(fā)現(xiàn)客戶所需要的服務(wù)：天氣、旅游、購(gòu)物等,計(jì)算思維的移動(dòng)化,移動(dòng)通訊設(shè)備的廣泛應(yīng)用，催生了諸多新型的商業(yè)應(yīng)用模式,10,,計(jì)算思維的信息化促進(jìn)了政務(wù)、商務(wù)、教育和社會(huì)的信息化,,小學(xué)校園的門禁系統(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ì)算思維的信息化,11,,中國(guó)經(jīng)濟(jì)發(fā)展正在向服務(wù)型經(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）正在引

6、起關(guān)注,,計(jì)算思維的服務(wù)化,云計(jì)算模型示意,12,,計(jì)算思維的智能化促進(jìn)了交通管理的智能化、業(yè)務(wù)流程的智能化、電子服務(wù)的智能化,,電子服務(wù)和社會(huì)生活的智能化的需求反過(guò)來(lái)促進(jìn)計(jì)算思維智能化的進(jìn)一步發(fā)展,,計(jì)算思維的智能化,智能化能夠緩解交通擁堵？,13,,計(jì)算思維從計(jì)算理論、計(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ì)算思維的工程化,14,,計(jì)算思維的人性化促進(jìn)了人－機(jī)交互的人性化、計(jì)算工具的人性化和社會(huì)的進(jìn)步,,計(jì)算和信息技術(shù)對(duì)人類產(chǎn)生的負(fù)面影響同樣不

7、可小視,,信息社會(huì)中的“,宅人,”,,數(shù)碼相機(jī),vs.,膠片工業(yè),,數(shù)字印刷,vs.,鉛字印刷,計(jì)算思維的人性化,人性化設(shè)計(jì) 筆記本電腦支架,15,,層次化源于社會(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ì)算思維的層次化,16,,結(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),,多核CPU,,GPGPU（通用圖形處

8、理器）,,網(wǎng)絡(luò)體系結(jié)構(gòu),,ISO/OSI 參考模型,,TCP/IP模型,計(jì)算思維的結(jié)構(gòu)化,Intel Core 2 Duo Processor,,17,,計(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ò)程化,18,,計(jì)算意義與計(jì)算思維,小結(jié),“計(jì)算思維”是面向所有的人，所有學(xué)科的，應(yīng)當(dāng)具有普適性，但這種普適的內(nèi)部是有差異的,,計(jì)算機(jī)科學(xué)是新興學(xué)科，其內(nèi)容日新月異，以及人的智力水于有高低之分，人們已掌握的計(jì)算機(jī)知識(shí)各有差異，不同人的計(jì)算思維具有很大差別，因此,計(jì)算思維具有層次性

9、,,只要具有思維品質(zhì)中的獨(dú)創(chuàng)性，就能創(chuàng)造性地解決問(wèn)題,,不同層次上的計(jì)算機(jī)思維均可得到,同質(zhì)性的發(fā)展,19,,科學(xué)界一般認(rèn)為，科學(xué)方法分為理論、實(shí)驗(yàn)和計(jì)算三大類,,與三大科學(xué)方法相對(duì)的是三大科學(xué)思維，理論思維以數(shù)學(xué)為基礎(chǔ)，實(shí)驗(yàn)思維以物理等學(xué)科為基礎(chǔ)，計(jì)算思維以計(jì)算機(jī)科學(xué)為基礎(chǔ),,20,,理論源于數(shù)學(xué)，理論思維支撐著所有的學(xué)科領(lǐng)域。正如數(shù)學(xué)一樣，定義是理論思維的靈魂，定理和證明則是它的精髓,,公理化方法是最重要的理論思維方法，科學(xué)界一般認(rèn)為，公理化方法是世界科學(xué)技術(shù)革命推動(dòng)的源頭。,理論思維,21,,實(shí)驗(yàn)思維方法可以分為以下三個(gè)步驟：,,①先提取出從現(xiàn)象中獲得的直觀認(rèn)識(shí)的主要部分，用最簡(jiǎn)單的數(shù)學(xué)

10、形式表示出來(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ō)，最為重要的事情就是設(shè)計(jì)、制造實(shí)驗(yàn)儀器和追求理想的實(shí)驗(yàn)環(huán)境,實(shí)驗(yàn)思維,22,,計(jì)算思維最根本的內(nèi)容，即其本質(zhì)是抽象（Abstraction）與自動(dòng)化（Automation）,,計(jì)算思維中的抽象完全超越物理的時(shí)空觀，并完全用符號(hào)來(lái)表示，其中，數(shù)字抽象只是其中的一類特例,,計(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)廠家能夠向公眾提供各種不同抽象

11、層次之間的翻譯工具,,計(jì)算思維,23,,計(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é),的“源”與“流”,24,,計(jì)算理論是研究使用計(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)造，作用和

12、關(guān)系作為研究對(duì)象的數(shù)學(xué)理論（描述通用計(jì)算機(jī)計(jì)算能力的,圖靈機(jī)模型,）,,可計(jì)算性理論,的中心問(wèn)題是建立計(jì)算的數(shù)學(xué)模型，進(jìn)而研究哪些是可計(jì)算的，哪些是不可計(jì)算的,,計(jì)算的復(fù)雜性理論,研究算法的時(shí)間復(fù)雜性和空間復(fù)雜性,,25,,計(jì)算機(jī)學(xué)科的方法論有三個(gè)過(guò)程：抽象、理論和自動(dòng)化設(shè)計(jì)及實(shí)現(xiàn),,最根本的問(wèn)題在于：?jiǎn)栴}如何進(jìn)行描述？哪些部分能夠被自動(dòng)化？如何進(jìn)行自動(dòng)化描述？,,建立物理符號(hào)系統(tǒng)并對(duì)其實(shí)施等價(jià)變換是計(jì)算機(jī)學(xué)科進(jìn)行問(wèn)題描述和求解的重要手段。,,“可行性”所要求的“形式化”及其“離散特征”使得數(shù)學(xué)成為重要的工具,,而計(jì)算模型無(wú)論從方法還是工具等方面，都表現(xiàn)出它在計(jì)算機(jī)上科學(xué)中的重要作用（參見(jiàn)1.

13、3節(jié)）,計(jì)算機(jī)學(xué)科的方法論,的三個(gè)過(guò)程,26,,科學(xué)：,關(guān)于自然、社會(huì)和思維的發(fā)展與變化規(guī)律的知識(shí)體系，其核心是,發(fā)現(xiàn),,技術(shù)：,根據(jù)實(shí)踐經(jīng)驗(yàn)和科學(xué)原理而發(fā)展形成的各種工藝操作方法、技能和技巧，其核心是,發(fā)明,,工程：,將科學(xué)原理應(yīng)用到生產(chǎn)實(shí)踐中，是某種形式的科學(xué)應(yīng)用，其核心是,建造,,現(xiàn)代科技工作者的素養(yǎng),我們所使用的工具影響著我們的思維方式和思維習(xí)慣，從而也將深刻地影響著我們的思維能力,,,Edsger Dijkstra,27,,霍夫曼編碼使用,變長(zhǎng)編碼表,對(duì)源符號(hào)（如文件中的字母）進(jìn)行編碼,,變長(zhǎng)編碼表通過(guò)評(píng)估來(lái)源符號(hào)出現(xiàn)概率的方法得到的，概率高的字母用較短的編碼，出現(xiàn)概率低的則用較長(zhǎng)的

14、編碼,,使編碼之后的字符串的平均長(zhǎng)度、期望值,降低,，從而達(dá)到,無(wú)損壓縮數(shù)據(jù)的目的,四個(gè)狀態(tài)的霍夫曼編碼過(guò)程,28,,設(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位，共需112位。該字符串中有9個(gè)不同的符號(hào)，至少需要4位二進(jìn)制才能表示，這樣傳送該字符串也要56位。若用計(jì)算的Huffman編碼，只需要42位。,霍夫曼編碼

15、舉例,︺,29,,霍夫曼編碼過(guò)程,,可以得到：,,a的編碼00 e的編碼 111 I的編碼1101 m的編碼1100,,t的編碼1011 c的編碼 1010 h的編碼1001 r的編碼 1000,,原字符串（二進(jìn)制）長(zhǎng)度：= 112（14×8）位,,Huffman編碼長(zhǎng)度： = 42位,,（01 00 111 1101 1100 1011 1010 1001 1000）,30,,在數(shù)論中，,反運(yùn)算,的問(wèn)題往往是極難求解的，或者說(shuō)極難計(jì)算的,,離散對(duì)數(shù)和整數(shù)因式分解問(wèn)題就屬于困難的計(jì)算數(shù)論問(wèn)題,,如果給出兩個(gè)素?cái)?shù)p和q

16、，要求兩者的乘積，即使p和q很大，那計(jì)算它們的乘積仍然是可行的,,但反過(guò)來(lái)，給出N，要求p和q就,極為困難,了,,利用反計(jì)算的難度，對(duì)數(shù)據(jù)進(jìn)行加密，是現(xiàn)代密碼學(xué)的基礎(chǔ),,計(jì)算機(jī)通訊中的公開(kāi)密鑰加密算法，就是利用了數(shù)論的這個(gè)原理,31,,密鑰舉例：,,在馬丁?加德納的《數(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ù),,,經(jīng)過(guò)它加密后得到的密文C是,,,問(wèn)C加密前的明文是什么？,32,,問(wèn)題結(jié)論,這個(gè)問(wèn)題在1994年4月2日，即相隔了17年之后由

17、迪里克?阿特金斯（Derek Atkins），邁克爾?克拉弗（Michael Graff）和阿爾金?K?廉斯特拉（Arjen K?Lenstra），帕爾?雷蘭德（Panl Leyland）解出，他們對(duì)上述的N成功地進(jìn)行因式分解，它的兩素因子是：,,,,和,,,,在得到了p和q后，從密文計(jì)算明文的障礙就被克服了，這個(gè)明文是,,,它是：,THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE（這些魔術(shù)般的詞是魚(yú)鷹,。）,,33,,生物信息學(xué)是一門新興交叉學(xué)科，其發(fā)展的標(biāo)志便是大量生命科學(xué)數(shù)據(jù)的快速積累以及為處理這些復(fù)雜數(shù)據(jù)而設(shè)計(jì)的新算法的不斷涌現(xiàn),,最常用的數(shù)據(jù)結(jié)構(gòu)主要包括

18、四種類型：,,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)通路,34,,計(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),,,35,,計(jì)算機(jī)學(xué)科的核心概念是ACM/IEEE-C

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

20、指隨著問(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,）,38,,對(duì)一個(gè)想法或問(wèn)題進(jìn)行形式化、特征化、可視化思維的方法,,數(shù)據(jù)流圖和E-R圖等都屬于概念模型，而邏輯理論、開(kāi)關(guān)理論和計(jì)算理論中的模型大都屬于形式模型,,UML,，統(tǒng)一建模語(yǔ)言是軟件工程中的重要工具和方法,CS,核心概念,-,概念和形式模型（,Conceptual and Format

21、 Models,）,39,,一致性包括用于形式說(shuō)明的一組公理的一致性、事實(shí)和理論的一致性，以及一種語(yǔ)言或接口設(shè)計(jì)的內(nèi)部一致性,,例如，由于計(jì)算機(jī)資源的部署原因，服務(wù)器的,網(wǎng)絡(luò)地址,可能發(fā)生變化，但由于用戶訪問(wèn)的是,域名地址,，只要保證正確的映射關(guān)系，網(wǎng)絡(luò)地址的變化不會(huì)影響用戶訪問(wèn)，這就是一致性在發(fā)揮作用,CS,核心概念,-,一致性和完備性（,Consistency and Completeness,），,40,,關(guān)于時(shí)間、空間、人力和財(cái)力等資源消耗的度量,,在計(jì)算機(jī),軟,硬,件的設(shè)計(jì)中，要充分考慮某種預(yù)期果達(dá)到的效率，以及一個(gè)給定的實(shí)現(xiàn)過(guò)程較之替代的實(shí)現(xiàn)過(guò)程的效率,,例如，原用于圖形顯示的圖形

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

23、：遵循科學(xué)的方法來(lái)建立新的知識(shí),,無(wú)論這些知識(shí)只是對(duì)日常生活中的現(xiàn)象，或是學(xué)科的前沿發(fā)現(xiàn),43,,邏輯思維是從已知的些微（但非常重要的）信息中推導(dǎo)出盡可能多的信息，而不要輕易下結(jié)論,,新的信息收集必須按照確定的規(guī)程，你不能僅僅因?yàn)樾疫\(yùn)的而走對(duì)路,,計(jì)算思維的技能,-,邏輯思維,數(shù)獨(dú)問(wèn)題求解,44,,有些問(wèn)題是一次性的，但解決這些問(wèn)題的方案，則可以不斷發(fā)展,,在同類問(wèn)題一再出現(xiàn)時(shí)，算法思維就可以介入。沒(méi)有必要重新每次從頭思考，而是采用每次都行之有效的解決方案,,囚徒困境（prisoner's dilemma,）是博弈論的非零和博弈中具代表性的例子，反映個(gè)人最佳選擇并非團(tuán)體最佳選擇,,雖然困境本身

24、只屬模型性質(zhì)，但現(xiàn)實(shí)中的價(jià)格競(jìng)爭(zhēng)、環(huán)境保護(hù)等方面，也會(huì)頻繁出現(xiàn)類似情況,計(jì)算思維的技能,-,算法思維,45,,算法思維案例：囚徒困境,兩個(gè)罪犯準(zhǔn)備搶劫銀行，但作案前失手被擒。警方懷疑他們意圖搶劫，苦干證據(jù)只夠起訴非法持有槍械，于是將其分開(kāi)審訊。,,為離間雙方，警方分別對(duì)兩人說(shuō)：,,若都保持沉默(“,合作,”)，則一同入獄,1年,；,,若是互相檢舉(互相“,背叛,”)，則一同入獄,5年,,若你認(rèn)罪并檢舉對(duì)方(“,背叛,”對(duì)方)，他保持沉默，他入人獄,10年,，你可以,獲釋,(,反之亦然,),,結(jié)果兩人都選擇了,招供（最希望的結(jié)果）。,46,,情況分析,,孤立地看，這是最符合個(gè)體利益的“,理性,”

25、選擇。以A為例：若B招供，A自己招供獲刑5年，不招供獲刑10年；若B不招供，自己,招供,可以免刑，不招供獲刑1年。兩種情況下，選擇,招供,都更有利，事實(shí)上卻比兩人都拒不招供的結(jié)果糟。,,由囚徒困境可知，,公共生活中，如果每個(gè)人都從眼前利益、個(gè)人利益出發(fā)，結(jié)果會(huì)對(duì)整體的利益(間接對(duì)個(gè)人的利益)造成傷害。,47,,為解決“囚徒困境”難題，美國(guó)曾組織競(jìng)賽，要求參賽者根據(jù)“重復(fù)囚徒困境”(雙方不止一次相遇，“背叛”可能在以后遭到報(bào)復(fù))來(lái)設(shè)計(jì)程序。,,將程序輸入計(jì)算機(jī)反復(fù)互相博弈，以最終得分評(píng)估優(yōu)劣(雙方合作各得3分；雙方背叛各得1分；一方合作一方背叛，合作方得0分，背叛方得5分)；,,有些程序采用“,

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

27、你選擇“,永遠(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ò)去相處多好，仍然對(duì)背叛有反應(yīng)；它是寬容的，不因一次背叛而選擇玉石俱焚,。,50,,計(jì)算機(jī)科學(xué)家效率觀念有非常精確的定義，通用的方式是討論如何盡量減少使用的資源來(lái)完成任務(wù),,可減少資源各有不同，但最重要的往往是'時(shí)間‘,,重要的是尋找某種途徑，保證能夠任

28、務(wù)完成而且使用盡可能少的步驟,,計(jì)算思維的技能,-,效率思維,紅綠球的換位游戲，如何使完成步驟最少？,51,,計(jì)算機(jī)科學(xué)家是進(jìn)行系統(tǒng)集成的專家,,不只是應(yīng)用今天的技術(shù)，而且還創(chuàng)造明天的技術(shù),,什么是當(dāng)今世界的10名大的創(chuàng)新？互聯(lián)網(wǎng)，手機(jī)，個(gè)人計(jì)算機(jī)，光纖，電子郵件，衛(wèi)星導(dǎo)航系統(tǒng)，記憶存儲(chǔ)磁盤，數(shù)碼相機(jī)和RFID標(biāo)簽,,計(jì)算機(jī)科學(xué)家則將它們組合在一起，構(gòu)建新的系統(tǒng)并滿足社會(huì)的需求,,“,需要發(fā)掘用戶需要但無(wú)從表達(dá)的需求 –喬布斯,”—實(shí)際上是創(chuàng)造用戶的需求,計(jì)算思維的技能,-,創(chuàng)新思維,52,,任何新技術(shù)都是一把雙刃劍,,+,現(xiàn)代計(jì)算機(jī)系統(tǒng)的成是帶來(lái)對(duì)數(shù)字信息進(jìn)行分析、處理和共享的便利,,-也

29、存在大量負(fù)面的影響,,例如，如何處理創(chuàng)建電子商務(wù)客戶聯(lián)機(jī)檔案的便利性與隱私問(wèn)題之間的平衡，是當(dāng)代信息系統(tǒng)引發(fā)的倫理問(wèn)題之一,計(jì)算思維的技能,-,倫理思維,53,,弄清事實(shí),,界定沖突或困境并識(shí)別有關(guān)的更高序列上的價(jià)值理念,,確定利益相關(guān)者,,理性的選擇解決方案,,確認(rèn)解決方案可能帶來(lái)的后果,,,倫理分析過(guò)程,54,,計(jì)算思維是在計(jì)算學(xué)科與其他學(xué)科思想方法的交互中發(fā)展的，比如許多算法的思想來(lái)源于人類對(duì)特定學(xué)科研究對(duì)象的認(rèn)識(shí)，又反過(guò)來(lái)作用于這些學(xué)科和更多學(xué)科的發(fā)展,,從計(jì)算思維的內(nèi)涵上講，它闡述計(jì)算的基本思想和方法，究其根源這些思想和方法均來(lái)自人類的共同智慧，不但有助于計(jì)算學(xué)科中問(wèn)題的求解，也與人

30、類在其他領(lǐng)域工作和生活中解決問(wèn)題的方法相通,本章小結(jié),55,,周以真．計(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ì)算機(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月專輯, vol.35, no.11, pp.31-35.,,孫兆豪, 孫俊卿, 郭喜鳳. 論計(jì)算思維和計(jì)算機(jī)思維 [BS/OL],,程向前等. 計(jì)算機(jī)應(yīng)用基礎(chǔ)2011 [M]. 中國(guó)人民大學(xué)出版社 2010,參考文獻(xiàn)：,56,,