计算理论概述

计算理论概述第一页，共二十五页，编辑于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年，星期五展望一个核心

计算模型是核心中的核心—纲举目张量子计算、光