课程内容 课程内容 围绕学科理论体系中的模型理论，程序理论和计算理论 1.模型理论关心的问题 给定模型M,哪些问题可以由模型M解决；如何 比较模型的表达能力 本讲座讨论递归函数的语 2.程序理论关心的问题义，了解离散数学的重要性 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、 程序设计、 形式语义、类型论、程序验证、程序分析等 3.计算理论关心的问题 给定模型M和一类问题，解决该类问题需多少资源
课 程 内 容 • 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何 比较模型的表达能力 2. 程序理论关心的问题 – 给定模型M，如何用模型M解决问题 – 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源2 本讲座讨论递归函数的语 义, 了解离散数学的重要性
讲座提纲 离散数学和计算机科学的关系 -离散数学的特点、与计算机科学的关系 基本知识 偏序集合、最小上界、完全偏序集合、函数序、 函数的单调性和连续性 递归函数的定义式的求解 函数的不动点、递归函数定义、递归函数定义的 解、不动点算子、最小不动点定理 编程语言递归函数的数学语义 -最小不动点语义 3
讲 座 提 纲 • 离散数学和计算机科学的关系 – 离散数学的特点、与计算机科学的关系 • 基本知识 – 偏序集合、最小上界、完全偏序集合、函数序、 函数的单调性和连续性 • 递归函数的定义式的求解 – 函数的不动点、递归函数定义、递归函数定义的 解、不动点算子、最小不动点定理 • 编程语言递归函数的数学语义 – 最小不动点语义 3
离散数学和计算机科学的关系 本课程已谈及的相关内容 数理逻辑 ·经典逻辑、等式逻辑、 程序逻辑、类型系统 ·都包括合式公式、公理、推理规则、演绎推理 集合论 良基关系、良基归纳法，偏序关系（本次课) 代数结构（抽象代数） 常见的抽象数据类型（表、栈、二叉树等）是代数 本课程还会介绍 可计算性和算法分析等
离散数学和计算机科学的关系 • 本课程已谈及的相关内容 – 数理逻辑 • 经典逻辑、等式逻辑、程序逻辑、类型系统 • 都包括合式公式、公理、推理规则、演绎推理 – 集合论 良基关系、良基归纳法，偏序关系（本次课） – 代数结构（抽象代数） 常见的抽象数据类型 (表、栈、二叉树等) 是代数 • 本课程还会介绍 – 可计算性和算法分析等 4
离散数学和计算机科学的关系 离散数学的特点 离散数学是数学的几个分支的总称，研究基于离 散而不是连续的数学结构 与光滑变化的实数不同，离散数学的研究对象， 例如整数、图和逻辑中的命题，都包含有区别和 分离的值，且所包含的值并非光滑变化 离散数学被视为处理可数集合（与自然数集有相 同基数的集合)的数学分支 离散数学无准确且普遍接受的定义，它经常被定 义为不包含连续变化量及相关概念的数学，也用 包含什么内容的方式来定义
离散数学和计算机科学的关系 • 离散数学的特点 – 离散数学是数学的几个分支的总称，研究基于离 散而不是连续的数学结构 – 与光滑变化的实数不同，离散数学的研究对象， 例如整数、图和逻辑中的命题，都包含有区别和 分离的值，且所包含的值并非光滑变化 – 离散数学被视为处理可数集合（与自然数集有相 同基数的集合）的数学分支 – 离散数学无准确且普遍接受的定义，它经常被定 义为不包含连续变化量及相关概念的数学，也用 包含什么内容的方式来定义 5
离散数学和计算机科学的关系 离散数学和计算机科学的关系 离散数学的研究在20世纪后半叶，由于电子计算 机的出现而迅猛发展 离散数学的概念和表示法在研究和描述计算机科 学一些分支的对象和问题时非常有用，如计算机 算法、编程语言、自动定理证明、密码学和软件 研发 把离散数学的概念用于现实世界的问题时（如运 筹学中的问题)，计算机实现是十分重要的
离散数学和计算机科学的关系 • 离散数学和计算机科学的关系 – 离散数学的研究在20世纪后半叶，由于电子计算 机的出现而迅猛发展 – 离散数学的概念和表示法在研究和描述计算机科 学一些分支的对象和问题时非常有用， 如计算机 算法、编程语言、自动定理证明、密码学和软件 研发 – 把离散数学的概念用于现实世界的问题时（如运 筹学中的问题），计算机实现是十分重要的 6