经典计算的计算模型计算机科学导论第五讲.ppt
《经典计算的计算模型计算机科学导论第五讲.ppt》由会员分享,可在线阅读,更多相关《经典计算的计算模型计算机科学导论第五讲.ppt(47页珍藏版)》请在三一文库上搜索。
1、经典计算的计算模型 计算机科学导论第五讲,计算机科学技术学院 陈意云 0551-63607043 ,课 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M,哪些问题可以由模型M解决;如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源,讲 座 提 纲,基本知识 计算、计算模型、并行计算模型 图灵机概述 图灵的基本思想、基本图灵机、图灵机的变种 演算 表
2、达式的文法、 演算的变换规则、Church数码 递归函数 直观意义的可计算函数、原始递归函数、递归函数,基 本 知 识,计算 抽象地说,计算就是从一个符号序列 得出另一个符号序列(从 出发,在有限步内真正求出) : 12+3, : 15 /该计算是加法 : x x, : 2x /该计算是微分 : 英文句子, : 含意相同的中文句子 /翻译 : 一组公理和推理规则, : 一个定理 /定理证明 下面的f是完全定义的函数,但函数值求不出来 1 若在 的十进制表示中有连续x个5 f(x) = 0 其他情况,基 本 知 识,计算 不要狭隘理解计算 很多非数值问题(如文字识别,图像处理等)都 可以通过转化
3、成为数值问题来交给计算机处理(可 以在有限步骤内被解决) 不要对计算有过高预期 哥德巴赫猜想问题不属于“可计算问题”之列, 因为计算机无法给出数学意义上的证明 没有任何理由期待计算机能解决世界上所有的问 题,基 本 知 识,计算模型 刻画计算概念的抽象形式系统或数学系统 如图灵机、演算、递归函数和Post系统 在可计算性理论和计算复杂性理论中,计算模型 是指包括一组操作及其代价的抽象机器 可用来实现算法 可度量算法的执行时间和空间的复杂性 可分析算法需要的计算资源 可讨论算法或计算机的局限,基 本 知 识,并行计算模型 通常指把各种(至少一类)并行计算机的基本特 征抽象出来,形成的抽象并行机器
4、 对于串行计算机,全世界基本上都在使用冯诺伊 曼的计算模型;对于并行计算,一些有价值的参考 计算模型已提出,但没有一个能被大家接受的统一 的计算模型 新型计算的计算模型 网域计算模型、云计算模型、海计算模型,图 灵 机 概 述,图灵的基本思想 用机器来模拟人用纸和笔进行数学计算的过程, 该过程由两类简单动作的序列构成 在纸上写出或擦除某个符号 把注意力从纸上一个位置移到另一个位置 决定下一步动作的依据:纸上某个位置的符号和 人当前的思维状态 为模拟人的这种计算过程,图灵在20世纪30年代 构造了一种假想的简单机器,图 灵 机 概 述,基本图灵机 T= Q, , b, , q0, F, Q: 有
5、穷非空的状态集 : 有穷非空的带符号集 b: 空白符号 b: 输入符号集 q0Q: 开始状态 FQ: 终止状态集 :(QF ) Q L, R: 迁移函数, L和R表 示读写头的左右移 例如: (q0, 0)(q1, X, R), (q1, 1)(q2, Y, L),图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 策略:从左向右轮 番把带上最左的0和1分别写成X和Y(期间要向右和 向左移动读写头),直至全部写完 T= Q, , b, , q0, F, Q = q0, q1, , q5 = 0, 1, b, X, Y = 0, 1 F = q5 见下一页,图 灵 机 概 述
6、,例: 识别语言 L=0n1n | n 1 的图灵机 (q0, 0)(q1, X, R) (q2, 0)(q4, 0, L) (q1, 0)(q1, 0, R) (q4, 0)(q4, 0, L) (q1, Y)(q1, Y, R) (q4, X)(q0, X, R) (q1, 1)(q2, Y, L) (q3, Y)(q3, Y, R) (q2, Y)(q2, Y, L) (q3, B)(q5, Y, R) (q2, X)(q3, X, R),图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R),图 灵 机 概 述
7、,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R),图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R),图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L),图 灵
8、 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L) (q2, 0)(q4, 0, L),图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L) (q2, 0)(q4, 0, L) (q4, 0)(q4, 0, L),图 灵 机 概 述
9、,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L) (q2, 0)(q4, 0, L) (q4, 0)(q4, 0, L) (q4, X)(q0, X, R),然后又从q0 继续,图 灵 机 概 述,图灵机的变种 纸带两端都可以无限伸展 多道图灵机 多带图灵机 不确定图灵机,等等 它们的计算能力都等价于基本图灵机 图灵机的计算能力 等价于下面讨论演算和递归函数, 演 算,演算的历史 Church在20世纪30年代研究的定义可计
10、算函数的一种形式体系 Kleene在1936年证明,可定义的所有自然数函数正好是所有的递归函数 Turing在1937年证明,可定义的数值函数正好是Turing机可计算的函数 起初演算是无类型的,因在基于无类型演算的逻辑中发现一个悖论,导致类型化演算的研究 演算一直影响着程序设计语言的研究, 演 算,演算和程序设计语言 20世纪50年代,无类型演算明显影响了Lisp语言的研究 20世纪60年代认识到,程序设计语言的语义可以通过使用拓展的演算给出 现代的观点认为,类型化演算引导对程序设计语言进行更加涉及本质的分析 让类型化演算的类型对应到程序设计语言中的类型,就可以忠实地为类型化程序设计语言的能
11、力和局限性建模, 演 算,无类型表达式( 项)的文法 E := x /原子表达式,x是变量(标识符) E := y. E /抽象表达式, y被称为约束变量 E := E E /应用表达式 E := (E) /括号用于改变运算次序 例如: x, y, x.x, (x.xx) (x.xx), x.(y.(xy) x) 约定: 抽象表达式的体延伸到表达式的结束或第1个不能匹配的右括号, x.xy表示x. (xy)而不是(x.x)y 并置是左结合的,如xyz表示(xy)z而不是x(yz), 演 算,变量的自由出现和约束出现 在表达式y.x(x.yx)中 y.x(x.yx)的y约束出现在y. 的体中 y
12、.x(x.yx)的x约束出现在x. 的体中 y.x(x.yx)的x并未出现在任何x. 的体中,它是一个自由出现 用FV(E)表示E中出现的自由变量集, 演 算,项的代换 x.x/xy.x(x.yx)表示y.x(x.yx)中自由出现的x 用x.x来代换,结果是y.(x.x)(x.yx) 严格定义 E/xx = E E/xE1E2 = (E/xE1)(E/xE2) E2/xx.E1 = x.E1 E2/xy.E1 = y.E2/xE1, 只要x y并且yFV(E2) E2/xy.E1 = z.E2/xz/yE1, 其中zFV(E1E2)并且y, z x E2/x(E1) = (E2/xE1), 演
13、 算,演算的变换规则 1. 变换规则 x. E = y. y/xE /约束变元x改名为y 2. 变换规则 (x. E1)E2 = E2/xE1 /可理解为函数应用到变元 3. 变换规则 x. Ex = E,只要 xFV(E) /表达函数外延性 因为对任何表达式M, (x. Ex)M = EM 注:该规则与下面的讨论关系不大, 演 算,演算的归约系统 变换规则自左向右定向,必要时可使用规则 更换约束变元的名字 定理(Church-Rosser定理) 演算的归约系统是合流的 演算的归约系统不是终止的,例如 (x. xx) (x. xx) (x. xx) (x. xx),演算中的算术,Church数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 经典 计算 模型 计算机科学 导论 第五
链接地址:https://www.31doc.com/p-3171047.html