计算理论概述.pptVIP

第1页，共25页，星期日，2025年，2月5日内容提要什么是计算什么是计算理论计算理论的核心问题计算理论的主要内容计算理论的地位和作用现代问题求解方法展望第2页，共25页，星期日，2025年，2月5日什么是计算

--两类典型的计算问题从计数到计算实物计数-屈指计数-结绳计数-刻符计数-发明数字-数制数系算筹-运算技巧（古代中国称术）-算术（整数运算）数值计算问题求解计算方法从逻辑到计算古希腊哲学家和数学家发展逻辑学和逻辑演绎方法十九世纪数理逻辑问世将逻辑与计算联系起来通过计算进行逻辑演绎，通过逻辑推理实现计算-符号运算非数值计算问题求解组合优化方法刘徽祖冲之亚里士多德第3页，共25页，星期日，2025年，2月5日什么是计算

--不只是工匠算法与计算算法（Algorithm)一词来源于古阿拉伯一本数学名著的书名，指的是一种计算过程—问题的求解过程，具有如下性质：（1）通用性-适用于某类问题的求解（2）能行性-有明确的求解步骤（3）确定性-每个步骤都是机械的、明确的，无歧义（4）有穷性-对某些输入在有限步内结束，并给出结果（5）离散性-输入输出是离散的符号（数字和字母）问题的求解是计算，求解算法中的每个步骤是计算计算的过程是算法，算法又由计算步骤构成计算的目的由算法实现，算法的执行由计算完成欧几里得第4页，共25页，星期日，2025年，2月5日什么是计算

--从工匠到设计师计算机械化与现代化计算技术发展：个人的才智与技能-大众技能-计算工具-自动化-现代化早期工具：算筹-算盘-计算尺-手摇计算机（早期发报机）现代工具：电子计算机（器）-超级计算机-网络无处不在的计算：计算网格与云计算-物联网与普适计算计算模型-万变不离其中图灵机-跳不出的如来佛手心递归函数-以有穷构造无穷的必由之路λ演算-严格的函数运算乔姆斯基范型-语言与文法计算机（物化的计算模型）、算法与高级语言第5页，共25页，星期日，2025年，2月5日什么是计算理论问题求解问题描述问题模型计算模型、算法、程序、复杂性问题特征、分类不可解证明可解？是否计算复杂性理论可计算性理论计算理论第6页，共25页，星期日，2025年，2月5日计算理论的核心问题计算模型及其计算能力问题是否可解-可计算性问题是否难解-计算复杂性相互关联相辅相成第7页，共25页，星期日，2025年，2月5日计算理论的主要内容丘奇-图灵论题图灵-图灵机（TM）丘奇-λ演算—递归函数论算法可计算函数都是递归函数，也是图灵机可计算函数，可称为计算公理—从直观到严格的数学定义从计算能力考查—各计算模型是等价的图灵机的各种变形是等价的算法求解问题的能力与图灵机一样单机与超级计算机等价图灵歌德尔第8页，共25页，星期日，2025年，2月5日可计算性理论可判定性可判定性的定义（图灵机）有不可判定的问题吗？-停机问题-怎样证明怎样证明其他问题的不可判定性？-可归约性方法可计算性理论的数学背景-不可计算的根源罗素康托第9页，共25页，星期日，2025年，2月5日计算复杂性理论时间复杂性及其定义P与NP理论-P类问题与NP类问题的定义（图灵机）NP完全理论-NP完全问题的定义-库克（Cook）定理及其证明（1971）-库克定理的意义、可归约性方法空间复杂性及其定义难解性与层次定理-问题难度的分类与层次斯蒂芬库克第10页，共25页，星期日，2025年，2月5日复杂性理论高级专题近似算法-局部有哪些信誉好的足球投注网站法-概率算法-现代启发式算法-自然与演化计算方法复杂性的应用-密码学（难的妙用）-密钥-公钥密码系统-单向函数-天窗函数第11页，共25页，星期日，2025年，2月5日计算理论的地位和作用计算机学科的基石令人着迷、引人入胜的领域受到优秀的数学家、哲学家、逻辑学家和物理学家等的青睐起源于上世纪30年代，成型于70年代，现在依然充满活力计算机科学领域其他学科和方向的思想源泉、理论基础和方法之本多学科交叉的纽带，新兴学科方向的拐点第12页，共25页，星期日，2025年，2月5日现代问题求解方