1、計算機科學中計算機科學中趙沁平趙沁平 創(chuàng)新研究的對象創(chuàng)新研究的對象 已有理論已有理論 自然世界自然世界 人類活動人類活動 創(chuàng)新的類型創(chuàng)新的類型 發(fā)現(xiàn)發(fā)現(xiàn) 發(fā)明發(fā)明 發(fā)展發(fā)展 指出指出 提出提出 構(gòu)造構(gòu)造 證明證明 改進改進 原始創(chuàng)新原始創(chuàng)新 改進完善改進完善創(chuàng)新的條件創(chuàng)新的條件 激情、毅力、知識、智慧激情、毅力、知識、智慧 了解所研究的對象了解所研究的對象 特性特性 存在條件存在條件 與其他事物的關(guān)系與其他事物的關(guān)系 已有研究結(jié)果已有研究結(jié)果 研究對象是已有論斷研究對象是已有論斷 分析已知論斷分析已知論斷 懷疑懷疑 不滿不滿 猜想猜想 找反例找反例 改進改進 證明證明創(chuàng)新的起步創(chuàng)新的起步 懷疑

2、已有的論斷，尋找它們與客觀懷疑已有的論斷，尋找它們與客觀實際不符或矛盾之處，進而指出其存在實際不符或矛盾之處，進而指出其存在的問題或推翻該論斷，這本身也是一種的問題或推翻該論斷，這本身也是一種創(chuàng)新工作。創(chuàng)新工作。例例1 1 找到找到XXXXXX教授在可計算理論研究中提出的一條教授在可計算理論研究中提出的一條公理的反例，從而推翻了他的這一公理。公理的反例，從而推翻了他的這一公理。 XXX在計算機研究與發(fā)展1988年第11期“什么是可計算性”一文中針對丘奇-圖靈論題的公理化問題，在M.Blum四條公理的基礎(chǔ)上，提出了一條新的公理： 一組可計算函數(shù)一組可計算函數(shù)fifi 如果有最小上界如果有最小上界

3、g g，則，則g g也是可計算的。也是可計算的。注 如果兩個函數(shù) f 和 g 的值相等，而f的定義域小于g，則定義f小于g，用fg表示。設(shè)fi是一組函數(shù)，g是一個函數(shù)。滿足：fig（一切i）則g叫這組函數(shù)的一個上界。如果g是fi的上界，而且對fi的任何上界h，gh，則說g是fi的最小上界。選擇一個不可計算函數(shù)g，其定義域 D 是可數(shù)無限的。我們?nèi)≡摱x域的一個有限部分D1作為新的定義域，可以得到函數(shù)f1，f1g，由于D1是可數(shù)有限的，因此f1一定是可計算的。再將D1在D上適當擴大為D2，可得到函數(shù)f2，則有f1f2，且f2g。如此重復可以的到一組可計算函數(shù)fi，fi的最小上界顯然是g，而g是一

4、個不可計算函數(shù)。因此馬提出的公理是不成立的。 研究研究對象是自然世界或人類活動對象是自然世界或人類活動 了解問題了解問題 確定目標確定目標 合理假設(shè)合理假設(shè) 創(chuàng)新研究創(chuàng)新研究 計算機學科面向自然世界和人類活動，計算機學科面向自然世界和人類活動，研究內(nèi)容豐富多彩，方法各種各樣，是產(chǎn)生研究內(nèi)容豐富多彩，方法各種各樣，是產(chǎn)生原始創(chuàng)新的源泉。其主要創(chuàng)新目標有三個方原始創(chuàng)新的源泉。其主要創(chuàng)新目標有三個方面面 使計算機系統(tǒng)：使計算機系統(tǒng)： 更高效更高效 更聰明更聰明 更適人更適人創(chuàng)新的方法創(chuàng)新的方法1 1、概念形成、概念形成 概念形成、判斷、推理是思維的三種基本形概念形成、判斷、推理是思維的三種基本形式，

5、各自代表了理性認識的一個階段。式，各自代表了理性認識的一個階段。 概念的形成是人的認識過程由低級的感性認識概念的形成是人的認識過程由低級的感性認識上升到高級的理性認識的一次質(zhì)的飛躍。概念不同上升到高級的理性認識的一次質(zhì)的飛躍。概念不同于感覺的特征，在于概念的抽象性和概括性。于感覺的特征，在于概念的抽象性和概括性。概念的內(nèi)涵與外延概念的內(nèi)涵與外延 內(nèi)涵和外延是概念的兩個方面，是概念的基本內(nèi)涵和外延是概念的兩個方面，是概念的基本邏輯特征。邏輯特征。 概念的內(nèi)涵是概念所反映的對象的共同屬性的概念的內(nèi)涵是概念所反映的對象的共同屬性的總和；概念的外延是概念所反映的對象的總和?？偤停桓拍畹耐庋邮歉拍钏从?/p>

6、的對象的總和。 概念的內(nèi)涵與外延之間有反比關(guān)系。即增加內(nèi)涵概念的內(nèi)涵與外延之間有反比關(guān)系。即增加內(nèi)涵（屬性），其外延會縮小；減少內(nèi)涵，外延會增大。（屬性），其外延會縮?。粶p少內(nèi)涵，外延會增大。定義定義 定義是認識主體使用命題的語言邏輯形式，定義是認識主體使用命題的語言邏輯形式，指指出對象的本質(zhì)屬性，把這一對象和其他與之相似的出對象的本質(zhì)屬性，把這一對象和其他與之相似的對象區(qū)別開。下定義的方法有兩大類，一是邏輯方對象區(qū)別開。下定義的方法有兩大類，一是邏輯方法，即屬概念加種差定義；一是發(fā)生定義。法，即屬概念加種差定義；一是發(fā)生定義。 定義概念是定義問題、研究問題的基礎(chǔ)，概念定義概念是定義問題、研究

7、問題的基礎(chǔ)，概念定義的方法和水平直接影響后續(xù)的創(chuàng)新研究。定義的方法和水平直接影響后續(xù)的創(chuàng)新研究。 屬概念加種差定義屬概念加種差定義 由被定義概念的最鄰近的屬概念加種差構(gòu)成的定義。由被定義概念的最鄰近的屬概念加種差構(gòu)成的定義。 例如，堆棧是一個下限為常數(shù)，上限可變化的向量。例如，堆棧是一個下限為常數(shù)，上限可變化的向量。 發(fā)生定義發(fā)生定義 是屬概念加種差定義的特殊形式。發(fā)生定義所列舉的屬性是屬概念加種差定義的特殊形式。發(fā)生定義所列舉的屬性（種差）是被定義概念所反映的對象的發(fā)生過程。（種差）是被定義概念所反映的對象的發(fā)生過程。 例如，遞歸過程是一個直接或間接調(diào)用自身的過程。例如，遞歸過程是一個直接或

8、間接調(diào)用自身的過程。 定義時必須遵守的邏輯規(guī)則定義時必須遵守的邏輯規(guī)則 定義不能包含被定義概念本身或和它意義相同定義不能包含被定義概念本身或和它意義相同的概念，否則就是同語反復。的概念，否則就是同語反復。 必須采用科學的、確定的術(shù)語和概念，不能用必須采用科學的、確定的術(shù)語和概念，不能用比喻和模糊的語言。比喻和模糊的語言。 必須用肯定語，不能用否定語。必須用肯定語，不能用否定語。 聚類與分類聚類與分類 聚類：概念形成聚類：概念形成 分類：形成子概念分類：形成子概念 分類的關(guān)鍵是選定分類特征分類的關(guān)鍵是選定分類特征 分類首先要確定其分類特征，如果分類特征不分類首先要確定其分類特征，如果分類特征不明

9、確就不是好的分類法明確就不是好的分類法。 分類（子概念）要盡可能成為一種對概念外延分類（子概念）要盡可能成為一種對概念外延的劃分（沒有遺漏，也沒有重疊）。的劃分（沒有遺漏，也沒有重疊）。 用于分類的特征應(yīng)當是所屬領(lǐng)域的一些本質(zhì)特用于分類的特征應(yīng)當是所屬領(lǐng)域的一些本質(zhì)特性。對于計算機學科來說，要性。對于計算機學科來說，要從數(shù)據(jù)類型、信息流從數(shù)據(jù)類型、信息流向、計算模型等計算特性的角度進行分類向、計算模型等計算特性的角度進行分類。 科學地形成概念，本質(zhì)地進行分類就是一種創(chuàng)新?？茖W地形成概念，本質(zhì)地進行分類就是一種創(chuàng)新。例例2 2 計算機體系結(jié)構(gòu)的分類計算機體系結(jié)構(gòu)的分類 以指令流和數(shù)據(jù)流為分類特征

10、以指令流和數(shù)據(jù)流為分類特征 單指令流單數(shù)據(jù)流單指令流單數(shù)據(jù)流 SISD SISD 馮馮 諾依曼體系結(jié)構(gòu)諾依曼體系結(jié)構(gòu) 單指令流多數(shù)據(jù)流單指令流多數(shù)據(jù)流 SIMD SIMD 向量（陣列）機向量（陣列）機 多指令流單數(shù)據(jù)流多指令流單數(shù)據(jù)流 MISD MISD 流水線處理流水線處理 多指令流多數(shù)據(jù)流多指令流多數(shù)據(jù)流 MIMD MIMD 多處理機系統(tǒng)多處理機系統(tǒng) 以指令的驅(qū)動方式（計算模型）為分類特征以指令的驅(qū)動方式（計算模型）為分類特征 控制驅(qū)動控制驅(qū)動 數(shù)據(jù)驅(qū)動數(shù)據(jù)驅(qū)動 需求驅(qū)動需求驅(qū)動例例3 3 關(guān)于虛擬實體的分類關(guān)于虛擬實體的分類 動態(tài)實體動態(tài)實體 ？ 靜態(tài)實體靜態(tài)實體 人在環(huán)實體人在環(huán)實體

11、CGF 實況實體實況實體 上述分類就不是從計算本質(zhì)的分類。上述分類就不是從計算本質(zhì)的分類。問題：問題：分布式計算的分類，網(wǎng)絡(luò)計算、網(wǎng)格計算、 云計算從計算角度的區(qū)別是什么？2 2、演繹法、演繹法 特殊化方法特殊化方法 證明一個對象屬于某概念，因而具有該概念的內(nèi)涵屬性的邏輯方法。是從一般到個體的推理。是從一般到個體的推理。 在計算機科學研究中常對應(yīng)用范圍較寬，但效率相對較低的方法，根據(jù)具體情況增加一些約束條件，適當縮小論域，然后尋找效率較高的方法。 G(xG(x)| )| G(xG(x)| )| 一個算法程序、一個封閉的軟件系統(tǒng)都一個算法程序、一個封閉的軟件系統(tǒng)都是演繹系統(tǒng)，典型的是一個邏輯式程

12、序，如是演繹系統(tǒng)，典型的是一個邏輯式程序，如Prolog Prolog 程序。程序。 在虛擬現(xiàn)實研究中，特殊化方法是一種在虛擬現(xiàn)實研究中，特殊化方法是一種常用的改進或?qū)嵱没瘎?chuàng)新方法。常用的改進或?qū)嵱没瘎?chuàng)新方法。例例4 4 半動態(tài)對象繪制的半動態(tài)對象繪制的LOMLOM方法方法 在繪制半動態(tài)對象，如隨風擺動的樹林時，為在繪制半動態(tài)對象，如隨風擺動的樹林時，為增強實時性，對視距進行劃分，不同視距范圍采用增強實時性，對視距進行劃分，不同視距范圍采用不同的運動模型，遠距離的樹枝不動，中距離的樹不同的運動模型，遠距離的樹枝不動，中距離的樹枝擺動，近距離的樹枝擺動加扭動。從而既提高了枝擺動，近距離的樹枝擺動

13、加扭動。從而既提高了效率，又保證了視覺效果。效率，又保證了視覺效果。3 3、歸納法、歸納法 泛化（擴張）方法泛化（擴張）方法 從若干同類對象的共同屬性得到該類整體屬性的邏輯方法。是從個體到一般的推理。是從個體到一般的推理。 計算機科學研究中常對考慮因素較多、適用范圍較窄的方法，忽略一些因素（約束），得到適用范圍較寬的方法。 G(xG(x)| )| G(x G(x)| )| 對論域限定較窄的方法，根據(jù)具體應(yīng)用適當擴對論域限定較窄的方法，根據(jù)具體應(yīng)用適當擴大論域，然后尋求新的方法，也即得到適用范圍更大論域，然后尋求新的方法，也即得到適用范圍更寬的方法。寬的方法。 G(x)G(x)， x x a,b

14、a,b a,b a,b a,ba,b G(y)G(y)，y y a,ba,b例例5 5 我們擴展布爾函數(shù)的值域，得到模我們擴展布爾函數(shù)的值域，得到模糊糊邏輯函數(shù)和模糊邏輯方程邏輯函數(shù)和模糊邏輯方程 布爾函數(shù)布爾函數(shù)f f的變量值域是的變量值域是00，11，將其擴展為，將其擴展為0,10,1區(qū)間上的實數(shù)就得到模糊邏輯函數(shù)區(qū)間上的實數(shù)就得到模糊邏輯函數(shù) 。 令：令： = = 0,10,1得到模糊邏輯方程。得到模糊邏輯方程。4 4、結(jié)合法、結(jié)合法 將針對同一問題的兩種不同解決方法相結(jié)合，將針對同一問題的兩種不同解決方法相結(jié)合，得到新的方法。得到新的方法。 E(x),F(xE(x),F(x) G(E(

15、x),F(x) G(E(x),F(x) 將一種方法引入另一種方法，得到新方法。將一種方法引入另一種方法，得到新方法。 G(x,y),F(xG(x,y),F(x) G(x,F(z),) G(x,F(z),例例6 6 在新型程序設(shè)計語言在新型程序設(shè)計語言KLNDKLND中將邏輯式與函中將邏輯式與函數(shù)式兩種程序設(shè)計風格相結(jié)合。數(shù)式兩種程序設(shè)計風格相結(jié)合。 邏輯式與函數(shù)式兩種風格的程序設(shè)計語言是人工智能中邏輯式與函數(shù)式兩種風格的程序設(shè)計語言是人工智能中常用的兩類語言，常用的兩類語言，基于不同的數(shù)學模型，前者是一階謂詞演基于不同的數(shù)學模型，前者是一階謂詞演算，后者是算，后者是 演算，這演算，這使得它們使

16、得它們在知識表示和處理方面在知識表示和處理方面具備各具備各自的優(yōu)點，分別適用于不同的應(yīng)用領(lǐng)域。我們把兩種程序設(shè)計自的優(yōu)點，分別適用于不同的應(yīng)用領(lǐng)域。我們把兩種程序設(shè)計風格結(jié)合起來，以提高語言的表達能力。風格結(jié)合起來，以提高語言的表達能力。 兩者可以有機結(jié)合，不是機械地湊在一起的基礎(chǔ)是它們的兩者可以有機結(jié)合，不是機械地湊在一起的基礎(chǔ)是它們的計算模型是可以統(tǒng)一的，函數(shù)是特殊的關(guān)系，關(guān)系又是以真、計算模型是可以統(tǒng)一的，函數(shù)是特殊的關(guān)系，關(guān)系又是以真、假為值的函數(shù)；同時參數(shù)傳遞機制模式匹配與合一相容。假為值的函數(shù)；同時參數(shù)傳遞機制模式匹配與合一相容。 例例7 7 將類比方法引入啟發(fā)式搜索，得到基于類將

17、類比方法引入啟發(fā)式搜索，得到基于類比的啟發(fā)式搜索方法。比的啟發(fā)式搜索方法。 啟發(fā)式搜索方法是啟發(fā)式搜索方法是利用與待求解問題有關(guān)的信息，對搜索利用與待求解問題有關(guān)的信息，對搜索路徑的取向給予一定選擇的搜索方法。啟發(fā)式方法提高了搜索路徑的取向給予一定選擇的搜索方法。啟發(fā)式方法提高了搜索效率，在許多領(lǐng)域，特別是人工智能應(yīng)用中取得了良好效果，效率，在許多領(lǐng)域，特別是人工智能應(yīng)用中取得了良好效果，成為人工智能的主要技術(shù)之一。成為人工智能的主要技術(shù)之一。 我們將類比推理引入我們將類比推理引入啟發(fā)式搜索，提出一種基于類比推理啟發(fā)式搜索，提出一種基于類比推理的啟發(fā)式搜索方法。該方法將與待求解問題相同或相似的

18、已知的啟發(fā)式搜索方法。該方法將與待求解問題相同或相似的已知問題的求解過程作為啟發(fā)信息來指導新問題的求解。問題的求解過程作為啟發(fā)信息來指導新問題的求解。5 5、類比法、類比法 聯(lián)想、平移方法聯(lián)想、平移方法 參考與當前要研究對象具有相似性的已有對象的有關(guān)理論，將其方法平移處理為關(guān)于被研究對象的理論方法。是從一類個體到另一類個體的推理是從一類個體到另一類個體的推理 G(x)| G(x)| F(x)| F(x)| 例例8 8 我們類比我們類比LODLOD提出提出LOLLOL、LoILoI、LOMLOM方法。方法。 為降低圖形系統(tǒng)的負載，對景物依視距不同使用為降低圖形系統(tǒng)的負載，對景物依視距不同使用多種

19、細節(jié)水平的幾何表示，這就是細節(jié)層次多種細節(jié)水平的幾何表示，這就是細節(jié)層次LODLOD技術(shù)。技術(shù)。 類比這一思想，在虛擬環(huán)境光照處理中，引入了類比這一思想，在虛擬環(huán)境光照處理中，引入了光照層次光照層次LOLLOL的概念，使光源在不同空間距離中具有不的概念，使光源在不同空間距離中具有不同的表現(xiàn)方式；為提高半動態(tài)對象的繪制效率同的表現(xiàn)方式；為提高半動態(tài)對象的繪制效率, ,提出運提出運動層次動層次LOMLOM的概念；的概念；為進行分布交互仿真的網(wǎng)絡(luò)擁塞控為進行分布交互仿真的網(wǎng)絡(luò)擁塞控制，提出興趣層次方法。制，提出興趣層次方法。6 6、嘗試對稱思維、反向思維、嘗試對稱思維、反向思維 自然界的規(guī)律是簡潔的

20、，對稱、對偶、矛與盾是普遍的。 有意識地在研究問題時嘗試從對稱、反對稱、反方向角度進行思考，提出猜象或想象，有時會得到靈感。例如，由數(shù)據(jù)驅(qū)動想到需求驅(qū)動。例如，由數(shù)據(jù)驅(qū)動想到需求驅(qū)動。問題：是什么決定了算法的時間和空間效率之間的對偶性，也就是說兩者測度的乘積在一定水平是一個不變量。7 7、發(fā)現(xiàn)結(jié)構(gòu)與尋找算法、發(fā)現(xiàn)結(jié)構(gòu)與尋找算法 發(fā)現(xiàn)所研究對象域中的數(shù)學結(jié)構(gòu)（序關(guān)系、等發(fā)現(xiàn)所研究對象域中的數(shù)學結(jié)構(gòu)（序關(guān)系、等價類、各種代數(shù)結(jié)構(gòu)等），然后尋找有關(guān)對象的數(shù)價類、各種代數(shù)結(jié)構(gòu)等），然后尋找有關(guān)對象的數(shù)學性質(zhì)或高速算法。學性質(zhì)或高速算法。具有數(shù)學結(jié)構(gòu)才有高速算法，無序的對象只有枚舉。 發(fā)現(xiàn)類比匹配問題中

21、的等價類，因而得發(fā)現(xiàn)類比匹配問題中的等價類，因而得到快速匹配算法。到快速匹配算法。 一般匹配等價于子圖同態(tài)問題，是一般匹配等價于子圖同態(tài)問題，是NPNP難解的。難解的。我們定義了匹配的名我們定義了匹配的名集和映射名集，而且證明了存集和映射名集，而且證明了存在等價類，從而找到了快速匹配算法。在等價類，從而找到了快速匹配算法。8 8、模型化、模型化 給出所研究對象的數(shù)學模型，將其形式化、模給出所研究對象的數(shù)學模型，將其形式化、模型化，然后尋找關(guān)于所研究對象的有關(guān)公理和數(shù)學型化，然后尋找關(guān)于所研究對象的有關(guān)公理和數(shù)學解，或者將所研究對象進行計算機仿真。解，或者將所研究對象進行計算機仿真。 這類研究會

22、導致較深刻的結(jié)果和原始性創(chuàng)新。這類研究會導致較深刻的結(jié)果和原始性創(chuàng)新。例例10 10 將具有過渡過程的邏輯電路抽象為將具有過渡過程的邏輯電路抽象為三值邏輯。三值邏輯。 f:0 x1 x2 x1 x2 x1:0 1 x2:1 0 f 分析險象的傳統(tǒng)方法是布爾差分法。該方法是判斷型分析險象的傳統(tǒng)方法是布爾差分法。該方法是判斷型的，即已知一個邏輯電路的輸入向量的，即已知一個邏輯電路的輸入向量 ，可以判定其是否存，可以判定其是否存在險象。在險象。 我們提出一種邏輯電路的三值邏輯模型，在該模型中，我們提出一種邏輯電路的三值邏輯模型，在該模型中，邏輯電路的輸出值可以是邏輯電路的輸出值可以是0 0、1 1或

23、或1/21/2。輸出值是。輸出值是1/21/2表示電路表示電路處于過渡狀態(tài)，可能產(chǎn)生險象。令：處于過渡狀態(tài)，可能產(chǎn)生險象。令： f(X)= 1/2 f(X)= 1/2 通過求解上述三值邏輯方程，可以得到使邏輯電路通過求解上述三值邏輯方程，可以得到使邏輯電路f(X)f(X)可能可能產(chǎn)生險象的全部輸入解向量產(chǎn)生險象的全部輸入解向量 (x1,x2,xn(x1,x2,xn) )，再通過一定的，再通過一定的方法（如布爾差分等）求得會產(chǎn)生險象的全部輸入解向量。方法（如布爾差分等）求得會產(chǎn)生險象的全部輸入解向量。9 9、模擬人的思維方法、模擬人的思維方法 用電腦代替人腦是計算機和人工智能研究人員的用電腦代替人腦是計算機和人工智能研究人員的一個追求目標，因此模擬人的思維是計算機科學和人一個追求目標，因此模擬人的思維是計算機科學和人工智能創(chuàng)新的源泉。工智能創(chuàng)新的源泉。 例如人工智能中關(guān)于“知道”的邏輯： 人對“知道”的一種認識 公 理（1）a知道的p都是真的 KaP P（2）a知道P，則a就知道a知道P KaP KaKaP（3）a知道PQ，則a知道P時就知道Q Ka(PQ)(KaPKaQ)例例1111對類比思維進行建模。對類比思維進行建模。 人類的類比思維過程人類的類比思維過程 形式模型（形式化）形式模型（形式化） 計算模