計算機科學導論基于計算思維的思想與方法計算機學科體系第二章新工科建設之路·計算機類系列教材01計算機學科體系的構建計算機學科體系的構建011.什么是科學從詞源上說，“科學”一詞的英文“Science"源于拉丁文Scientia，

意為知識和學問。中國《辭海》(1999年版)對科學的解釋是：科學是運用范疇、定理和定律等思維形式反映現實世界中各種現象的本質和運動規律的知識體系。《韋氏字典》中對科學的定義：科學是從確定研究對象的性質和規律這一且標出發，通過觀察、調查和實驗而得到的系統知識。一、科學與學科的概念計算機學科體系的構建012.什么是學科學科本身具有二重含義：首先是指相對獨立的知識體系或學術分類，含義較廣；其次是指為培養人才而設立的教學科目。我們通常意義上所講的學科既具有第一重含義的特征，又包含第二重含義的特征，特別指高等學校或研究部門為培養高級專門人才而設立的教學科目。一、科學與學科的概念計算機學科體系的構建013.學科與科學的關系“學科”與“科學”兩者之間有著自然和必然的關系：科學是以問題為基礎的，凡是有問題的地方就會有科學和科學研究；學科是在科學的發展中不斷分化和整合而形成的，是科學研究發展成熟的產物。但并不是所有的科學研究領域最后都能發展成為學科。一、科學與學科的概念計算機學科體系的構建01二、計算作為一門學科1.計算學科的起源1989年1月，該工作組提交了ComputingasaDiscipline(計算作為一門學科)的報告，其主要內容刊登在1989年1月的CommumicationsoftheACM(ACM通訊)雜志上。這個報告回答了計算學科中長期以來一直爭論的一些問題，完成了計算學科的“存在性”證明，確定了計算學科的“知識框架”體系以及對知識框架進行研究的思想方法。計算機學科體系的構建01二、計算作為一門學科2.計算學科的定義計算學科(ComputingDiscipline)是對信息描述和變換的算法過程(包括對其理論分析、設計、效率分析、實現和應用等)進行的系統研究。計算學科的研究包括了從算法與可計算性的研究以及可計算硬件和軟件的實際實現問題的研究。這樣，計算學科不但包括從總體上對算法和信息處理過程進行研究的內容，而且包括滿足給定規格要求的有效而可靠的軟件、硬件設計，包括所有科目的理論、研究、實驗方法和工程設計。計算機學科體系的構建01三、CC2005學科體系1.計算學科的分支學科CC2005中包含多個報告，并將計算學科劃分為5個分支學科，其構成如圖2-1所示。計算機學科體系的構建01三、CC2005學科體系2.計算機科學的課程體系ACM和IEEE-CS提出的計算機科學知識體系概念，為各分支學科體系的建立提供了范式，將各分支學科(也稱為專業方向)劃分為知識領域(Area)、知識單元(Unit)和知識點(Topic)三個層次：知識領域代表分支學科中的課程名稱；知識單元代表知識領域中的基礎內容，分為核心單元和選修單元，核心單元代表該學科都必須學習的基礎內容，選修單元代表該學科選擇學習的基礎內容；知識點代表知識單元中單獨的主題模塊。計算機學科體系的構建01四、CCC2002學科體系1.中國計算機教程我國計算機專業本科教育始于1956年哈爾濱工業大學開設的“計算裝置與儀器”專業，隨后許多大學相繼開設類似專業，經歷了計算機及應用、計算機軟件、計算機科學教育、計算機器件及設備等名稱的變化。1998年，教育部進行本科專業目錄調整，計算機類專業名稱統一為計算機科學與技術專業。從2001年開始，在原有專業的基礎上，增設了軟件工程專業和網絡工程專業。計算機學科體系的構建01四、CCC2002學科體系2.中國計算機專業規范(1)在計算機科學與技術專業名稱下，鼓勵不同的學校根據社會需求和自身實際情況，為學生提供不同人才培養類型的教學計劃和培養方案。(2)將人才培養的規格歸納為四個專業方向、三種類型：計算機科學(研究型)、計算機工程(工程型)、軟件工程(工程型)、信息技術(應用型)。(3)給出了4個專業方向的專業規范，包括培養目標和規格、教育內容和知識體系、辦學條件、主要參考指標、核心課程描述等內容。計算機學科體系的構建01四、CCC2002學科體系3.計算機科學與技術學科體系國務院學位委員會將計算機科學與技術學科劃分為一個一級學科和3個二級學科，如圖2-2所示。02計算機學科方法論計算機學科方法論021.計算機學科方法論的定義計算機學科方法論在哲學方法論和一般科學論方法論的指導下，對計算機領域認識和實踐過程中的一般方法、性質、特點、內在聯系和變化規律進行系統研究和理論總結。一、計算機學科方法論概念計算機學科方法論022.計算機學科方法論的體現(1)在計算機硬件方面：由以運算器為中的“馮·諾依曼結構”改進為以存儲器為中心的現代體系結構，并且采用流水線處理器系統、并行處理器系統、多處理器系統、精簡指令系統等。(2)在計算機軟件方面：由程序控制發展為用操作系統對硬件系統全面控制和管理。(3)在程序設計方面：程序設計語言由低級語言發展成為高級語言，由面向過程語言發展成為面向對象語言；程序設計方法由流程圖→模塊化→結構化，并由程序開發發展成為軟件工程。(4)在應用技術方面：科學計算→多媒體→數據處理→人工智能→數據庫→計算機網絡。一、計算機學科方法論概念計算機學科方法論023.計算機學科方法論的研究目前計算機學科方法論的研究成果主要體現在以下6個方面。(1)計算機學科的知識體系(2)計算機學科的三個形態(3)計算機學科的核心概念(4)計算機科學的典型方法(5)計算機學科的數學方法(6)計算思維方法一、計算機學科方法論概念計算機學科方法論02二、計算機學科的三個形態1.抽象形態抽象源于建模，是自然科學的根本，其研究內容：一是建立對客觀事物進行抽象描述的方法；二是采用統一的描述方法(符號化、圖形化語言)建立具體問題的概念模型，從而獲得對客觀世界的感性認識。抽象的基本步驟：數據采集和假設的形式說明→模型的構造與預測→實驗分析→結果分析，為可能的算法、數據結構和系統結構等構造模型時使用的過程。抽象的結果是概念、符號、模型。計算機學科方法論02二、計算機學科的三個形態2.理論形態理論源于數學，是數學的根本，其研究內容：一是建立完整的理論體系；二是在現有理論的指導下建立具體問題的數學模型，從而實現對客觀世界的理性認識，成為分析問題的思想指導。理論的基本步驟：定義→公理→定理→證明，使用形式化方法對事物進行嚴密的定義和論證。計算機學科方法論02二、計算機學科的三個形態3.設計形態設計源于工程，是工程的根本，所研究的內容包括：一是在對客觀世界的感性認識和理性認識的基礎上完成一個具體的任務；二是對工程設計中所遇到的問題進行總結、提出問題、由理論界去解決，并將工程設計中所積累的經驗和教訓進行總結，形成方法，以便指導以后的工程設計。設計的基本步驟：需求分析→建立規格說明→設計并實現該系統→對系統進行測試與分析。計算機學科方法論02二、計算機學科的三個形態4.三個形態之間的關系三個形態之間的相互關系如圖2-3所示。計算機學科方法論02三、計算機學科的核心概念計算機學科方法論02三、計算機學科的核心概念計算機學科方法論02四、計算機學科的典型方法(1)問題描述語義抽象(2)計算系統分層抽象(3)程序設計語言抽象(4)程序設計方法抽象1.抽象方法計算機學科方法論02四、計算機學科的典型方法構造是指由基本元素進行有機組合形成新的結構體，構造性是指結構體所呈現的基本要素和特性。構造性是計算機學科最本質的方法，在計算機學科中構造性方法可以概括為以下3個方面。(1)計算機系統的構造性(2)計算機語言的構造性(3)計算機數學的構造性2.構造性方法計算機學科方法論02四、計算機學科的典型方法公理化方法是一種構造理論體系的演繹方法，即從盡可能少的基本概念和公理出發，運用演繹推理規則推導出一系列的命題，從而建立整個理論體系。構造性是計算機軟/硬件系統的最基本特征，遞歸和迭代是最具代表性的構造性數學方法，已經被廣泛應用于計算機學科的各領域。用公理化構建的理論體系稱為公理系統，它是一套完整的理論法則，3.公理化方法計算機學科方法論02四、計算機學科的典型方法形式化方法是一種基于命題邏輯的數學方法，即采用數理邏輯證明的手段對計算機系統進行建模、規約、分析、推理和驗證，把各種具有不同內容的思維形式(命題和推理)加以比較，找出其中各個部分相互聯結的方式，如命題中包含概念彼此間的聯結，推理中則是各個命題之間的聯結，抽取出它們共同的形式結構，利用表達形式結構的符號語言，嚴密、精確而又毫無歧義地描述系統的方法。4.形式化方法計算機學科方法論02四、計算機學科的典型方法計算機學科中的系統科學方法主要體現在以下5個方面。(1)系統分析方法(2)信息甄別方法(3)功能模擬方法(4)黑盒檢驗方法(5)整體優化方法5.系統科學方法03計算機學科中的數學方法計算機學科中的數學方法031.數學方法的基本特征數學是研究現實世界的空間形式及其數量關系的一門學科，數學方法具有以下3個基本特征。(1)高度的抽象性(2)嚴密的邏輯性(3)普遍的實用性一、數學方法及其作用體現計算機學科中的數學方法032.數學方法的基本策略數學方法是一種科學方法，使用數學方法解決實際問題所涉及的基本策略可概括以下兩類。(1)歸納、演繹、類比方法：歸納是從個別到一般，演繹則是從一般到個別，兩者是認識過程中解決問題的兩個相反相成的方法，而類比是歸納和演繹的綜合運用。(2)分析、綜合、抽象方法：分析是把事物分解為各個部分并加以考察的方法；綜合是把事物看成一個有機整體來加以考察的方法。一、數學方法及其作用體現計算機學科中的數學方法033.數學方法的作用表現數學方法在科學技術方法論中的作用主要表現在以下3個方面。(1)為科學技術研究提供簡潔的形式化語言(2)為科學技術研究提供定量分析和計算方法(3)為科學技術研究提供嚴密的邏輯推理工具一、數學方法及其作用體現計算機學科中的數學方法031.直接證明法直接證明法是指假設命題A為真，通過使用公理或已證明的定理以及正確的推理規則證明B也為真，以此證明蘊涵式A→B為真。二、構造性數學與證明方法計算機學科中的數學方法032.間接證明法間接證明是相對于直接證明而言的，因為蘊涵式A→B為真與其逆否命題B→一4等價，因此可通過證明B→4來證明蘊涵式A→B為真。間接證明的常用方法是反證法，其證明過程是首先提出命題，然后設定反命題，并依據推理規則進行推演，以證明反命題的虛假。二、構造性數學與證明方法計算機學科中的數學方法033.數學歸納法數學歸納法是一種用于證明某個給定命題在整個自然數范圍內成立的方法。該方法是用“有限”的步驟解決“無窮”的對象的論證問題。數學歸納法的基本步驟為：當n=1時，顯然成立；當n=k時也成立；則當n=k+1時仍成立，則原命題對任意正整數均成立。二、構造性數學與證明方法計算機學科中的數學方法034.存在性證明存在性證明是指存在一個x使命題P(x)成立，并且可表示為

，我們把對形如

命題的證明稱為存在性證明。換句話說，存在性證明通常表現為間接證明，即假設所述對象不存在，就會導致矛盾。二、構造性數學與證明方法計算機學科中的數學方法035.構造性證明構造性證明是計算機科學中廣泛使用的一種證明方法，它是通過找出一個使得命題P(a)為真的元素a，從而完成該函數值的存在性證明。具體說，就是構造一個帶有命題所要求的特定性質的實例，以顯示具有該性質的物體或概念的存在性。二、構造性數學與證明方法計算機學科中的數學方法036.遞歸方法與迭代方法(1)遞歸方法：遞歸方法是在“有限”步驟內根據特定法則或公式對一個或多個前面的元素進行運算，以此確定一系列元素。(2)迭代方法：是通過反復替換處理的重復性計算問題。二、構造性數學與證明方法計算機學科中的數學方法03三、計算機學科的根本問題問題的可計算性是指什么是可計算的和不可計算的。由于數字計算機是一種離散結構，只能處理離散的或離散化了的數量關系，因此可計算性決定了計算機的體系結構和計算機所處理的對象都只能是離散型的，而非離散(連續)的對象必須轉化為離散型。1.問題的可計算性計算機學科中的數學方法03三、計算機學科的根本問題問題求解過程的能行性邏輯關系如圖2-4所示。2.計算過程的能行性計算機學科中的數學方法03三、計算機學科的根本問題計算結果的正確性是任何計算工具和計算方法研究中不可回避的問題，特別是使用自動計算機器進行的各種計算。一個問題在給出了能行的操作系列并解決了其效率問題之后，必須確保計算結果的正確性，否則，計算便毫無意義。3.計算結果的正確性04計算機學科的經典問題計算機學科的經典問題04一、現實意義上的不可計算問題——計算復雜性1.漢諾塔問題計算機學科的經典問題04一、現實意義上的不可計算問題——計算復雜性2.旅行商問題旅行商問題也被稱為旅行推銷員問題，是哈密頓和英國數學家柯克曼于19世紀初提出的一個數學問題：若干城市，任何兩個城市之間的距離都是確定的，現要求一旅行商從某城市出發，必須經過每個城市且只能在每個城市停留一次，最后回到原出發城市。計算機學科的經典問題04一、現實意義上的不可計算問題——計算復雜性3.四色問題四色問題又被稱為四色猜想或四色定理(Four-ColorTheorem)，1852年首先由英國大學生古思里(FrancisGuthrie)提出。4.P=NP?問題解決NP完全問題的可行方法是尋找具有多項式時間復雜度的近似算法，即求得的是最優解的近似解，但算法的復雜度大為降低，是可用于實際計算的算法。計算機學科的經典問題04二、理論意義上的可計算問題——計算機智能問題1.圖靈測試圖靈測試方法和過程為：由一個男人A、一個女人B和一個性別不限的提問者c來完成。提問者C待在與兩個回答者相隔離的房間里，如圖2-14所示。計算機學科的經典問題04二、理論意義上的可計算問題——計算機智能問題2.西爾勒中文小屋與人工智能有關的另一