中国科学技术大学：《计算机科学导论》课程教学资源（PPT课件讲稿）第四讲 离散数学与计算机科学

离散数学和计算机科学的关系 本科期间的离散数学课程 数理逻辑、图论、代数结构（抽象代数） 使用离散数学知识的课程： 数据结构、操作系统、编译原理、人工智能、数 据库、算法设计与分析、程序设计语言基础等

离散数学和计算机科学的关系 • 本科期间的离散数学课程 – 数理逻辑、图论、代数结构（抽象代数） – 使用离散数学知识的课程： 数据结构、操作系统、编译原理、人工智能、数 据库、算法设计与分析、程序设计语言基础等 7

探讨的问题一 递归函数的语义 ·两个C语言写的递归函数(x≥0) int f(int x){ if(x==0)return 1;else return x*f(x-1); int g(int x) 若x是偶数，结 if (x=-0)return 1; 果为1；否则计算 else if(x==l)return g③)； 不终止 else return g(x-2); 一非形式地，这两个C函数的语义都能描述 -本讲座介绍，如何用数学语言给出它们的语义？

探讨的问题——递归函数的语义 • 两个C语言写的递归函数（x  0） – int f(int x) { if(x==0) return 1; else return x*f(x−1); } – int g(int x) { if (x==0) return 1; else if (x==1)return g(3); else return g(x−2); } – 非形式地，这两个C函数的语义都能描述 – 本讲座介绍，如何用数学语言给出它们的语义？ 若x是偶数，结 果为1；否则计算 不终止 8

探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -x) ifx=0 then 1 else xx fx-1) -g(c) ifx =0 then 1 else (if x =1 then g(3)else g(x-2)) 它们是递归定义式，代表什么函数？ 函数：集合A到集合B的一种二元关系R,并且对 任何a∈A,正好只有一个b∈B,使得a,b)∈R -上述第一个定义代表阶乘函数 {0,1),1,1,2,2),3,6),(4,24),5,120),…}

探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（x  0） – f(x) if x = 0 then 1 else x  f(x−1) – g(x) if x = 0 then 1 else (if x =1 then g(3) else g(x−2)) 它们是递归定义式，代表什么函数？ – 函数：集合A到集合B的一种二元关系R，并且对 任何aA，正好只有一个bB，使得a, bR – 上述第一个定义代表阶乘函数 { 0, 1, 1, 1, 2, 2, 3, 6, 4, 24, 5, 120, … } 9

探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -x) ifx=0 then 1 else xx fx-1) -g(c) ifx=0 then 1 else (if x =1 then g(3)else g(x-2)) 它们是递归定义式，代表什么函数？ 函数：集合A到集合B的一种二元关系R,并且对 任何a∈A,正好只有一个b∈B,使得(a,b》∈R 上述第二个定义代表什么函数？ 注：x是奇数时，计算g(x)的演算不终止

探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（x  0） – f(x) if x = 0 then 1 else x  f(x−1) – g(x) if x = 0 then 1 else (if x =1 then g(3) else g(x−2)) 它们是递归定义式，代表什么函数？ – 函数：集合A到集合B的一种二元关系R，并且对 任何aA，正好只有一个bB，使得a, bR – 上述第二个定义代表什么函数？ 注：x是奇数时，计算g(x)的演算不终止 10

探讨的问题一 递归函数的语义 对应的整数域上的数学函数的定义(x≥0》 -x) ifx=0 then 1 else xx fx-1) -g(c) ifx=0 then 1 else (if x =1 then g(3)else g(x-2)) 它们是递归定义式，代表什么函数？ 函数：集合A到集合B的一种二元关系R,并且对 任何a∈A,正好只有一个beB,使得(a,b》∈R 偏函数(partial function,部分函数)：..最多只 有一个b∈B 注：需要这个概念来回答上述问题

探讨的问题——递归函数的语义 • 对应的整数域上的数学函数的定义（x  0） – f(x) if x = 0 then 1 else x  f(x−1) – g(x) if x = 0 then 1 else (if x =1 then g(3) else g(x−2)) 它们是递归定义式，代表什么函数？ – 函数：集合A到集合B的一种二元关系R，并且对 任何aA，正好只有一个bB，使得a, bR – 偏函数（partial function, 部分函数）：…最多只 有一个bB … 注：需要这个概念来回答上述问题 11