計(jì)算理論概述

計(jì)算理論概述第一頁，共二十五頁，2022年，8月28日內(nèi)容提要什么是計(jì)算什么是計(jì)算理論計(jì)算理論的核心問題計(jì)算理論的主要內(nèi)容計(jì)算理論的地位和作用現(xiàn)代問題求解方法展望第二頁，共二十五頁，2022年，8月28日什么是計(jì)算

--兩類典型的計(jì)算問題從計(jì)數(shù)到計(jì)算實(shí)物計(jì)數(shù)-屈指計(jì)數(shù)-結(jié)繩計(jì)數(shù)-刻符計(jì)數(shù)-發(fā)明數(shù)字-數(shù)制數(shù)系算籌-運(yùn)算技巧（古代中國稱術(shù)）-算術(shù)（整數(shù)運(yùn)算）

數(shù)值計(jì)算問題求解計(jì)算方法從邏輯到計(jì)算古希臘哲學(xué)家和數(shù)學(xué)家發(fā)展邏輯學(xué)和邏輯演繹方法十九世紀(jì)數(shù)理邏輯問世將邏輯與計(jì)算聯(lián)系起來通過計(jì)算進(jìn)行邏輯演繹，通過邏輯推理實(shí)現(xiàn)計(jì)算-符號(hào)運(yùn)算

非數(shù)值計(jì)算問題求解組合優(yōu)化方法劉徽祖沖之亞里士多德第三頁，共二十五頁，2022年，8月28日什么是計(jì)算

--不只是工匠算法與計(jì)算算法（Algorithm)一詞來源于古阿拉伯一本數(shù)學(xué)名著的書名，指的是一種計(jì)算過程—問題的求解過程，具有如下性質(zhì)：（1）通用性-適用于某類問題的求解（2）能行性-有明確的求解步驟（3）確定性-每個(gè)步驟都是機(jī)械的、明確的，無歧義（4）有窮性-對(duì)某些輸入在有限步內(nèi)結(jié)束，并給出結(jié)果（5）離散性-輸入輸出是離散的符號(hào)（數(shù)字和字母）問題的求解是計(jì)算，求解算法中的每個(gè)步驟是計(jì)算計(jì)算的過程是算法，算法又由計(jì)算步驟構(gòu)成計(jì)算的目的由算法實(shí)現(xiàn)，算法的執(zhí)行由計(jì)算完成歐幾里得第四頁，共二十五頁，2022年，8月28日什么是計(jì)算

--從工匠到設(shè)計(jì)師計(jì)算機(jī)械化與現(xiàn)代化

計(jì)算技術(shù)發(fā)展：個(gè)人的才智與技能-大眾技能-計(jì)算工具

-自動(dòng)化-現(xiàn)代化早期工具：算籌-算盤-計(jì)算尺-手搖計(jì)算機(jī)（早期發(fā)報(bào)機(jī)）現(xiàn)代工具：電子計(jì)算機(jī)（器）-超級(jí)計(jì)算機(jī)-網(wǎng)絡(luò)

無處不在的計(jì)算：計(jì)算網(wǎng)格與云計(jì)算-物聯(lián)網(wǎng)與普適計(jì)算計(jì)算模型-萬變不離其中圖靈機(jī)-跳不出的如來佛手心遞歸函數(shù)-以有窮構(gòu)造無窮的必由之路

λ演算-嚴(yán)格的函數(shù)運(yùn)算喬姆斯基范型-語言與文法計(jì)算機(jī)（物化的計(jì)算模型）、算法與高級(jí)語言第五頁，共二十五頁，2022年，8月28日什么是計(jì)算理論問題求解問題描述問題模型計(jì)算模型、算法、程序、復(fù)雜性問題特征、分類不可解證明可解？是否計(jì)算復(fù)雜性理論可計(jì)算性理論計(jì)算理論第六頁，共二十五頁，2022年，8月28日計(jì)算理論的核心問題計(jì)算模型及其計(jì)算能力問題是否可解-可計(jì)算性

問題是否難解-計(jì)算復(fù)雜性

相互關(guān)聯(lián)相輔相成第七頁，共二十五頁，2022年，8月28日計(jì)算理論的主要內(nèi)容丘奇-圖靈論題

圖靈-圖靈機(jī)（TM）丘奇-λ演算—遞歸函數(shù)論

算法可計(jì)算函數(shù)都是遞歸函數(shù)，也是圖靈機(jī)可計(jì)算函數(shù)，可稱為計(jì)算公理—從直觀到嚴(yán)格的數(shù)學(xué)定義從計(jì)算能力考查—各計(jì)算模型是等價(jià)的圖靈機(jī)的各種變形是等價(jià)的算法求解問題的能力與圖靈機(jī)一樣

單機(jī)與超級(jí)計(jì)算機(jī)等價(jià)圖靈歌德爾第八頁，共二十五頁，2022年，8月28日可計(jì)算性理論

可判定性

可判定性的定義（圖靈機(jī)）

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

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

可計(jì)算性理論的數(shù)學(xué)背景-不可計(jì)算的根源羅素康托第九頁，共二十五頁，2022年，8月28日計(jì)算復(fù)雜性理論

時(shí)間復(fù)雜性及其定義

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

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

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

空間復(fù)雜性及其定義

難解性與層次定理-問題難度的分類與層次斯蒂芬?guī)炜说谑摚捕屙摚?022年，8月28日復(fù)雜性理論高級(jí)專題

近似算法-局部搜索法-概率算法-現(xiàn)代啟發(fā)式算法-自然與演化計(jì)算方法

復(fù)雜性的應(yīng)用-密碼學(xué)（難的妙用）-密鑰-公鑰密碼系統(tǒng)-單向函數(shù)-天窗函數(shù)第十一頁，共二十五頁，2022年，8月28日計(jì)算理論的地位和作用計(jì)算機(jī)學(xué)科的基石令人著迷、引人入勝的領(lǐng)域受到優(yōu)秀的數(shù)學(xué)家、哲學(xué)家、邏輯學(xué)家和物理學(xué)家等的青睞起源于上世紀(jì)30年代，成型于70年代，現(xiàn)在依然充滿活力計(jì)算機(jī)科學(xué)領(lǐng)域其他學(xué)科和方向的思想源泉、理論基礎(chǔ)和方法之本多學(xué)科交叉的紐帶，新興學(xué)科方向的拐點(diǎn)第十二頁，共二十五頁，2022年，8月28日現(xiàn)代問題求解方法—源于復(fù)雜性面臨困境與挑戰(zhàn)復(fù)雜問題求解復(fù)雜信息處理

復(fù)雜系統(tǒng)實(shí)際應(yīng)用領(lǐng)域的需求第十三頁，共二十五頁，2022年，8月28日信息時(shí)代的呼喚工業(yè)時(shí)代能量資源-創(chuàng)造動(dòng)力的工具-獲得能量物理學(xué)、化學(xué)創(chuàng)造動(dòng)力工具的理論基礎(chǔ)信息時(shí)代信息資源-創(chuàng)造智能的工具-獲得智能智能計(jì)算理論創(chuàng)造智能工具的理論基礎(chǔ)第十四頁，共二十五頁，2022年，8月28日現(xiàn)代啟發(fā)式計(jì)算-回歸自然自下而上的研究思路

傳統(tǒng)人工智能研究思路是自上而下，現(xiàn)代智能計(jì)算方法強(qiáng)調(diào)通過計(jì)算實(shí)現(xiàn)生物內(nèi)在的智能行為，也稱為計(jì)算智能從簡單到復(fù)雜的演化進(jìn)程

智能的獲得不是一蹴而就，是漸進(jìn)式的積累過程，簡單中孕育復(fù)雜，平凡中蘊(yùn)含智慧在傳統(tǒng)學(xué)科中尋找算法

如生命科學(xué)（遺傳算法）、物理學(xué)（模擬退火算法）和化學(xué)（DNA計(jì)算）等從自然與社會(huì)系統(tǒng)中獲得靈感

如螞蟻算法、禁忌搜索和粒子群優(yōu)化方法，模糊計(jì)算及模糊系統(tǒng)、粗造集及其系統(tǒng)第十五頁，共二十五頁，2022年，8月28日相互關(guān)系

計(jì)算智能與人工智能的界限并非十分明顯，1992年Bezdek給出了一個(gè)有趣的關(guān)系圖，其中

NN—神經(jīng)網(wǎng)絡(luò)，PR—模式識(shí)別，I—智能A－Artificial，表示人工的（非生物的），即人造的B－Biological，表示物理的＋化學(xué)的＋（？？）＝生物的C－Computational，表示數(shù)學(xué)＋計(jì)算機(jī)ABC的關(guān)系圖計(jì)算智能是一種智力方式的低層認(rèn)知，傳統(tǒng)人工智能是中層認(rèn)知，中層系統(tǒng)含有知識(shí)，當(dāng)一個(gè)智能計(jì)算系統(tǒng)以非數(shù)值方式加上知識(shí)值，則為人工智能系統(tǒng)

第十六頁，共二十五頁，2022年，8月28日自然計(jì)算自然計(jì)算的含義

學(xué)習(xí)、運(yùn)用自然規(guī)律，模擬自然系統(tǒng)乃至社會(huì)系統(tǒng)的演變過程的智能計(jì)算方法，借鑒自然科學(xué)學(xué)科的原理和理論進(jìn)行問題的求解方法自然計(jì)算方法

演化計(jì)算、蟻群算法、粒子群優(yōu)化方法、人工免疫系統(tǒng)、模糊計(jì)算第十七頁，共二十五頁，2022年，8月28日蟻群算法概述受螞蟻覓食行為的的啟發(fā)，90年代Dorigo提出蟻群優(yōu)化算法(Ant

Colony

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

ACO已成功用于解決其他組合優(yōu)化問題

圖的著色(Graph

Coloring)問題最短超串(Shortest

Common

Supersequence)問題網(wǎng)絡(luò)路由問題第十八頁，共二十五頁，2022年，8月28日蟻群覓食原理ABCD蟻穴食物螞蟻從蟻穴出發(fā)覓食，可沿AC找到食物，也可沿ABC找到，如右圖。每個(gè)螞蟻找到食物后沿原路返回，并在路上留下外激素。AC路徑短，AC上留下了兩次外激素，而ABC路徑長，沿CBA返回的螞蟻，還只到了D處，故AD上只留下一次外激素。后續(xù)離穴覓食者選擇外激素濃度大的AC路徑，于是AC上外激素濃度將越來越大，最后，絕大多數(shù)螞蟻沿較短的AC路徑覓食。第十九頁，共二十五頁，2022年，8月28日蟻群算法初始化，設(shè)置時(shí)間計(jì)數(shù)器，循環(huán)計(jì)數(shù)器，為每條邊設(shè)置信息素濃度的初始值初始化tabu表

tabu表滿？按概率將某一個(gè)螞蟻從第i個(gè)城市移動(dòng)到第j個(gè)城市，并將j插入其tabu表封閉回路，分別計(jì)算每個(gè)螞蟻?zhàn)哌^的總長度，記錄最短路徑，計(jì)算信息素濃度改變量達(dá)到最大循環(huán)次數(shù)或不發(fā)展?fàn)顟B(tài)？輸出結(jié)果是否是否第二十頁，共二十五頁，2022年，8月28日粒子群優(yōu)化概述粒子群優(yōu)化算法(ParticleSwarmOptimization，PSO)1995年由Eberhart和Kennedy提出，源于模擬鳥群捕食行為一群鳥在隨機(jī)搜索區(qū)域里的一塊食物，所有的鳥都不知道食物在那里，但知道當(dāng)前的位置離食物還有多遠(yuǎn)那么找到食物的最優(yōu)策略是什么呢？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域PSO中，優(yōu)化問題的可行解就是搜索空間中的一只鳥，稱之為“粒子”，一群鳥稱為粒子群，所有的粒子都有一個(gè)由優(yōu)化的函數(shù)決定的適應(yīng)值（fitness

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

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

評(píng)價(jià)每個(gè)粒子的適應(yīng)度；Step3：

對(duì)每個(gè)粒子，將其適應(yīng)值與其經(jīng)歷過的最好位置pbest作比較，如果較好，則將其作為當(dāng)前的最好位置pbest；Step4：

對(duì)每個(gè)粒子，將其適應(yīng)值與全局所經(jīng)歷的最好位置gbest作比較，如果較好，則重新設(shè)置gbest的索引號(hào)；Step5：

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

如未達(dá)到結(jié)束條件（通常為足夠好的適應(yīng)值或達(dá)到一個(gè)預(yù)設(shè)最大代數(shù)Gmax），則返回Step2標(biāo)準(zhǔn)PSO的算法流程第二十三頁，共二十五頁，2022年，8月28日展望一個(gè)核心

計(jì)算模型是核心中的核心—綱舉目張量子計(jì)算、