計算機科學(xué)導(dǎo)論-基于計算思維的思想與方法（第4版） 課件【ch02】計算機學(xué)科體系

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

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

，我們把對形如

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