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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、在性證明。,9.6.3 數學中的證明方法,構造性證明 存在性證明示例：每個喜歡步行的人都不喜歡坐汽車；每個人或者喜歡坐汽車或者喜歡騎自行車；有的人不喜歡騎自行車，因而有的人不喜歡步行。 假設謂詞如下： 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) 結論：(x)(H(x)R(x),9.6.4 遞歸方法與迭代方法,遞歸方法 含義：一種在有限步驟內，根據特定的法則或公式對一個或多個前面的元素進行運算，以確定一系列元

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

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

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

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