第2章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科

1、計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院本章討論的主要問題是：本章討論的主要問題是：1. 什么是計(jì)算機(jī)學(xué)科？任何學(xué)科都具有抽象、理論和設(shè)計(jì)三什么是計(jì)算機(jī)學(xué)科？任何學(xué)科都具有抽象、理論和設(shè)計(jì)三個(gè)學(xué)科形態(tài)，如何理解計(jì)算機(jī)學(xué)科的學(xué)科形態(tài)？個(gè)學(xué)科形態(tài)，如何理解計(jì)算機(jī)學(xué)科的學(xué)科形態(tài)？2. 計(jì)算機(jī)學(xué)科的根本任務(wù)就是（自動(dòng)）計(jì)算，所有問題都可計(jì)算機(jī)學(xué)科的根本任務(wù)就是（自動(dòng)）計(jì)算，所有問題都可以被自動(dòng)計(jì)算嗎？如何判別可計(jì)算問題的資源消耗（例如計(jì)以被自動(dòng)計(jì)算嗎？如何判別可計(jì)算問題的資源消耗（例如計(jì)算時(shí)間）？算時(shí)間）？3. 宏觀上說，計(jì)算機(jī)學(xué)科存在哪些科學(xué)問題？科學(xué)問題的提宏觀上說，計(jì)算機(jī)學(xué)科存在哪些科學(xué)問題

2、？科學(xué)問題的提出和解決如何推動(dòng)了計(jì)算機(jī)學(xué)科的發(fā)展？出和解決如何推動(dòng)了計(jì)算機(jī)學(xué)科的發(fā)展？第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院情景問題情景問題學(xué)科的存在性證明學(xué)科的存在性證明n科學(xué)科學(xué)是關(guān)于自然、社會(huì)和思維的發(fā)展與變化規(guī)律的知識(shí)體是關(guān)于自然、社會(huì)和思維的發(fā)展與變化規(guī)律的知識(shí)體系，是由人類在生產(chǎn)活動(dòng)和社會(huì)活動(dòng)中產(chǎn)生和發(fā)展的，是系，是由人類在生產(chǎn)活動(dòng)和社會(huì)活動(dòng)中產(chǎn)生和發(fā)展的，是人類實(shí)踐經(jīng)驗(yàn)的結(jié)晶。人類實(shí)踐經(jīng)驗(yàn)的結(jié)晶。n學(xué)科學(xué)科是在科學(xué)發(fā)展中不斷分化和整合而形成和發(fā)展的，是是在科學(xué)發(fā)展中不斷分化和整合而形成和發(fā)展的，是科學(xué)研究發(fā)展成熟的產(chǎn)物?？茖W(xué)研究發(fā)

3、展成熟的產(chǎn)物。n科學(xué)研究是以問題為基礎(chǔ)的，只要有問題的地方就會(huì)有科科學(xué)研究是以問題為基礎(chǔ)的，只要有問題的地方就會(huì)有科學(xué)和科學(xué)研究。學(xué)和科學(xué)研究。n科學(xué)研究發(fā)展成熟成為一個(gè)獨(dú)立學(xué)科的標(biāo)志是：獨(dú)立的研科學(xué)研究發(fā)展成熟成為一個(gè)獨(dú)立學(xué)科的標(biāo)志是：獨(dú)立的研究內(nèi)容、成熟的研究方法、規(guī)范的學(xué)科體制。究內(nèi)容、成熟的研究方法、規(guī)范的學(xué)科體制。 科學(xué)與學(xué)科科學(xué)與學(xué)科計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院情景問題情景問題學(xué)科的存在性證明學(xué)科的存在性證明n1962年，美國普渡大學(xué)、斯坦福大學(xué)開設(shè)計(jì)算機(jī)科學(xué)學(xué)位年，美國普渡大學(xué)、斯坦福大學(xué)開設(shè)計(jì)算機(jī)科學(xué)學(xué)位課程。課程。n爭議：使用計(jì)算機(jī)是否需要進(jìn)行科學(xué)思考？計(jì)算機(jī)

4、科學(xué)能爭議：使用計(jì)算機(jī)是否需要進(jìn)行科學(xué)思考？計(jì)算機(jī)科學(xué)能否成為一門學(xué)科？計(jì)算機(jī)科學(xué)是理科還是工科？或者只是否成為一門學(xué)科？計(jì)算機(jī)科學(xué)是理科還是工科？或者只是一門技術(shù)、一個(gè)職業(yè)？一門技術(shù)、一個(gè)職業(yè)？n1985年春，年春，ACM和和IEEE-CS聯(lián)手組成攻關(guān)組，經(jīng)過近聯(lián)手組成攻關(guān)組，經(jīng)過近4年年的工作，攻關(guān)組提交了的工作，攻關(guān)組提交了計(jì)算作為一門學(xué)科計(jì)算作為一門學(xué)科（Computing as a Discipline）的報(bào)告。將當(dāng)時(shí)的計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工）的報(bào)告。將當(dāng)時(shí)的計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工程、計(jì)算機(jī)科學(xué)與工程、計(jì)算機(jī)信息學(xué)以及其他類似名稱程、計(jì)算機(jī)科學(xué)與工程、計(jì)算機(jī)信息學(xué)以及其他類似名稱的專業(yè)及

5、其研究范疇統(tǒng)稱為的專業(yè)及其研究范疇統(tǒng)稱為計(jì)算學(xué)科計(jì)算學(xué)科。 計(jì)算學(xué)科（計(jì)算機(jī)學(xué)科）計(jì)算學(xué)科（計(jì)算機(jī)學(xué)科）計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科學(xué)科的定義學(xué)科的定義n 計(jì)算機(jī)學(xué)科計(jì)算機(jī)學(xué)科是對(duì)是對(duì)描述和變換信息描述和變換信息的算法過程，包括對(duì)其理的算法過程，包括對(duì)其理論、分析、設(shè)計(jì)、效率、實(shí)現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究。它論、分析、設(shè)計(jì)、效率、實(shí)現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究。它來源于對(duì)算法理論、數(shù)理邏輯、計(jì)算模型、自動(dòng)計(jì)算機(jī)器的來源于對(duì)算法理論、數(shù)理邏輯、計(jì)算模型、自動(dòng)計(jì)算機(jī)器的研究，并與存儲(chǔ)式電子計(jì)算機(jī)的發(fā)明一起形成于研究，并與存儲(chǔ)式電子計(jì)算機(jī)的發(fā)明一

6、起形成于20世紀(jì)世紀(jì)40年年代初期。代初期。 n 計(jì)算機(jī)學(xué)科包括計(jì)算機(jī)學(xué)科包括科學(xué)科學(xué)和和技術(shù)技術(shù)兩個(gè)方面，二者高度融合是計(jì)兩個(gè)方面，二者高度融合是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的突出特點(diǎn)。（算機(jī)科學(xué)與技術(shù)學(xué)科的突出特點(diǎn)。（科學(xué)科學(xué)側(cè)重于研究現(xiàn)象、側(cè)重于研究現(xiàn)象、揭示規(guī)律；揭示規(guī)律；技術(shù)技術(shù)側(cè)重于研制計(jì)算機(jī)、研究使用計(jì)算機(jī)進(jìn)行信側(cè)重于研制計(jì)算機(jī)、研究使用計(jì)算機(jī)進(jìn)行信息處理的方法與技術(shù)手段。）息處理的方法與技術(shù)手段。）n 計(jì)算機(jī)學(xué)科是一門計(jì)算機(jī)學(xué)科是一門科學(xué)科學(xué)性與性與工程工程性并重的學(xué)科，表現(xiàn)為理性并重的學(xué)科，表現(xiàn)為理論和實(shí)踐緊密結(jié)合的特征。論和實(shí)踐緊密結(jié)合的特征。計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工

7、業(yè)學(xué)院n 所謂所謂學(xué)科形態(tài)學(xué)科形態(tài)是指從事一類學(xué)科研究與發(fā)展工作且具有共性是指從事一類學(xué)科研究與發(fā)展工作且具有共性的文化方式。的文化方式。n抽象抽象也稱模型化，是指在思維中對(duì)同類事物去除現(xiàn)象的、次也稱模型化，是指在思維中對(duì)同類事物去除現(xiàn)象的、次要的方面，抽取共同的、主要的方面，從而做到從個(gè)別中把要的方面，抽取共同的、主要的方面，從而做到從個(gè)別中把握一般、從現(xiàn)象中把握本質(zhì)的認(rèn)知過程和思維方法。握一般、從現(xiàn)象中把握本質(zhì)的認(rèn)知過程和思維方法。n抽象源于現(xiàn)實(shí)世界，它的研究內(nèi)容表現(xiàn)在兩個(gè)方面：抽象源于現(xiàn)實(shí)世界，它的研究內(nèi)容表現(xiàn)在兩個(gè)方面：（1）建立對(duì)客觀事物進(jìn)行抽象描述的方法；）建立對(duì)客觀事物進(jìn)行抽象描

8、述的方法；（2）采用現(xiàn)有的描述方法建立具體問題的概念模型，從而獲）采用現(xiàn)有的描述方法建立具體問題的概念模型，從而獲得對(duì)客觀世界的感性認(rèn)識(shí)。得對(duì)客觀世界的感性認(rèn)識(shí)。第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科學(xué)科形態(tài)學(xué)科形態(tài)抽象形態(tài)抽象形態(tài) 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院n理論理論是指為理解一個(gè)領(lǐng)域中對(duì)象之間的關(guān)系而構(gòu)建的基本是指為理解一個(gè)領(lǐng)域中對(duì)象之間的關(guān)系而構(gòu)建的基本概念和符號(hào)。概念和符號(hào)。n科學(xué)理論科學(xué)理論是經(jīng)過實(shí)踐檢驗(yàn)的系統(tǒng)化的科學(xué)知識(shí)體系，由科是經(jīng)過實(shí)踐檢驗(yàn)的系統(tǒng)化的科學(xué)知識(shí)體系，由科學(xué)概念、科學(xué)原理以及對(duì)這些概念、原理的理論論證所組成學(xué)概念、科學(xué)原理以及對(duì)這些概念、原理

9、的理論論證所組成的體系，表現(xiàn)為定義、定理和性質(zhì)及其證明。的體系，表現(xiàn)為定義、定理和性質(zhì)及其證明。n理論源于數(shù)學(xué)，它的研究內(nèi)容表現(xiàn)在兩個(gè)方面：理論源于數(shù)學(xué)，它的研究內(nèi)容表現(xiàn)在兩個(gè)方面：（1）建立完整的理論體系；）建立完整的理論體系；（2）在現(xiàn)有理論的指導(dǎo)下，建立具體問題的數(shù)學(xué)模型，從）在現(xiàn)有理論的指導(dǎo)下，建立具體問題的數(shù)學(xué)模型，從而實(shí)現(xiàn)對(duì)客觀世界的理性認(rèn)識(shí)。而實(shí)現(xiàn)對(duì)客觀世界的理性認(rèn)識(shí)。第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科學(xué)科形態(tài)學(xué)科形態(tài)理論形態(tài)理論形態(tài) 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院n設(shè)計(jì)設(shè)計(jì)是指構(gòu)造支持不同應(yīng)用領(lǐng)域的計(jì)算機(jī)系統(tǒng)。是指構(gòu)造支持不同應(yīng)用領(lǐng)域的計(jì)算機(jī)系統(tǒng)。n工程

10、設(shè)計(jì)具有較強(qiáng)的實(shí)踐性、社會(huì)性和綜合性，其實(shí)現(xiàn)要工程設(shè)計(jì)具有較強(qiáng)的實(shí)踐性、社會(huì)性和綜合性，其實(shí)現(xiàn)要受社會(huì)因素、客觀條件（包括其他相關(guān)學(xué)科）的影響。受社會(huì)因素、客觀條件（包括其他相關(guān)學(xué)科）的影響。n設(shè)計(jì)源于工程，它的研究內(nèi)容表現(xiàn)在兩個(gè)方面：設(shè)計(jì)源于工程，它的研究內(nèi)容表現(xiàn)在兩個(gè)方面：（1）在對(duì)客觀世界的感性認(rèn)識(shí)和理性認(rèn)識(shí)的基礎(chǔ)上，完成）在對(duì)客觀世界的感性認(rèn)識(shí)和理性認(rèn)識(shí)的基礎(chǔ)上，完成一個(gè)具體的工程任務(wù)；一個(gè)具體的工程任務(wù)；（2）對(duì)工程設(shè)計(jì)中遇到的問題進(jìn)行總結(jié)，提出問題由理論）對(duì)工程設(shè)計(jì)中遇到的問題進(jìn)行總結(jié)，提出問題由理論界去解決，同時(shí)，還要將工程設(shè)計(jì)中積累的經(jīng)驗(yàn)和教訓(xùn)進(jìn)界去解決，同時(shí)，還要將工程設(shè)計(jì)中

11、積累的經(jīng)驗(yàn)和教訓(xùn)進(jìn)行總結(jié)，形成方法去指導(dǎo)以后的工程設(shè)計(jì)。行總結(jié)，形成方法去指導(dǎo)以后的工程設(shè)計(jì)。設(shè)計(jì)形態(tài)設(shè)計(jì)形態(tài) 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科學(xué)科形態(tài)學(xué)科形態(tài)計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院三個(gè)形態(tài)之間的關(guān)系三個(gè)形態(tài)之間的關(guān)系 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科學(xué)科形態(tài)學(xué)科形態(tài)人類的認(rèn)識(shí)是從感性認(rèn)識(shí)（抽象）到理性認(rèn)識(shí)（理論），人類的認(rèn)識(shí)是從感性認(rèn)識(shí)（抽象）到理性認(rèn)識(shí)（理論），再由理性認(rèn)識(shí)（理論）回到實(shí)踐（工程設(shè)計(jì)）中來。再由理性認(rèn)識(shí)（理論）回到實(shí)踐（工程設(shè)計(jì)）中來。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院 核心概念是核心概念是CC1991報(bào)告首次提出的

12、，是具有報(bào)告首次提出的，是具有普遍性、持久性的重要思想、原則和方法，具有如普遍性、持久性的重要思想、原則和方法，具有如下基本特征：下基本特征：（1）在學(xué)科及各分支學(xué)科中普遍出現(xiàn)；）在學(xué)科及各分支學(xué)科中普遍出現(xiàn)；（2）在理論、抽象和設(shè)計(jì)的各個(gè)層面上都有很多）在理論、抽象和設(shè)計(jì)的各個(gè)層面上都有很多示例；示例；（3）在理論上具有可延展和變形的作用，在技術(shù)）在理論上具有可延展和變形的作用，在技術(shù)上有高度的獨(dú)立性。上有高度的獨(dú)立性。 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科核心概念核心概念計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院1. 綁定。綁定。綁定是通過將一個(gè)對(duì)象（或事物）與其某種屬性相綁定是

13、通過將一個(gè)對(duì)象（或事物）與其某種屬性相聯(lián)系，從而使抽象的概念具體化的過程。例如，將一個(gè)進(jìn)程聯(lián)系，從而使抽象的概念具體化的過程。例如，將一個(gè)進(jìn)程與一個(gè)處理機(jī)、一個(gè)變量與其類型或值分別聯(lián)系起來。這種與一個(gè)處理機(jī)、一個(gè)變量與其類型或值分別聯(lián)系起來。這種聯(lián)系的建立，實(shí)際上就是建立了某種約束。聯(lián)系的建立，實(shí)際上就是建立了某種約束。2. 大問題的復(fù)雜性大問題的復(fù)雜性。大問題的復(fù)雜性是指隨著問題規(guī)模的增。大問題的復(fù)雜性是指隨著問題規(guī)模的增長使問題的復(fù)雜性呈非線性增加的效應(yīng)。這種非線性增加的長使問題的復(fù)雜性呈非線性增加的效應(yīng)。這種非線性增加的效應(yīng)是區(qū)分和選擇各種現(xiàn)有方法和技術(shù)的重要因素。效應(yīng)是區(qū)分和選擇各種現(xiàn)

14、有方法和技術(shù)的重要因素。3. 概念和形式模型。概念和形式模型。概念和形式模型是對(duì)一個(gè)想法或問題進(jìn)概念和形式模型是對(duì)一個(gè)想法或問題進(jìn)行形式化、特征化、可視化思維的方法。例如，數(shù)據(jù)流圖和行形式化、特征化、可視化思維的方法。例如，數(shù)據(jù)流圖和E-R圖等都屬于概念模型，而邏輯理論、開關(guān)理論和計(jì)算理論圖等都屬于概念模型，而邏輯理論、開關(guān)理論和計(jì)算理論中的模型大都屬于形式模型。概念模型和形式模型以及形式中的模型大都屬于形式模型。概念模型和形式模型以及形式證明是將計(jì)算機(jī)學(xué)科各分支統(tǒng)一起來的重要核心概念。證明是將計(jì)算機(jī)學(xué)科各分支統(tǒng)一起來的重要核心概念。 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科核心概念核心概

15、念計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院4. 一致性和完備性一致性和完備性。一致性包括用于形式說明的一組公理的。一致性包括用于形式說明的一組公理的一致性、事實(shí)和理論的一致性，以及一種語言或接口設(shè)計(jì)的一致性、事實(shí)和理論的一致性，以及一種語言或接口設(shè)計(jì)的內(nèi)部一致性。完備性包括給出的一組公理的完備性、使其能內(nèi)部一致性。完備性包括給出的一組公理的完備性、使其能獲得預(yù)期行為的充分性、軟件和硬件系統(tǒng)功能的充分性，以獲得預(yù)期行為的充分性、軟件和硬件系統(tǒng)功能的充分性，以及系統(tǒng)處于出錯(cuò)和非預(yù)期情況下保持正常行為的能力等。及系統(tǒng)處于出錯(cuò)和非預(yù)期情況下保持正常行為的能力等。5. 效率效率。效率是關(guān)于時(shí)間、空間

16、、人力和財(cái)力等資源消耗的。效率是關(guān)于時(shí)間、空間、人力和財(cái)力等資源消耗的度量。在計(jì)算機(jī)軟硬件的設(shè)計(jì)中，要充分考慮某種預(yù)期結(jié)果度量。在計(jì)算機(jī)軟硬件的設(shè)計(jì)中，要充分考慮某種預(yù)期結(jié)果達(dá)到的效率，以及一個(gè)給定的實(shí)現(xiàn)過程較之替代的實(shí)現(xiàn)過程達(dá)到的效率，以及一個(gè)給定的實(shí)現(xiàn)過程較之替代的實(shí)現(xiàn)過程的效率。的效率。6. 演化演化。演化指的是系統(tǒng)的結(jié)構(gòu)、狀態(tài)、特征、行為和功能。演化指的是系統(tǒng)的結(jié)構(gòu)、狀態(tài)、特征、行為和功能等隨著時(shí)間的推移而發(fā)生的更改。這里主要指的是了解系統(tǒng)等隨著時(shí)間的推移而發(fā)生的更改。這里主要指的是了解系統(tǒng)更改的事實(shí)和意義以及應(yīng)采取的對(duì)策。更改的事實(shí)和意義以及應(yīng)采取的對(duì)策。第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)

17、科認(rèn)識(shí)計(jì)算機(jī)學(xué)科核心概念核心概念計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院7. 抽象層次抽象層次。抽象層次指的是通過對(duì)不同層次的細(xì)節(jié)和指標(biāo)。抽象層次指的是通過對(duì)不同層次的細(xì)節(jié)和指標(biāo)的抽象對(duì)一個(gè)系統(tǒng)或?qū)嶓w進(jìn)行表述。在復(fù)雜系統(tǒng)的設(shè)計(jì)中，的抽象對(duì)一個(gè)系統(tǒng)或?qū)嶓w進(jìn)行表述。在復(fù)雜系統(tǒng)的設(shè)計(jì)中，隱藏細(xì)節(jié)，對(duì)系統(tǒng)各層次進(jìn)行描述（抽象），從而控制系統(tǒng)隱藏細(xì)節(jié)，對(duì)系統(tǒng)各層次進(jìn)行描述（抽象），從而控制系統(tǒng)的復(fù)雜程度。的復(fù)雜程度。8. 按空間排序按空間排序。按空間排序指的是各種定位方式，如物理上。按空間排序指的是各種定位方式，如物理上的定位（如網(wǎng)絡(luò)和存儲(chǔ)中的定位），組織方式上的定位（如的定位（如網(wǎng)絡(luò)和存儲(chǔ)中的定位

18、），組織方式上的定位（如處理機(jī)進(jìn)程、類型定義和有關(guān)操作的定位）以及概念上的定處理機(jī)進(jìn)程、類型定義和有關(guān)操作的定位）以及概念上的定位（如軟件的轄域、耦合、內(nèi)聚等）。位（如軟件的轄域、耦合、內(nèi)聚等）。9. 按時(shí)間排序。按時(shí)間排序。按時(shí)間排序指的是事件的執(zhí)行對(duì)時(shí)間的依賴按時(shí)間排序指的是事件的執(zhí)行對(duì)時(shí)間的依賴性。例如，在具有時(shí)態(tài)邏輯的系統(tǒng)中，要考慮與時(shí)間有關(guān)的性。例如，在具有時(shí)態(tài)邏輯的系統(tǒng)中，要考慮與時(shí)間有關(guān)的時(shí)序問題，在分布式系統(tǒng)中，要考慮進(jìn)程同步的問題。時(shí)序問題，在分布式系統(tǒng)中，要考慮進(jìn)程同步的問題。第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科核心概念核心概念計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工

19、業(yè)學(xué)院10. 重用重用。重用指的是在新的環(huán)境下，系統(tǒng)中各類實(shí)體、技術(shù)、。重用指的是在新的環(huán)境下，系統(tǒng)中各類實(shí)體、技術(shù)、概念等可被再次使用的能力，如軟件庫和硬件部件的重用等。概念等可被再次使用的能力，如軟件庫和硬件部件的重用等。 11. 安全性安全性。安全性指的是計(jì)算機(jī)軟硬件系統(tǒng)對(duì)合法用戶的響。安全性指的是計(jì)算機(jī)軟硬件系統(tǒng)對(duì)合法用戶的響應(yīng)及對(duì)非法請(qǐng)求的抗拒，以保護(hù)系統(tǒng)不受外界影響和攻擊的應(yīng)及對(duì)非法請(qǐng)求的抗拒，以保護(hù)系統(tǒng)不受外界影響和攻擊的能力。能力。12. 折衷和結(jié)論折衷和結(jié)論。折衷指的是為滿足系統(tǒng)的可實(shí)施性而對(duì)系統(tǒng)。折衷指的是為滿足系統(tǒng)的可實(shí)施性而對(duì)系統(tǒng)設(shè)計(jì)中的技術(shù)、方案所做出的一種合理的取舍

20、。設(shè)計(jì)中的技術(shù)、方案所做出的一種合理的取舍。第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科核心概念核心概念計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院計(jì)算機(jī)學(xué)科的根本問題是：計(jì)算機(jī)學(xué)科的根本問題是：什么能被（有效地）自動(dòng)計(jì)算什么能被（有效地）自動(dòng)計(jì)算。這包含三個(gè)層次的問題：這包含三個(gè)層次的問題：（1）什么能被）什么能被自動(dòng)自動(dòng)計(jì)算？計(jì)算？ 可計(jì)算和不可計(jì)算?？捎?jì)算和不可計(jì)算。（2）什么能被）什么能被有效有效地自動(dòng)計(jì)算？地自動(dòng)計(jì)算？ 易解問題和難解問題。易解問題和難解問題。（3）進(jìn)一步研究可計(jì)算但不能有效計(jì)算的問題。）進(jìn)一步研究可計(jì)算但不能有效計(jì)算的問題。 NP問題和問題和NP完全問題。完全問題。

21、第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科學(xué)科根本問題學(xué)科根本問題計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院n 從字源上考察：從字源上考察：計(jì)：從言從十，有數(shù)數(shù)或計(jì)數(shù)的含義；計(jì)：從言從十，有數(shù)數(shù)或計(jì)數(shù)的含義；算：從竹從具，指計(jì)算工具。算：從竹從具，指計(jì)算工具。計(jì)算的原始含義是利用計(jì)算工具進(jìn)行計(jì)數(shù)。計(jì)算的原始含義是利用計(jì)算工具進(jìn)行計(jì)數(shù)。 n 直觀的計(jì)算：數(shù)的加減乘除；函數(shù)的微分、積分；微分方直觀的計(jì)算：數(shù)的加減乘除；函數(shù)的微分、積分；微分方程的求解；定理的證明推導(dǎo)等等。程的求解；定理的證明推導(dǎo)等等。n 計(jì)算的實(shí)質(zhì)：從一個(gè)符號(hào)串計(jì)算的實(shí)質(zhì)：從一個(gè)符號(hào)串 f（輸入）得出另一個(gè)符號(hào)串（輸入）得出另

22、一個(gè)符號(hào)串 g（輸出）。（輸出）。第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型什么是計(jì)算？什么是計(jì)算？計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院在在20世紀(jì)世紀(jì)40年代以前，可以這樣理解計(jì)算：年代以前，可以這樣理解計(jì)算： 計(jì)算計(jì)算 = = 算術(shù)算術(shù) = = 數(shù)值計(jì)算數(shù)值計(jì)算 計(jì)算機(jī)計(jì)算機(jī) = = 計(jì)算器計(jì)算器 = = 計(jì)算工具計(jì)算工具隨著計(jì)算機(jī)日益廣泛而深刻的應(yīng)用，計(jì)算這個(gè)原本隨著計(jì)算機(jī)日益廣泛而深刻的應(yīng)用，計(jì)算這個(gè)原本專門的數(shù)學(xué)概念被拓廣并泛化到了人類的整個(gè)知識(shí)專門的數(shù)學(xué)概念被拓廣并泛化到了人類的整個(gè)知識(shí)領(lǐng)域，應(yīng)該這樣理解計(jì)算：領(lǐng)域，應(yīng)該這樣理解計(jì)算： 計(jì)算計(jì)算 = = 數(shù)

23、值計(jì)算數(shù)值計(jì)算+ +非數(shù)值計(jì)算非數(shù)值計(jì)算 = = 符號(hào)變換符號(hào)變換 = = 數(shù)據(jù)處理數(shù)據(jù)處理 計(jì)算機(jī)計(jì)算機(jī) = = 數(shù)據(jù)處理機(jī)數(shù)據(jù)處理機(jī)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型什么是計(jì)算？什么是計(jì)算？計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院 從符號(hào)串從符號(hào)串“12+3”變換成符號(hào)串變換成符號(hào)串“15”加法；加法； 符號(hào)串符號(hào)串“x2”變換成符號(hào)串變換成符號(hào)串“2x”微分；微分； f 表示一組公理和推導(dǎo)規(guī)則，表示一組公理和推導(dǎo)規(guī)則，g 是一個(gè)定理，從是一個(gè)定理，從 f 到到 g 的的一系列變換一系列變換定理定理g的證明；的證明； f 代表一個(gè)英文句子，代表一個(gè)英文句子，g

24、 為含義相同的中文句子，從為含義相同的中文句子，從 f 到到 g 的變換的變換英文翻譯成中文；英文翻譯成中文； f 代表一個(gè)原始音頻文件，代表一個(gè)原始音頻文件，g為對(duì)應(yīng)的為對(duì)應(yīng)的mp3文件，從文件，從 f 到到 g的變換的變換數(shù)據(jù)壓縮；從數(shù)據(jù)壓縮；從 g 到到 f 的變換的變換解壓縮。解壓縮。 這些變換有什么共同點(diǎn)？這些變換有什么共同點(diǎn)？為什么他們都叫做計(jì)算？為什么他們都叫做計(jì)算？第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算的例子計(jì)算的例子計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院有限狀態(tài)有限狀態(tài) 控制器控制器工作帶工作帶n 一條無限長的工作帶：工作帶上的每個(gè)單元可以一條

25、無限長的工作帶：工作帶上的每個(gè)單元可以存放一個(gè)符號(hào)；所有允許出現(xiàn)的符號(hào)屬于一個(gè)預(yù)先存放一個(gè)符號(hào)；所有允許出現(xiàn)的符號(hào)屬于一個(gè)預(yù)先規(guī)定好的字母表。規(guī)定好的字母表。第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院 n 一個(gè)讀寫頭：讀寫頭可以左移一個(gè)單元、右移一一個(gè)讀寫頭：讀寫頭可以左移一個(gè)單元、右移一個(gè)單元或者保持不動(dòng)。個(gè)單元或者保持不動(dòng)。有限狀態(tài)有限狀態(tài) 控制器控制器工作帶工作帶第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院n 一個(gè)控制器：控制器在每個(gè)時(shí)刻處于一定狀態(tài)，一個(gè)控制器：控制

26、器在每個(gè)時(shí)刻處于一定狀態(tài)，當(dāng)讀寫頭從工作帶上讀出一個(gè)符號(hào)后，控制器就根當(dāng)讀寫頭從工作帶上讀出一個(gè)符號(hào)后，控制器就根據(jù)這個(gè)符號(hào)和當(dāng)時(shí)的機(jī)器狀態(tài)，指揮讀寫頭進(jìn)行讀據(jù)這個(gè)符號(hào)和當(dāng)時(shí)的機(jī)器狀態(tài)，指揮讀寫頭進(jìn)行讀寫或者移動(dòng)，并決定是否改變機(jī)器狀態(tài)。寫或者移動(dòng)，并決定是否改變機(jī)器狀態(tài)。有限狀態(tài)有限狀態(tài) 控制器控制器工作帶工作帶第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院計(jì)算與可計(jì)算計(jì)算與可計(jì)算所謂計(jì)算就是計(jì)算者（人或機(jī)器）對(duì)一條可以無限所謂計(jì)算就是計(jì)算者（人或機(jī)器）對(duì)一條可以無限延長的工作帶上的符號(hào)串執(zhí)行指令，一步一步地改延長的工作帶上的符號(hào)串執(zhí)

27、行指令，一步一步地改變工作帶上的符號(hào)串，經(jīng)過有限步驟，最后得到一變工作帶上的符號(hào)串，經(jīng)過有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號(hào)串的變換過程。個(gè)滿足預(yù)先規(guī)定的符號(hào)串的變換過程。 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院基本思想：使讀寫頭往返移動(dòng)，每往返移動(dòng)一次，就成對(duì)基本思想：使讀寫頭往返移動(dòng)，每往返移動(dòng)一次，就成對(duì)地對(duì)輸入符號(hào)串地對(duì)輸入符號(hào)串左端的一個(gè)左端的一個(gè)a和右端的一個(gè)和右端的一個(gè)b匹配并做標(biāo)匹配并做標(biāo)記。如果恰好把輸入符號(hào)串記。如果恰好把輸入符號(hào)串的所有符號(hào)都做了標(biāo)記，說的所有符號(hào)都做了標(biāo)記，說明左端的符號(hào)明左端的符號(hào)a

28、和右端的符號(hào)和右端的符號(hào)b的個(gè)數(shù)相等；否則，說明左的個(gè)數(shù)相等；否則，說明左端的符號(hào)端的符號(hào)a和右端的符號(hào)和右端的符號(hào)b的個(gè)數(shù)不相等，或者符號(hào)的個(gè)數(shù)不相等，或者符號(hào)a和和b交交替出現(xiàn)。替出現(xiàn)。 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型構(gòu)造一個(gè)識(shí)別符號(hào)串構(gòu)造一個(gè)識(shí)別符號(hào)串a(chǎn)nbn（n1）的圖靈機(jī)）的圖靈機(jī)控制器的操作指令（也就是程序）如下：控制器的操作指令（也就是程序）如下：(q0 a a R q0) (q0 b x L q1)(q1 x x L q1) (q1 a x R q2) (q1 B B H qN)(q2 x x R q2) (q2 b x L q1) (q2 B B

29、 L q3)(q3 x x L q3) (q3 a a H qN) (q3 B B H qF)計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型構(gòu)造一個(gè)識(shí)別符號(hào)串構(gòu)造一個(gè)識(shí)別符號(hào)串a(chǎn)nbn（n1）的圖靈機(jī)）的圖靈機(jī)控制器的指令序列對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)移圖，計(jì)算就是在執(zhí)行控制器的指令序列對(duì)應(yīng)一個(gè)狀態(tài)轉(zhuǎn)移圖，計(jì)算就是在執(zhí)行指令的過程進(jìn)行狀態(tài)的變化，也是指令的過程進(jìn)行狀態(tài)的變化，也是變換符號(hào)變換符號(hào)的過程。的過程。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1,

30、 a x R q2)(q1, B B H qN)(q2, x x R q2)程序程序假定假定n2，輸入符號(hào)串，輸入符號(hào)串a(chǎn)abb控控制制器器B a a b b B指令指令機(jī)器狀態(tài)機(jī)器狀態(tài)當(dāng)前讀當(dāng)前讀到的字符到的字符當(dāng)前寫當(dāng)前寫入的字符入的字符讀寫頭的動(dòng)作讀寫頭的動(dòng)作R:右移右移L:左移左移H:不動(dòng)不動(dòng)下一機(jī)器狀態(tài)下一機(jī)器狀態(tài)讀寫頭讀寫頭第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x

31、 R q2)讀寫頭讀寫頭程序程序控控制制器器B a a b b B讀寫頭掃描到符號(hào)讀寫頭掃描到符號(hào)a，則繼續(xù)往右走則繼續(xù)往右走 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭讀寫頭程序程序控控制制器器B a a b b B讀寫頭掃描到符號(hào)讀寫頭掃描到符號(hào)a，則繼續(xù)往右走則繼續(xù)往右走 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成

32、都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭讀寫頭程序程序控控制制器器B a a b b B讀寫頭掃描到符號(hào)讀寫頭掃描到符號(hào)b，將當(dāng)前單元寫入字符將當(dāng)前單元寫入字符x，并使讀寫頭往左走，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q1。 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q

33、2)(q1, B B H qN)(q2, x x R q2)讀寫頭讀寫頭程序程序控控制制器器B a a x b B讀寫頭掃描到符號(hào)讀寫頭掃描到符號(hào)b，將當(dāng)前單元寫入字符將當(dāng)前單元寫入字符x，并使讀寫頭往左走，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q1。 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭讀寫頭程序程序控控制制器器B a a x b B讀寫頭掃描到符號(hào)讀

34、寫頭掃描到符號(hào)a，則把則把a(bǔ)改為標(biāo)記改為標(biāo)記x，并使讀寫頭往右走，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q2 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭讀寫頭程序程序控控制制器器B a x x b B讀寫頭掃描到符號(hào)讀寫頭掃描到符號(hào)a，則把則把a(bǔ)改為標(biāo)記改為標(biāo)記x，并使讀寫頭往右走，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q2 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)

35、計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)讀寫頭讀寫頭程序程序控控制制器器B a x x b B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走則繼續(xù)往右走 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院(q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4

36、)讀寫頭讀寫頭程序程序控控制制器器B a x x b B若讀寫頭掃描到符號(hào)若讀寫頭掃描到符號(hào)b，則把則把b改為標(biāo)記改為標(biāo)記x，并使讀寫頭往左走，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q1 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B a x x x B若讀寫頭掃描到符號(hào)若讀寫頭掃描到符號(hào)b，則把則把b改為標(biāo)記改為標(biāo)記x，并使讀寫頭往左走，并使讀寫頭往左走，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q1 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1,

37、 B B H qN)(q2, x x R q2)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B a x x x B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走則繼續(xù)往左走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B a x x x B讀寫

38、頭掃描到符號(hào)讀寫頭掃描到符號(hào)a，則把則把a(bǔ)改為標(biāo)記改為標(biāo)記x，并使讀寫頭往右走，并使讀寫頭往右走，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q2； (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走則繼續(xù)往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1

39、)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走則繼續(xù)往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序

40、控控制制器器B x x x x B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往右走則繼續(xù)往右走 (q0, a a R q0) (q0, b x L q1)(q1, x x L q1)(q1, a x R q2)(q1, B B H qN)(q2, x x R q2)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x B讀寫頭掃描到空白符讀寫頭掃描到空白符B，說明符號(hào)說明符號(hào)b已處理完畢，已處理完畢，則把狀態(tài)改為則把狀態(tài)改為q3，并使讀寫頭往左走并使讀寫頭往左走 (q2, b x L q1)

41、(q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x B讀寫頭掃描到空白符讀寫頭掃描到空白符B，說明符號(hào)說明符號(hào)b已處理完畢，已處理完畢，則把狀態(tài)改為則把狀態(tài)改為q3，并使讀寫頭往左走并使讀寫頭往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)

42、科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走則繼續(xù)往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走則繼續(xù)往左走 (q2, b x L q1) (q2, B B L q3)(

43、q3, x x L q3)(q3, a a H qN)(q3, B B H q4)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x B讀寫頭掃描到標(biāo)記讀寫頭掃描到標(biāo)記x，則繼續(xù)往左走則繼續(xù)往左走 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院讀寫頭讀寫頭程序程序控控制制器器B x x x x

44、B讀寫頭掃描到空白符讀寫頭掃描到空白符B，說明符號(hào)說明符號(hào)a和和b已成對(duì)標(biāo)記，已成對(duì)標(biāo)記，轉(zhuǎn)移到狀態(tài)轉(zhuǎn)移到狀態(tài)q4，達(dá)到接受狀態(tài)。達(dá)到接受狀態(tài)。 (q2, b x L q1) (q2, B B L q3)(q3, x x L q3)(q3, a a H qN)(q3, B B H q4)第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院從圖靈模型我們看到了什么？從圖靈模型我們看到了什么？n圖靈模型在一定程度上反映了人類最基本的、最原始的圖靈模型在一定程度上反映了人類最基本的、最原始的計(jì)算能力，它的基本動(dòng)作非常簡單、機(jī)械、確定。因此，計(jì)算能力

45、，它的基本動(dòng)作非常簡單、機(jī)械、確定。因此，可以用真正的機(jī)器來實(shí)現(xiàn)圖靈機(jī)?？梢杂谜嬲臋C(jī)器來實(shí)現(xiàn)圖靈機(jī)。n程序并非必須順序執(zhí)行，指令中關(guān)于下一狀態(tài)的指定，程序并非必須順序執(zhí)行，指令中關(guān)于下一狀態(tài)的指定，實(shí)際上表明指令可以不按程序中所表示的順序執(zhí)行。這實(shí)際上表明指令可以不按程序中所表示的順序執(zhí)行。這意味著，雖然程序只能按線性順序來表示指令序列，但意味著，雖然程序只能按線性順序來表示指令序列，但程序的實(shí)際執(zhí)行可以與表示的順序不同。程序的實(shí)際執(zhí)行可以與表示的順序不同。n計(jì)算的對(duì)象、中間結(jié)果和最終結(jié)果都在帶上，程序則在計(jì)算的對(duì)象、中間結(jié)果和最終結(jié)果都在帶上，程序則在控制器中。這意味著什么？控制器中。這意

46、味著什么？第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科圖靈模型圖靈模型將做一件復(fù)雜事情的過程分解成許多簡單的、將做一件復(fù)雜事情的過程分解成許多簡單的、機(jī)械的步驟，你是否有過成功的經(jīng)驗(yàn)？機(jī)械的步驟，你是否有過成功的經(jīng)驗(yàn)？計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院可計(jì)算問題與不可計(jì)算問題可計(jì)算問題與不可計(jì)算問題第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科可計(jì)算問題可計(jì)算問題nTuring論題論題：一個(gè)問題是：一個(gè)問題是可計(jì)算的可計(jì)算的當(dāng)且僅當(dāng)它在圖靈機(jī)上當(dāng)且僅當(dāng)它在圖靈機(jī)上經(jīng)過經(jīng)過有限步驟有限步驟最后得到正確的結(jié)果。最后得到正確的結(jié)果。nTuring論題把人類面臨的所有問題劃分成兩類，一類是論題

47、把人類面臨的所有問題劃分成兩類，一類是可可計(jì)算計(jì)算的，另一類是的，另一類是不可計(jì)算不可計(jì)算的。的。nTuring論題中論題中“有限步驟有限步驟”是一個(gè)相當(dāng)寬松的條件，即使是一個(gè)相當(dāng)寬松的條件，即使需要計(jì)算幾個(gè)世紀(jì)的問題，在理論上也都是可計(jì)算的。因需要計(jì)算幾個(gè)世紀(jì)的問題，在理論上也都是可計(jì)算的。因此此Turing論題界定出的可計(jì)算問題幾乎包括了人類遇到的論題界定出的可計(jì)算問題幾乎包括了人類遇到的所有問題。所有問題。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院不可計(jì)算問題的典型例子不可計(jì)算問題的典型例子 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科可計(jì)算問題可計(jì)算問題n停機(jī)問題停機(jī)問題。給定一個(gè)

48、計(jì)算機(jī)程序和一個(gè)特定的輸入，判斷。給定一個(gè)計(jì)算機(jī)程序和一個(gè)特定的輸入，判斷該程序是否可以停機(jī)。如果停機(jī)問題是可計(jì)算的，那么編該程序是否可以停機(jī)。如果停機(jī)問題是可計(jì)算的，那么編譯系統(tǒng)就能夠在運(yùn)行程序之前檢查出程序中是否有死循環(huán)，譯系統(tǒng)就能夠在運(yùn)行程序之前檢查出程序中是否有死循環(huán)，事實(shí)上，當(dāng)一個(gè)程序處于死循環(huán)時(shí)，系統(tǒng)無法確切地知道事實(shí)上，當(dāng)一個(gè)程序處于死循環(huán)時(shí)，系統(tǒng)無法確切地知道它只是一個(gè)很慢的程序，還是一個(gè)進(jìn)入死循環(huán)的程序。它只是一個(gè)很慢的程序，還是一個(gè)進(jìn)入死循環(huán)的程序。n判斷一個(gè)程序中是否包含計(jì)算機(jī)病毒判斷一個(gè)程序中是否包含計(jì)算機(jī)病毒。實(shí)際的病毒檢測(cè)程。實(shí)際的病毒檢測(cè)程序做得很好，通常能夠確定

49、一個(gè)程序中是否包含特定的計(jì)序做得很好，通常能夠確定一個(gè)程序中是否包含特定的計(jì)算機(jī)病毒，至少能夠檢測(cè)現(xiàn)在已經(jīng)知道的那些病毒，但是算機(jī)病毒，至少能夠檢測(cè)現(xiàn)在已經(jīng)知道的那些病毒，但是心懷惡意的人總能開發(fā)出病毒檢測(cè)程序還不能夠識(shí)別出來心懷惡意的人總能開發(fā)出病毒檢測(cè)程序還不能夠識(shí)別出來的新病毒，換言之，不存在一個(gè)病毒檢測(cè)程序，能夠檢測(cè)的新病毒，換言之，不存在一個(gè)病毒檢測(cè)程序，能夠檢測(cè)出所有未來的新病毒。出所有未來的新病毒。計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院易解問題與難解問題易解問題與難解問題 第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科易解問題易解問題n 理論上可計(jì)算的問題不一定是實(shí)際可計(jì)算的

50、。理論上可計(jì)算的問題不一定是實(shí)際可計(jì)算的。n Cook論題論題：一個(gè)問題是實(shí)際可計(jì)算的當(dāng)且僅當(dāng)它在圖靈機(jī)：一個(gè)問題是實(shí)際可計(jì)算的當(dāng)且僅當(dāng)它在圖靈機(jī)上經(jīng)過上經(jīng)過多項(xiàng)式步驟多項(xiàng)式步驟得到正確的結(jié)果。得到正確的結(jié)果。n 易解問題易解問題：可以在多項(xiàng)式時(shí)間內(nèi)求解的問題，這類問題在：可以在多項(xiàng)式時(shí)間內(nèi)求解的問題，這類問題在可以接受的時(shí)間內(nèi)實(shí)現(xiàn)問題求解?？梢越邮艿臅r(shí)間內(nèi)實(shí)現(xiàn)問題求解。n 難解問題難解問題：需要指數(shù)時(shí)間求解的問題，這類問題的計(jì)算時(shí)：需要指數(shù)時(shí)間求解的問題，這類問題的計(jì)算時(shí)間隨著問題規(guī)模（輸入量的大?。┑脑鲩L而快速增長，即間隨著問題規(guī)模（輸入量的大?。┑脑鲩L而快速增長，即使中等規(guī)模的輸入，其計(jì)

51、算時(shí)間也是以世紀(jì)來衡量的。使中等規(guī)模的輸入，其計(jì)算時(shí)間也是以世紀(jì)來衡量的。計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院難解問題的典型例子難解問題的典型例子第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科易解問題易解問題漢諾塔問題：在世界剛被創(chuàng)建的時(shí)候有一座寶塔（塔漢諾塔問題：在世界剛被創(chuàng)建的時(shí)候有一座寶塔（塔A），其），其上有上有64個(gè)金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。個(gè)金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個(gè)寶塔（塔緊挨著這座塔有另外兩個(gè)寶塔（塔B和塔和塔C）。從世界創(chuàng)始之）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔日起，婆羅門的牧師們就一直在

52、試圖把塔A上的碟子移動(dòng)到塔上的碟子移動(dòng)到塔C上去，其間借助于塔上去，其間借助于塔B的幫助。每次只能移動(dòng)一個(gè)碟子，任的幫助。每次只能移動(dòng)一個(gè)碟子，任何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們完何時(shí)候都不能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們完成任務(wù)時(shí)，世界末日也就到了。成任務(wù)時(shí)，世界末日也就到了。計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院ABC難解問題的典型例子難解問題的典型例子第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科易解問題易解問題計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院ABC難解問題的典型例子難解問題的典型例子第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科易解問題易解問

53、題計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院難解問題的典型例子難解問題的典型例子第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科易解問題易解問題1212221222)0(21)1)2(2(21)1(2)(121121-=+=+=+-=+-=-nnnnhnhnhnhh(64) = 264-1=18,446,744,073,709,551,615 如果每秒移動(dòng)一次，則僧侶們一刻不停地來回移動(dòng)，則需要如果每秒移動(dòng)一次，則僧侶們一刻不停地來回移動(dòng)，則需要花費(fèi)花費(fèi)5849億年的時(shí)間；假定計(jì)算機(jī)以每秒億年的時(shí)間；假定計(jì)算機(jī)以每秒1000萬個(gè)碟子的速萬個(gè)碟子的速度進(jìn)行移動(dòng)，則需要花費(fèi)度進(jìn)行移動(dòng)，則需要花費(fèi)58

54、,490年的時(shí)間。年的時(shí)間。計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院證比求易證比求易第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科NP問題問題n 通常來說，求解一個(gè)問題往往比較困難，但驗(yàn)證一個(gè)問題相通常來說，求解一個(gè)問題往往比較困難，但驗(yàn)證一個(gè)問題相對(duì)來說就比較容易，也就是對(duì)來說就比較容易，也就是證比求易證比求易。n 從是否可以被驗(yàn)證的角度，計(jì)算復(fù)雜性理論將難解問題劃分從是否可以被驗(yàn)證的角度，計(jì)算復(fù)雜性理論將難解問題劃分為為NP問題和非問題和非NP問題。問題。n NP問題問題：可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的問題。：可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的問題。n NP完全問題完全問題：NP問題中有大量問題都具有這

55、樣的特性：可問題中有大量問題都具有這樣的特性：可以多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證，但是不知道是否可以在多項(xiàng)式時(shí)以多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證，但是不知道是否可以在多項(xiàng)式時(shí)間內(nèi)得到求解，同時(shí)，我們不能證明這些問題中的任何一個(gè)間內(nèi)得到求解，同時(shí)，我們不能證明這些問題中的任何一個(gè)無法在多項(xiàng)式時(shí)間內(nèi)得到求解，這類問題稱為無法在多項(xiàng)式時(shí)間內(nèi)得到求解，這類問題稱為NP完全問題。完全問題。 計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院NP完全問題的典型例子完全問題的典型例子第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科NP問題問題TSP問題（又稱貨郎擔(dān)問題、郵遞員問題、售貨員問題（又稱貨郎擔(dān)問題、郵遞員問題、售貨員問題）是數(shù)學(xué)

56、家克克曼于問題）是數(shù)學(xué)家克克曼于19世紀(jì)初提出的一個(gè)數(shù)學(xué)世紀(jì)初提出的一個(gè)數(shù)學(xué)問題，是指旅行家要旅行問題，是指旅行家要旅行n個(gè)城市然后回到出發(fā)城個(gè)城市然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。的路程最短。計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院8abdc23571否否 18adcba6否否 23adbca5是是 11acdba4否否 23acbda3是是 11abdca2否否 18abcda1是否最短是否最短路徑長度路徑長度路徑路徑序號(hào)序號(hào)NP完全問題的典型例子完全問題的典型例子第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)

57、科NP問題問題對(duì)于具有對(duì)于具有 n 個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的TSP問題，可能的解有問題，可能的解有 (n-1)!/2個(gè)。個(gè)。 10城市的城市的TSP問題有大約問題有大約180,000個(gè)可能解。個(gè)可能解。 20城市的城市的TSP問題有大約問題有大約60,000,000,000,000,000個(gè)可能解。個(gè)可能解。 50城市的城市的TSP問題有大約問題有大約1062個(gè)可能解。個(gè)可能解。計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院n 考慮考慮TSP問題的驗(yàn)證形式：給定一個(gè)正整數(shù)問題的驗(yàn)證形式：給定一個(gè)正整數(shù)k，是否存在一，是否存在一條路徑長度小于條路徑長度小于k的簡單回路。的簡單回路。n 假設(shè)有一個(gè)可以同時(shí)測(cè)

58、試所有可能答案的超級(jí)并行計(jì)算機(jī)，假設(shè)有一個(gè)可以同時(shí)測(cè)試所有可能答案的超級(jí)并行計(jì)算機(jī)，首先生成首先生成TSP問題的所有可能的回路，然后并行驗(yàn)證所有可問題的所有可能的回路，然后并行驗(yàn)證所有可能的答案，即把各個(gè)邊的代價(jià)加起來，驗(yàn)證路徑長度是否小能的答案，即把各個(gè)邊的代價(jià)加起來，驗(yàn)證路徑長度是否小于于k。顯然，這可以在多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證。顯然，這可以在多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證。NP完全問題的典型例子完全問題的典型例子第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科NP問題問題計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院n 科學(xué)問題的提出和解決是任何一個(gè)學(xué)科持續(xù)發(fā)展的動(dòng)力，科學(xué)問題的提出和解決是任何一個(gè)學(xué)科持

59、續(xù)發(fā)展的動(dòng)力，一個(gè)學(xué)科如果沒有科學(xué)問題需要解決，這個(gè)學(xué)科的生命也就一個(gè)學(xué)科如果沒有科學(xué)問題需要解決，這個(gè)學(xué)科的生命也就該結(jié)束了。該結(jié)束了。 n 在計(jì)算機(jī)學(xué)科各個(gè)分支學(xué)科方向的發(fā)展進(jìn)程中，存在一些在計(jì)算機(jī)學(xué)科各個(gè)分支學(xué)科方向的發(fā)展進(jìn)程中，存在一些在表現(xiàn)形式上雖然不同，但在科學(xué)哲學(xué)的解釋下本質(zhì)上是相在表現(xiàn)形式上雖然不同，但在科學(xué)哲學(xué)的解釋下本質(zhì)上是相同或相近的問題，即學(xué)科研究與發(fā)展普遍關(guān)心的基本問題。同或相近的問題，即學(xué)科研究與發(fā)展普遍關(guān)心的基本問題。 什么是科學(xué)問題什么是科學(xué)問題第第 2 章章 認(rèn)識(shí)計(jì)算機(jī)學(xué)科認(rèn)識(shí)計(jì)算機(jī)學(xué)科科學(xué)問題科學(xué)問題計(jì)算機(jī)導(dǎo)論計(jì)算機(jī)導(dǎo)論成都工業(yè)學(xué)院成都工業(yè)學(xué)院為了實(shí)現(xiàn)自動(dòng)計(jì)

60、算，人們首先想到要發(fā)明和制造自動(dòng)計(jì)算機(jī)器，為了實(shí)現(xiàn)自動(dòng)計(jì)算，人們首先想到要發(fā)明和制造自動(dòng)計(jì)算機(jī)器，不僅要在理論上提供計(jì)算的平臺(tái)不僅要在理論上提供計(jì)算的平臺(tái)觀察和描述計(jì)算的起點(diǎn)，觀察和描述計(jì)算的起點(diǎn)，而且要實(shí)際制造出能夠真正運(yùn)行的自動(dòng)計(jì)算機(jī)器。進(jìn)一步地，而且要實(shí)際制造出能夠真正運(yùn)行的自動(dòng)計(jì)算機(jī)器。進(jìn)一步地，從廣義計(jì)算的概念出發(fā)，計(jì)算的平臺(tái)在使用上還必須方便，例從廣義計(jì)算的概念出發(fā)，計(jì)算的平臺(tái)在使用上還必須方便，例如，計(jì)算模型、計(jì)算機(jī)體系結(jié)構(gòu)、實(shí)際的計(jì)算機(jī)系統(tǒng)、系統(tǒng)軟如，計(jì)算模型、計(jì)算機(jī)體系結(jié)構(gòu)、實(shí)際的計(jì)算機(jī)系統(tǒng)、系統(tǒng)軟件和工具軟件、高級(jí)程序設(shè)計(jì)語言、軟件開發(fā)工具與環(huán)境等都件和工具軟件、高級(jí)程序設(shè)