華中科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)方法論 3計(jì)算學(xué)科中的三個(gè)學(xué)科形態(tài)

第3章計(jì)算學(xué)科中的三個(gè)學(xué)科形態(tài)文坤梅E-Mail:kunmei.wen@智能與分布計(jì)算實(shí)驗(yàn)室IntelligenceandDistributedComputingLab第3章計(jì)算學(xué)科中的三個(gè)學(xué)科形態(tài)抽象—理論—設(shè)計(jì)（三種形態(tài)）：計(jì)算學(xué)科中的基本內(nèi)容，基本概念；同時(shí)反映了人們的認(rèn)識是從感性認(rèn)識（抽象）到理性認(rèn)識（理論），再由理性認(rèn)識（理論）回到實(shí)踐（設(shè)計(jì)）中來的一般科學(xué)思維方法1、抽象形態(tài)——科學(xué)抽象是指在思維中對同類事物去除其現(xiàn)象的、次要的方面，抽取其共同的、主要的方面，從而做到從個(gè)別中把握一般，從現(xiàn)象中把握本質(zhì)的認(rèn)知過程和思維方法。學(xué)科中的抽象形態(tài)包含著具體的內(nèi)容，它們是學(xué)科中所具有的科學(xué)概念、科學(xué)符號和思想模型。一、三種形態(tài)與各領(lǐng)域中三個(gè)形態(tài)的主要內(nèi)容（P49-P59）1、抽象形態(tài)——源于現(xiàn)實(shí)世界（建立對客觀事物進(jìn)行抽象描述的方法，建立概念模型）形成假設(shè)建造模型并作出預(yù)測設(shè)計(jì)實(shí)驗(yàn)并收集數(shù)據(jù)對結(jié)果進(jìn)行分析科學(xué)認(rèn)識由感性階段上升為理性階段，就形成了科學(xué)理論。科學(xué)理論是經(jīng)過實(shí)踐檢驗(yàn)的系統(tǒng)化了的科學(xué)知識體系，它是由科學(xué)概念、科學(xué)原理以及對這些概念、原理的理論論證所組成的體系。理論源于數(shù)學(xué)，是從抽象到抽象的升華，它們已經(jīng)完全脫離現(xiàn)實(shí)事物，不受現(xiàn)實(shí)事物的限制，具有精確的、優(yōu)美的特征，因而更能把握事物的本質(zhì)。2、理論形態(tài)——表述研究對象的特征（定義和公理）假設(shè)對象之間的基本性質(zhì)和對象之間可能存在的關(guān)系（定理）確定這些關(guān)系是否為真（證明）結(jié)論2、理論形態(tài)——源于數(shù)學(xué)（建立理論體系，建立數(shù)學(xué)模型）3、設(shè)計(jì)形態(tài)——設(shè)計(jì)形態(tài)與抽象、理論兩個(gè)形態(tài)存在的聯(lián)系 設(shè)計(jì)源于工程，用于系統(tǒng)或設(shè)備的開發(fā)，實(shí)現(xiàn)給定的任務(wù)設(shè)計(jì)形態(tài)和抽象、理論兩個(gè)形態(tài)都須以對自然規(guī)律的認(rèn)識為前提設(shè)計(jì)必須創(chuàng)造出相應(yīng)的人工系統(tǒng)和人工條件，還必須認(rèn)識自然規(guī)律的具體表現(xiàn)形式設(shè)計(jì)形態(tài)的主要特征與抽象、理論兩個(gè)形態(tài)的主要區(qū)別： 設(shè)計(jì)形態(tài)具有較強(qiáng)的實(shí)踐性、社會性、綜合性需求分析建立規(guī)格說明設(shè)計(jì)并實(shí)現(xiàn)該系統(tǒng)對系統(tǒng)進(jìn)行測試與分析3、設(shè)計(jì)形態(tài)——源于工程（完成一個(gè)具體任務(wù)，總結(jié)與升華）三個(gè)學(xué)科形態(tài)的內(nèi)在聯(lián)系在計(jì)算機(jī)科學(xué)與技術(shù)方法論的原始命題中，蘊(yùn)含著人類認(rèn)識過程的兩次飛躍，第一次飛躍是從物質(zhì)到精神，從實(shí)踐到認(rèn)識的飛躍。這次飛躍包括兩個(gè)決定性的環(huán)節(jié)：一個(gè)是科學(xué)抽象，另一個(gè)是科學(xué)理論。第二次飛躍是從精神到物質(zhì)，從認(rèn)識到實(shí)踐的飛躍。這次飛躍的實(shí)質(zhì)對技術(shù)學(xué)科（計(jì)算學(xué)科就是一門技術(shù)學(xué)科）而言，其實(shí)就是要在理論的指導(dǎo)下，以抽象的成果為工具來完成各種設(shè)計(jì)工作。抽象源于現(xiàn)實(shí)世界。建立對客觀事物進(jìn)行抽象描述的方法，建立具體問題的概念模型，實(shí)現(xiàn)對客觀世界的感性認(rèn)識。

理論源于數(shù)學(xué)。建立完整的理論體系，建立具體問題的數(shù)學(xué)模型，從而實(shí)現(xiàn)對客觀世界的理性認(rèn)識。設(shè)計(jì)源于工程。對客觀世界的感性認(rèn)識和理性認(rèn)識的基礎(chǔ)上，完成一個(gè)具體的任務(wù)；對工程設(shè)計(jì)中所遇到的問題進(jìn)行總結(jié)，提出問題，由理論界去解決它。三個(gè)學(xué)科形態(tài)的內(nèi)在聯(lián)系

4、各領(lǐng)域中三個(gè)形態(tài)的主要內(nèi)容（P54-P59）二、例子1信息系統(tǒng)（數(shù)據(jù)庫）三種形態(tài)實(shí)例（P44-P48）1、問題：實(shí)體：學(xué)生與課程，聯(lián)系：多對多，要建立一個(gè)信息管理系統(tǒng)。實(shí)體：客觀存在并可相互區(qū)別的事物實(shí)體集屬性：實(shí)體所具有的某一方面的特性關(guān)鍵字（碼）：能唯一標(biāo)識實(shí)體的屬性集聯(lián)系：不同實(shí)體集之間的聯(lián)系

1:1，1:N，N:M2、抽象形態(tài)——建模（1）實(shí)體（Entity）、屬性（Attribute）、關(guān)鍵字（Key）與聯(lián)系（Relationship）三種圖元素：實(shí)體(矩形)、屬性(橢圓)、聯(lián)系(菱形)P45圖3.1學(xué)生選課E-R圖（2）E-R模型實(shí)體及實(shí)體之間的聯(lián)系均用關(guān)系（二維表）表示笛卡爾積：設(shè)D1，D2，…，Dn為任意集合，定義

D1，D2，…，Dn笛卡爾積為：D1D2…Dn

={(d1,d2,…,dn)|diDi,i=1,…,n}

關(guān)系：笛卡爾積D1D2…Dn的任意一個(gè)子集，稱為

D1，D2，…，Dn上的一個(gè)n元關(guān)系

關(guān)系模式：二維表的表框架，R=<U，F(xiàn)>U：關(guān)系中所有屬性的集合

F：屬性集合U上的一組函數(shù)依賴（3）關(guān)系模型3、理論形態(tài)——規(guī)范化理論定義：設(shè)有關(guān)系模式R（A1,A2,…,An），X和Y均為

{A1,A2,…,An}的子集，r是R的任一具體關(guān)系（R-型，

r-值）。如果R的所有關(guān)系r都存在著：對于X的每一個(gè)具體值，都有Y唯一的具體值與之對應(yīng)，則稱X函數(shù)決定Y，或Y函數(shù)依賴于X。記為XY（1）函數(shù)依賴：屬性間的關(guān)系函數(shù)依賴判別簡法：設(shè)有屬性集X、Y及關(guān)系模式R①如果X、Y之間是“1:1”關(guān)系，則

XYYX②如果X、Y之間是“N:1”關(guān)系，則

XY③如果X、Y之間是“N:M”關(guān)系，則

X、Y之間不存在函數(shù)依賴插入異常刪除異常冗余太大（2）感性認(rèn)識中存在的問題

1NF（1NormalForm）:每個(gè)屬性值都是不可再分的最小單元

2NF：若R1NF，且每一非主屬性不存在對關(guān)鍵字的部分依賴，則R2NF。部分依賴：設(shè)R中XY，Y–X

，如果存在X的真子集X1Y成立，則稱Y部分依賴于X，否則稱Y完全函數(shù)依賴于X。（3）規(guī)范化理論

3NF：若R2NF，且每一非主屬性不存在對關(guān)鍵字的傳遞依賴，則R3NF。傳遞依賴：對R，X、Y、Z均為R的屬性子集，如果

XY，Y–Z，則稱Z傳遞依賴于X。結(jié)論：從感性認(rèn)識（抽象）而來的關(guān)系模式，必須用規(guī)范化（理論）方法，使之在3NF以上。4、設(shè)計(jì)形態(tài)——依賴具體的DBMS進(jìn)行定義與應(yīng)用（SQL語句）三、例子2程序設(shè)計(jì)語言三種形態(tài)實(shí)例自然語言應(yīng)用語言（4GL）高級語言匯編語言機(jī)器語言（表3.3）（表3.2）（表3.1）（表3.4）抽象理論設(shè)計(jì)t計(jì)算機(jī)語言在裸機(jī)級所取得的主要成果計(jì)算機(jī)語言抽象理論設(shè)計(jì)裸機(jī)級的主要內(nèi)容和成果

語言的符號集為：{0，1}；用機(jī)器指令對算法進(jìn)行描述圖靈機(jī)（過程語言的基礎(chǔ)）、波斯特系統(tǒng)（字符串處理語言的基礎(chǔ)）、λ-演算（函數(shù)式語言的基礎(chǔ)）等計(jì)算模型馮·諾依曼型計(jì)算機(jī)等實(shí)現(xiàn)技術(shù)；數(shù)字電子計(jì)算機(jī)產(chǎn)品BACK1、自然語言與形式語言歧義性；不夠嚴(yán)格和不夠統(tǒng)一的語法結(jié)構(gòu)。 他的發(fā)理得好。他的理發(fā)水平高；理發(fā)師理他的發(fā)理得好。 他的小說看不完。他寫的小說看不完；他收藏的小說看不完；他是個(gè)小說迷。

人類的語言（文字）是人類最普遍使用的符號系統(tǒng)。其最基本、最普遍的形式是自然語言符號系統(tǒng)高級語言的歧義性問題

高級程序設(shè)計(jì)語言其實(shí)也有語義的歧義性問題,高級程序設(shè)計(jì)語言存在較少的歧義性而已例3.4

IF(表達(dá)式1)THENIF(表達(dá)式2)THEN語句1ELSE語句2。IF(表達(dá)式1)THEN(IF(表達(dá)式2)THEN語句1ELSE語句2)；IF(表達(dá)式1)THEN(IF(表達(dá)式2)THEN語句1)ELSE語句2。

形式語言有一組初始的、專門的符號集；有一組精確定義的，由初始的、專門的符號組成的符號串轉(zhuǎn)換成另一個(gè)符號串的規(guī)則。在形式語言中，不允許出現(xiàn)根據(jù)形成規(guī)則無法確定的符號串。人工語言符號系統(tǒng)發(fā)展的第二階段叫形式化語言，簡稱形式語言。形式語言是進(jìn)行形式化工作的元語言，它是以數(shù)學(xué)和數(shù)理邏輯為基礎(chǔ)的科學(xué)語言。2.圖靈機(jī)圖靈的觀點(diǎn)及結(jié)論：凡是能用算法方法解決的問題，也一定能用圖靈機(jī)解決；凡是圖靈機(jī)解決不了的問題，任何算法也解決不了。與圖靈機(jī)等價(jià)的計(jì)算模型：遞歸函數(shù)λ-演算POST規(guī)范系統(tǒng)圖靈機(jī)是從過程這一角度來刻畫計(jì)算的本質(zhì)，其結(jié)構(gòu)簡單、操作運(yùn)算規(guī)則也較少，從而為更多的人所理解。圖靈機(jī)

圖靈機(jī)由一條兩端可無限延長的帶子、一個(gè)讀寫頭以及一組控制讀寫頭工作的命令組成，圖靈機(jī)寫在帶子上的符號為一個(gè)有窮字母表：{S0，S1，S2，…，Sp}?？梢哉J(rèn)為這個(gè)有窮字母表僅有S0、S1兩個(gè)字符，其中S0可以看作是“0”，S1可以看作是“1”，由“0”和“1”組成的字母表可以表示任何一個(gè)數(shù)。一個(gè)給定機(jī)器的“程序”機(jī)器內(nèi)的五元組（qiSjSkR（或L或N）ql）形式的指令集，五元組定義了機(jī)器在一個(gè)特定狀態(tài)下讀入一個(gè)特定字符時(shí)所采取的動(dòng)作。5個(gè)元素的含義如下：

qi表示機(jī)器目前所處的狀態(tài)；

Sj表示機(jī)器從方格中讀入的符號；

Sk表示機(jī)器用來代替Sj寫入方格中的符號；

R、L、N分別表示向右移一格、向左移一格、不移動(dòng)；ql表示下一步機(jī)器的狀態(tài)。

一個(gè)機(jī)器計(jì)算的結(jié)果是從機(jī)器停止時(shí)帶子上的信息得到的。容易看出，q1S2S2Rq3指令和q3S3S3Lq1指令如果同時(shí)出現(xiàn)在機(jī)器中，當(dāng)機(jī)器處于狀態(tài)q1，第一條指令讀入的是S2，第二條指令讀入的是S3，那么機(jī)器會在兩個(gè)方塊之間無休止地工作。另外，如果q3S2S2Rq4和q3S2S4Lq6指令同時(shí)出現(xiàn)在機(jī)器中，當(dāng)機(jī)器處于狀態(tài)q3并在帶子上掃描到符號S2時(shí)，就產(chǎn)生了二義性的問題，機(jī)器就無法判定。例3.9b表示空格，q1表示機(jī)器的初始狀態(tài)，

q4表示機(jī)器的結(jié)束狀態(tài)，設(shè)帶子上的輸入信息是10100010，讀入頭位對準(zhǔn)最右邊第一個(gè)為0的方格，狀態(tài)為初始狀態(tài)q1。規(guī)則如下。q101L

q2q110L

q3q1

b

b

N

q4q200L

q2q211L

q2q2

b

b

N

q4q301L

q2q310L

q3q3

b

b

N

q4計(jì)算過程如下：計(jì)算結(jié)果是10100011，即對給定的數(shù)加1。以上命令計(jì)算的是這樣一個(gè)函數(shù)：S(x)＝x＋1。當(dāng)沒有輸入時(shí)，即初始狀態(tài)所指的方格為空格（b）時(shí)，不改變空格符，讀寫頭不動(dòng)并停機(jī)。

圖靈機(jī)的計(jì)算能力圖靈機(jī)可以計(jì)算S(x)＝x＋1（后繼函數(shù)），N(x)＝0（零函數(shù)），Ui(n)(x1，x2，…，xn)＝xi，1≤i≤n（投影函數(shù)）上述3個(gè)函數(shù)的任意組合。從遞歸論中，我們知道這3個(gè)函數(shù)屬于初始遞歸函數(shù)，任何原始遞歸函數(shù)都是從這3個(gè)初始遞歸函數(shù)經(jīng)有限次的復(fù)合、遞歸和極小化操作得到的。從可計(jì)算理論可知每一個(gè)原始遞歸函數(shù)都是圖靈機(jī)可計(jì)算的。

3、預(yù)備知識——馮·諾依曼計(jì)算機(jī)ENIAC的結(jié)構(gòu)在很大程度上是依照機(jī)電系統(tǒng)設(shè)計(jì)的，還存在重大的線路結(jié)構(gòu)等問題。在圖靈等人工作的影響下，1946年6月，美國杰出的數(shù)學(xué)家馮·諾依曼（VonNeumann）及其同事完成了關(guān)于“電子計(jì)算裝置邏輯結(jié)構(gòu)設(shè)計(jì)”的研究報(bào)告，具體介紹了制造電