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

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

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

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

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

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

什么是計算

■從字源上考察：

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

算：從竹從具，指計算工具。

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

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

什么是計算

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

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

■計算的實質(zhì)：從一個符號串/（輸入）得出另

一個符號串g（輸出）。

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

計算的例子

A從符號串“12+3”變換成符號串“15”——加法計

算

?符號串變換成符號串——微分；

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

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

?符號串/代表一個英文句子，符號串g為含義相

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

磁中暹變換有什么共同點？

儂為什么他們都叫做計算？

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

>5

圖靈模型

有限狀態(tài)

控制器

工作帶

■一條無限長的工作帶：工作帶上的每個單元可以

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

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

圖靈模型

有限狀態(tài)

控制器

工作帶

■一個讀寫頭：讀寫頭可以左移一個單元、右移一

個單元或者保持不動。

圖靈模型

有限狀態(tài)

控制器

1

工作帶

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

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

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

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

計算與可計算

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

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

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

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

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

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

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

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

用圖靈模型來計算

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

基本思想：使讀寫頭往返移動，每往返移動一

次，就成對地對輸入符號串。左端的一個4和右

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

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

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

的符號〃和右端的符號〃的個數(shù)不相等，或者符

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

用圖靈模型來計算

假定〃=2,輸入符號串”=的防

工作帶BaabbB

指令

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

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

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

的字符

當(dāng)前讀

到的字筠讀寫頭的動作

R:右移L：左移H:不動

用圖靈模型來計算

子母表：

讀寫頭{a,b,B}

工作帶BaabbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)

制讀寫頭掃描到符號處

(夕1,xxLql)

器則繼續(xù)往右走

(夕1,axRql)

(夕1,BBHqN)

(夕2,xxRql)

用圖靈模型來計算

讀寫頭

工作市BaabbB

程序

(夕0,aaR夕0)

控(夕0,bxL夕1)

制讀寫頭掃描到符號處

(夕1,xxLql)

器則繼續(xù)往右走

(夕1,axRql)

(夕

1,BBHqN)

(夕2,xxRql)

用圖靈模型來計算

讀寫頭

工作市BaabbB

程序

（夕0,aaR夕0）

控（夕0,bxL夕1）讀寫頭掃描到符號兒

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

器

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

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

（夕1,BBHqJ1

（夕2,xxR夕2）

用圖靈模型來計算

讀寫頭

工作市BaaxbB

程序

(夕0,aaR夕0)

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

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

器

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

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

(夕2,xxRql)

用圖靈模型來計算

讀寫頭

工作市BaaxbB

程序

（夕0,aaR夕0）

控讀寫頭掃描到符號小

（夕0,bxL夕1）

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

（夕LxxLql）

器并使讀寫頭往右走，

（夕夕）

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

（夕1,BBHqJ

（夕2,xxR夕2）

用圖靈模型來計算

讀寫頭

工作市BaxxbB

程序

（夕0,aaR夕0）

控讀寫頭掃描到符號小

（夕0,bxL夕1）

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

（夕LxxLql）

器并使讀寫頭往右走，

（夕夕）

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

（夕1,BBHqJ

（夕2,xxR夕2）

用圖靈模型來計算

讀寫頭

工作市BaxxbB

程序

(夕0,aaR夕0)

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

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(夕2,xxRql)

用圖靈模型來計算

讀寫頭

工作帶BaxxbB

程序

（夕2,bxL夕1）

控若讀寫頭掃描到符號

（夕2,BBLq3）A,

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

（夕3,xxL夕3）I6

器并使讀寫頭往左走，

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

（夕3,BBHq4）

用圖靈模型來計算

讀寫頭

工作市BaxxxB

程序

(夕0,aaR夕0)

控若讀寫頭掃描到符號A,

(夕0,bxL夕1)

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

(夕1,xxLql)

器并使讀寫頭往左走，

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

(ql,BBHqJ

(夕2,xxRql)

用圖靈模型來計算

讀寫頭

工作市BaxxxB

程序

(夕0,aaR夕0)

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

(夕0,bxL夕1)

制則繼續(xù)往左走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(夕2,xxRql)

用圖靈模型來計算

讀寫頭

工作市BaxxxB

程序

（夕0,aaR夕0）

控讀寫頭掃描到符號小

（夕0,bxL夕1）

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

（夕LxxLql）

器并使讀寫頭往右走，

（夕夕）

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

（夕1,BBHqJ

（夕2,xxR夕2）

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

(夕0,aaR夕0)

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

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

(夕0,aaR夕0)

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

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

(夕0,aaR夕0)

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

(夕0,bxL夕1)

制則繼續(xù)往右走

(夕1,xxLql)

器

(夕1,axRql)

(ql,BBHqJ

(ql^xxRql)

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

(夕2,bxLql)

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

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

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

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

(夕3,BBHq4)

平用圖靈模型來計算

讀寫頭

工作帶BxxxXB

程序

（夕2,bxL夕1）

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

（夕2,BBLq3）

制說明符號A已處理完畢,

（夕3,xxL夕3）

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

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

（夕3,BBHq4）

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

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

（夕2,BBLq3）x

制則繼續(xù)往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

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

（夕2,BBLq3）x

制則繼續(xù)往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

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

（夕2,BBLq3）x

制則繼續(xù)往左走

（夕3,xxL夕3）

器

（夕3,aaHqQ

（夕3,BBHq4）

用圖靈模型來計算

讀寫頭

工作市BxxxxB

程序

（夕2,bxL夕1）

控讀寫頭掃描到空白符以

（夕2,BBLq3）

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

（夕3,xxL夕3）

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

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

（夕3,BBHq4）

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

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

計算能力，它的基本動作非常簡單、機(jī)械、確定。因

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

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

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

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

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

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

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

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

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

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

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

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

實踐經(jīng)驗的結(jié)晶。

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

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

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

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

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

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

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

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

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

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

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

志是：必須有獨立的研究內(nèi)容、成熟的研究

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

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

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

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

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

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

模型、自動計算機(jī)器的研究，并與存儲式電

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

期。

計算機(jī)學(xué)科的特點

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

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

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

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

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

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

出特點。

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

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

計算機(jī)學(xué)科的特點

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

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

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

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

是發(fā)明。

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

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

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

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

效地）自動計算。

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

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

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

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

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

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

起來的。

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

的發(fā)展。

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

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

什么是科學(xué)問題

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

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

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

域，但尚無確定的答案。

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

（1）時代性（2）混沌性（3）可解決性（4）

可變異性（5）可待解性

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

的動力。

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

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

核心：計算問題的能行性

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

核心：算法及算法分析

3.計算的正確性問題

核心：各種語言的語義

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

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

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

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

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

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

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

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

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

術(shù)。

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

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

特拉首次提出了GOTO語句是

有害的。

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

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

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

而公正的論述。

面條程序示例

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

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

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

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

序更清晰、效率更高。

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

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

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

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

哥尼斯堡七橋問題與圖論

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

座橋后回到起點，且每座橋

D

只經(jīng)過一次。

哥尼斯堡七橋問題與圖論

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

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

歐拉回路；

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

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

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

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

哈密頓回路問題

1

哈密頓回路：要求

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

經(jīng)過每個城市恰好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í)行時進(jìn)程同步的兩個關(guān)鍵問題一

—死鎖和饑餓：

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

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

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

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

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

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

時放下左手筷子，等一會，又同時拿起左手筷子，如此重

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

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

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

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

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

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

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

塔A上的碟子移動到塔C上去，其間借助于塔B

的幫助。每次只能移動一個碟子，任何時候都不

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

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

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

ABC

A

(b)

ABC

LAX

(c)

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

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

個碟子的漢諾塔問題需要移動的碟子數(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

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

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

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

■如果每秒移動一次，一年有31,536,000秒，則僧

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

時間；

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

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

Q理論上可以計算的問題，實際上并不一定能行，

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

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

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

題往往比較困難，但驗證一個問題相對來說就

比較容易——證比求易。

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

個難解問題，但是驗證〃=223,092,871是不是大

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

A求一個線性方程組的解可能很困難，但是驗

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

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

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

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

在多項式時間內(nèi)驗證的問題稱為NP類問題。

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

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

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

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

這些問題中的任何一個存在多項式時間算法，

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

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

TSP問題與組合爆炸

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

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

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

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

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

由于TSP問題有著貌似簡單的表述、重要

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

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

學(xué)工作者。

，ft

TSP問題與組合爆炸

序號路徑路徑長度是否最短

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問題與組合爆炸

對于具有〃個頂點的TSP問題，可能的解有：

(?1)!/2個。

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

■20城市的TSP問題有大約60,000,000,000,000,000個

可能解。

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

星上也只有10口升水。

組合爆炸

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

排列或一個組合，這個對象能夠滿足特定的約

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

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

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

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

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

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

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

圖靈測試與人工智能

回答者A回答者B

圖靈測試與人工智能

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

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

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

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

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

人類思維過程也可以用某種符號來描述。

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

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

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

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

圖靈測試與人工智能

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

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

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

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

哈密頓回路問題。

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

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

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

程就是一種計算的思想。

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

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

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

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

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

于2004年6月1日公布的CC2004報告，在上述

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

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

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

組織系統(tǒng)行為

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

軟件開發(fā)

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

計算機(jī)硬件體系

論

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

理

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

新

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

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

組織系統(tǒng)行為

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

軟件開發(fā)

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

計算機(jī)硬件體系

計算機(jī)工程

組織系統(tǒng)行為

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

軟件開發(fā)

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

計算機(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)行為