计算理论概述精选PPT.ppt

计算理论概述第1页，此课件共25页哦内容提要内容提要什么是计算什么是计算什么是计算理论什么是计算理论计算理论的核心问题计算理论的核心问题计算理论的主要内容计算理论的主要内容计算理论的地位和作用计算理论的地位和作用现代问题求解方法现代问题求解方法展望展望第2页，此课件共25页哦什么是计算什么是计算-两类典型的计算问题两类典型的计算问题从计数到计算 实物计数-屈指计数-结绳计数-刻符计数-发明数字-数制数系 算筹-运算技巧（古代中国称术）-算术（整数运算）数值计算问题求解 计算方法从逻辑到计算 古希腊哲学家和数学家发展逻辑学和逻辑演绎方法 十九世纪数理逻辑问世将逻辑与计算联系起来 通过计算进行逻辑演绎，通过逻辑推理实现计算-符号运算 非数值计算问题求解 组合优化方法刘徽祖冲之亚里士多德第3页，此课件共25页哦什么是计算什么是计算-不只是工匠不只是工匠算法与计算 算法（Algorithm)一词来源于古阿拉伯一本数学名著的书名，指的是一种计算过程问题的求解过程，具有如下性质：（1）通用性-适用于某类问题的求解 （2）能行性-有明确的求解步骤 （3）确定性-每个步骤都是机械的、明确的，无歧义 （4）有穷性-对某些输入在有限步内结束，并给出结果 （5）离散性-输入输出是离散的符号（数字和字母）问题的求解是计算，求解算法中的每个步骤是计算计算的过程是算法，算法又由计算步骤构成计算的目的由算法实现，算法的执行由计算完成欧几里得第4页，此课件共25页哦什么是计算什么是计算-从工匠到设计师从工匠到设计师计算机械化与现代化 计算技术发展：个人的才智与技能-大众技能-计算工具 -自动化-现代化 早期工具：算筹-算盘-计算尺-手摇计算机（早期发报机）现代工具：电子计算机（器）-超级计算机-网络 无处不在的计算：计算网格与云计算-物联网与普适计算计算模型-万变不离其中 图灵机-跳不出的如来佛手心 递归函数-以有穷构造无穷的必由之路 演算-严格的函数运算 乔姆斯基范型-语言与文法计算机（物化的计算模型）、算法与高级语言第5页，此课件共25页哦什么是计算理论什么是计算理论问题求解问题描述问题模型计算模型、算法、程序、复杂性问题特征、分类不可解证明可解？是否计算复杂性理论可计算性理论计算理论第6页，此课件共25页哦计算理论的核心问题计算理论的核心问题计算模型及其计算能力问题是否可解-可计算性 问题是否难解-计算复杂性 相互关联相辅相成第7页，此课件共25页哦计算理论的主要内容计算理论的主要内容丘奇-图灵论题 图灵-图灵机（TM）丘奇-演算递归函数论 算法可计算函数都是递归函数，也是图灵机可计算函数，可称为计算公理从直观到严格的数学定义 从计算能力考查 各计算模型是等价的 图灵机的各种变形是等价的 算法求解问题的能力与图灵机一样 单机与超级计算机等价图灵歌德尔第8页，此课件共25页哦可计算性理论 可判定性 可判定性的定义（图灵机）有不可判定的问题吗？-停机问题 -怎样证明 怎样证明其他问题的不可判定性？-可归约性方法 可计算性理论的数学背景 -不可计算的根源罗素康托第9页，此课件共25页哦计算复杂性理论 时间复杂性及其定义 P与NP理论 -P类问题与NP类问题的定义（图灵机）NP完全理论 -NP完全问题的定义 -库克（Cook）定理及其证明（1971）-库克定理的意义、可归约性方法 空间复杂性及其定义 难解性与层次定理-问题难度的分类与层次斯蒂芬库克第10页，此课件共25页哦复杂性理论高级专题 近似算法 -局部搜索法 -概率算法 -现代启发式算法 -自然与演化计算方法 复杂性的应用 -密码学（难的妙用难的妙用）-密钥 -公钥密码系统 -单向函数 -天窗函数第11页，此课件共25页哦计算理论的地位和作用计算理论的地位和作用计算机学科的基石令人着迷、引人入胜的领域受到优秀的数学家、哲学家、逻辑学家和物理学家等的青睐起源于上世纪30年代，成型于70年代，现在依然充满活力计算机科学领域其他学科和方向的思想源泉、理论基础和方法之本多学科交叉的纽带，新兴学科方向的拐点第12页，此课件共25页哦现代问题求解方法现代问题求解方法源于复杂性源于复杂性面临困境面临困境与挑战与挑战复杂问题求解复杂问题求解复杂信息处理复杂信息处理 复杂系统复杂系统实际应用领域的需求第13页，此课件共25页哦信息时代的呼唤信息时代的呼唤工业时代工业时代能量资源能量资源-创造动力的工具创造动力的工具-获得能量获得能量物理学、化学物理学、化学创造动力工具的理论基础创造动力工具的理论基础信息时代信息时代信息资源信息资源-创造智能的工具创造智能的工具-获得智能获得智能智能计算理论智能计算理论创造智能工具的理论基础创造智能工具的理论基础第14页，此课件共25页哦现代启发式计算现代启发式计算-回归自然回归自然自下而上的研究思路自下而上的研究思路传传统统人人工工智智能能研研究究思思路路是是自自上上而而下下，现现代代智智能能计计算算方方法法强强调调通通过过计计算算实实现生物内在的智能行为，也称为计算智能现生物内在的智能行为，也称为计算智能从简单到复杂的演化进程从简单到复杂的演化进程智智能能的的获获得得不不是是一一蹴蹴而而就就，是是渐渐进进式式的的积积累累过过程程，简简单单中中孕孕育育复复杂杂，平凡中蕴含智慧平凡中蕴含智慧在传统学科中寻找算法在传统学科中寻找算法 如如生生命命科科学学（遗遗传传算算法法）、物物理理学学（模模拟拟退退火火算算法法）和和化化学学（DNADNA计算）等计算）等从自然与社会系统中获得灵感从自然与社会系统中获得灵感 如如蚂蚂蚁蚁算算法法、禁禁忌忌搜搜索索和和粒粒子子群群优优化化方方法法，模模糊糊计计算算及及模模糊糊系系统统、粗粗造造集集及其系统及其系统第15页，此课件共25页哦相互关系相互关系 计算智能与人工智能的界限并非十分明显，计算智能与人工智能的界限并非十分明显，19921992年年BezdekBezdek给出了一个有趣的关系给出了一个有趣的关系图，其中图，其中 NNNN神经网络，神经网络，PRPR模式识别，模式识别，II智能智能AArtificial，表示人工的（非生物的），即人造的表示人工的（非生物的），即人造的BBiological，表示物理的化学的（？）生物的表示物理的化学的（？）生物的CComputational，表示数学计算机表示数学计算机ABC的关系图的关系图计算智能是一种智力方式的低层认知，传统人工智能是中层认计算智能是一种智力方式的低层认知，传统人工智能是中层认知，中层系统含有知识，当一个智能计算系统以非数值方式加知，中层系统含有知识，当一个智能计算系统以非数值方式加上知识值，则为人工智能系统上知识值，则为人工智能系统 第16页，此课件共25页哦自然计算自然计算自然计算的含义自然计算的含义 学习、运用自然规律，模拟自然系统乃至社会系统的学习、运用自然规律，模拟自然系统乃至社会系统的演变过程的智能计算方法，借鉴自然科学学科的原理演变过程的智能计算方法，借鉴自然科学学科的原理和理论进行问题的求解方法和理论进行问题的求解方法自然计算方法自然计算方法 演化计算、蚁群算法、粒子群优化方法、人工免疫系统、演化计算、蚁群算法、粒子群优化方法、人工免疫系统、模糊计算模糊计算第17页，此课件共25页哦蚁群算法概述蚁群算法概述受蚂蚁觅食行为的的启发，受蚂蚁觅食行为的的启发，9090年代年代DorigoDorigo提出蚁群优化算法提出蚁群优化算法(AntColonyOptimization(AntColonyOptimization，ACO)ACO)求解求解TSPTSP问题问题设计虚拟的设计虚拟的“蚂蚁蚂蚁”，摸索不同路线，并留下会随时间挥发的虚，摸索不同路线，并留下会随时间挥发的虚拟拟“信息素信息素”根据根据“信息素较浓，则路径更短信息素较浓，则路径更短”的原则，每只蚂蚁每次随机选择要的原则，每只蚂蚁每次随机选择要走的路径，但倾向于信息素比较浓的路径走的路径，但倾向于信息素比较浓的路径算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择择 ACOACO已成功用于解决其他组合优化问题已成功用于解决其他组合优化问题 图的着色图的着色(Graph(GraphColoring)Coloring)问题问题 最短超串最短超串(Shortest(ShortestCommonCommonSupersequence)Supersequence)问题问题 网络路由问题网络路由问题第18页，此课件共25页哦蚁群觅食原理蚁群觅食原理ABCD蚁穴食物蚂蚁从蚁穴出发觅食，可沿蚂蚁从蚁穴出发觅食，可沿ACAC找到食物，也可沿找到食物，也可沿ABCABC找到，如右图。找到，如右图。每个蚂蚁找到食物后沿原路返回，并在路上留下外激素。每个蚂蚁找到食物后沿原路返回，并在路上留下外激素。ACAC路径短，路径短，ACAC上留下了两次外激素，而上留下了两次外激素，而ABCABC路径长，沿路径长，沿CBACBA返回的蚂蚁，还只到了返回的蚂蚁，还只到了D D处，故处，故ADAD上只留下一次外激素。上只留下一次外激素。后续离穴觅食者选择外激素浓度大的后续离穴觅食者选择外激素浓度大的ACAC路径，路径，于是于是ACAC上外激素浓度将越来越大，上外激素浓度将越来越大，最后，绝大多数蚂蚁沿较短的最后，绝大多数蚂蚁沿较短的ACAC路径觅食。路径觅食。第19页，此课件共25页哦蚁群算法蚁群算法初初始始化化，设设置置时时间间计计数数器器，循循环环计计数数器器，为为每每条条边设置信息素浓度的初始值边设置信息素浓度的初始值初始化初始化tabutabu表表 tabutabu表满？表满？按按概概率率将将某某一一个个蚂蚂蚁蚁从从第第i i个个城城市市移移动动到到第第j j个城市，并将个城市，并将j j插入其插入其tabutabu表表封封闭闭回回路路，分分别别计计算算每每个个蚂蚂蚁蚁走走过过的的总总长长度度，记记录录最最短短路径，计算信息素浓度改变量路径，计算信息素浓度改变量达达到到最最大大循循环环次次数数或或不不 发展状态？发展状态？输出结果输出结果第20页，此课件共25页哦粒子群优化概述粒子群优化概述粒子群优化算法粒子群优化算法(Particle Swarm Optimization(Particle Swarm Optimization，PSO)1995PSO)1995年由年由EberhartEberhart和和KennedyKennedy提出，源于模拟鸟群捕食行为提出，源于模拟鸟群捕食行为一群鸟在随机搜索区域里的一块食物，所有的鸟都不知道食物在那里，但知道当一群鸟在随机搜索区域里的一块食物，所有的鸟都不知道食物在那里，但知道当前的位置离食物还有多远前的位置离食物还有多远那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域围区域PSOPSO中，优化问题的可行解就是搜索空间中的一只鸟，称之为中，优化问题的可行解就是搜索空间中的一只鸟，称之为“粒子粒子”，一群鸟，一群鸟称为粒子群，所有的粒子都有一个由优化的函数决定的适应值称为粒子群，所有的粒子都有一个由优化的函数决定的适应值（fitnessfitnessvalue)value)每个粒子还有一个速度决定其飞行的方向和距离，目的是追随当前的最优粒子在解空每个粒子还有一个速度决定其飞行的方向和距离，目的是追随当前的最优粒子在解空间中搜索间中搜索粒子通过跟踪两个粒子通过跟踪两个“极值极值”来更新自己，第一个就是粒子自己当前找到的最优解，来更新自己，第一个就是粒子自己当前找到的最优解，这个解叫做个体极值这个解叫做个体极值pBestpBest，另一个极值是整个种群目前找到的最优解，这个极值是，另一个极值是整个种群目前找到的最优解，这个极值是全局极值全局极值gBest gBest 第21页，此课件共25页哦粒子移动原理粒子移动原理粒子粒子i i在在N N维空间里的位置维空间里的位置表示为矢量表示为矢量XiXi(x x1 1，x x2 2，xNxN)，飞行速度表，飞行速度表示为矢量示为矢量ViVi(v1v1，v2v2，vNvN)对于第对于第k k次迭代，次迭代，PSOPSO中的中的每一个粒子的移动按照下每一个粒子的移动按照下式进行式进行第22页，此课件共25页哦粒子群优化算法粒子群优化算法Step1Step1：初始化一群粒子初始化一群粒子(群体规模为群体规模为m)m)，包括随，包括随 机机 位置和速度；位置和速度；Step2Step2：评价每个粒子的适应度；评价每个粒子的适应度；Step3Step3：对每个粒子，将其适应值与其经历过的最好位置对每个粒子，将其适应值与其经历过的最好位置pbestpbest作比较，如果较好，作比较，如果较好，则将其作为当前的最好位置则将其作为当前的最好位置pbestpbest；Step4Step4：对每个粒子，将其适应值与全局所经历的最好位置对每个粒子，将其适应值与全局所经历的最好位置gbestgbest作比较，如果较好，作比较，如果较好，则重新设置则重新设置gbestgbest的索引号；的索引号；Step5Step5：根据方程根据方程(1)(1)变化粒子的速度和位置；变化粒子的速度和位置；Step6Step6：如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数如未达到结束条件（通常为足够好的适应值或达到一个预设最大代数GmaxGmax），），则返回则返回Step2Step2标准标准PSOPSO的算法流程的算法流程第23页，此课件共25页哦展展望望一个核心一个核心计算模型是核心中的核心计算模型是核心中的核心纲举目张纲举目张 量子计算、光计算等，还有神谕模型量子计算、光计算等，还有神谕模型 将发展全新的计算理论将发展全新的计算理论-难题不难，不可计算也许可计算难题不难，不可计算也许可计算一个难题一个难题P=NP?一百万美金！（美国克雷一百万美金！（美国克雷-Clay数学研究所）数学研究所）无论是肯定还是否定的答案都是重大成果！无论是肯定还是否定的答案都是重大成果！一个方兴未艾的领域一个方兴未艾的领域现代启发式方法与智能科学现代启发式方法与智能科学探索智能的奥秘探索智能的奥秘找寻神谕之门找寻神谕之门化解难题之法化解难题之法三个“一”任你选择第24页，此课件共25页哦谢谢谢谢！Thanks!第25页，此课件共25页哦