1、1大學計算機基礎上課信息第一大班：經(jīng)濟第一大班：經(jīng)濟1114 講課：周一講課：周一 7、8節(jié)節(jié) 周四周四1、2節(jié)節(jié) 上機：周四上機：周四 9、10節(jié)（節(jié)（19：0021：00）第二大班第二大班: 經(jīng)濟經(jīng)濟1518 講課：周一講課：周一5、6節(jié)節(jié) 周四周四5、6節(jié)節(jié) 上機：周四上機：周四7、8節(jié)節(jié)機器安排機器安排2教師：教師： 賈應智賈應智 E-Mail: 交作業(yè)服務器：交作業(yè)服務器：98 用戶名：用戶名：student 口令：口令：ctec3大學計算機基礎大學計算機基礎4計算意義與計算思維計算意義與計算思維計算科學方法概論計算科學方法概論可計算性與計算過程可

2、計算性與計算過程計算思維的跨學科交融計算思維的跨學科交融計算機學科的核心概念計算機學科的核心概念與問題求解與問題求解計算思維的技能計算思維的技能科學思維科學思維邏輯思維邏輯思維算法思維算法思維效率思維效率思維創(chuàng)新思維創(chuàng)新思維倫理思維倫理思維5計算思維（計算思維（Computational thinking,CT）由美國）由美國 Carnegie Mellon 大學計算機科學教授周以真女士大學計算機科學教授周以真女士于于2006年提出年提出她認為，計算思維是運用計算機科學的基礎概念她認為，計算思維是運用計算機科學的基礎概念進行進行問題求解問題求解、系統(tǒng)設計系統(tǒng)設計、以及、以及人類行為理解人類行為

3、理解等涵蓋計算機科學之廣度的一系列等涵蓋計算機科學之廣度的一系列思維活動思維活動計算思維代表著計算思維代表著一種普遍的態(tài)度一種普遍的態(tài)度和和一類普適的技一類普適的技能能，每一個人都應熱心于它的學習和運用，每一個人都應熱心于它的學習和運用6 是是概念化的抽象思維而概念化的抽象思維而不只是不只是程序設計程序設計 是是基本的而基本的而不是不是死記硬背的技能死記硬背的技能 是是人的而人的而不是不是計算機的思維方式計算機的思維方式 是是數(shù)學和工程思維的互補與融合數(shù)學和工程思維的互補與融合 是是思想而思想而不是不是人造品人造品 面向面向所有的人和所有地方所有的人和所有地方 關注依舊亟待理解和解決的智力上極

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

5、；各種信息的處理、規(guī)范和管理；用計算機開展的科研活動；用計算機開展的科研活動；使計算機系統(tǒng)具有智能行為；使計算機系統(tǒng)具有智能行為；創(chuàng)建和使用通信和娛樂媒體；創(chuàng)建和使用通信和娛樂媒體；尋找和收集與任何目的有關的信息等尋找和收集與任何目的有關的信息等8本章涉及的本章涉及的“計算計算”包含了包含了computation和和computing的內容的內容對于計算機基礎學習而言，了解對于計算機基礎學習而言，了解計算思維的宏觀計算思維的宏觀特性特性，對于個人專業(yè)發(fā)展具有重要意義，對于個人專業(yè)發(fā)展具有重要意義9通過網(wǎng)絡可以求解的問題通過網(wǎng)絡可以求解的問題信息查詢信息查詢交流與溝通交流與溝通資源的發(fā)布與共享資

6、源的發(fā)布與共享10移動通信與地理信息移動通信與地理信息系統(tǒng)的結合，產(chǎn)生了系統(tǒng)的結合，產(chǎn)生了新的計算模式：新的計算模式：與位與位置有關的計算置有關的計算利用利用GPS定位，可以找定位，可以找到周邊的服務設施到周邊的服務設施通過移動信號基站，發(fā)通過移動信號基站，發(fā)現(xiàn)客戶所需要的服務：現(xiàn)客戶所需要的服務：天氣、旅游、購物等天氣、旅游、購物等移動通訊設備的廣泛應用，催生了諸多新型的商業(yè)應用模式11計算思維的信息化促進了計算思維的信息化促進了政務、商務、教育和社會政務、商務、教育和社會的信息化的信息化小學校園的門禁系統(tǒng)與移動小學校園的門禁系統(tǒng)與移動通信結合，產(chǎn)生學生在校、通信結合，產(chǎn)生學生在校、離校信息

7、服務離校信息服務信用卡消費信息與移動通信信用卡消費信息與移動通信和因特網(wǎng)結合，產(chǎn)生實時和因特網(wǎng)結合，產(chǎn)生實時消費報告和無紙化賬單報消費報告和無紙化賬單報告告校園一卡通校園一卡通12中國經(jīng)濟發(fā)展正在向服務中國經(jīng)濟發(fā)展正在向服務型經(jīng)濟轉型型經(jīng)濟轉型計算機科學與技術及信息計算機科學與技術及信息技術則是現(xiàn)代服務型經(jīng)濟技術則是現(xiàn)代服務型經(jīng)濟發(fā)展的根本保障發(fā)展的根本保障Software as a service (SaaS)和服務計算（和服務計算（service computing）正在引起關）正在引起關注注云計算模型示意13計算思維的智能化促進計算思維的智能化促進了交通管理的智能化、了交通管理的智能化、

8、業(yè)務流程的智能化、業(yè)務流程的智能化、電子服務的智能化電子服務的智能化電子服務和社會生活的電子服務和社會生活的智能化的需求反過來智能化的需求反過來促進計算思維智能化促進計算思維智能化的進一步發(fā)展的進一步發(fā)展智能化能夠緩解交通擁堵？14計算思維從計算理論、計算計算思維從計算理論、計算技術、計算工程、計算工具、技術、計算工程、計算工具、計算服務和計算應用的轉化計算服務和計算應用的轉化就是計算思維的工程化就是計算思維的工程化計算思維的工程化促進了諸計算思維的工程化促進了諸如計算機、手機、平板電腦如計算機、手機、平板電腦等計算工具和系統(tǒng)的發(fā)展，等計算工具和系統(tǒng)的發(fā)展，后者反過來促進了計算思維后者反過來促

9、進了計算思維的工程化的工程化15計算思維的人性化促進計算思維的人性化促進了人機交互的人性了人機交互的人性化、計算工具的人性化、計算工具的人性化和社會的進步化和社會的進步計算和信息技術對人類計算和信息技術對人類產(chǎn)生的負面影響同樣產(chǎn)生的負面影響同樣不可小視不可小視信息社會中的信息社會中的“宅人宅人”數(shù)碼相機數(shù)碼相機 vs.膠片工業(yè)膠片工業(yè)數(shù)字印刷數(shù)字印刷 vs. 鉛字印刷鉛字印刷人性化設計人性化設計 筆記本電腦支架筆記本電腦支架16層次化源于社會組織和分工層次化源于社會組織和分工計算思維的層次包括計算理論思維、計算技術思計算思維的層次包括計算理論思維、計算技術思維、計算工程思維、計算工具思維、計算

10、服務維、計算工程思維、計算工具思維、計算服務思維和計算應用思維六個層次思維組成思維和計算應用思維六個層次思維組成 它們分別對應計算理論、計算技術、計算工程、它們分別對應計算理論、計算技術、計算工程、計算工具、計算服務和計算應用計算工具、計算服務和計算應用每個層次上的思維都至少包含許多不同的思維過每個層次上的思維都至少包含許多不同的思維過程、思維模式和思維規(guī)律程、思維模式和思維規(guī)律17結構化源于軟件開發(fā)結構化源于軟件開發(fā)的結構化系統(tǒng)分析、的結構化系統(tǒng)分析、結構化設計和結構結構化設計和結構化程序設計化程序設計重要的案例重要的案例計算機體系結構計算機體系結構多核多核CPUGPGPU（通用圖形處（通用

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

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

13、科學方法相對的與三大科學方法相對的是三大科學思維，理是三大科學思維，理論思維以數(shù)學為基礎，論思維以數(shù)學為基礎，實驗思維以物理等學實驗思維以物理等學科為基礎，計算思維科為基礎，計算思維以計算機科學為基礎以計算機科學為基礎21理論源于數(shù)學，理論理論源于數(shù)學，理論思維支撐著所有的思維支撐著所有的學科領域。正如數(shù)學科領域。正如數(shù)學一樣，定義是理學一樣，定義是理論思維的靈魂，定論思維的靈魂，定理和證明則是它的理和證明則是它的精髓精髓公理化方法是最重要公理化方法是最重要的理論思維方法，的理論思維方法，科學界一般認為，科學界一般認為，公理化方法是世界公理化方法是世界科學技術革命推動科學技術革命推動的源頭。的

14、源頭。22實驗思維方法可以分為以下實驗思維方法可以分為以下三個步驟：三個步驟：先提取出從現(xiàn)象中獲得的先提取出從現(xiàn)象中獲得的直觀認識的主要部分，用直觀認識的主要部分，用最簡單的數(shù)學形式表示出最簡單的數(shù)學形式表示出來，以建立量的概念；來，以建立量的概念； 再由此試用數(shù)學方法導出再由此試用數(shù)學方法導出另一易于實驗證實的數(shù)量另一易于實驗證實的數(shù)量關系；關系；然后通過實驗證實這種數(shù)然后通過實驗證實這種數(shù)量關系量關系對于實驗思維來說，最為重對于實驗思維來說，最為重要的事情就是設計、制造要的事情就是設計、制造實驗儀器和追求理想的實實驗儀器和追求理想的實驗環(huán)境驗環(huán)境23計算思維最根本的內容，即其本質是抽象計算

15、思維最根本的內容，即其本質是抽象（Abstraction）與自動化（）與自動化（Automation）計算思維中的抽象完全超越物理的時空觀，并完計算思維中的抽象完全超越物理的時空觀，并完全用符號來表示，其中，數(shù)字抽象只是其中的全用符號來表示，其中，數(shù)字抽象只是其中的一類特例一類特例計算思維中的抽象最終是要能夠利用機器的一步計算思維中的抽象最終是要能夠利用機器的一步步自動執(zhí)行。為了確保機器的自動化，就需要步自動執(zhí)行。為了確保機器的自動化，就需要在抽象的過程中進行精確和嚴格的符號標記和在抽象的過程中進行精確和嚴格的符號標記和建模建模還要求計算機系統(tǒng)或軟件系統(tǒng)生產(chǎn)廠家能夠向公還要求計算機系統(tǒng)或軟件系

16、統(tǒng)生產(chǎn)廠家能夠向公眾提供各種不同抽象層次之間的翻譯工具眾提供各種不同抽象層次之間的翻譯工具24計算機科學在本質上源自數(shù)學思維，因為像所有計算機科學在本質上源自數(shù)學思維，因為像所有的科學一樣，它的形式化基礎建筑于數(shù)學之上的科學一樣，它的形式化基礎建筑于數(shù)學之上計算機科學又從本質上源自工程思維，因為我們計算機科學又從本質上源自工程思維，因為我們建造的是能夠與實際世界互動的系統(tǒng)，基本計建造的是能夠與實際世界互動的系統(tǒng)，基本計算設備的限制迫使計算機科學家必須計算性地算設備的限制迫使計算機科學家必須計算性地思考，而不能只是數(shù)學性地思考思考，而不能只是數(shù)學性地思考構建虛擬世界的自由使我們能夠超越物理世界的

17、構建虛擬世界的自由使我們能夠超越物理世界的各種系統(tǒng)各種系統(tǒng)數(shù)學和工程思維的互補與融合很好的體現(xiàn)在抽象、數(shù)學和工程思維的互補與融合很好的體現(xiàn)在抽象、理論和設計三個學科形態(tài)（或過程）上理論和設計三個學科形態(tài)（或過程）上25計算理論是研究使用計算機解決計算問題的數(shù)學計算理論是研究使用計算機解決計算問題的數(shù)學理論理論有三個核心領域：自動機理論、可計算性理論和有三個核心領域：自動機理論、可計算性理論和計算的復雜性理論計算的復雜性理論自動機將離散數(shù)學系統(tǒng)的構造，作用和關系作為研究自動機將離散數(shù)學系統(tǒng)的構造，作用和關系作為研究對象的數(shù)學理論（描述通用計算機計算能力的對象的數(shù)學理論（描述通用計算機計算能力的圖

18、靈機圖靈機模型模型）可計算性理論的中心問題是建立計算的數(shù)學模型，進的中心問題是建立計算的數(shù)學模型，進而研究哪些是可計算的，哪些是不可計算的而研究哪些是可計算的，哪些是不可計算的計算的復雜性理論研究算法的時間復雜性和空間復雜研究算法的時間復雜性和空間復雜性性26計算機學科的方法論有三個過程：抽象、理論和計算機學科的方法論有三個過程：抽象、理論和自動化設計及實現(xiàn)自動化設計及實現(xiàn)最根本的問題在于：問題如何進行描述？哪些部分能最根本的問題在于：問題如何進行描述？哪些部分能夠被自動化？如何進行自動化描述？夠被自動化？如何進行自動化描述？建立物理符號系統(tǒng)并對其實施等價變換是計算機建立物理符號系統(tǒng)并對其實施

19、等價變換是計算機學科進行問題描述和求解的重要手段。學科進行問題描述和求解的重要手段。“可行性可行性”所要求的所要求的“形式化形式化”及其及其“離散特征離散特征”使得數(shù)學成為重要的工具使得數(shù)學成為重要的工具而計算模型無論從方法還是工具等方面，都表現(xiàn)而計算模型無論從方法還是工具等方面，都表現(xiàn)出它在計算機上科學中的重要作用（參見出它在計算機上科學中的重要作用（參見1.3節(jié)）節(jié)）27科學：關于自然、社關于自然、社會和思維的發(fā)展與變會和思維的發(fā)展與變化規(guī)律的知識體系，化規(guī)律的知識體系，其核心是其核心是發(fā)現(xiàn)發(fā)現(xiàn)技術：根據(jù)實踐經(jīng)驗根據(jù)實踐經(jīng)驗和科學原理而發(fā)展形和科學原理而發(fā)展形成的各種工藝操作方成的各種工藝

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

21、低的則用較長的編碼長的編碼使編碼之后的字符串使編碼之后的字符串的平均長度、期望值的平均長度、期望值降低降低，從而達到，從而達到無損無損壓縮數(shù)據(jù)的目的壓縮數(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位，共需位

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

23、0）31在數(shù)論中，在數(shù)論中，反運算反運算的問題往往是極難求解的，或的問題往往是極難求解的，或者說極難計算的者說極難計算的離散對數(shù)和整數(shù)因式分解問題就屬于困難的計算數(shù)論離散對數(shù)和整數(shù)因式分解問題就屬于困難的計算數(shù)論問題問題如果給出兩個素數(shù)如果給出兩個素數(shù)p和和q，要求兩者的乘積，即使，要求兩者的乘積，即使p和和q很大，那計算它們的乘積仍然是可行的很大，那計算它們的乘積仍然是可行的但反過來，給出但反過來，給出N，要求，要求p和和q就就極為困難極為困難了了利用反計算的難度，對數(shù)據(jù)進行加密，是現(xiàn)代密利用反計算的難度，對數(shù)據(jù)進行加密，是現(xiàn)代密碼學的基礎碼學的基礎計算機通訊中的公開密鑰加密算法，就是利用了

24、計算機通訊中的公開密鑰加密算法，就是利用了數(shù)論的這個原理數(shù)論的這個原理32密鑰舉例： 在馬丁在馬丁加德納的加德納的數(shù)學游戲數(shù)學游戲一書中，報告了一書中，報告了1977年由年由RSA（Rivest,shamir和和Adleman）懸賞）懸賞100美元求解對一個美元求解對一個密鑰的破解問題。給出一對整數(shù)（密鑰的破解問題。給出一對整數(shù)（e,N）作為公開鑰，）作為公開鑰，e=9007，N是一個隨機的是一個隨機的129位數(shù)位數(shù)114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123

25、5639587058989075147599290026878543541經(jīng)過它加密后得到的密文經(jīng)過它加密后得到的密文C是是9686961375462206147714092225435588290575999112457431987469512093081629822514570835693147662288398962801339905518299451557815154問問C加密前的明文是什么？加密前的明文是什么？33問題結論這個問題在這個問題在1994年年4月月2日，即相隔了日，即相隔了17年之后由迪里克年之后由迪里克阿特金斯阿特金斯（Derek Atkins），邁克爾），邁克爾克拉弗

26、（克拉弗（Michael Graff）和阿爾金）和阿爾金K廉斯特廉斯特拉（拉（Arjen KLenstra），帕爾），帕爾雷蘭德（雷蘭德（Panl Leyland）解出，他們對上）解出，他們對上述的述的N成功地進行因式分解，它的兩素因子是：成功地進行因式分解，它的兩素因子是： 3490529510847650949147849619903898133417764638493387843990820577 和和 3276913299326670954996198819083446143177642967991941539798288533在得到了在得到了p和和q后，從密文計算明文的障礙就被克服了

27、，這個明文是后，從密文計算明文的障礙就被克服了，這個明文是20080500130070903002315180419000118050019172105011309190800151919090618010705它是：它是：THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE（這些魔術般的（這些魔術般的詞是魚鷹詞是魚鷹。）。）34生物信息學是一門新興交叉學科，其發(fā)展的標志生物信息學是一門新興交叉學科，其發(fā)展的標志便是大量生命科學數(shù)據(jù)的快速積累以及為處理便是大量生命科學數(shù)據(jù)的快速積累以及為處理這些復雜數(shù)據(jù)而設計的新算法的不斷涌現(xiàn)這些復雜數(shù)據(jù)而設計的新算法的不斷涌現(xiàn)最常用

28、的數(shù)據(jù)結構主要包括四種類型：最常用的數(shù)據(jù)結構主要包括四種類型：1) 字符串結構，表示字符串結構，表示DNA，RNA和氨基酸序列；和氨基酸序列；2) 樹結構，表示各種生物有機體的系統(tǒng)進化樹；樹結構，表示各種生物有機體的系統(tǒng)進化樹；3) 三維空間點和連接集合結構，表示蛋白質的三維結三維空間點和連接集合結構，表示蛋白質的三維結構；構；4) 圖結構，表示代謝和信號傳導通路圖結構，表示代謝和信號傳導通路35計算科學中許多仿生計算算法都是受到生物學中計算科學中許多仿生計算算法都是受到生物學中群體行為的啟發(fā)而模仿設計出來的群體行為的啟發(fā)而模仿設計出來的例如，計算科學中的神經(jīng)網(wǎng)絡算法、遺傳算法、演化例如，計算

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

30、想、原則和方法，核心概念具有如性的重要思想、原則和方法，核心概念具有如下基本特征：下基本特征：（1）在學科及各分支學科中普遍出現(xiàn)；）在學科及各分支學科中普遍出現(xiàn)；（2）在理論、抽象和設計的各個層面上都有很多示）在理論、抽象和設計的各個層面上都有很多示例；例；（3）在理論上具有可延展和變形的作用，在技術上有）在理論上具有可延展和變形的作用，在技術上有高度的獨立性高度的獨立性37通過將一個對象（或事物）與其某種屬性相聯(lián)系，通過將一個對象（或事物）與其某種屬性相聯(lián)系，從而使抽象的概念具體化的過程從而使抽象的概念具體化的過程將一個進程與一個處理機、一個變量與其類型或值分將一個進程與一個處理機、一個變量

31、與其類型或值分別聯(lián)系起來別聯(lián)系起來這種聯(lián)系的建立，實際上就是建立了某種約束這種聯(lián)系的建立，實際上就是建立了某種約束在數(shù)據(jù)庫中的不同表之間建立在數(shù)據(jù)庫中的不同表之間建立“關系關系”和參照完整性和參照完整性，就是用約束關系來保證數(shù)據(jù)的完整性。就是用約束關系來保證數(shù)據(jù)的完整性。38指隨著問題規(guī)模的增長使問指隨著問題規(guī)模的增長使問題的復雜性呈非線性增加題的復雜性呈非線性增加的效應的效應這種非線性增加的效應是區(qū)這種非線性增加的效應是區(qū)分和選擇各種現(xiàn)有方法和分和選擇各種現(xiàn)有方法和技術的重要因素技術的重要因素幾十萬考生的高考成績排序，幾十萬考生的高考成績排序，須認真選擇排序算法須認真選擇排序算法氣候變暖對全

32、球經(jīng)濟的影響，氣候變暖對全球經(jīng)濟的影響，仿真與模擬仿真與模擬39對一個想法或問題進行形式化、特征化、可視化對一個想法或問題進行形式化、特征化、可視化思維的方法思維的方法數(shù)據(jù)流圖和數(shù)據(jù)流圖和E-R圖等都屬于概念模型，而邏輯理論、開圖等都屬于概念模型，而邏輯理論、開關理論和計算理論中的模型大都屬于形式模型關理論和計算理論中的模型大都屬于形式模型UML，統(tǒng)一建模語言是軟件工程中的重要工具和方法，統(tǒng)一建模語言是軟件工程中的重要工具和方法40一致性包括用于形式說明的一組公理的一致性、一致性包括用于形式說明的一組公理的一致性、事實和理論的一致性，以及一種語言或接口設事實和理論的一致性，以及一種語言或接口設

33、計的內部一致性計的內部一致性例如，由于計算機資源的部署原因，服務器的例如，由于計算機資源的部署原因，服務器的網(wǎng)絡地網(wǎng)絡地址址可能發(fā)生變化，但由于用戶訪問的是可能發(fā)生變化，但由于用戶訪問的是域名地址域名地址，只，只要保證正確的映射關系，網(wǎng)絡地址的變化不會影響用要保證正確的映射關系，網(wǎng)絡地址的變化不會影響用戶訪問，這就是一致性在發(fā)揮作用戶訪問，這就是一致性在發(fā)揮作用41關于時間、空間、人力和財力等資源消耗的度量關于時間、空間、人力和財力等資源消耗的度量在計算機在計算機軟軟硬硬件的設計中，要充分考慮某種預期件的設計中，要充分考慮某種預期果達到的效率，以及一個給定的實現(xiàn)過程較之果達到的效率，以及一個給

34、定的實現(xiàn)過程較之替代的實現(xiàn)過程的效率替代的實現(xiàn)過程的效率例如，原用于圖形顯示的圖形處理器（例如，原用于圖形顯示的圖形處理器（GPU），現(xiàn)廣），現(xiàn)廣泛應用于數(shù)據(jù)密集型的高性能計算場合（泛應用于數(shù)據(jù)密集型的高性能計算場合（GPGPU，通，通用圖形處理器），而這種應用可以大大節(jié)省高性能處用圖形處理器），而這種應用可以大大節(jié)省高性能處理中的成本和能源消耗理中的成本和能源消耗42指系統(tǒng)的結構、狀態(tài)、特征、行為和功能等隨著指系統(tǒng)的結構、狀態(tài)、特征、行為和功能等隨著時間的推移而發(fā)生的更改時間的推移而發(fā)生的更改從從CLI（命令行界面）到（命令行界面）到GUI（圖形用戶界面），是計（圖形用戶界面），是計算機應用

35、方式演化的里程碑；算機應用方式演化的里程碑；而瀏覽器的出現(xiàn)，結束了桌面系統(tǒng)一統(tǒng)天下的局面而瀏覽器的出現(xiàn)，結束了桌面系統(tǒng)一統(tǒng)天下的局面最容易使用戶最容易使用戶受到困擾受到困擾的是軟件的是軟件無止境的演化無止境的演化，從而，從而預見和適應計算機系統(tǒng)的演化預見和適應計算機系統(tǒng)的演化43所謂科學思維最基本的內容是所謂科學思維最基本的內容是沒有證據(jù)就不要求沒有證據(jù)就不要求急于下結論急于下結論：遵循科學的方法來建立新的知識：遵循科學的方法來建立新的知識無論這些知識只是對日常生活中的現(xiàn)象，或是學科的無論這些知識只是對日常生活中的現(xiàn)象，或是學科的前沿發(fā)現(xiàn)前沿發(fā)現(xiàn)44邏輯思維是從已知的些微邏輯思維是從已知的些微

36、（但非常重要的）信息中（但非常重要的）信息中推導出盡可能多的信息，推導出盡可能多的信息，而不要輕易下結論而不要輕易下結論新的信息收集必須按照確定新的信息收集必須按照確定的規(guī)程，你不能僅僅因為的規(guī)程，你不能僅僅因為幸運的而走對路幸運的而走對路數(shù)獨問題求解45有些問題是一次性的，但解決這些問題的方案，有些問題是一次性的，但解決這些問題的方案，則可以不斷發(fā)展則可以不斷發(fā)展在同類問題一再出現(xiàn)時，算法思維就可以介入。在同類問題一再出現(xiàn)時，算法思維就可以介入。沒有必要重新每次從頭思考，而是采用每次都沒有必要重新每次從頭思考，而是采用每次都行之有效的解決方案行之有效的解決方案囚徒困境（囚徒困境（prison

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

38、警方分別對兩人說：若都保持沉默若都保持沉默(“合作合作”)，則一同入獄，則一同入獄1年年；若是互相檢舉若是互相檢舉(互相互相“背叛背叛”)，則一同入獄，則一同入獄5年年若你認罪并檢舉對方若你認罪并檢舉對方(“背叛背叛”對方對方)，他保持沉默，他，他保持沉默，他入人獄入人獄10年年，你可以，你可以獲釋獲釋(反之亦然反之亦然) 結果兩人都選擇了結果兩人都選擇了招供（最希望的結果）。招供（最希望的結果）。47 孤立地看，這是最符合個體利益的孤立地看，這是最符合個體利益的“理性理性”選擇。以選擇。以A A為例：若為例：若B B招供，招供，A A自己招供獲刑自己招供獲刑5 5年，不招供獲刑年，不招供獲刑

39、1010年；年；若若B B不招供，自己不招供，自己招供招供可以免刑，不招供獲刑可以免刑，不招供獲刑1 1年。兩年。兩種情況下，選擇種情況下，選擇招供招供都更有利，事實上卻比兩人都拒都更有利，事實上卻比兩人都拒不招供的結果糟。不招供的結果糟。 由囚徒困境可知，由囚徒困境可知，公共生活中，如果每個人都從眼前公共生活中，如果每個人都從眼前利益、個人利益出發(fā)，結果會對整體的利益利益、個人利益出發(fā)，結果會對整體的利益( (間接對個間接對個人的利益人的利益) )造成傷害。造成傷害。48 為解決為解決“囚徒困境囚徒困境”難題，美國曾組織競賽，要求參賽難題，美國曾組織競賽，要求參賽者根據(jù)者根據(jù)“重復囚徒困境重

40、復囚徒困境”(雙方不止一次相遇，雙方不止一次相遇，“背叛背叛”可能在以后遭到報復可能在以后遭到報復)來設計程序。來設計程序。 將程序輸入計算機反復互相博弈，以最終得分評估優(yōu)劣將程序輸入計算機反復互相博弈，以最終得分評估優(yōu)劣(雙方合作各得雙方合作各得3分；雙方背叛各得分；雙方背叛各得1分；一方合作一方分；一方合作一方背叛，合作方得背叛，合作方得0分，背叛方得分，背叛方得5分分)；有些程序采用有些程序采用“隨機隨機”對策；對策；有些采用有些采用“永遠背叛永遠背叛”對策；對策；有些采用有些采用“永遠合作永遠合作”對策；對策； 結果，加拿大多倫多大學的結果，加拿大多倫多大學的阿納托爾阿納托爾拉帕波特拉

41、帕波特教授的教授的“一報還一報一報還一報”策略奪得了最高分。策略奪得了最高分。49 我方在第一次相遇時選擇我方在第一次相遇時選擇“合作合作”，之后就采取對方上一，之后就采取對方上一次的選擇。這意味著：次的選擇。這意味著： 在對方每一次背叛后，我方就在對方每一次背叛后，我方就“以牙還牙以牙還牙”，也背叛一次；，也背叛一次； 對方每一次合作后，我方就對方每一次合作后，我方就“以德報德以德報德”一次；一次；論語論語憲問憲問中，有人問孔子：中，有人問孔子：“以德報怨，何如以德報怨，何如?”孔孔子反問：子反問：“何以報德何以報德?以直報怨，以德報德。以直報怨，以德報德。 該策略該策略有別于有別于“善良善

42、良”的的“永遠合作永遠合作”或或“邪惡邪惡”的的“永永遠背叛遠背叛”對策，及對方一旦對策，及對方一旦“不忠不忠”，我方就不再給機會，我方就不再給機會，長久對抗的策略長久對抗的策略。50 如果你選擇如果你選擇“永遠背叛永遠背叛”策略，你或許會在第一局拿到策略，你或許會在第一局拿到最高分，但之后的各局可能都只能拿到低分，最后雖最高分，但之后的各局可能都只能拿到低分，最后雖然可能然可能“戰(zhàn)勝戰(zhàn)勝”不少對手，但由于總分很低，最終難不少對手，但由于總分很低，最終難逃被淘汰出局的命運。逃被淘汰出局的命運。 所以除非很難與對方再次相遇，不用擔心其日后的反應，所以除非很難與對方再次相遇，不用擔心其日后的反應，

43、才可選擇對抗與背叛；才可選擇對抗與背叛； 而在而在長期互動、博弈長期互動、博弈的關系中，的關系中，“一報還一報一報還一報”是最佳是最佳策略：策略：它是善意的，從不首先背叛；它不迂腐，不管它是善意的，從不首先背叛；它不迂腐，不管過去相處多好，仍然對背叛有反應；它是寬容的，不過去相處多好，仍然對背叛有反應；它是寬容的，不因一次背叛而選擇玉石俱焚因一次背叛而選擇玉石俱焚。51計算機科學家效率觀念有非常精確的定義，通用計算機科學家效率觀念有非常精確的定義，通用的方式是討論如何盡量減少使用的資源來完成的方式是討論如何盡量減少使用的資源來完成任務任務可減少資源各有不同，但最重要的往往是可減少資源各有不同，但最重要的往往是時間時間重要的是尋找某種途徑，保證能夠任務完成而且重要的是尋找某種途徑，保證能夠任務完成而且使用盡可能少的步驟使用盡可能少的步驟紅綠球的換位游戲，如何使完成步驟最少？52計算機科學家是進行系統(tǒng)集成的專家計算機科學家是進行系統(tǒng)集成的專家不只是應用今天的技術，而且還創(chuàng)造明天的技