第1章-計算機與計算思維

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

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

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

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

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

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

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

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

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

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

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

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

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

14、層次之間的翻譯工具,計算思維,24,計算機科學在本質(zhì)上源自數(shù)學思維，因為像所有的科學一樣，它的形式化基礎建筑于數(shù)學之上計算機科學又從本質(zhì)上源自工程思維，因為我們建造的是能夠與實際世界互動的系統(tǒng)，基本計算設備的限制迫使計算機科學家必須計算性地思考，而不能只是數(shù)學性地思考構建虛擬世界的自由使我們能夠超越物理世界的各種系統(tǒng)數(shù)學和工程思維的互補與融合很好的體現(xiàn)在抽象、理論和設計三個學科形態(tài)（或過程）上,計算機科學的“源”與“流”,25,計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、法均來自人類的共同智慧，不但有助于計算學科中問題的求解，也與人類在其他領域工作和生活中解決問題的方法相通,本章小結,56,周以真．計算思維．中國計算機學會通訊[J].2007，3(11)．王飛躍．從計算思維到計算文化[J]．中國計算機學會通訊．2007，3(11)．董榮勝．計算機科學導論——思想與方法[M]．高等教育出版社，2007．董榮勝，古天龍．計算機科學與技術方法論[M]．人民郵電出版社，2002．張曉如，張再躍. 再談計

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