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

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

2.1什么是計(jì)算機(jī)學(xué)科

2.2計(jì)算機(jī)學(xué)科的科學(xué)問題

2.3計(jì)算機(jī)學(xué)科的經(jīng)典問題

2.4計(jì)算機(jī)學(xué)科的知識(shí)體系

什么是計(jì)算

■從字源上考察：

計(jì)：從言從十，有數(shù)數(shù)或計(jì)數(shù)的含義;

算：從竹從具，指計(jì)算工具。

■《現(xiàn)代漢語詞典》對(duì)計(jì)算的定義：

根據(jù)已知數(shù)通過數(shù)學(xué)方法求得未知數(shù)。

什么是計(jì)算

■直觀的計(jì)算：數(shù)的加減乘除；函數(shù)的微分、積

分；微分方程的求解；定理的證明推導(dǎo)等等。

■計(jì)算的實(shí)質(zhì)：從一個(gè)符號(hào)串/（輸入）得出另

一個(gè)符號(hào)串g（輸出）。

■數(shù)學(xué)概念一普適概念

計(jì)算的例子

A從符號(hào)串“12+3”變換成符號(hào)串“15”——加法計(jì)

算

?符號(hào)串變換成符號(hào)串——微分；

?/表示一組公理和推導(dǎo)規(guī)則，g是一個(gè)定理，那么

從f到g的一系列變換——定理g的證明；

?符號(hào)串/代表一個(gè)英文句子，符號(hào)串g為含義相

同的中文句子，那么從/到g的變換——英文翻

磁中暹變換有什么共同點(diǎn)？

儂為什么他們都叫做計(jì)算？

圖靈與巨人計(jì)算機(jī)

>5

圖靈模型

有限狀態(tài)

控制器

工作帶

■一條無限長(zhǎng)的工作帶：工作帶上的每個(gè)單元可以

存放一個(gè)符號(hào)；所有允許出現(xiàn)的符號(hào)屬于一個(gè)預(yù)先

規(guī)定好的字母表。

圖靈模型

有限狀態(tài)

控制器

工作帶

■一個(gè)讀寫頭：讀寫頭可以左移一個(gè)單元、右移一

個(gè)單元或者保持不動(dòng)。

圖靈模型

有限狀態(tài)

控制器

1

工作帶

■一個(gè)控制器：控制器在每個(gè)時(shí)刻處于一定的狀態(tài),

當(dāng)讀寫頭從工作帶上讀出一個(gè)符號(hào)后，控制器就根

據(jù)這個(gè)符號(hào)和當(dāng)時(shí)的機(jī)器狀態(tài)，指揮讀寫頭進(jìn)行讀

寫或者移動(dòng)，并決定是否改變機(jī)器狀態(tài)。

計(jì)算與可計(jì)算

所謂計(jì)算就是計(jì)算者（人或機(jī)器）對(duì)一條可以無

限延長(zhǎng)的工作帶上的符號(hào)串執(zhí)行指令，一步一步

地改變工作帶上的符號(hào)串，經(jīng)過有限步驟，最后

得到一個(gè)滿足預(yù)先規(guī)定的符號(hào)串的變換過程。

什么樣的任務(wù)才是可計(jì)算的任務(wù)？這是計(jì)算機(jī)科

學(xué)必須要回答的一個(gè)最基本的問題。這是關(guān)系到

計(jì)算機(jī)能做什么、不能做什么的根本問題。

類比：什么樣的衣服才是洗衣機(jī)可洗的？

用圖靈模型來計(jì)算

構(gòu)造一個(gè)識(shí)別符號(hào)串口=仍〃（〃21）的圖靈機(jī)

基本思想：使讀寫頭往返移動(dòng)，每往返移動(dòng)一

次，就成對(duì)地對(duì)輸入符號(hào)串。左端的一個(gè)4和右

端的一個(gè)〃匹配并做標(biāo)記心如果恰好把輸入符

號(hào)串。的所有符號(hào)都做了標(biāo)記，說明左端的符號(hào)

。和右端的符號(hào)〃的個(gè)數(shù)相等；否則，說明左端

的符號(hào)〃和右端的符號(hào)〃的個(gè)數(shù)不相等，或者符

號(hào)〃和力交替出現(xiàn)。

用圖靈模型來計(jì)算

假定〃=2,輸入符號(hào)串”=的防

工作帶BaabbB

指令

機(jī)器狀態(tài)

---------------------------S

、^當(dāng)前數(shù)器狀態(tài)

的字符

當(dāng)前讀

到的字筠讀寫頭的動(dòng)作

R:右移L：左移H:不動(dòng)

用圖靈模型來計(jì)算

子母表：

讀寫頭{a,b,B}

工作帶BaabbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)

制讀寫頭掃描到符號(hào)處

(夕1,xxLql)

器則繼續(xù)往右走

(夕1,axRql)

(夕1,BBHqN)

(夕2,xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BaabbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)

制讀寫頭掃描到符號(hào)處

(夕1,xxLql)

器則繼續(xù)往右走

(夕1,axRql)

(夕

1,BBHqN)

(夕2,xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BaabbB

程序

（夕0,aaR夕0）

控（夕0,bxL夕1）讀寫頭掃描到符號(hào)兒

制（夕1,xxL夕1）將當(dāng)前單元寫入字符X,

器

（夕1,axR夕2）并使讀寫頭往左走，

轉(zhuǎn)移到狀態(tài)夕。

（夕1,BBHqJ1

（夕2,xxR夕2）

用圖靈模型來計(jì)算

讀寫頭

工作市BaaxbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)讀寫頭掃描到符號(hào)兒

制(夕1,xxLql)將當(dāng)前單元寫入字符x,

器

(夕1,axRql)并使讀寫頭往左走，

(ql,BBHqJ轉(zhuǎn)移到狀態(tài)夕1。

(夕2,xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BaaxbB

程序

（夕0,aaR夕0）

控讀寫頭掃描到符號(hào)小

（夕0,bxL夕1）

制貝時(shí)巴〃改為標(biāo)記X,

（夕LxxLql）

器并使讀寫頭往右走，

（夕夕）

1,axR2轉(zhuǎn)移到狀態(tài)夕2

（夕1,BBHqJ

（夕2,xxR夕2）

用圖靈模型來計(jì)算

讀寫頭

工作市BaxxbB

程序

（夕0,aaR夕0）

控讀寫頭掃描到符號(hào)小

（夕0,bxL夕1）

制貝時(shí)巴〃改為標(biāo)記X,

（夕LxxLql）

器并使讀寫頭往右走，

（夕夕）

1,axR2轉(zhuǎn)移到狀態(tài)夕2

（夕1,BBHqJ

（夕2,xxR夕2）

用圖靈模型來計(jì)算

讀寫頭

工作市BaxxbB

程序

(夕0,aaR夕0)

控讀寫頭掃描到標(biāo)記x,

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(夕2,xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作帶BaxxbB

程序

（夕2,bxL夕1）

控若讀寫頭掃描到符號(hào)

（夕2,BBLq3）A,

制貝」把改為標(biāo)記達(dá)

（夕3,xxL夕3）I6

器并使讀寫頭往左走，

（夕3,aaH如）轉(zhuǎn)移到狀態(tài)貝

（夕3,BBHq4）

用圖靈模型來計(jì)算

讀寫頭

工作市BaxxxB

程序

(夕0,aaR夕0)

控若讀寫頭掃描到符號(hào)A,

(夕0,bxL夕1)

制貝I」把6改為標(biāo)記x,

(夕1,xxLql)

器并使讀寫頭往左走，

(夕1,axRql)轉(zhuǎn)移到狀態(tài)貝

(ql,BBHqJ

(夕2,xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BaxxxB

程序

(夕0,aaR夕0)

控讀寫頭掃描到標(biāo)記x,

(夕0,bxL夕1)

制則繼續(xù)往左走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(夕2,xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BaxxxB

程序

（夕0,aaR夕0）

控讀寫頭掃描到符號(hào)小

（夕0,bxL夕1）

制貝時(shí)巴〃改為標(biāo)記X,

（夕LxxLql）

器并使讀寫頭往右走，

（夕夕）

1,axR2轉(zhuǎn)移到狀態(tài)夕2；

（夕1,BBHqJ

（夕2,xxR夕2）

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

(夕0,aaR夕0)

控讀寫頭掃描到標(biāo)記x,

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

(夕0,aaR夕0)

控讀寫頭掃描到標(biāo)記x,

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

(夕0,aaR夕0)

控讀寫頭掃描到標(biāo)記x,

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

(夕2,bxLql)

控(夕2,BBLq3)讀寫頭掃描到空白符5,

制(夕3,xxL夕3)說明符號(hào)A已處理完畢,

器則把狀態(tài)改為夕3,

(夕3,aaH如)并使讀寫頭往左走

(夕3,BBHq4)

平用圖靈模型來計(jì)算

讀寫頭

工作帶BxxxXB

程序

（夕2,bxL夕1）

控讀寫頭掃描到空白符5,

（夕2,BBLq3）

制說明符號(hào)A已處理完畢,

（夕3,xxL夕3）

器則把狀態(tài)改為夕3,

（夕3,aaHqQ并使讀寫頭往左走

（夕3,BBHq4）

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

控讀寫頭掃描到標(biāo)記

（夕2,BBLq3）x

制則繼續(xù)往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

控讀寫頭掃描到標(biāo)記

（夕2,BBLq3）x

制則繼續(xù)往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

控讀寫頭掃描到標(biāo)記

（夕2,BBLq3）x

制則繼續(xù)往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用圖靈模型來計(jì)算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

控讀寫頭掃描到空白符以

（夕2,BBLq3）

制說明符號(hào)〃和〃已成對(duì)標(biāo)記,

（夕3,xxL夕3）

器轉(zhuǎn)移到狀態(tài)夕4,

（夕3,aaH如）達(dá)到接受狀態(tài)。

（夕3,BBHq4）

從圖靈機(jī)我們看到了什么?

■圖靈機(jī)在一定程度上反映了人類最基本的、最原始的

計(jì)算能力，它的基本動(dòng)作非常簡(jiǎn)單、機(jī)械、確定。因

止匕有條件用真正的機(jī)器來實(shí)現(xiàn)圖靈機(jī)。

■程序并非必須順序執(zhí)行，指令中關(guān)于下一狀態(tài)的指定,

實(shí)際上表明指令可以不按程序中所表示的順序執(zhí)行。

這意味著，雖然程序只能按線性順序來表示指令序列,

但程序的實(shí)際執(zhí)行可以與表示的順序不同。

-計(jì)算的對(duì)象、中間結(jié)果和最終結(jié)果都在帶上，程序則

在控制器中。這意味著什么？

思考：將做一件復(fù)雜事情的過程分解成許多簡(jiǎn)

單的、機(jī)械的步驟，你是否有過成功的經(jīng)驗(yàn)？

科學(xué)與學(xué)科

科學(xué)是關(guān)于自然、社會(huì)和思維的發(fā)展與變化規(guī)律的知識(shí)體

系，是由人類在生產(chǎn)活動(dòng)和社會(huì)活動(dòng)中產(chǎn)生和發(fā)展的，是人類

實(shí)踐經(jīng)驗(yàn)的結(jié)晶。

（1）科學(xué)是逐步發(fā)展起來的

（2）科學(xué)的發(fā)展需要某種特殊的方法

（3）科學(xué)在不斷超越中永無止境地發(fā)展

學(xué)科本身具有二重含義：

（1）指知識(shí)體系或?qū)W術(shù)分類，含義較廣；

（2）指為培養(yǎng)人才而設(shè)立的教學(xué)科目。

科學(xué)與學(xué)科

■科學(xué)研究是以問題為基礎(chǔ)的，學(xué)科是在科學(xué)

發(fā)展中不斷分化和整合而形成和發(fā)展的，是

科學(xué)研究發(fā)展成熟的產(chǎn)物。

-科學(xué)研究發(fā)展成熟而成為一個(gè)獨(dú)立學(xué)科的標(biāo)

志是：必須有獨(dú)立的研究?jī)?nèi)容、成熟的研究

方法、規(guī)范的學(xué)科體制。

計(jì)算機(jī)學(xué)科的定義

計(jì)算機(jī)學(xué)科是對(duì)描述和變換信息的算法

過程，包括對(duì)其理論、分析、設(shè)計(jì)、效率、

實(shí)現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究。

它來源于對(duì)算法理論、數(shù)理邏輯、計(jì)算

模型、自動(dòng)計(jì)算機(jī)器的研究，并與存儲(chǔ)式電

子計(jì)算機(jī)的發(fā)明一起形成于20世紀(jì)40年代初

期。

計(jì)算機(jī)學(xué)科的特點(diǎn)

■計(jì)算機(jī)學(xué)科包括科學(xué)和技術(shù)兩個(gè)方面。

A科學(xué)側(cè)重于研究現(xiàn)象、揭示規(guī)律；

A技術(shù)則側(cè)重于研制計(jì)算機(jī)、研究使用計(jì)算機(jī)

進(jìn)行信息處理的方法與技術(shù)手段。

■科學(xué)是技術(shù)的依據(jù)，技術(shù)是科學(xué)的體現(xiàn)。

■二者高度融合是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的突

出特點(diǎn)。

■計(jì)算機(jī)學(xué)科是一門科學(xué)性與工程性并重的學(xué)

科，表現(xiàn)為理論和實(shí)踐緊密結(jié)合的特征。

計(jì)算機(jī)學(xué)科的特點(diǎn)

■科學(xué)：關(guān)于自然、社會(huì)和思維的發(fā)展與變化

規(guī)律的知識(shí)體系，其核心是發(fā)現(xiàn)。

■技術(shù)：根據(jù)實(shí)踐經(jīng)驗(yàn)和科學(xué)原理而發(fā)展形成

的各種工藝操作方法、技能和技巧，其核心

是發(fā)明。

■工程：將科學(xué)原理應(yīng)用到生產(chǎn)實(shí)踐中，是某

種形式的科學(xué)應(yīng)用，其核心是建造。

計(jì)算機(jī)學(xué)科的根本問題

■計(jì)算機(jī)學(xué)科的根本問題是：什么能被（有

效地）自動(dòng)計(jì)算。

■計(jì)算機(jī)學(xué)科所有分支領(lǐng)域的根本任務(wù)就是

進(jìn)行計(jì)算，其實(shí)質(zhì)就是字符串的變換。

計(jì)算機(jī)學(xué)科的符號(hào)化特征

?一一一一一一一一一一一一一一一一一」

計(jì)算機(jī)學(xué)科與其他學(xué)科的關(guān)系

■計(jì)算機(jī)學(xué)科是在數(shù)學(xué)和電子學(xué)基礎(chǔ)上發(fā)展

起來的。

■計(jì)算機(jī)學(xué)科的發(fā)展也必然受制于其它學(xué)科

的發(fā)展。

■計(jì)算機(jī)學(xué)科可以在幾乎所有的學(xué)科領(lǐng)域，

甚至我們?nèi)粘Ｉ畹母鱾€(gè)方面找到應(yīng)用。

什么是科學(xué)問題

科學(xué)問題是指一定時(shí)代的科學(xué)認(rèn)識(shí)主體，在已完

成的科學(xué)知識(shí)和科學(xué)實(shí)踐的基礎(chǔ)上，提出的需要解決

且有可能解決的問題，它包含一定的求解目標(biāo)和應(yīng)答

域，但尚無確定的答案。

科學(xué)問題具有如下主要特征：

（1）時(shí)代性（2）混沌性（3）可解決性（4）

可變異性（5）可待解性

科學(xué)問題的提出和解決是任何一個(gè)學(xué)科持續(xù)發(fā)展

的動(dòng)力。

計(jì)算機(jī)學(xué)科的科學(xué)問題

1.計(jì)算的平臺(tái)與環(huán)境問題

核心：計(jì)算問題的能行性

2.計(jì)算過程的能行操作與效率問題

核心：算法及算法分析

3.計(jì)算的正確性問題

核心：各種語言的語義

上述基本問題普遍出現(xiàn)在學(xué)科的各個(gè)分支

學(xué)科和研究方向之中，是學(xué)科研究與發(fā)展中經(jīng)

常面對(duì)而又必須解決的科學(xué)問題。

計(jì)算機(jī)學(xué)科的經(jīng)典問題

經(jīng)典問題是指那些反映學(xué)科某一方面內(nèi)

在規(guī)律和本質(zhì)內(nèi)容的典型問題。

經(jīng)典問題往往以深入淺出的形式表達(dá)學(xué)

科深?yuàn)W的科學(xué)規(guī)律和本質(zhì)內(nèi)容，在學(xué)科研究

中常常用來輔助說明思想、原理、方法和技

術(shù)。

GOTO語句問題與程序設(shè)計(jì)方法學(xué)

■1968年，計(jì)算機(jī)科學(xué)家狄杰斯

特拉首次提出了GOTO語句是

有害的。

■1974年，計(jì)算機(jī)科學(xué)家克努斯

發(fā)表論文《帶有GOTO語句的

結(jié)構(gòu)化程序設(shè)計(jì)》作了較全面

而公正的論述。

面條程序示例

GOTO語句問題與程序設(shè)計(jì)方法學(xué)

濫用GOTO語句是有害的，完全禁止也

是不明智的，在不破壞程序良好結(jié)構(gòu)的前提

下，有限制地使用GOTO語句，有可能使程

序更清晰、效率更高。

關(guān)于“GOTO語句”問題的爭(zhēng)論直接導(dǎo)

致了一個(gè)新的學(xué)科分支領(lǐng)域——程序設(shè)計(jì)方

法學(xué)的產(chǎn)生，它是一個(gè)對(duì)程序的性質(zhì)及其設(shè)

計(jì)的理論和方法進(jìn)行研究的學(xué)科。

哥尼斯堡七橋問題與圖論

在一次步行中穿越全部的七

座橋后回到起點(diǎn)，且每座橋

D

只經(jīng)過一次。

哥尼斯堡七橋問題與圖論

歐拉回路的判定規(guī)則:

（1）如果通奇數(shù)橋的地方多于兩個(gè)，則不存在

歐拉回路；

（2）如果只有兩個(gè)地方通奇數(shù)橋，可以從這兩

個(gè)地方之一出發(fā)，找到歐拉回路；

（3）如果沒有一個(gè)地方是通奇數(shù)橋的，則無論

從哪里出發(fā)，都能找到歐拉回路。

哈密頓回路問題

1

哈密頓回路：要求

從一個(gè)城市出發(fā)，

經(jīng)過每個(gè)城市恰好202

一次，然后回到出

發(fā)城市。

哲學(xué)家共餐問題與進(jìn)程同步

哲學(xué)家的生活進(jìn)程可表示為：

(1)思考問題；

(2)俄了停止思考，左手拿起一只

筷子(如果左側(cè)哲學(xué)家已持有它，則

等待)；

(3)右手拿起一只筷子(如果右側(cè)

哲學(xué)家已持有它，則等待)；

(4)進(jìn)餐；

(5)放下左手筷子；

(6)放下右手筷子；

(7)重新回到狀態(tài)(1)思考問題；

哲學(xué)家共餐問題與進(jìn)程同步

程序并發(fā)執(zhí)行時(shí)進(jìn)程同步的兩個(gè)關(guān)鍵問題一

—死鎖和饑餓：

(1)按哲學(xué)家的生活進(jìn)程，當(dāng)所有的哲學(xué)家都同時(shí)拿起

左手筷子時(shí)，則所有哲學(xué)家都將拿不到右手筷子，并處于

等待狀態(tài)，那么，哲學(xué)家都將無法進(jìn)餐，最終餓死。

(2)將哲學(xué)家的生活進(jìn)程修改為當(dāng)拿不到右手筷子時(shí)，

就放下左手筷子。但是，可能在一個(gè)瞬間，所有的哲學(xué)家

都同時(shí)拿起左手筷子，則自然拿不到右手筷子，于是都同

時(shí)放下左手筷子，等一會(huì)，又同時(shí)拿起左手筷子，如此重

復(fù)下去，則所有的哲學(xué)家都將無法進(jìn)餐。

漢諾塔問題與計(jì)算復(fù)雜性

漢諾塔問題：在世界剛被創(chuàng)建的時(shí)候有一座

鉆石寶塔（塔A）,其上有64個(gè)金碟。所有碟子

按從大到小的次序從塔底堆放至塔頂。緊挨著這

座塔有另外兩個(gè)鉆石寶塔（塔B和塔C）。從世

界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把

塔A上的碟子移動(dòng)到塔C上去，其間借助于塔B

的幫助。每次只能移動(dòng)一個(gè)碟子，任何時(shí)候都不

能把一個(gè)碟子放在比它小的碟子上面。當(dāng)牧師們

完成任務(wù)時(shí)，世界末日也就到了。

漢諾塔問題與計(jì)算復(fù)雜性

ABC

A

(b)

ABC

LAX

(c)

漢諾塔問題與計(jì)算復(fù)雜性

〃個(gè)碟子的漢諾塔問題需要移動(dòng)的碟子數(shù)是

個(gè)碟子的漢諾塔問題需要移動(dòng)的碟子數(shù)的2倍再

加1。因此：

Zz(n)=2h(n—1)+1

=2(2/z(n-2)+1)+1

=22h{n-2)+2+1

=2nh(U)+2"T+???+22+21+1

=2"i+???+22+21+1

=2n-1

漢諾塔問題與計(jì)算復(fù)雜性

I?64個(gè)碟子的漢諾塔問題，需要移動(dòng)的碟子數(shù)為：

264-1=18,446,744,073,709,551,615

■如果每秒移動(dòng)一次，一年有31,536,000秒，則僧

侶們一刻不停地來回移動(dòng)，也需要花費(fèi)5849億年的

時(shí)間；

■假定計(jì)算機(jī)以每秒1000萬個(gè)碟子的速度進(jìn)行移動(dòng),

則需要花費(fèi)58,490年的時(shí)間。

Q理論上可以計(jì)算的問題，實(shí)際上并不一定能行，

K這屬于計(jì)算復(fù)雜性領(lǐng)域的研究?jī)?nèi)容。

7證比求易問題與NP完全問題

■在計(jì)算復(fù)雜性領(lǐng)域中，一般認(rèn)為求解一個(gè)問

題往往比較困難，但驗(yàn)證一個(gè)問題相對(duì)來說就

比較容易——證比求易。

?求大整數(shù)5=49,770,428,644,836,899的因子是

個(gè)難解問題，但是驗(yàn)證〃=223,092,871是不是大

整數(shù)S的因子卻很容易；

A求一個(gè)線性方程組的解可能很困難，但是驗(yàn)

證一組解是否是方程組的解卻很容易。

證比求易問題與NP完全問題

■在計(jì)算復(fù)雜性領(lǐng)域中，將所有可以在多項(xiàng)式時(shí)

間內(nèi)求解的問題稱為P類問題，而將所有可以

在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的問題稱為NP類問題。

■P=NP是否成立是計(jì)算科學(xué)和當(dāng)代數(shù)學(xué)研究中

最大的懸而未決的問題之一。

■20世紀(jì)70年代初，庫(kù)克在證明了NP類中某些

問題的復(fù)雜性與整個(gè)NP類的復(fù)雜性有關(guān)，當(dāng)

這些問題中的任何一個(gè)存在多項(xiàng)式時(shí)間算法，

則所有這些NP類問題都是在多項(xiàng)式時(shí)間內(nèi)可

解決的，這些問題稱為NP完全問題。

TSP問題與組合爆炸

TSP問題（又稱貨郎擔(dān)問題、郵遞員問題、

售貨員問題）是數(shù)學(xué)家克克曼于19世紀(jì)初提出

的一個(gè)數(shù)學(xué)問題，是指旅行家要旅行〃個(gè)城市

然后回到出發(fā)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)

歷一次，并要求所走的路程最短。

由于TSP問題有著貌似簡(jiǎn)單的表述、重要

的應(yīng)用、以及和其他NP完全問題的重要關(guān)系，

它在近200年的時(shí)間里強(qiáng)烈地吸引著計(jì)算機(jī)科

學(xué)工作者。

，ft

TSP問題與組合爆炸

序號(hào)路徑路徑長(zhǎng)度是否最短

1a一b一c一d—a18否

2a一b一d—c-a11是

3a—c一b一d—a23否

4a—c一d—b一a11是

5a一d—b一c-a23否

6a一d—c一b一a18否

TSP問題與組合爆炸

對(duì)于具有〃個(gè)頂點(diǎn)的TSP問題，可能的解有：

(?1)!/2個(gè)。

■10城市的TSP問題有大約180,000個(gè)可能解。

■20城市的TSP問題有大約60,000,000,000,000,000個(gè)

可能解。

■50城市的TSP問題有大約1062個(gè)可能解，而一個(gè)行

星上也只有10口升水。

組合爆炸

-組合優(yōu)化問題：尋找一個(gè)組合對(duì)象，比如一個(gè)

排列或一個(gè)組合，這個(gè)對(duì)象能夠滿足特定的約

束條件并使得某個(gè)目標(biāo)函數(shù)取得極值。

■無論從理論的觀點(diǎn)還是實(shí)踐的觀點(diǎn)，組合優(yōu)化

問題都是計(jì)算領(lǐng)域中最難的問題，其原因是：

(1)隨著問題規(guī)模的增大，組合對(duì)象的數(shù)量增

長(zhǎng)產(chǎn)生組合爆炸；

(2)還沒有一種已知算法能在可接受的時(shí)間內(nèi),

精確地求解絕大多數(shù)這類問題。

圖靈測(cè)試與人工智能

回答者A回答者B

圖靈測(cè)試與人工智能

■行為主義（弱AI）：不要求接受測(cè)試的思維機(jī)器

在內(nèi)部構(gòu)造上與人腦相同，而只是從功能的角度

來判定機(jī)器是否具有思維，也就是從行為角度對(duì)

機(jī)器思維進(jìn)行定義。

■符號(hào)主義（強(qiáng)AI）：認(rèn)知是一種符號(hào)處理過程，

人類思維過程也可以用某種符號(hào)來描述。

■由于人們對(duì)心理學(xué)和生物學(xué)的認(rèn)識(shí)還很不成熟，

對(duì)人腦的結(jié)構(gòu)還沒有真正了解，更無法建立起人

腦思維完整的數(shù)學(xué)模型。因此，到目前為止，思

維就是計(jì)算的思想沒有實(shí)質(zhì)性的突破。

圖靈測(cè)試與人工智能

■1994年11月，美國(guó)科學(xué)家阿德勒曼教授發(fā)表了

論文《解決組合問題的分子計(jì)算》。

■該論文論證了DNA（脫氧核糖核酸）計(jì)算技術(shù)

的可行性，并用DNA技術(shù)解決了一個(gè)簡(jiǎn)單的有向

哈密頓回路問題。

■2002年，阿德勒曼教授應(yīng)用DNA技術(shù)解決了具

有200萬種可能結(jié)果的有向哈密頓回路問題。

■阿德勒曼教授的工作從一個(gè)側(cè)面探討了生命過

程就是一種計(jì)算的思想。

計(jì)算機(jī)學(xué)科的知識(shí)體系

隨著計(jì)算技術(shù)的發(fā)展，IEEE/ACM在CC2001

中將計(jì)算機(jī)學(xué)科稱為計(jì)算學(xué)科，并將計(jì)算學(xué)科

分為四個(gè)領(lǐng)域（也稱專業(yè)方向），分別是計(jì)算

機(jī)科學(xué)、計(jì)算機(jī)工程、軟件工程和信息系統(tǒng)。

于2004年6月1日公布的CC2004報(bào)告，在上述

四個(gè)領(lǐng)域的基礎(chǔ)上，增加了一個(gè)信息技術(shù)專業(yè)

學(xué)科領(lǐng)域，并預(yù)留了未來的新發(fā)展領(lǐng)域。

計(jì)算機(jī)學(xué)科的問題空間

組織系統(tǒng)行為

應(yīng)用技術(shù)

軟件開發(fā)

系統(tǒng)平臺(tái)結(jié)構(gòu)

計(jì)算機(jī)硬件體系

論

理開發(fā)應(yīng)用

理

原<------——->部署

新

創(chuàng)傾向理論傾向應(yīng)用配置

計(jì)算機(jī)科學(xué)

組織系統(tǒng)行為

應(yīng)用技術(shù)

軟件開發(fā)

系統(tǒng)平臺(tái)結(jié)構(gòu)

計(jì)算機(jī)硬件體系

計(jì)算機(jī)工程

組織系統(tǒng)行為

應(yīng)用技術(shù)

軟件開發(fā)

系統(tǒng)平臺(tái)結(jié)構(gòu)

計(jì)算機(jī)硬件體系

應(yīng)

用

論

理開發(fā)

部

署

理

原<------------------------------------>

置

配

新

創(chuàng)傾向理論傾向應(yīng)用

軟件工程

應(yīng)

用

論

理開發(fā)

部

署

理

原<------------------------------------>

置

配

新

創(chuàng)傾向理論傾向應(yīng)用

信息系統(tǒng)

應(yīng)

用

論

理開發(fā)

部

署

理

原<------------------------------------>

置

配

新

創(chuàng)傾向理論傾向應(yīng)用

信息技術(shù)

組織系統(tǒng)行為