計算理論概述第一頁，共二十五頁，編輯于2023年，星期五內容提要什么是計算什么是計算理論計算理論的核心問題計算理論的主要內容計算理論的地位和作用現代問題求解方法展望第二頁，共二十五頁，編輯于2023年，星期五什么是計算

--兩類典型的計算問題從計數到計算實物計數-屈指計數-結繩計數-刻符計數-發明數字-數制數系算籌-運算技巧（古代中國稱術）-算術（整數運算）

數值計算問題求解計算方法從邏輯到計算古希臘哲學家和數學家發展邏輯學和邏輯演繹方法十九世紀數理邏輯問世將邏輯與計算聯系起來通過計算進行邏輯演繹，通過邏輯推理實現計算-符號運算

非數值計算問題求解組合優化方法劉徽祖沖之亞里士多德第三頁，共二十五頁，編輯于2023年，星期五什么是計算

--不只是工匠算法與計算算法（Algorithm)一詞來源于古阿拉伯一本數學名著的書名，指的是一種計算過程—問題的求解過程，具有如下性質：（1）通用性-適用于某類問題的求解（2）能行性-有明確的求解步驟（3）確定性-每個步驟都是機械的、明確的，無歧義（4）有窮性-對某些輸入在有限步內結束，并給出結果（5）離散性-輸入輸出是離散的符號（數字和字母）問題的求解是計算，求解算法中的每個步驟是計算計算的過程是算法，算法又由計算步驟構成計算的目的由算法實現，算法的執行由計算完成歐幾里得第四頁，共二十五頁，編輯于2023年，星期五什么是計算

--從工匠到設計師計算機械化與現代化

計算技術發展：個人的才智與技能-大眾技能-計算工具

-自動化-現代化早期工具：算籌-算盤-計算尺-手搖計算機（早期發報機）現代工具：電子計算機（器）-超級計算機-網絡

無處不在的計算：計算網格與云計算-物聯網與普適計算計算模型-萬變不離其中圖靈機-跳不出的如來佛手心遞歸函數-以有窮構造無窮的必由之路

λ演算-嚴格的函數運算喬姆斯基范型-語言與文法計算機（物化的計算模型）、算法與高級語言第五頁，共二十五頁，編輯于2023年，星期五什么是計算理論問題求解問題描述問題模型計算模型、算法、程序、復雜性問題特征、分類不可解證明可解？是否計算復雜性理論可計算性理論計算理論第六頁，共二十五頁，編輯于2023年，星期五計算理論的核心問題計算模型及其計算能力問題是否可解-可計算性

問題是否難解-計算復雜性

相互關聯相輔相成第七頁，共二十五頁，編輯于2023年，星期五計算理論的主要內容丘奇-圖靈論題

圖靈-圖靈機（TM）丘奇-λ演算—遞歸函數論

算法可計算函數都是遞歸函數，也是圖靈機可計算函數，可稱為計算公理—從直觀到嚴格的數學定義從計算能力考查—各計算模型是等價的圖靈機的各種變形是等價的算法求解問題的能力與圖靈機一樣

單機與超級計算機等價圖靈歌德爾第八頁，共二十五頁，編輯于2023年，星期五可計算性理論

可判定性

可判定性的定義（圖靈機）

有不可判定的問題嗎？-停機問題-怎樣證明

怎樣證明其他問題的不可判定性？-可歸約性方法

可計算性理論的數學背景-不可計算的根源羅素康托第九頁，共二十五頁，編輯于2023年，星期五計算復雜性理論

時間復雜性及其定義

P與NP理論-P類問題與NP類問題的定義（圖靈機）

NP完全理論-NP完全問題的定義

-庫克（Cook）定理及其證明（1971）-庫克定理的意義、可歸約性方法

空間復雜性及其定義

難解性與層次定理-問題難度的分類與層次斯蒂芬庫克第十頁，共二十五頁，編輯于2023年，星期五復雜性理論高級專題

近似算法-局部搜索法-概率算法-現代啟發式算法-自然與演化計算方法

復雜性的應用-密碼學（難的妙用）-密鑰-公鑰密碼系統-單向函數-天窗函數第十一頁，共二十五頁，編輯于2023年，星期五計算理論的地位和作用計算機學科的基石令人著迷、引人入勝的領域受到優秀的數學家、哲學家、邏輯學家和物理學家等的青睞起源于上世紀30年代，成型于70年代，現在依然充滿活力計算機科學領域其他學科和方向的思想源泉、理論基礎和方法之本多學科交叉的紐帶，新興學科方向的拐點第十二頁，共二十五頁，編輯于2023年，星期五現代問題求解方法—源于復雜性面臨困境與挑戰復雜問題求解復雜信息處理

復雜系統實際應用領域的需求第十三頁，共二十五頁，編輯于2023年，星期五信息時代的呼喚工業時代能量資源-創造動力的工具-獲得能量物理學、化學創造動力工具的理論基礎信息時代信息資源-創造智能的工具-獲得智能智能計算理論創造智能工具的理論基礎第十四頁，共二十五頁，編輯于2023年，星期五現代啟發式計算-回歸自然自下而上的研究思路

傳統人工智能研究思路是自上而下，現代智能計算方法強調通過計算實現生物內在的智能行為，也稱為計算智能從簡單到復雜的演化進程

智能的獲得不是一蹴而就，是漸進式的積累過程，簡單中孕育復雜，平凡中蘊含智慧在傳統學科中尋找算法

如生命科學（遺傳算法）、物理學（模擬退火算法）和化學（DNA計算）等從自然與社會系統中獲得靈感

如螞蟻算法、禁忌搜索和粒子群優化方法，模糊計算及模糊系統、粗造集及其系統第十五頁，共二十五頁，編輯于2023年，星期五相互關系

計算智能與人工智能的界限并非十分明顯，1992年Bezdek給出了一個有趣的關系圖，其中

NN—神經網絡，PR—模式識別，I—智能A－Artificial，表示人工的（非生物的），即人造的B－Biological，表示物理的＋化學的＋（？？）＝生物的C－Computational，表示數學＋計算機ABC的關系圖計算智能是一種智力方式的低層認知，傳統人工智能是中層認知，中層系統含有知識，當一個智能計算系統以非數值方式加上知識值，則為人工智能系統

第十六頁，共二十五頁，編輯于2023年，星期五自然計算自然計算的含義

學習、運用自然規律，模擬自然系統乃至社會系統的演變過程的智能計算方法，借鑒自然科學學科的原理和理論進行問題的求解方法自然計算方法

演化計算、蟻群算法、粒子群優化方法、人工免疫系統、模糊計算第十七頁，共二十五頁，編輯于2023年，星期五蟻群算法概述受螞蟻覓食行為的的啟發，90年代Dorigo提出蟻群優化算法(Ant

Colony

Optimization，ACO)求解TSP問題設計虛擬的“螞蟻”，摸索不同路線，并留下會隨時間揮發的虛擬“信息素”根據“信息素較濃，則路徑更短”的原則，每只螞蟻每次隨機選擇要走的路徑，但傾向于信息素比較濃的路徑算法利用了正反饋機制，使得較短的路徑能夠有較大的機會得到選擇

ACO已成功用于解決其他組合優化問題

圖的著色(Graph

Coloring)問題最短超串(Shortest

Common

Supersequence)問題網絡路由問題第十八頁，共二十五頁，編輯于2023年，星期五蟻群覓食原理ABCD蟻穴食物螞蟻從蟻穴出發覓食，可沿AC找到食物，也可沿ABC找到，如右圖。每個螞蟻找到食物后沿原路返回，并在路上留下外激素。AC路徑短，AC上留下了兩次外激素，而ABC路徑長，沿CBA返回的螞蟻，還只到了D處，故AD上只留下一次外激素。后續離穴覓食者選擇外激素濃度大的AC路徑，于是AC上外激素濃度將越來越大，最后，絕大多數螞蟻沿較短的AC路徑覓食。第十九頁，共二十五頁，編輯于2023年，星期五蟻群算法初始化，設置時間計數器，循環計數器，為每條邊設置信息素濃度的初始值初始化tabu表

tabu表滿？按概率將某一個螞蟻從第i個城市移動到第j個城市，并將j插入其tabu表封閉回路，分別計算每個螞蟻走過的總長度，記錄最短路徑，計算信息素濃度改變量達到最大循環次數或不發展狀態？輸出結果是否是否第二十頁，共二十五頁，編輯于2023年，星期五粒子群優化概述粒子群優化算法(ParticleSwarmOptimization，PSO)1995年由Eberhart和Kennedy提出，源于模擬鳥群捕食行為一群鳥在隨機搜索區域里的一塊食物，所有的鳥都不知道食物在那里，但知道當前的位置離食物還有多遠那么找到食物的最優策略是什么呢？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域PSO中，優化問題的可行解就是搜索空間中的一只鳥，稱之為“粒子”，一群鳥稱為粒子群，所有的粒子都有一個由優化的函數決定的適應值（fitness

value)每個粒子還有一個速度決定其飛行的方向和距離，目的是追隨當前的最優粒子在解空間中搜索粒子通過跟蹤兩個“極值”來更新自己，第一個就是粒子自己當前找到的最優解，這個解叫做個體極值pBest，另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest第二十一頁，共二十五頁，編輯于2023年，星期五粒子移動原理粒子i在N維空間里的位置表示為矢量Xi＝(x1，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)對于第k次迭代，PSO中的每一個粒子的移動按照下式進行第二十二頁，共二十五頁，編輯于2023年，星期五粒子群優化算法Step1：

初始化一群粒子(群體規模為m)，包括隨機位置和速度；Step2：

評價每個粒子的適應度；Step3：

對每個粒子，將其適應值與其經歷過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest；Step4：

對每個粒子，將其適應值與全局所經歷的最好位置gbest作比較，如果較好，則重新設置gbest的索引號；Step5：

根據方程(1)變化粒子的速度和位置；Step6：

如未達到結束條件（通常為足夠好的適應值或達到一個預設最大代數Gmax），則返回Step2標準PSO的算法流程第二十三頁，共二十五頁，編輯于2023年，星期五展望一個核心

計算模型是核心中的核心—綱舉目張量子計算、光