數(shù)理邏輯和算法理論 課件 袁相碗 第5-7章 丘奇-圖靈論題的創(chuàng)立和計算機的出現(xiàn)-人工智能與算法

數(shù)理邏輯和算法理論

——計算機科學與人工智能的數(shù)學基礎第5章丘奇-圖靈論題的創(chuàng)立和計算機的出現(xiàn)1可計算性理論的興起2丘奇-圖靈論題的創(chuàng)立3圖靈理想計算機的意義4計算機的出現(xiàn)可計算性理論的興起5.15.1可計算性理論的興起哥德爾首次精確地給出原始遞歸函數(shù)的描述性定義之后，激起了人們在原始遞歸函數(shù)基礎上進一步尋找與研究更為一般的可計算函數(shù)的熱情，開始提出并猜測:原始遞歸函數(shù)是否窮盡了一切可計算的函數(shù)？結果很快發(fā)現(xiàn)了其答案是否定的。因為，令0,…,如表示原始遞歸函數(shù)的有窮序列,如果定義函數(shù)g(n)=如3)+1,則這個函數(shù)g直觀上是可計算的，但它不出現(xiàn)在這一有窮序列之中，而且不是原始遞歸的。據(jù)此,可計算的但非原始遞歸的函數(shù)必是存在的。5.1可計算性理論的興起5.1.1阿克曼函數(shù)希爾伯特在1925年《論無窮》的演講中，提出了是否有些遞歸式可以定義非原始遞歸函數(shù)呢？他的學生阿克曼在1928年的《論實數(shù)的希爾伯特構造》中解決了這個問題。5.1可計算性理論的興起5.1.2三種可計算函數(shù)模型的提出阿克曼函數(shù)的發(fā)現(xiàn)，雖然表明了可計算但非原始遞歸函數(shù)是存在的，但是除原始遞歸函數(shù)之外,是否還有其他可計算函數(shù),以及如何給出相應的數(shù)學定義這一根本問題并未解決。于是，在1930年代研究可計算函數(shù)的熱潮中，最早提出一般遞歸函數(shù)精確定義的是法國學者艾爾伯朗(J.Herbrand)o他在1931年的一封致哥德爾的信中提出了一般遞歸函數(shù)的定義。然后，哥德爾在1934年的講演《論形式數(shù)學系統(tǒng)屮的不可判定命題》中,根據(jù)艾爾伯朗的提議，給出了一般遞歸函數(shù)的如下定義：如果屮表示一個未知函數(shù),饑,…，如是已知函數(shù)，并且如果?和少各以最一般的方式彼此代入，而所得表達式的某些對是相等的，那么若所得的函數(shù)等式集合對屮有一個且僅僅有一個解，則寸是_個遞歸函數(shù)。丘奇一圖靈論題的創(chuàng)立5.25.2丘奇一圖靈論題的創(chuàng)立1930年代發(fā)現(xiàn)的艾爾伯朗一哥德爾一克林的一般遞歸函數(shù)、丘奇的X可定義性函數(shù)和圖靈的理想計算機及其可計算函數(shù)（奇妙的是克林和圖靈都是丘奇的學生，丘奇的X可定義性函數(shù)在歷史上是最早發(fā)現(xiàn)的），它們的動機和方法是截然不同的，但卻相互獨立地刻畫了本質上等同的可計算性函數(shù)。不久，丘奇和克林證明了'定義性函數(shù)和一般遞歸函數(shù)是等價的。接著,圖靈在《論可計算數(shù)》的附錄中，又證明了他的可計算函數(shù)和X可定義性函數(shù)也是等價的。亦即三人證明了：“一切算法可計算函數(shù)=一般遞歸函數(shù)-X可定義性函數(shù)=圖靈可計算函數(shù)”（其中“表示等同，互推或當且僅當）5.2丘奇一圖靈論題的創(chuàng)立5.2.1丘奇一圖靈論題是可計算性的理論基礎丘奇一圖靈論題的主要目的是為了將計算性函數(shù)及其算法刻畫為既直觀又清晰、既簡要又有一定理論依據(jù)的“斷言”（相當于通用的可計算性函數(shù)或算法）o其思想方法是:數(shù)學的公理化思想和自然科學的假設演繹法相結合，其思維過程如圖5-2所示。5.2丘奇一圖靈論題的創(chuàng)立由此可見:丘奇一圖靈論題相當于自然科學方法論中的經“由果到因”的數(shù)學思維過程概括出來的“科學定律”（數(shù)學假設），是可計算性理論的基本原理。其主要內涵是：①丘奇一圖靈論題是源于數(shù)學實踐中發(fā)現(xiàn)的三種不同的可計算性數(shù)學模型，通過非邏輯的歸納思維方式將其概括出來的。它不是數(shù)學定理，也非嚴格意義上的命題，但它在數(shù)學的實踐檢驗中是正確而可靠的，像數(shù)學中的猜想,至今尚未發(fā)現(xiàn)任一反例。它的數(shù)學真理性是“問題求解”的算法可計算性的正確性與有效性，而非數(shù)學的公理化嚴密性與抽邏輯性。②丘奇一圖靈論題從直觀的初始函數(shù)或原始遞歸函數(shù)出發(fā)，通過“代入”和“替換”等計算規(guī)則，將可計算性對象在有限步驟內計算出來的數(shù)學理論;本質上則是立足于可信性、能行性、可構造性，以自然數(shù)論和潛無窮論為基礎的算法化的數(shù)學思想方法。丘奇一圖靈論題的是判定可計算性對象和不可計算性對象的一個嚴格的準則。5.2丘奇一圖靈論題的創(chuàng)立5.2.2丘奇一圖靈論題本質上是“判定性臺可計算性”一階謂詞演算的判定性問題源于20世紀20年代希爾伯特提出的用計算代替推理的謂詞運算的判定性問題，丘奇和圖靈在分別而獨立地提出相互等價的X演算和可機算性函數(shù)的同時，分別而獨立地提出并證明了一階謂詞演算的不可判定性定理，其中應用了“判定性O可計算性”的原理。5.2丘奇一圖靈論題的創(chuàng)立5.2.3丘奇一圖靈論題的算法概念計算和算法是密不可分的、既有聯(lián)系又有區(qū)別的兩個不同概念，總體而言,任何計算都是在一定的算法支持下進行的。丘奇一圖靈論題則首次將算法概念從計算概念中獨立出來，將其作為數(shù)學的直接研究對象，并在此基礎上革新了算法的概念，提升了算法的地位。圖靈理想計算機的意義5.35.3圖靈理想計算機的意義20世紀30年代，圖靈在研究哥德爾不完全性定理的過程中,為了解決數(shù)理邏輯中一個基本理論問題（相容性以及數(shù)學問題機械可解性或可計算性的判定問題）和給出“可計算性”概念的嚴格定義,別具一格地提出了理想計算機及其可計算性理論。圖靈的理想計算機本質上是一個虛擬的“計算機”，其關注的焦點是邏輯結構，其出發(fā)點是用理想計算機代替或定義數(shù)學的“形式系統(tǒng)”，其目的是使其成為可以模擬任何特定圖靈機的“廣義計算機”、“通用計算機”或“萬能計算機”，簡稱UTM（即UniversalTuringMachine,通用圖靈機）。5.3圖靈理想計算機的意義5.3.1圖靈機給出了“形式系統(tǒng)”的精確定義丘奇在提出了“丘奇論題”之后,為了解釋與辯護它的正確性，曾提出了有兩個更為一般的能行可計算性的定義方法:①符號算法的方法（如丘奇的X運算和圖靈的可計算函數(shù)）；②形式系統(tǒng)的方法（如艾爾伯朗-哥德爾-克林的一般遞歸函數(shù)）。圖靈［第5章丘奇一圖靈論題的創(chuàng)立和計算機的出現(xiàn)的理想計算機及其可計算函數(shù)，所采用的“機械程序”（或“算法”）則不僅具有相當于形式系統(tǒng)的功能，而且可借此精確地定義“形式系統(tǒng)”的概念。這在數(shù)理邏輯發(fā)展史上是繼哥德爾不完全性定理之后的又一個重大成果。5.3圖靈理想計算機的意義5.3.2圖靈機是一種通用計算機（UTM）有關圖靈機的定義（或原理），我們已在5.1中作了簡要的論述，指出了它的主體結構是由如下三個部分（或要素）組成的：①一條無窮長的用帶（相當于存儲器），用于存儲信息和圖靈程序；②一個讀寫頭（相當于計算器），根據(jù)圖靈指令讀取冊帶上內容，執(zhí)行計算過程中的每一步的計算；③一個控制裝置（相當于控制器），用于保證圖靈指令按照計算規(guī)則得到嚴格而無歧義的執(zhí)行。所以，人稱圖靈機是人類有史以來發(fā)明的在直覺上是最簡單、最可靠、最通用、最有效的計算裝置。這意味著：①圖靈機是數(shù)字的、離散的，可模擬任意一個離散狀態(tài)，并精確描述從某一確定的離散狀態(tài)到另一個離散狀態(tài)的轉換；②如果不考慮速度的話,那么圖靈機便是一種通用的數(shù)字計算機；③圖靈機從理論上證明了設計、研制與或制造任一類的計算機是可能的。5.3圖靈理想計算機的意義5.3.3圖靈機是一種“存儲程序型”的UTM圖靈針對當時人們的計算方式及其過程,致力于用計算機模擬人腦思維的計算過程。首先，對人腦思維的計算方式及其過程進行數(shù)學的理解與分析。在此基礎上，用機器的語言符號系統(tǒng)將其概括為“計算模型”（數(shù)學模型）;其次，設計并選定一個用機器語言符號表示的被編碼的計算機程序（算法）；最后，將程序輸入計算機，由計算機一步一步地將其存入存儲器中，并在有限步驟內獲得結論。因此,圖靈機是一種“存儲程序型”的UTM,其主要內涵是：①控制器按圖靈指令讀取存儲器中的程序；②計算器按圖靈指令執(zhí)行每一步的計算；③如果需要修正或改變程序,只需更改存儲器的內容,而不必重寫控制器。因此，“存儲程序”是圖靈機的一個十分重要而深刻的核心思想，人稱是“圖靈機軟件”，其主要功能是:控制計算機整體運轉,發(fā)揮機器主體結構各部分的的功能，協(xié)調機器主體結構各部分的相互作用,提高計算機計算力和高效性,是機器（物理系統(tǒng)）能否按照人類設計的被編碼的計算機程序正確而高效地完成計算任務的前提條件。5.3圖靈理想計算機的意義5.3.4圖靈機的局限性丘奇一圖靈論題的立足點或出發(fā)點是求解問題，其思維過程是在對求解問題進行分析研究的基礎上找到相應的算法，然后利用算法獲得求解問題的解答。其思維過程如圖5-3所示。計算機的出現(xiàn)5.45.4計算機的出現(xiàn)自古以來，用機器代替人工計算是人類的長期追求。在這一歷史過程中,數(shù)學家始終扮演著主要的角色。早在17世紀，著名的德國數(shù)學家和數(shù)理邏輯的創(chuàng)始者萊布尼茨曾大聲疾呼:“把計算交給機器去做，讓優(yōu)秀的人才從繁重的計算中解脫出來”，并身體力行地設計與制造了一臺“算術計算器”0從此開始,計算機器的設計與制造一直是數(shù)學家追求與研究的重大課題。5.4計算機的出現(xiàn)5.4.1計算機器的進化古代的計算機械有算盤,十進位值制的算盤最早出現(xiàn)在中國，明代著作《魁本對相四言雜字＞（1371年）中載有十檔算盤圖，意味著算盤發(fā)明早于此前;程大位（1533-1606）的《算法統(tǒng)綜》詳述了珠算已相當普及?！端惴ńy(tǒng)綜》不僅傳至日本，而且古希臘人與羅馬人也使用過。17世紀的歐洲，人們開始借助于齒輪技術追求更復雜精確的計算機器,1642年，法國著名數(shù)學家帕斯卡(Pascal,1623-1662)發(fā)明了第一臺能做加減運算的機械式的臺式計算機(通過齒輪將數(shù)據(jù)輸入機器，再轉動曲柄來進行計算)。1671年，萊布尼茨著手改進帕斯卡的計算機器，采用梯形軸設計與制造了一臺能做加減乘除四則運算的“算術計算器”。但是,帕斯卡的與萊布尼茨的計算機器都不是很實用。直至1818年,法國的托馬斯(Thomas)在帕斯卡和萊布尼茨的基礎上研制成托馬斯型的手搖計算機,并于1821年建廠投產，首批生產了15臺,開創(chuàng)了計算機器的制造業(yè)。5.4計算機的出現(xiàn)在計算機器發(fā)展史上，邁出關鍵性一步的是英國著名數(shù)學家巴貝奇(Babbage,1791-1871)他對19世紀英國數(shù)學的復興貢獻良多,1816年當選為皇家學會會員，1827年任劍橋大學盧卡斯教授。他熱衷于計算機制造，并頗具獨創(chuàng)性。1823年,在英國政府的資助下，他著手研制一種有26位有效數(shù)字，能計算做四則運算的，并能打印出六階差的“差分機”，其結果并沒有取得令人滿意的進展。十年之后，他放棄了差分機，雄心勃勃地開始設計與研制一種能完全自動地進行由操作者指定的一系列算術運算的“分析機”0這種分析機由“加工部”、“存儲部”以及專門控制運算程序的設備所組成，其性能已相當于現(xiàn)代電子計算機，其主要裝置有：①存儲裝置；②提取存儲數(shù)并進行計算的裝置；③控制演算開始或終止的裝置；④輸出，輸入裝置。5.4計算機的出現(xiàn)為了研制這臺分析機，巴貝奇付出了畢生的精力和全部財產，甚至不惜辭去榮譽極高的劍橋大學盧卡斯教授席位，但是，由于時代的限制，巴貝奇分析機的純機械的設計方案在技術實施上遇到了巨大的障礙，直至他去世仍未能實現(xiàn)他的夢想。事后，從他留下的大量而詳盡的設計方案、圖常和說明中，人們發(fā)現(xiàn)了他的真知灼見，并確認:他的分析機實質上是世界上最早的通用程序控制數(shù)字計算機的設計思想。巴貝奇則是現(xiàn)代電子計算機的先驅。進入20世紀以來，為了適應科學技術發(fā)展的需要，提高計算機的計算速度,人們開始致力于突破機械設計的框框,試圖用電器元件來代替機械齒輪。1941年，德國工程師朱斯(KZuse)制成第一臺全部采用繼電器的通用程序控制計算機(Z-3)。不幸的是1944年，它被砸毀。1944年，美國國際商用機器公司(IBM)和哈佛大學聯(lián)合研制成“MARK-1”，這是世界第一臺能實際操作的通用程序控制計算機(它只部分地使用了繼電器，實質上仍是一臺機械計算機)。1945-1947年，全部采用繼電器的“MARK-2”研制成功。這種機電型的計算機的研制成功，不僅在一百年之后實現(xiàn)了巴貝奇的夢想，而且意味著電子技術開始進入了計算機，預示著電子計算機時代即將來臨。5.4計算機的出現(xiàn)5.4.2計算機的出現(xiàn)由于繼電器開關速度大約是百分之一秒，以繼電器為元件的計算裝置仍遠不能滿足科學技術發(fā)展的實際需要。而且MRAK-1和MRAK-2這類機電型計算機從開始運作時就已顯得有些過時，于是,20世紀30年代開始，一些目光敏銳的學者已看到了20世紀初發(fā)明的電子管代替繼電器的可能性（真空三極管柵極控制電流開關的速度比繼電器快一萬倍）。為此，為了滿足科學技術發(fā)展的需求，特別是第二次世界大戰(zhàn)軍事上的燃眉之急，美國阿伯丁彈道實驗研究室和賓夕法尼亞大學莫爾學院合作，承擔了為陸軍研制高速計算機（能每天提供6張炮擊火力表）的任務（因為從二戰(zhàn)開始,這個實驗室用于200多名計算員，一張火力表往往要計算兩三個月，戰(zhàn)爭急需研制一種新型的高速計算機）。在其中起著牽頭和核心作用的是原數(shù)學家，年僅24歲的阿伯丁實驗室的總工程師戈德斯坦（HColdstine）中尉。5.4計算機的出現(xiàn)5.4.3馮?諾依曼是計算機的奠基人馮?諾依曼（JohnvonNeumann,1903—1957）于1903年12月28日出生于匈牙利的布達佩斯，是一個罕見的神通,19歲就讀于布達佩斯大學,1926年獲數(shù)學博士學位,1933年作為創(chuàng)始數(shù)學家之一加入普林斯頓高等研究院，在數(shù)學、理論物理和數(shù)理邏輯等領域都作出過重要貢獻。二戰(zhàn)期間馮?諾依曼的研究方向發(fā)生了根本性的轉變，從純粹數(shù)學研究轉向了應用數(shù)學，特別是反法西斯戰(zhàn)爭的有關軍事項目，如1943年參與曼哈頓計劃。二戰(zhàn)結束后，其主要精力則致力于計算機的研究。5.4計算機的出現(xiàn)馮?諾依曼在計算機工程與技術中的開創(chuàng)性貢獻，其主要思想集中在他牽頭撰寫的EDVAC的報告中。這個報告被定義為“馮?諾依曼架構”，它不僅體現(xiàn)了馮?諾依曼設計思想，而且為計算機產業(yè)的形成與發(fā)展奠定了基礎。其中最核心的思想是：（1）明確指出了計算機的主體結構（2）將“外插型程序”變?yōu)椤按鎯Τ绦蛐汀保?）對ENIAC的設計思想作出了三點改進或變革5.4計算機的出現(xiàn)5.4.4數(shù)字電子計算機的發(fā)展從圖靈的理想計算機到馮?諾依曼設計與研制成功的EDVAC（一種“數(shù)字電子計算機".digitalelectroniccomputer），是以電子為元器件的“數(shù)字化（其數(shù)據(jù)都用離散信號表示的）”的協(xié)助人類用于數(shù)值與非數(shù)值計算的機器（簡稱計算機）。數(shù)字電子計算機的發(fā)展從1945年至1970年代已發(fā)展到第四代。第6章計算機科學與算法1計算機科學是研究算法的科學2算法基礎-—可計算性理論3計算機算法的原理4計算機算法的執(zhí)行——程序設計語言與程序計算機科學是研究算法的科學6.16.1計算機科學是研究算法的科學1965年，美國出現(xiàn)了一門新學科:ComptuerSciene,通常被翻譯為計算機科學。隨著計算機的快速發(fā)展和計算機應用的迅速擴展，“計算機科學”這個名詞很快地流行起來,世界上眾多知名大學隨之紛紛設立起以計算機科學命名的科系或研究機構。其發(fā)展之快，吸引力之大，在新學科中也是罕見的。但是，什么是計算機科學及其學科性質？當時人們并沒有深究。1974年，美國計算機學會曾對世界各地59個計算機系進行過一次調查，其結果是各校對此沒有統(tǒng)一的認識。1.計算機科學學科性質的探討2.計算機科學是研究算法的科學3.計算機算法的主要特征6.2算法基礎——可計算性理論可計算性理論源于20世紀30年代丘奇一圖靈論題的創(chuàng)立。計算機出現(xiàn)之后,為建立計算機算法的理論基礎，人們的關注點從可計算函數(shù)的探索轉向了對不可計算對象的分類及其數(shù)學結構的研究。于是，計算機的可計算性理論便成為主要研究計算復雜性和不可計算對象結構的一個數(shù)學分支。它是數(shù)理邏輯的主要領域之一，又是計算機科學的理論基礎。6.2算法基礎——可計算性理論6.2.1URM模型及其可計算函數(shù)定義20世紀30年代，克林給出了可計算函數(shù)的數(shù)學描述,丘奇用A演算定義了可計算函數(shù)，圖靈的理想計算機及其可機算函數(shù)則為計算注入了一種全新的理念，并為計算機科學奠定了理論基礎。20世紀50年代至60年代，先后出現(xiàn)了多種以“計算機”為背景，以“指令和程序”為基礎的理想計算機計算模型。1963年，謝菲爾得森(Shepherdson)和斯圖吉斯(Sturgis)引進了以理想的無窮存儲器(UnlimitedRegisterMachine,URM)為計算模型的指令和程序。由于URM所采用的指令系統(tǒng)和計算方法與現(xiàn)代計算機的計算形式十分相似，較好地展現(xiàn)了現(xiàn)代計算機的計算本質，故人稱這是繼圖靈之后，理想計算機及其可機算函數(shù)的定義邁出了新的重要的一步。1.URM計算模型2.URM指令3.URM程序4.URM的計算5.URM可計算函數(shù)的定義6.2算法基礎——可計算性理論6.2.1URM模型及其可計算函數(shù)定義20世紀30年代，克林給出了可計算函數(shù)的數(shù)學描述,丘奇用A演算定義了可計算函數(shù)，圖靈的理想計算機及其可機算函數(shù)則為計算注入了一種全新的理念，并為計算機科學奠定了理論基礎。20世紀50年代至60年代，先后出現(xiàn)了多種以“計算機”為背景，以“指令和程序”為基礎的理想計算機計算模型。1963年，謝菲爾得森(Shepherdson)和斯圖吉斯(Sturgis)引進了以理想的無窮存儲器(UnlimitedRegisterMachine,URM)為計算模型的指令和程序。由于URM所采用的指令系統(tǒng)和計算方法與現(xiàn)代計算機的計算形式十分相似，較好地展現(xiàn)了現(xiàn)代計算機的計算本質，故人稱這是繼圖靈之后，理想計算機及其可機算函數(shù)的定義邁出了新的重要的一步。1.URM計算模型2.URM指令3.URM程序4.URM的計算5.URM可計算函數(shù)的定義計算機算法的原理6.36.2算法基礎——可計算性理論算法概念自古有之,0.3我們簡略地介紹了算法概念的演變過程;計算機出現(xiàn)之后,我們在6.1中將計算機科學定位于一門研究計算機算法的學科;6.2則指出了可計算性理論是算法基礎。本節(jié)進_步對計算機算法的原理進行探討。6.2算法基礎——可計算性理論6.3.1計算機算法的有關概念在6.1與6.2中，我們已對算法的概念及其特征與性質作了較為詳細的論述。計算機算法是計算機出現(xiàn)后，以丘奇一圖靈論題為基礎,在創(chuàng)立計算機科學的過程中形成的。它實現(xiàn)了圖靈理想計算機及其可計算性理論，本質上是一種人機結合的、讓計算機替代人類計算過程的算法。1.計算機算法的定義算法是某類問題求解的方案或過程，其目的在于將某類問題的計算過程表示為有限的序列。對某類問題的求解,首先必須建立一個符號系統(tǒng)，將問題求解概括為一個模型。然后，構造一個合適的執(zhí)行流程，稱為算法,在算法指引下編寫程序接著指導計算機執(zhí)行,并最終獲得計算結果，這種算法便稱為“計算機算法”o據(jù)此,計算機科學中所涉及的算法都是計算機算法（有關計算機算法的主要性質和6.2所論及的是完全相同的，這里不再重復）。2.計算機算法的主要內涵是“計算”與“過程”6.2算法基礎——可計算性理論3.計算機算法的描述一般常用的計算機算法的描述有三種。（1） 形式化描述用符號形式描述計算機算法（或稱其為“類語言”描述或“偽代碼”描述）。（2） 半形式化描述這是一種用符號描述和自然語言混合的算法描述,是一種用圖示形式表示算法的描述方法。其中有三種基本圖示符號，將它們之間用常箭頭的直線相連而構成一個算法的流程，稱為“算法流程圖”。6.2算法基礎——可計算性理論算法流程圖的三種基本圖示符號及箭頭是:①矩形:計算單位,用于表示計算(或操作)，其內容可用自然語言書寫在矩形內，如圖6-6(a)所示；②菱形:用于表示控制中的斷判條件，其內容可用自然語言書寫在菱形內，如圖6-6(b)所示；③橢圓形:用于表示算法的起點與終點，其有關說明可用自然語言書寫于橢圓形內，如圖6~6(c)所示；④箭頭:用于表示控制流程執(zhí)行的次序，如圖64(d)所示。(3)非形式化描述這是計算機算法最原始的描述。它一般以自然語言為主，也可使用少量類語言。圖6-5所示的描述方式，即非形式化描述的算法。6.2算法基礎——可計算性理論單擊此處輸入你的正文6.2算法基礎——可計算性理論6.3.2計算機算法的復雜性表示1.算法復雜性“階”的概念計算機算法復雜性，又稱為算法復雜度(AlgorithmComplexity)，其中的“度量”是按“階”分類的，并提出“有效算法”與“指數(shù)算法”的概念。算法復雜度的分“階”，在前面的討論中,我們已指出了時間與空間的復雜度都是n的函數(shù)。如果將算法的時間與空間復雜度分別記為『5)與g("),用。表示將7(")和g5)所分成的檔次，稱為階。(1)算法時間復雜度的分“階”（2）算法空間復雜度的分“階”6.2算法基礎——可計算性理論2.多項式算法和指數(shù)算法的定義有鑒于用“階”的概念劃分復雜度與所使用的處理系統(tǒng)是無關的。因此，若取常量c>0和正整數(shù)恥當n>N時，有g（n）>c>1/（n）I，則稱g（zi）=O（f（n））。如果g（n）=。（/（游），M/（n）=0（g（"））,則稱g（"）=?（/（?））（亦即空間復雜度和時間復雜度是互推或等階的）。這樣，對于圖靈機而言，如果存在一整數(shù)礦使九（兒）=?（z?）,則稱心為多項式算法。如果TM=?（2"），便稱心是指數(shù)時間算法。6.2算法基礎——可計算性理論這樣,在對人n）和g（幾）作了上述六個階的劃分之后，又可將算法根據(jù)復雜度由低到高分成三個級別：?線性級算法（可計算性）：①?④，此類可在線性時間內完成；?多項式級算法（確定性算法）：此類算法可在多項式時間內完成。其復雜度大于線性級算法。它可以接受，但是實現(xiàn)難度大；?指數(shù)級算法（非確定性算法）：具有高度復雜性與困難度的算法。雖然對指數(shù)范圍加以限定時，可在計算機上計算，但是效率極低。當指數(shù)范圍不作限定時,則是不可計算的，故一般不予選用。6.2算法基礎——可計算性理論3.“有效算法”的概念根據(jù)算法復雜度的分階，關于有效算法概念較具代表性的定義是：①對于一個算法，如果其運行時間（空間規(guī)模）可以表示為輸入規(guī)模的多項式,則稱該算法是有效算法。②《人工智能簡史》則指出，計算機算法有兩個層面：其一，可計算性滿足丘奇一圖靈論題；其二,復雜性遵循洪加威相似性:各類計算模型可以在多項式時間（空間規(guī)模）內實現(xiàn)相互模擬。6.2算法基礎——可計算性理論4.“指數(shù)級算法”的概念根據(jù)算法復雜度的分階，關于“指數(shù)級算法”概念較具代表性的定義是：①對于一個算法，如果其運行時間（空間規(guī)模）可以表示為輸入規(guī)模的指數(shù)級算法,則稱該算法是“非有效算法”，也稱“指數(shù)級算法”。②也可以說，計算機算法有兩個層面：其一，可計算性滿足丘奇一圖靈論題。其二，復雜性遵循洪加威相似性:各類計算模型在指數(shù)時間（空間規(guī)模）內實現(xiàn)相互模擬。從目前情況看，計算機科學很難接受指數(shù)級算法。但是在實際操作中，經常會出現(xiàn)此類算法,為此我們進_步對它作分類分成兩種。6.2算法基礎——可計算性理論6.3.3計算機算法的設計計算機算法的設計，主要是指算法構造的過程及其方法。1.計算機算法設計的目標計算機算法設計的目標是將算法轉換成計算機程序。為此,必須引入程序設計的語言，最終用算法編碼成計算機能執(zhí)行的有序的計算程序。2.計算機算法評估計算機算法和其他算法一樣，不是唯一的，而是多個的。所以，算法有好壞之分,優(yōu)劣之列，它是需要評估的，其評估指標包括三個部分：①算法的可計算性:必須滿足丘奇一圖靈論題；②算法的正確性:有輸入必有輸出;算法的正確性是必須證明的；③算法的效率性:盡量少地消耗計算機的時間與空間資源。一般而言，多項式時間與空間算法是可以接受的，而復雜性過高的指數(shù)算法則是不予采用的。6.2算法基礎——可計算性理論3.計算機算法的完整表示到此為止，我們已經對計算機算法做了全面的介紹,下面介紹一個算法的完整表示。一個算法的完整表示有兩個部分:算法的描述部分與算法的評價部分。（1）算法的描述部分算法的描述部分共含4個內容，分別是：①算法名:給出算法的標識，用于唯一標識指定的算法，在算法名中還可以附帶一些必要的說明。②算法輸入:給出算法的輸入數(shù)據(jù)及相應的說明，有時，算法可以允許沒有輸入。③算法輸出:給出算法的輸出數(shù)據(jù)要求及相應說明。任何算法必須有輸出。否則,該算法就是一個無效算法。④算法流程:給出算法的計算過程，它可以用形式化描述，也可以用半形式或非形式化描述，但是它_般不用程序設計語言描述。6.2算法基礎——可計算性理論(2)算法的評價部分算法的評價部分是算法中所必需的，它包括兩方面內容。①算法的正確性:必須對算法是否正確給出證明，特別是對復雜的算法尤為需要。算法的證明一般用數(shù)學方法實現(xiàn)。但對簡單的算法只要做必要說明即可。②算法分析:包括算法時間復雜性分析與空間復雜性分析。一般來說，戲幾)與S(n)在有效時間與空間之內都是可以接受的，當然它們的階越低越好。但是,對指數(shù)級算法一般不予接受。一個完整的算法表示一定包括這6個內容。計算機算法的執(zhí)行——

程序設計語言與程序6.46.4計算機算法的執(zhí)行——程序設計語言與程序6.4.1計算機算法與程序計算機算法是圖靈的理想計算機及其可計算性的原理的產物。它有一個符號系統(tǒng)，用以將計算機模擬人類計算的過程,給出形式化的描述。但這種描述可以有多種，可以選擇其最優(yōu)者，稱為算法設計。但最終所選定的算法并不能驅動計算機運行而得到結果，因此必須將選定的計算機算法轉換成用程序設計語言表示的,并被編碼了的計算機程序。將程序輸入計算機,由計算機執(zhí)行，并最終獲得正確的結果。由此可見,算法不等同于程序。算法的目標是設計一個正確而高效的計算過程,而程序的功能則是實現(xiàn)一個正確而高效的計算過程。算法是程序設計的基礎，程序是實現(xiàn)算法的目的。據(jù)此,計算機模擬人類計算過程,是算法和程序設計相互合作的過程,可用圖6-7表示。6.4計算機算法的執(zhí)行——程序設計語言與程序6.4.2程序設計語言由計算機算法轉換成計算機程序是由程序設計語言作為工具而完成的。程序設計語言是計算機所能理解的一種人工制作的語言。計算機是以電子器件為主的一種裝置,一般情況下它不能執(zhí)行操作，它只能理解程序設計語言，并聽從于用程序設計語言編寫的程序執(zhí)行操作。人類以算法為依據(jù)，用程序設計語言編寫程序并發(fā)送給計算機，此后計算機即按程序要求執(zhí)行，最后獲得結果。因此程序設計語言是將算法在計算機中實現(xiàn)的關鍵。下面討論程序設計語言中的幾個主要問題。1.程序設計語言的基本組成6.4計算機算法的執(zhí)行——程序設計語言與程序程序設計語言有多種，現(xiàn)就目前常用的C語言為例說明程序設計語言的主要內容和成分。一個程序設計語言一般由三部分組成:數(shù)據(jù)說明、處理描述及程序結構規(guī)則。⑴數(shù)據(jù)說明程序的處理對象是數(shù)據(jù)，因此在程序設計語言中必有數(shù)據(jù)描述。程序設計語言中包含三種基本數(shù)據(jù)元素,它們是：①數(shù)值型:包括整數(shù)型、實數(shù)型等；②字符型:包括變長字符串、定長字符串等；③布爾型:即僅由True及False兩個值組成的類型。在程序設計語言中，一般用變量表示數(shù)據(jù)。變量一般由變量名與變量類型兩部分組成。在C語言中,intx定義了一個變量名為x,類型為整型的變量。在語言中，四種基本類型為整數(shù)型、實數(shù)型、字符型及布爾型等，可分別表示為int、real、char及boolean。此處還可用常量表示固定數(shù)據(jù)。現(xiàn)代的程序設計語言中還會包括常用的數(shù)據(jù)元素及數(shù)據(jù)單元，如元組、數(shù)組等。6.4計算機算法的執(zhí)行——程序設計語言與程序(2)處理描述處理描述給出了程序中的基本處理操作。①基本運算處理。?數(shù)值操作:針對數(shù)值型數(shù)據(jù)的一些操作，如算術運算、比較運算等；?字符操作:針對字符型數(shù)據(jù)的一些操作,如字符串比較、拼接、刪、減等；?邏輯操作:針對布爾型數(shù)據(jù)的一些操作，如邏輯運算、邏輯比較等。在程序設計語言中，處理描述首先定義一些運算符，如+、-、x、+、＜、＞、=等。其次,由運算符、變量及常量可以組成表達式，如x=a+bxc等。它們組成了基本運算處理單元。6.4計算機算法的執(zhí)行——程序設計語言與程序②流程控制。流程控制一■般有三種。?順序控制:程序執(zhí)行的常規(guī)方式是順序控制,即程序在執(zhí)行完一條語句后，順序執(zhí)行下_條語句。順序控制并不需要用專門的控制語句表示；?轉移控制:程序執(zhí)行在某些時候需要改變順序執(zhí)行方式而轉向執(zhí)行另外的語句，稱為轉移控制。轉移控制的實現(xiàn)需要用專門的轉移控制語句完成；?轉移控制:一般有兩種，一種是無條件轉移，另一種是條件轉移。所謂條件轉移，即預設有一個條件，當條件滿足時,程序轉向執(zhí)行指定的語句;否則順序執(zhí)行。無條件轉移，即不預先設定任何條件，不管發(fā)生何種情況，程序總是轉向執(zhí)行某指定語句。6.4計算機算法的執(zhí)行——程序設計語言與程序③循環(huán)控制。在程序中經常會出現(xiàn)反復執(zhí)行某段程序,直到某條件不滿足為止,稱為循環(huán)控制O循環(huán)控制的實現(xiàn)需要用專門語句完成,稱為循環(huán)控制語句0在C語言中可用while語句、for語句等表示循環(huán)控制語句。while語句如下：while(p)A；上述語句表示若條件P滿足則重復執(zhí)行操作A,直到p不滿足為止。④賦值功能。賦值功能主要用于將常量賦予變量。在程序設計語言中,一般用“=”表示賦值。如“intx；x=18”表示將常量18賦予變量x,x=18稱為賦值語句。⑤傳輸功能。傳輸功能用于程序中數(shù)據(jù)的輸入、輸出。C語言中有兩個函數(shù),它們是scanf()與printf()，分另0用于標準的輸入、輸出。6.4計算機算法的執(zhí)行——程序設計語言與程序(3)程序結構規(guī)則程序是有結構的，不同語言的程序結構是不同的。程序結構是指如何構造程序,它需要按語言所給予的規(guī)則構造。在C語言中的函數(shù)結構，程序按函數(shù)組織,程序中有一個主函數(shù),其他函數(shù)都可由主函數(shù)通過調用進行連接。6.4計算機算法的執(zhí)行——程序設計語言與程序2.編碼用程序設計語言編寫程序的過程稱為編程或編碼。編碼是依據(jù)算法進行的，一般有以下幾個部分的工作。①依據(jù)算法中的輸入、輸出及流程中的數(shù)據(jù)，定義數(shù)據(jù)結構；②依據(jù)算法中的計算單位用程序設計語言中的基本運算處理單元（如表達式）、賦值、傳輸?shù)扔嬎愎δ芫幋a；③依據(jù)算法中的順序、選擇、循環(huán)控制單位用程序設計語言中相應的順序、選擇、循環(huán)語句編碼。6.4計算機算法的執(zhí)行——程序設計語言與程序3.翻譯系統(tǒng)世界上有兩種語言，一種是自然語言，如漢語、英語及日語等，另一種是人工語言,如計算機中機器語言、程序設計語言等。機器語言是計算機自身內部語言，也稱指令系統(tǒng)。程序設計語言是人類與計算機交流的語言。在自然語言中要相互理解,必須翻譯。同樣，計算機中，人類與計算機之間要相互理解,也必須翻譯。這種翻譯是將程序設計語言翻譯成為計算機機器語言,稱為計算機翻譯。這種翻譯有兩種，一種是逐句翻譯，稱解釋;另一種是全文翻譯，稱編譯。為了翻譯，須有一個翻譯軟件，稱為翻譯器,或翻譯系統(tǒng)。第7章人工智能與算法1人工智能學科研究的核心是算法2人工智能學科的發(fā)展史是一部算法的發(fā)展史3人工智能的推理算法4人工智能的歸納算法5基于算法的人工智能理論研究人工智能學科研究的核心是算法7.17.1人工智能學科研究的核心是算法人工智能學科的研究對象是人類智能,需要特別強調的是人工智能是通過算法才能用計算機模擬人類智能（人腦功能）的。因此，人工智能算法是人工智能發(fā)展與繁榮的首要一環(huán),在其中始終起著關鍵性的核心作用，并處于中心地位。7.1.1人工智能及人工智能算法的定義現(xiàn)今有多種人工智能定義，一般而言，我們理解的正式介紹是：人工智能（ArtificalIntelligence,AI）就是用人造的機器模擬人類智能。但從目前而言,這種機器主要指的是計算機，而人類智能主要指的是人腦功能。因此，從最為簡單與宏觀的意義上看，人工智能即是用電腦模擬人腦的一門學科。7.1人工智能學科研究的核心是算法①人腦:人類的智能主要體現(xiàn)在人腦中，因此人工智能主要的研究目標是人腦。②電腦:模擬人腦的人造計算裝置或機器是計算機，或稱電腦。因此人工智能主要的研究工具是電腦。③模擬:就目前科學水平而言,人類對人腦的功能及其內部結構的了解很少,因此還無法從生物學或從物理學觀點著手制造出人腦，所以只能用模擬方法模仿人腦已知的功能，再通過電腦實現(xiàn)它。因此人工智能主要的研究方法是“模擬”。7.1人工智能學科研究的核心是算法這樣一來，人工智能就是用人工制造的計算機模擬人類智能(主要是人腦)的一門學科。其中人腦屬腦科學研究，電腦屬于計算機科學研究，而實際上真正人工智能研究的是“模擬”。通過模擬方法建立起相應的人腦理論模型(一般最終用數(shù)學形式表示)及相應的算法。然后,對人腦中的智能問題，通過模擬理論建立“模型”，并對模型求解，這種解應是算法解，這樣就可以用計算機開發(fā)若干工具，將算法編碼為程序,經計算機運行后實現(xiàn)這一模型。這樣就完成了從人腦中的智能問題到最終在計算機中獲得解決的全過程，它具有近似于人類智能的功能。在其中，算法起了核心的作用。7.1人工智能學科研究的核心是算法由此可見,人工智能的定義是:用模擬方法建立起相應的“理論模型”，再通過算法以計算機為工具實現(xiàn)這一智能模型。簡單來說:人工智能是通過算法用計算機模擬人類智能的一門新興學科。而人工智能的算法可定義為：能指導計算機執(zhí)行并模擬實現(xiàn)人類智能的過程稱為人工智能算法。某人類智能問題通過算法用計算機模擬的全過程可用圖7-2表示。7.1人工智能學科研究的核心是算法從上面的人工智能定義詳細介紹中可以看出，人工智能大致有理論模型和智能算法兩部分內容。⑴理論模型理論模型是模擬人類智能的一種理論體系，具有代表性的是按三個不同角度與層次對其做探究，從而形成的三種學派。①從人腦內部生物結構角度的研究所形成的學派，稱為連接主義學派(conectionism)，其典型的研究代表是人工神經網絡；②從人腦思維活動形式表示的角度的研究所形成的學派，稱為功能主義或符號主義學派(symbolicism)，其典型的研究代表是形式邏輯推理；③從人腦活動與外部世界動態(tài)環(huán)境交互行為角度的研究所形成的學派，稱為行為主義學派(actionism),其典型的研究代表是Agent07.1人工智能學科研究的核心是算法這三種方法從人腦內在的內涵、外延兩個方面以及人腦與環(huán)境動態(tài)交互行為等三個角度全方位研究人工智能，組合于一體形成了對人腦的全面的認識與了解。在這三種學派指引下，出現(xiàn)了多種理論，如控制理論、信息論、自動機理論、數(shù)理邏輯理論、感知機理論、智能體以及基于應用數(shù)學(如概率論、數(shù)理統(tǒng)計等)等多種理論,用這些理論做適當改造與發(fā)展，可以模擬不同的人類智能，這是一種具有智能表示能力的理論模型,也可稱為智能模型。7.1人工智能學科研究的核心是算法（2）智能算法人工智能中的問題求解都是用理論模型中的數(shù)學形式表示的。它的解一般有兩種,其一是算法解，另一種是非算法解,為了能在計算機中計算,必須是算法解。目前常用的算法有兩種,一種是演繹推理算法，另一種是歸納推理算法。因此,人工智能研究主要是討論三個學派與兩種算法。目前三個學派的研究已基本取得一致共識,而兩種算法的深入研討尚有艱巨復雜的研究任務，故而，它已成為人工智能當前的主要關注核心。7.1人工智能學科研究的核心是算法7.1.2人工智能算法和計算機算法的差異性人工智能算法和計算機算法都是建立在數(shù)理邏輯的可計算性理論之上的。人工智能算法是用計算機模擬人類智能，它是計算機算法“質”的提升,在研究對象、研究內容與研究方法等方面和計算機算法具有“質”的差異性。其一，人工智能算法的研究目標是人類智能,即是人類主觀世界,是讓計算機（機器）和人類一樣，具有會思考、會推理、會識別等功能。而計算機算法的研究目標則是人類所處客觀世界，如火車購票系統(tǒng)中的購票算法，如工廠生產流程管理系統(tǒng)中的生產流程算法等。其二，人工智能算法的研究對象是知識，而計算機算法的研究對象則是數(shù)據(jù)。其三,人工智能算法的研究方法目前主要是推理，包括演繹推理、歸納推理等。而計算機算法的研究方法則是計算。7.1人工智能學科研究的核心是算法7.1.3人工智能算法是人工智能學科研究的“核心”1.人工智能由數(shù)據(jù)（知識）、算力、算法三大要素構成2.人工智能算法是人工智能學科研究的“核心”3.關鍵在于算法的發(fā)現(xiàn)人工智能學科的發(fā)展史是一部算法的發(fā)展史7.27.2人工智能學科的發(fā)展史是一部算法的發(fā)展史這是人工智能發(fā)展史上的第_次高潮。它可細分為二個時期。1.萌芽期有關人工智能的最原始的研究，從古希臘時期就開始了。其代表性人物是亞里斯多德,他以哲學觀點研究人類思維形式化的規(guī)律，并形成了“形式邏輯”0計算機的出現(xiàn)及其廣泛應用形成了一個人工智能的萌芽期。來自各個不同學術領域的著名學者，從各自的學術視野出發(fā)，對人工智能提出了不同的理解、認識與方案，7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史2.第一高峰期1956年，在麥卡錫(見圖7-5)的發(fā)起與主持下,于達特茅斯召開了“人工智能夏季研討會”。7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史7.2.2知識工程和演繹推理算法(1970年代至1980年代末)經過近十年的寒冬,1970年代末開始,隨著計算機的不斷發(fā)展并進入了超大規(guī)模集成電路的第四代，人工智能的算法終于迎來了一個新的春天,并很快形成了一個世界性的第二次高潮。其主要標志是知識工程和演繹推理算法的創(chuàng)立及專家系統(tǒng)的出現(xiàn)與繁榮。1.專家系統(tǒng)的出現(xiàn)2.知識工程的出現(xiàn)3.以知識表示及以歸結原理為主的演繹推理算法4.推理算法的應用5.專家系統(tǒng)的兩個杰出代表7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史(1)第五代計算機1978年，日本通產省為了在全球信息產業(yè)中占據(jù)領導地位,決定委任時任東京大學計算中心主任的日本計算機學界的權威元岡達(TohruMotoOka,1929—1985)研制第五代計算機。三年后的1981年，以元岡達為首的委員會提交了一份長達89頁的報告，提出了第五代計算機六種先進的體系結構，它是一種以知識為中心，以知識推理為算法的具有人機對話功能的巨型計算機系統(tǒng)，它的研制促進了1980年代人工智能的知識推理算法的繁榮。7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史⑵深藍在20世紀90年代,IBM公司所開發(fā)的計算機“深藍”(DeepBlue)連續(xù)兩年戰(zhàn)勝了國際象棋大師、世界冠軍卞斯帕洛夫,從而轟動了世界,而這個深藍就是一個專家系統(tǒng)。圖7-7所示即深藍計算機。7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史7.2.3機器學習和歸納推理算法20世紀80年代開始，人工智能第二次高潮實際上已開始逐漸衰退，但是另_新的算法正在悄然升起，這就是歸納推理算法。對它的研究與成長的過程是經歷了一個漫長的近四十年的歷史。它包括在20世紀80年代開始以數(shù)據(jù)為中心的歸納推理算法——數(shù)據(jù)挖掘,以應用數(shù)學為中心的歸納推理算法——知識發(fā)現(xiàn)以及人工智能自身的歸納算法為主的研究方向，它們統(tǒng)稱為機器學習(machinelearning)。7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史1.機器學習機器學習方法應運而生,使得人工智能進入“機器學習時期”?！皺C器學習時期”也分為三個階段。①20世紀80年代，連接主義較為流行，代表工作有感知機(Perceptron)和神經網絡(NeuralNetwork)；②20世紀90年代，統(tǒng)計學習方法開始占據(jù)主流舞臺，代表性方法有支持向量機(SupportVectorMachine)；③進入21世紀,深度神經網絡被提出，連接主義卷土從來，隨著數(shù)據(jù)量和計算能力的不斷提升,以深度學習(DeepLearning)為基礎的諸多AI應用逐漸成熟。機器學習是一門多領域交叉學科，涉及概率論、統(tǒng)計學、逼近論、凸分析、算法復雜度理論等多門學科。它是繼專家系統(tǒng)之后人工智能應用的又一重要研究領域，也是人工智能和神經計算的核心研究課題之一。它是人工智能的核心，是使計算機具有智能的根本途徑，其應用遍及人工智能的各個領域，它主要使用歸納、綜合而不是演繹。機器學習的出現(xiàn)使得人工智能逐漸進入了_個新的以數(shù)據(jù)歸納為特色的新時代。7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史2.機器學習的歸納推理算法的改進——深度學習機器學習在實際應用中能發(fā)揮很好的作用，但也發(fā)現(xiàn)了很多的不足,主要是：①它須要海量數(shù)據(jù),所獲得知識的正確性與數(shù)據(jù)量關系很大。②所用的樣本數(shù)據(jù)的屬性與算法關系很大，一般很難用人工方式確定。③對人工智能中人類的視覺、聽覺及語言等學習能力效果很差。有基于此，必須在機器學習的算法基礎上進一步做改進與擴充，從而出現(xiàn)了深度學習算法。其典型的是基于人工神經網絡算法的改進版——卷積人工神經網絡算法。7.2人工智能學科的發(fā)展史是一部算法的發(fā)展史深度學習（深度人工神經網絡）的奠基人、連接主義學派的領頭人之一、多倫多大學的杰出教授辛頓（GeoffreyHinton,1947—）首次提出并形成了深度學習的概念,并應用深度人工神經網絡和卷積神經網絡開發(fā)了語言識別和圖像識別系統(tǒng)。2012年,連接主義學派的新星，時任斯坦福大學人工智能實驗室主任的吳恩達（1936-）模仿人腦的神經網絡,建造了一臺當時世界上最大的由多個神經形態(tài)芯片（神經元）搭建成的人工神經網絡（人工大腦），為深度學習機理提供了機器硬件基礎。在此基礎上形成了以感知功能為中心的深度學習算法（通過對含有很多隱含層的“深度學習模擬”的構建，來實現(xiàn)“特征學習”的目的）。在數(shù)據(jù)、算力和深度學習算法這三大要素的相互交織與融合，連接主義學派實現(xiàn)了用計算機模擬人類感知功能的目標。深度學習算法能自動獲取樣本屬性,能應用于視覺、聽覺及語言等領域,較易獲取數(shù)據(jù)。因此,21世紀問世后，其應用取得了突破進展，人工智能的第三次高潮正式出現(xiàn),特別是AlphaGo的問世，震驚全球。目前，人工智能還處在第三次發(fā)展高潮中，而深度學習算法是目前主要的應用算法。人工智能的推理算法7.37.3人工智能的推理算法人工智能的推理算法是符號主義（或符號邏輯）學派的算法思想,其主要特征是：①這是基于多種知識表示的人工智能算法；②目標是以知識為中心，用計算機推理算法模擬人類認知功能；③人工智能的知識推理算法的歷史軌跡是以邏輯推理為基礎，經推理獲取知識。在21世紀，形成以知識圖譜為知識表示的推理方法，成為新一代知識推理算法。7.3人工智能的推理算法7.3.1以知識為中心知識是人們在認識世界與改造世界的過程中形成的認識與經驗并經抽象而形成的實體。知識是由符號組成的，具有語義。從形式上看知識是一種帶有語義的符號系統(tǒng)。1.知識表示知識是需要表示的，為表示方便，一般采用形式化的表示，并具有規(guī)范化的方法。因此，知識表示就是用形式化、規(guī)范化的方式對知識的描述。其內容包括一組事實、規(guī)則以及控制性知識等，部分情況下還會組成知識模型。在網絡上為使用與管理方便還可以以海量形式組織知識庫。知識表示方法很多，如狀態(tài)空間、產生式、謂詞邏輯及知識圖譜等，其前期典型是謂詞邏輯。7.3人工智能的推理算法2.知識推理知識不僅需要表示，還需要推理，這樣才能從已知知識推出或證明新的知識。符號主義的知識推理算法是以演繹推理方法為主的一種由一般性知識（或已知知識）出發(fā)，通過演繹推理而獲得個別知識（或新的知識）7.3人工智能的推理算法3.知識表示不同會導致知識推理的不同知識的演繹推理是按規(guī)則從一般原理（或已知知識）推出具體知識（或未知知識）的知識創(chuàng)新算法。知識表示不同，會導致推理形式的差異。知識推理算法的歷史演變顯示:以邏輯推理為基礎，經1980年代的知識工程、專家系統(tǒng)，到21世紀演變?yōu)橹R圖譜技術。因此，邏輯推理算法是知識推理算法的基礎。7.3人工智能的推理算法7.3.2邏輯推理算法邏輯推理算法又稱機器證明,它以邏輯作為知識表示的語言,其知識推理是在計算機上進行謂詞邏輯的永真推理，其推理是從已知邏輯式推出未知邏輯式。20世紀50年代開始，一批著名數(shù)理邏輯學家為用計算機模擬數(shù)學家進行定理證明的思維過程而創(chuàng)立了“機器證明”（自動化定理證明）。7.3人工智能的推理算法7.3.3吳文俊推理算法在與歸結原理研究的同時，吳文俊開創(chuàng)了幾何定理自動證明的先河。吳文俊(1919—2017,見圖7-11))畢業(yè)中國交通大學數(shù)學系，1949年獲法國斯特拉斯大學博士學位，曾任中國科學院院士,2001年獲國家最高科學技術獎。他于1946年開始研究拓撲學,1974年后轉向中國數(shù)學史的研究,1976年開始,毅然決定從事數(shù)學機械化(亦即機器證明)研究。7.3人工智能的推理算法(1)幾何定理證明自動化的發(fā)明吳文俊聲稱他從事數(shù)學機械化研究的動因及其數(shù)學基礎是：?中國古代數(shù)學中的幾何代數(shù)化思想；笛卡爾的解析幾何思想；?希爾伯特的《幾何基礎》。吳文俊的幾何定理自動化證明的方法分為三步。第_步:從幾何定理體系出發(fā)，引進坐標，將任何幾何問題代數(shù)化；第二步:將證明題的假設和結論分別表示成多元多項式方程，并確定從假設到結論的推導步驟；第三步:將第二步確定的推導步驟編成程序并在計算機上運算，以判斷定理是否成立。然后,吳文俊運用自己的方法，在計算機上完成了西姆森線、費爾巴哈定理、毛萊定理等一系列初等幾何定理的證明。隨后,他又把證明的范圍擴大到非歐幾何、仿射幾何、圓幾何、線幾何、球幾何等領域。到20世紀80年代，運用吳文俊的方法，已證明了600多條幾何證明，有的定理只需幾秒甚至零點幾秒就可完成證明。其中有一些定理按傳統(tǒng)方式加以證明是相當繁雜的，即便由杰出的數(shù)學家來證明也是相當困難的。7.3人工智能的推理算法(2)機器證明的代數(shù)化吳文俊創(chuàng)立數(shù)學機械化理論的另一個轉折點是由單純的更一般的代數(shù)解方程而引發(fā)的。吳文俊在研究幾何定理機器證明的實踐中意識到:機器證明可看成是解方程的特殊應用。從而促進他思考并提出了一個后來被證明卓有成效的將問題化為代數(shù)方程求解的數(shù)學機械化方案。其中最關鍵的一步是將代數(shù)方程組化為單元代數(shù)方程。對于這一笛卡爾未置一詞至今尚無完整的求解非線性多項式方程組的方法，吳文俊則在研究機器證明代數(shù)化中發(fā)現(xiàn)了“三角化整序法”(國際上稱之為“吳方法”)，并使其成為目前唯一完整的方法。對于“吳方法”的創(chuàng)立,吳文俊說:其一,遵循笛卡爾的解析幾何學將其可化歸為代數(shù)方程組;其二，根據(jù)中國古代數(shù)學家朱世杰的四元術和三角化整序法將其化歸為單個高次代數(shù)方程式，再將這一高次代數(shù)方程式的求解問題編成程序輸入計算機，由計算機執(zhí)行并完成計算過程。7.3人工智能的推理算法(3)“吳方法”的意義吳文俊創(chuàng)立了幾何定理機器證明及其代數(shù)化方法后，在國際上得到了廣泛的關注，產生了巨大的影響，普遍確認：其一，王浩是邏輯系統(tǒng)定理證明自動化(機械化)的先驅，吳文俊則開了幾何定理證明的先河；其二,基于邏輯的定理證明自動化最適合解決代數(shù)問題，而幾何定理證明又都是基于代數(shù)的，所以吳文俊的機器證明代數(shù)化,為機器證明開辟了新紀元。為此,王浩在得知吳文俊的結果后，馬上寫信給吳文俊，建議他利用已有的代數(shù)包，甚至考慮自己動手寫個程序來實現(xiàn)吳的方法,并在國際上極力推薦吳方法的創(chuàng)造性與有效性,使吳文俊1997年獲得了第四屆埃爾布朗獎（這是定理證明領域的最高獎項）;其三,吳文俊是立足于數(shù)學及其本質的數(shù)學家。他不同于邏輯學家將機器證明當作目標（邏輯學真理），而把其當作工具（是否有用）。他從中國數(shù)學的構造性與機械化特征出發(fā)，斷言:每一次數(shù)學的重大突破，往往是腦力勞動的機械化體現(xiàn)。數(shù)學機械化是自古以來數(shù)學發(fā)展的主流思想。人工智能的歸納算法7.47.4人工智能的歸納算法人工智能的歸納算法是連接主義學派的主要算法思想（還包括部分行為主義學派）。其主要特征是：?反映人類智能內在活動規(guī)律（或稱內涵）的算法，它在人工智能中主要應用于機器學習；?目標是讓機器（計算機）具有學習功能；?機器學習中的算法很多，但目前最有效的是歸納算法；?歸納算法有很多種，但目前最活躍的是人工神經網絡算法。其算法演變的歷程是在感知器的基礎上經淺層學習中的基本人工神經網絡算法，到21世紀深度學習中的卷積人工神經網絡算法，目前己成為人工智能中最為活躍的一個分支。7.4人工智能的歸納算法7.4.1以學習為中心人腦的最大長處是“在學習中成長的能力”，而計算機的最大優(yōu)勢是具有高速的計算能力o機器學習算法則把兩者的長處結合起來,讓機器具有強大的人類學習能力O1.學習的概念學習是人類從外界獲取知識與創(chuàng)新知識的一個過程。人類的知識主要是通過“學習”得到的。一般而言，學習可分為直接學習和間接學習兩類：7.4人工智能的歸納算法直接學習：人類通過直接方式與外部世界環(huán)境接觸，包括觀察與實踐而獲得的知識；?間接學習:通過父母、師長、前輩的言傳身教以及從書本、視頻、音頻等途徑而獲得的知識。間接學習和直接學習都可以獲取知識，但其最根本的是直接學習,因此這里所討論的學習主要指的是直接學習。學習所獲得的知識主要是通過歸納的思維方法。這就形成了學習與歸納間的關系。其中學習是目標,歸納是方法。在歸納中,環(huán)境中形形色色的各類事物是歸納的對象,而經過歸納后所得到的結果是知識。而這個完整的過程是學習。7.4人工智能的歸納算法2.機器學習的概念機器學習的概念是建立在人類學習概念的基礎上的。其意是:用計算機系統(tǒng)模擬人類學習。它由三個部分組成。?算力，也稱計算機系統(tǒng)，它是機器學習的基礎。?算法，在機器學習中是歸納算法，或稱歸納推理算法。?數(shù)據(jù)，是環(huán)境中的大量、各種客體,在計算機中可用數(shù)據(jù)表示，它是學習對象。因此,機器學習是對外部環(huán)境存在著的大量數(shù)據(jù)，應用歸納算法，獲得知識(規(guī)律性、法則性、類似性)，7.4人工智能的歸納算法(1)算力算力是機器學習的基礎。算法和數(shù)據(jù)都建立在其上。算法和數(shù)據(jù)都是須要計算的。算力提供了計算的能力,它包括計算機系統(tǒng)。該系統(tǒng)有一定計算的能力,與算法和數(shù)據(jù)計算需求能相匹配。這種能力包括運算速度、并行性及分布性等，此外還包括相應的開發(fā)工具。⑵數(shù)據(jù)在機器學習中，環(huán)境中的各種客體在計算機中表現(xiàn)為具有一定結構的數(shù)據(jù)。識別各種客體都是通過其不同特性而實現(xiàn)的。因此,數(shù)據(jù)是由若干個屬性(即特性)組合而成，稱為樣本。樣本有兩種。其一是由人工收集后通過錄入進入計算機，其數(shù)據(jù)結構形式是表結構;其二是由傳感器自動從環(huán)境中收集后通過一定方式轉換成點陣式矩陣形式的數(shù)據(jù)。7.4人工智能的歸納算法(3)算法機器學習的核心是歸納算法。為構筑算法須經過三個步驟。①建立理論模型，以表示機器學習中的問題求解形式及解的框架，稱為模型框架。②機器建模，它由理論系統(tǒng)中的模型框架與樣本在算力支持下組成一組程序和數(shù)據(jù)。程序給出了學習過程，它是算法框架的計算機程序表示。其中有若干未知參數(shù)。數(shù)據(jù)是樣本在計算機中的表示。數(shù)據(jù)輸入程序做運算,稱為模型訓練，以不斷調整參數(shù)值,此過程稱為機器建模，它是一種歸納的過程。③學習模型，機器建模的最終，可得到學習的結果，是一種知識模型，稱為學習模型。學習模型是一種計算機算法。在完成學習模型后，即獲得了計算機中的歸納算法。接著可在算力支撐下以數(shù)據(jù)為操作對象進行運算，最后得到歸納結果知識。7.4人工智能的歸納算法3.建立在計算機系統(tǒng)上的機器學習整體結構模型機器學習的整體結構模型是建立在計算機系統(tǒng)上的。這種模型是學習模型在計算機上的具體化