课程内容 课程内容 围绕学科理论体系中的模型理论，程序理论和计算理论 1. 模型理论关心的问题 给定模型M,哪些问题可以由模型M解决；如何 比较模型的表达能力 本讲座简要介绍三种经 2.程序理论关心的问题典的抽象计算模型 给定模型M,如何用模型M解袂问题 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3.计算理论关心的问题 给定模型M和一类问题，解决该类问题需多少资源
课 程 内 容 • 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何 比较模型的表达能力 2. 程序理论关心的问题 – 给定模型M，如何用模型M解决问题 – 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源 本讲座简要介绍三种经 典的抽象计算模型 2
讲座提纲 基本知识 -计算、计算模型、 并行计算模型 图灵机概述 图灵的基本思想、基本图灵机、图灵机的变种 ·入演算 -入表达式的文法、)演算的变换规则、Church数 码 递归函数 直观意义的可计算函数、原始递归函数、递归函 数
讲 座 提 纲 • 基本知识 – 计算、计算模型、并行计算模型 • 图灵机概述 – 图灵的基本思想、基本图灵机、图灵机的变种 • 演算 – 表达式的文法、 演算的变换规则、Church数 码 • 递归函数 – 直观意义的可计算函数、原始递归函数、递归函 数 3
基本知识 ·计算 抽象地说，计算就是从一个符号序列得出另 个符号序列m（从y出发，在有限步内真正求出) -y:12+3,7:15 /该计算是加法 Y:x×x,7:2x /该计算是微分 y:英文句子，n:含意相同的中文句子/翻译 Y:一组公理和推理规则，：一个定理/定理证明 下面的是完全定义的函数，但函数值求不出来 若在π的十进制表示中有连续x个5 其他情况
基 本 知 识 • 计算 抽象地说，计算就是从一个符号序列 得出另一 个符号序列（从 出发，在有限步内真正求出） – : 12+3, : 15 //该计算是加法 – : x x, : 2x //该计算是微分 – : 英文句子, : 含意相同的中文句子 //翻译 – : 一组公理和推理规则, : 一个定理 //定理证明 下面的f是完全定义的函数，但函数值求不出来 1 若在 的十进制表示中有连续x个5 f(x) = 0 其他情况 4
基本知识 ·计算 -不要狭隘理解计算 很多非数值问题（如文字识别， 图像处理等)都 可以转化为数值问题来交给计算机处理（可以在有 限步骤内被解决) 不要对计算有过高预期 哥德巴赫猜想问题不属于“可计算问题”之列， 因为计算机无法给出数学意义上的证明 没有任何理由期待计算机能解决世界上所有的问 题
基 本 知 识 • 计算 – 不要狭隘理解计算 很多非数值问题（如文字识别，图像处理等）都 可以转化为数值问题来交给计算机处理（可以在有 限步骤内被解决） – 不要对计算有过高预期 哥德巴赫猜想问题不属于“可计算问题”之列， 因为计算机无法给出数学意义上的证明 没有任何理由期待计算机能解决世界上所有的问 题 5
基本知识 。计算模型 刻画计算概念的抽象形式(formal)系统或数学系统 如图灵机、入演算、递归函数和Post系统 在可计算性理论和计算复杂性理论中，计算模型 ●是指包括一组操作及其代价的抽象机器 ● 可用来实现算法 。可度量算法的执行时间和空间的复杂性 ·可分析算法需要的计算资源 ·可讨论算法或计算机的局限
基 本 知 识 • 计算模型 – 刻画计算概念的抽象形式(formal)系统或数学系统 如图灵机、演算、递归函数和Post系统 – 在可计算性理论和计算复杂性理论中，计算模型 • 是指包括一组操作及其代价的抽象机器 • 可用来实现算法 • 可度量算法的执行时间和空间的复杂性 • 可分析算法需要的计算资源 • 可讨论算法或计算机的局限 6