1、第9章 計算機學科方法論,內(nèi)容來源 中國計算機學會計算機學科教程研究組發(fā)布 中國計算機科學與技術(shù)學科教程2002。 教育部計算機教學指導委員會編制 高等學校計算機發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范（2006）。 IEEE-CS/ACM發(fā)布 CC1991（Computing Curricular 1991）. CC2001, CC2004, CC2005.,第9章 計算機學科方法論,學習目的 深入理解計算機學科的本質(zhì)。 提高學習質(zhì)量。 提高科學研究和技術(shù)開發(fā)能力。 拓寬思路、強化知識的系統(tǒng)性、培養(yǎng)創(chuàng)新思維。 知識、方法、思想。,第9章 計算機學科方法論,9.1 計算機學科方法論簡介 9.2 計算機學科的

2、定義 9.3 計算機學科方法論 9.4 計算機學科的三個過程 9.5 計算機學科中的核心概念 9.6 計算機學科中的數(shù)學方法 9.7 計算機學科中的系統(tǒng)科學方法 9.8 本章小結(jié),9.1 計算機學科方法論簡介,計算機學科的發(fā)展 計算機專業(yè)教學背景,9.1.1 計算機學科的發(fā)展,計算機學科的劃分 計算機科學。 計算機工程/軟件工程。 信息系統(tǒng)/信息技術(shù)。 擴充之后的計算機學科也稱為計算學科（Computing Discipline）,知識體系的變化 計算機發(fā)展早期 數(shù)學/離散數(shù)學/電子學/程序設計。 20世紀60-70年代 數(shù)據(jù)結(jié)構(gòu)與算法/計算機組成原理。 編譯原理/操作系統(tǒng)/數(shù)據(jù)庫原理。 20

3、世紀80年代以后 并行技術(shù)/分布計算/網(wǎng)絡技術(shù)。 軟件工程/嵌入式系統(tǒng)。,9.1.1 計算機學科的發(fā)展,國際背景 1962年美國普渡大學 首開計算機學位課程。 1991年IEEE-CS/ACM發(fā)布 Computing Curricula 1991（CC1991）. 2001年IEEE-CS/ACM發(fā)布 Computing Curricula 2001（CC2001）. 目前演變成CC2004, CC2005.,9.1.2 計算機專業(yè)教學背景,國內(nèi)背景 專業(yè)設置 1956年哈爾濱工業(yè)大學首開計算裝置與儀器專業(yè)。 經(jīng)歷了計算機及應用、計算機軟件、計算機科學教育、計算機器件及設備等名稱的變化。 19

4、98年統(tǒng)一為計算機科學與技術(shù)專業(yè)。 從2001年開始又增設了軟件工程和網(wǎng)絡工程專業(yè)。 招生學校與人數(shù) 2004年全國有505所高校開辦有計算機本科專業(yè)，在校學生數(shù)近30萬人。,9.1.2計算機專業(yè)教學背景,國內(nèi)背景 教學計劃 2002年中國計算機學會計算機學科教程研究組發(fā)布 中國計算機科學與技術(shù)學科教程2002。 2006年教育部計算機教學指導委員會編制 高等學校計算機專業(yè)發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范。 2008年教育部計算機教學指導委員會編制 高等學校計算機科學與技術(shù)專業(yè)公共核心知識體系與課程。 高等學校計算機科學與技術(shù)專業(yè)實踐教學體系與規(guī)范。,9.1.2 計算機專業(yè)教學背景,計算的本質(zhì) 計算

5、機學科的根本問題,9.2 計算機學科的定義,9.2.1 計算的本質(zhì),圖靈描述了計算的本質(zhì) 計算就是計算者對一條兩端可無限延長的紙帶上的一串0和1執(zhí)行指令；一步一步地改變紙帶上的0或1；經(jīng)過有限步驟, 最后得到一個滿足預先規(guī)定的符號串的變換過程。 任一過程是能行的, 當且僅當它能夠被一臺圖靈機實現(xiàn)。 圖靈機反映的是一種具有能行性的用數(shù)學方法精確定義的計算模型，現(xiàn)代計算機正是這種模型的具體實現(xiàn)。,9.2.2 計算機學科的根本問題,計算機學科的定義 計算機學科是研究計算機的設計、制造和利用計算機進行信息獲取、表示、存儲、處理、控制等的理論、原則、方法和技術(shù)的學科，包括科學和技術(shù)兩方面。 計算機科學側(cè)

6、重于研究現(xiàn)象、揭示規(guī)律。 計算機技術(shù)側(cè)重于研制計算機和研究使用計算機進行信息處理的方法和手段。 科學與技術(shù)相輔相成，相互作用。,計算機學科還具有較強的工程性 理論教學與實踐教學并重。 基礎理論知識扎實/動手能力強。 計算機學科是科學性/工程性/技術(shù)性的統(tǒng)一 側(cè)重點不同的學科分支 計算機科學/計算機工程/軟件工程/信息技術(shù)。 計算機學科和數(shù)學密切相關(guān),9.2.2 計算機學科的根本問題,9.3 計算機學科方法論,計算機學科方法論的定義 計算機學科方法論的主要內(nèi)容 計算機學科方法論研究的意義,Computer Science,9.3.1 計算機學科方法論的定義,計算機學科方法論 對計算機領(lǐng)域認識和實

7、踐過程中一般方法及其性質(zhì)、特點、內(nèi)在聯(lián)系和變化規(guī)律進行系統(tǒng)研究的理論總結(jié)。 是認知計算機學科的方法和工具，也是計算機學科認知領(lǐng)域的理論體系。 對于計算機領(lǐng)域的科學研究、技術(shù)開發(fā)和人才培養(yǎng)具有重要指導意義。,9.3.2 計算機學科方法論的主要內(nèi)容,主要內(nèi)容 學科的三個過程 抽象過程/理論總結(jié)過程/設計過程。 重復出現(xiàn)的12個核心概念 綁定/大問題的復雜性/概念和形式模型。 一致性和完備性/效率/演化/抽象層次。 按空間排序/按時間排序/重用/安全性/折衷和結(jié)論。 典型的學科方法 數(shù)學方法/系統(tǒng)科學方法。,9.3.3 計算機學科方法論研究的意義,重要意義 有助于總結(jié)經(jīng)驗，促進計算機學科的快速發(fā)展。

8、 有助于確立正確的思維方式，把握正確的研究方向。 有助于計算機學科的建設和人才培養(yǎng) 。,9.4 計算機學科的三個過程,理論總結(jié)過程 科學理論是經(jīng)過實踐檢驗的系統(tǒng)化了的科學知識體系，它是由科學概念、科學原理以及對這些概念、原理的理論論證所組成的體系。 計算機學科的理論與數(shù)學所用的方法類似，主要要素為定義和公理、定理、證明、結(jié)果的解釋。 用這一過程來建立和理解計算機學科所依據(jù)的數(shù)學原理。其研究內(nèi)容的基本特征是構(gòu)造性數(shù)學特征。,9.4 計算機學科的三個過程,抽象過程 抽象是指在思維中對同類事物去除其現(xiàn)象的、次要的方面，抽取其共同的、主要的方面，從而做到從個別中把握一般，從現(xiàn)象中把握本質(zhì)的認知過程和思

9、維方法。 抽象源于現(xiàn)實世界, 是對現(xiàn)實原型的理想化。,9.4 計算機學科的三個過程,設計過程 用來開發(fā)求解給定問題的系統(tǒng)和設備。 包括需求分析、建立規(guī)格說明、設計并實現(xiàn)系統(tǒng)、對系統(tǒng)進行測試分析、修改完善等內(nèi)容。 三個過程貫穿計算機學科各個分支領(lǐng)域 圖論中體現(xiàn)的是抽象與理論過程。 軟件工程中綜合體現(xiàn)了設計、抽象與理論三個過程。,9.5 計算機學科中的核心概念,綁定（Binding） 通過把一個抽象的概念和附加特性相聯(lián)系，從而使抽象的概念具體化。 具體問題的抽象描述和抽象描述對具體問題的表示。 大問題的復雜性（Complexity of Large Problems） 隨著問題規(guī)模的增長而使求解該

10、問題的復雜性呈非線性增加的效應。 是區(qū)分和選擇各種現(xiàn)有方法和技術(shù)的重要因素。,9.5 計算機學科中的核心概念,概念和形式模型（Conceptual and Format Models） 對一個想法或問題進行形式化、特征化、可視化思維的各種方法。 計算機求解問題的基礎就是對問題的概念抽象和形式化描述。 概念和形式模型是實現(xiàn)計算機問題求解的最典型、最有效的途徑。,9.5 計算機學科中的核心概念,一致性和完備性（Consistency and Completeness） 一致性包括 一組公理的一致性/事實和理論的一致性。 一種語言或接口設計的內(nèi)部一致性。 完備性包括 給出的一組公理，使其能獲得預期行

11、為的充分性。 軟件和硬件系統(tǒng)功能的充分性。 系統(tǒng)處于出錯和非預期情況下保持正常行為的能力。 在計算機系統(tǒng)設計中，正確性、健壯性和可靠性就是一致性和完備性的具體體現(xiàn)。,9.5 計算機學科中的核心概念,效率（Efficiency） 關(guān)于空間、時間、人力、財力等資源消耗的度量。 在計算機軟硬件系統(tǒng)的設計實現(xiàn)中，要充分考慮效率問題。 要想在空間、時間、人力、財力各方面都達到最優(yōu)是不可能的，可以根據(jù)具體環(huán)境重點考慮某一方面達到最優(yōu)或考慮達到綜合最優(yōu)。,9.5 計算機學科中的核心概念,演化（Evolution） 系統(tǒng)的結(jié)構(gòu)、狀態(tài)、特征、行為和功能等隨著時間的推移而發(fā)生的更改。 對計算機硬件進行更新?lián)Q代，要

12、考慮到已有軟件的適應性，對軟件進行更新?lián)Q代，要考慮到現(xiàn)有硬件的適應性。 向下兼容是一種很好的演化模式。,9.5 計算機學科中的核心概念,抽象層次（Levels of Abstraction） 通過對不同層次的細節(jié)和指標的抽象，對一個系統(tǒng)或?qū)嶓w進行表述。 在復雜系統(tǒng)的設計中，對系統(tǒng)進行不同層次的抽象描述，從而既能控制系統(tǒng)的復雜程度，又能充分描述系統(tǒng)的特性。 在數(shù)據(jù)庫系統(tǒng)設計中，分層E-R圖的思想就是這一核心概念的具體應用。,9.5 計算機學科中的核心概念,按時間排序（Ordering in Time） 事件的執(zhí)行對時間的依賴性 在具有時態(tài)邏輯的系統(tǒng)中，要考慮與時間有關(guān)的時序問題。 在分布式系統(tǒng)中

13、，要考慮進程同步的時間問題。 在依賴于時間的算法執(zhí)行中，要考慮其基本的組成要素。,9.5 計算機學科中的核心概念,按空間排序（Ordering in Space） 各種定位方式 物理上的定位，如在網(wǎng)絡和存儲中的定位。 組織方式上的定位，如處理機進程、類型定義和有關(guān)操作的定位。 概念上的定位，如軟件的轄域、耦合、內(nèi)聚等。 是計算技術(shù)中一個局部性和相鄰性的概念。,9.5 計算機學科中的核心概念,重用（Reuse） 在新的環(huán)境下，系統(tǒng)中各類實體、技術(shù)、概念等可被再次使用的能力。 在軟件工程中，軟件重用是一個重要的研究領(lǐng)域，有著很好的應用前景。,9.5 計算機學科中的核心概念,安全性（Security

14、） 計算機軟硬件系統(tǒng)對合法用戶的響應及對非法請求的抗拒，以保護系統(tǒng)不受外部影響和攻擊的能力。 一旦遭受攻擊受損，系統(tǒng)恢復到正確狀態(tài)的能力。,9.5 計算機學科中的核心概念,折衷和結(jié)果（Tradeoff and Consequences） 折衷指的是為滿足系統(tǒng)的可實施性而對系統(tǒng)設計中的技術(shù)方案所作出的一種合理的取舍。 折衷的結(jié)果是指選擇一種方案代替另一種方案所產(chǎn)生的技術(shù)、經(jīng)濟、文化及其他方面的影響。 折衷存在于計算機學科領(lǐng)域的各個層次上。 在設計算法時，要考慮空間和時間的折衷。 在設計系統(tǒng)時，要考慮成本和可靠性的折衷。,9.6 計算機學科中的數(shù)學方法,數(shù)學的基本特征 數(shù)學方法的作用 數(shù)學中的證明

15、方法 遞歸方法與迭代方法 公理化方法 形式化方法,計算機數(shù)學,9.6.1 數(shù)學的基本特征,數(shù)學 研究現(xiàn)實世界的空間形式和數(shù)量關(guān)系的一門科學。 三個特征 高度的抽象性/嚴密的邏輯性/普遍的適用性。 算法(程序)設計的基礎是數(shù)學。,9.6.2 數(shù)學方法的作用,對科學技術(shù)研究的作用 提供簡潔精確的形式化語言 提供定量分析和計算的方法 提供嚴密的邏輯推理工具,9.6.3 數(shù)學中的證明方法,直接證明法 含義：假定A為真，通過使用公理或已證明的定理以及正確的推理規(guī)則證明B也為真，以此證明蘊含式AB為真。 示例：若n為奇數(shù)，則n+1為偶數(shù)。 證明：因為 n為奇數(shù)； 所以 n = 2k+1（k為整數(shù)）； 因此

16、有 n+1 = 2k+2 = 2（k+1）； 所以 n+1是偶數(shù)。,9.6.3 數(shù)學中的證明方法,反證法 含義：首先假定要證明的命題不成立，然后通過正確的推理得出與已知（或假設）條件、公理、定理等相互矛盾或自相矛盾的結(jié)果，以此證明假定要證明的命題不成立是錯誤的，成立才是正確的。 示例：若n2為奇數(shù)，則n為奇數(shù)。 證明：假定在n2為奇數(shù)的前提下，n為偶數(shù)； 則有 n = 2k（k為整數(shù)）； 于是有 n2 = (2k)2 = 4k2 = 2（2k2）； 則有 n2是偶數(shù)，與原假定n2為奇數(shù)矛盾； 所以假定n為偶數(shù)是錯誤的，n應為奇數(shù)。,9.6.3 數(shù)學中的證明方法,數(shù)學歸納法 含義：是一種用于證明

17、與自然數(shù)有關(guān)的命題正確性的證明方法，該方法能用有限的步驟解決無窮對象的論證問題。 示例：一棵非空二叉樹的第i層（i1）上最多有2i-1個結(jié)點。 證明：設i=1，由于此時二叉樹只有一個結(jié)點，而2i-1=20=1， 所以i=1時正確； 設i=k（k1）時結(jié)論正確，即第k層上有2k-1個結(jié)點； 那么，i=k+1時，第k+1層上最多有22k-1=2k=2（k+1）-1 個結(jié)點； 結(jié)論得以證明。,9.6.3 數(shù)學中的證明方法,構(gòu)造性證明 存在性證明 存在一個x使命題P(x)成立可表示為xP(x)，對形如 xP(x)的命題的證明。 構(gòu)造性證明 通過找出一個使得命題P(a)為真的元素a，從而完成該函數(shù)值的存

18、在性證明。,9.6.3 數(shù)學中的證明方法,構(gòu)造性證明 存在性證明示例：每個喜歡步行的人都不喜歡坐汽車；每個人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車，因而有的人不喜歡步行。 假設謂詞如下： H(x)：x是人； P(x)：x喜歡坐汽車； Q(x)：x喜歡騎自行車； R(x)：x喜歡步行。 則題目中的句子可符號化為： 前提： x ( H(x)R(x) P(x)， x( H(x) P(x)Q(x)， (x)(H(x)Q(x) 結(jié)論：(x)(H(x)R(x),9.6.4 遞歸方法與迭代方法,遞歸方法 含義：一種在有限步驟內(nèi)，根據(jù)特定的法則或公式對一個或多個前面的元素進行運算，以確定一系列元

19、素的方法。 示例： 數(shù)列的遞歸定義。 對于數(shù)列1，2，3，5，8，13，21，34，55，89， 可以給出如下遞歸定義公式： a1=1； a2=2； an=an-1+an-2 （n3）。,迭代方法 含義：迭代就是反復替換的意思。在程序設計中，為了處理重復性計算的問題，最常用的方法就是迭代方法。 示例：用如下公式求的近似值，直到最后一項的絕對值小于10-4為止。 計算過程：循環(huán)做累加操作，當然每次累加項的值是不一樣的，當累加項的絕對值小于10-4時循環(huán)累加結(jié)束。,9.6.4 遞歸方法與迭代方法,9.6.5 公理化方法,公理化方法 一種構(gòu)造理論體系的演繹方法，它是從盡可能少的基本概念、公理出發(fā)，運

20、用演繹推理規(guī)則，推導出一系列的命題，從而建立整個理論體系的思想方法。 用公理化方法構(gòu)建的理論體系稱為公理系統(tǒng)，公理系統(tǒng)需要滿足如下條件： 無矛盾性。 獨立性。 完備性。,9.6.6 形式化方法,具體公理系統(tǒng)和抽象公理系統(tǒng) 具體公理系統(tǒng)：有現(xiàn)實背景的公理系統(tǒng)。 抽象公理系統(tǒng)：沒有現(xiàn)實背景的公理系統(tǒng)。 形式化方法 形式化實質(zhì)上就是一個算法，即一個可機械地實現(xiàn)的過程，用于將概念、斷言、事實、規(guī)則、推演乃至整個被描述系統(tǒng)表述得嚴密、精確而又無需任何專門的知識即可被毫無歧義地感知。,9.6.6 形式化方法,形式系統(tǒng) 理論系統(tǒng)或?qū)嶋H系統(tǒng)形式化的產(chǎn)物，在這種系統(tǒng)中所進行的推演均可被機械地測試，以確定它們是否

21、是正確的。 形式系統(tǒng)的組成部分 初始符號/形式規(guī)則/公理/變形規(guī)則 對計算機學科的影響 圖靈機就是對計算的形式化描述。 一階謂詞演算形式系統(tǒng)為知識的形式表示及定理的機器證明奠定了重要基礎。,9.7 計算機學科中的系統(tǒng)科學方法,系統(tǒng)科學的基本思想 系統(tǒng)科學的基本概念 系統(tǒng)科學方法遵循的一般原則,9.7.1 系統(tǒng)科學的基本思想,系統(tǒng)科學的定義 人類對于復雜系統(tǒng)規(guī)律的認識的總結(jié)；它在自然科學與社會科學各領(lǐng)域的大量實際經(jīng)驗的基礎之上，總結(jié)出人類認識、描述、設計、管理、控制復雜系統(tǒng)的一般性的理念、方法與具體步驟，用以加深人類對于宇宙的認識，提高人們做事的效率和有效性。 系統(tǒng)科學與計算機學科 隨著計算機科

22、學技術(shù)的迅猛發(fā)展，計算機軟硬件系統(tǒng)變得越來越復雜，系統(tǒng)科學方法在計算機學科中的作用也日顯重要。,9.7.1 系統(tǒng)科學的基本思想,系統(tǒng)科學強調(diào)的重點 強調(diào)整體性。 注重動態(tài)和過程。 注重質(zhì)變。 注重層次之間的差別。 關(guān)注由活的主體組成的系統(tǒng)。 對于不確定性的關(guān)注和研究。 對于人為事物和做事方法的關(guān)注和研究。,9.7.2 系統(tǒng)科學的基本概念,系統(tǒng)和子系統(tǒng) 系統(tǒng)是指由相互聯(lián)系、相互作用的若干元素構(gòu)成的，具有特定功能的統(tǒng)一整體。 一個大的系統(tǒng)往往是復雜的，它通常可以劃分為若干個較小的系統(tǒng)，這些較小的系統(tǒng)稱為子系統(tǒng)。,9.7.2 系統(tǒng)科學的基本概念,結(jié)構(gòu)和結(jié)構(gòu)分析 結(jié)構(gòu)是指系統(tǒng)內(nèi)各組成部分（元素和子系統(tǒng)）之間相互聯(lián)系、相互作用的框架。 結(jié)構(gòu)分析的重要內(nèi)容就是劃分子系統(tǒng)，并研究各子系統(tǒng)的結(jié)構(gòu)以及各子系統(tǒng)之間的相互關(guān)系。,9.7.2 系統(tǒng)科學的基本概念,層次和層次分析 層次是指某個子系統(tǒng)在整個系統(tǒng)結(jié)構(gòu)中所處的相對位置。 在一個系統(tǒng)中，系統(tǒng)、子系統(tǒng)、更小的子系統(tǒng)是處在不同層次上的，并且相互之間存在層次關(guān)系，高層次包含和支配低層次，低層次隸屬和支撐高層次。 層次分析的主要內(nèi)容有：系統(tǒng)是否劃分層次，劃分了哪些層次，各層次的內(nèi)容，層次