离散数学与计算机科学计算机科学导论第四讲省名师优质课赛课获奖课件市赛课一等奖课件.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,中国科大,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,离散数学与计算机科学,计算机科学导论第四讲,计算机科学技术学院,陈意云,0551-,6,3607043,yiyun,1/38,课 程 内 容,课程内容,围绕学科理论体系中模型理论,程序理论和计算理论,1.,模型理论关心问题,给定模型,M,，哪些问题能够由模型,M,处理；怎样比较模型表示能力,2.,程序理论关心问题,给定模型,M,，怎样用模型,M,处理问题,包含程序设计范型、,程序设计语言,、程序设计、,形式语义,、类型论、程序验证、程序分析等,3.,计算理论关心问题,给定模型,M,和一类问题,处理该类问题需多少资源,2/38,讲 座 提 纲,离散数学和计算机科学关系,离散数学特点、与计算机科学关系,基本知识,偏序集合、,最小上界、完全偏序集合,、序理论、函数序、,函数单调性和连续性,递归数学函数不动点语义,函数不动点、递归函数定义、递归函数定义解、不动点算子、最小不动点定理,编程语言递归函数,数学语义,最小不动点语义,3/38,离散数学和计算机科学关系,本课程已谈及相关内容,数理逻辑,经典逻辑、等式逻辑、程序逻辑、类型系统,都包含合式公式、公理、推理规则、演绎推理,集合论,良基关系、良基归纳法，偏序关系,(,此次课,),代数结构（抽象代数）,常见抽象数据类型,(,表、栈、二叉树等,),是代数,本课程还会谈及,可计算性和算法分析等,4/38,离散数学和计算机科学关系,离散数学特点,离散数学是数学几个分支总称，研究基于离散而不是连续数学结构,与光滑改变实数不一样，离散数学研究对象,，,比如整数、图和逻辑中命题,，都包含有区分和,分,离,值,，但所包含值并非,光滑改变,离散数学被视为处理可数集合,（,与,自然数,集,有相同,基数集合）数学分支,离散数学,无准确且普遍接收定义，它,经常被定义为不包含连续改变量及相关概念数学，,也用,包含什么内容,方式来定义,5/38,离散数学和计算机科学关系,离散数学和计算机科学关系,离散数学研究在,20,世纪后半叶，因为电子计算机出现而迅猛发展,离散数学概念和表示法在研究和描述计算机科学一些分支（如计算机算法、编程语言、自动定理证实、密码学和软件研发,),对象和问题时非常有用,把离散数学概念用于现实世界问题时（如运筹学中问题），,计算机,实现是十分主要,6/38,离散数学和计算机科学关系,本科期间离散数学课程,数理逻辑、图论、代数结构（抽象代数）,使用离散数学知识课程：,数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等,7/38,探讨问题,递归函数语义,两个,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/38,探讨问题,递归函数语义,对应两个递归数学函数定义（,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/38,探讨问题,递归函数语义,对应两个递归数学函数定义（,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,偏函数（部分函数）：,最多只有一个,b,B,10/38,探讨问题,递归函数语义,对应两个递归数学函数定义（,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,),把它们分别看成是关于,f,和,g,方程,阶乘函数是第一个方程解,把,f,用,0,1,1,1,2,2,3,6,代入，对于,任意自然数,x,，等式两边相等,11/38,探讨问题,递归函数语义,对应两个递归数学函数定义（,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,),把它们分别看成是关于,f,和,g,方程,阶乘函数是第一个方程解,第二个方程有没有数个解（,a,可取任意自然数）,1,x,是偶数,h,(,x,)=,a,x,是奇数,即,0,1,1,a,2,1,3,a,4,1,5,a,12/38,基 本 知 识,偏序关系（部分序关系）,1.,集合,D,上二元关系,，含有以下三个性质,自反性：,x,:,D,.,x,x,反对称性：,x,y,:,D,.,x,y,y,x,x,=,y,传递性：,x,y,z,:,D,.,x,y,y,z,x,z,2,.D,上二元关系,定义,x,y,当且仅当,x,y,x,y,3.,整数上,小于等于和小于关系分别是和,实例,4.,离散序,x,y,当且仅当,x,y,，即不一样元素之间无关系,13/38,基 本 知 识,偏序集合,有偏序关系,集合,D,，记为,D,1.,上界,若,D,，则子集,S,D,上界,是元素,x,D,，,含有性质：,y,:,S,.,y,x,2.,最小上界,S,一 个上界，它小于等于,S,任何其它上界,3.,线性序,x,y,:,S,.,x,y,y,x,14/38,基 本 知 识,例,偏序集合,a,0,b,0,a,1,b,1,a,2,b,2,，,其中对任意,i,j,都有,a,i,a,j,b,j,而且,b,i,a,j,b,j,两个线性序,a,0,a,1,a,2,，和,b,0,b,1,b,2,称它们为线性递增链,a,i,b,i,有上界,a,i,+1,和,b,i,+1,等，,但没有最小上界,a,0,a,1,a,2,b,0,b,1,b,2,a,i,和,b,i,没有最小上界,15/38,基 本 知 识,完全偏序集合,1.,完全偏序集合,D,（简称,CPO,）,D,中任何线性递增链,a,0,a,1,a,2,都有最小上界,2.,最小上界表示：,a,0,a,1,a,2,3.,例,使用离散序，任何集合都可看成,CPO,任何有限偏序集合都是,CPO,考虑普通算术序，自然数集合不是,CPO,有理数非平凡闭区间不是,CPO，,比如，全部,小于,有理数最小上界是无理数,2,16/38,基 本 知 识,完全偏序集合,4.,有底元（也叫最小元,）,CPO,D,存在元素,a,，,使得对,D,任何元素,b,都有,a,b,5.,D,上底元,用,或,D,表示,6.,例,为自然数集,N,增加,底元,，并定义偏序,关系如图，则,N,是有底元,CPO,称为提升集合,0,1,2,3,4,CPO,N,图形表示,17/38,基 本 知 识,例,以集合,关系为序,即,是,两个集合最小,上界就是它们并集,即,x,y,就是,x,y,1.,也能够,为序，把,图上下颠倒,2.,能够类似地定义下界、,最大下界和顶元,(,最大元,),等,d,1,d,2,d,3,d,1,d,2,d,1,d,3,d,2,d,3,d,1,d,2,d,3,(,),(,),18/38,基 本 知 识,序理论,研究各种二元关系,数学理论,格（,lattice,）,在离散数学中,有顶元和底元,D,称为格,有顶元或底元,D,称为半格,d,1,d,2,d,3,d,1,d,2,d,1,d,3,d,2,d,3,d,1,d,2,d,3,(,),(,),19/38,基 本 知 识,函数序,1.,函数能够用二元集合表示,阶乘函数,0,1,1,1,2,2,3,6,平方函数,0,0,1,1,2,4,2.,以函数,为偏序,则,f,g,表示：,f,和,g,都有,定义之处函数值一样，但,g,可能定义在更多变元上,0,1,1,1,2,1,常函数1,阶乘函数,0,1,1,1,2,2,0,1,1,1,0,1,0,5,.,.,.,.,.,.,.,.,20/38,基 本 知 识,单调函数,若,D,=,D,D,和,E,=,E,E,都是,CPO,，,且,f,:,D,E,是它们基础集合上函数，,若,d,d,蕴涵,f,(,d,),f,(,d,),则,f,单调,若,f,单调且,a,0,a,1,a,2,是递增链,，则,f,(,a,0,),f,(,a,1,),f,(,a,2,),也是递增链,21/38,例：从,B,到,B,单调函数,f,(,),f,(,true,),f,(,false,),f,(,),f,(,true,),f,(,false,),f,0,f,6,false,true,f,1,true,f,7,true false,f,2,false,f,8,false false,f,3,true,f,9,true,true true,f,4,false,f,10,false,false false,f,5,true true,f,0,f,1,f,2,f,3,f,4,f,5,f,6,f,7,f,8,f,9,f,10,下面偏序关系图基于把函数值为,了解成没有定义,22/38,基 本 知 识,连续函数,若,D,=,D,D,和,E,=,E,E,都是,CPO,，,且,f,:,D,E,是它们基础集合上函数，,且对,D,每个递增链,a,0,a,1,a,2,，都有,f,(,a,0,),f,(,a,1,),f,(,a,2,),=,f,(,a,0,a,1,a,2,),例,在实轴闭区间,x,y,上，若把,x,y,看成,CPO,时，则通常计算意义下连续函数依然连续,lim,f,(,x,),f,(,x,0,),x,x,0,23/38,基 本 知 识,连续函数,若,D,=,D,D,和,E,=,E,E,都是,CPO,，,且,f,:,D,E,是它们基础集合上函数，,且对,D,每个递增链,a,0,a,1,a,2,，都有,f,(,a,0,),f,(,a,1,),f,(,a,2,),=,f,(,a,0,a,1,a,2,),例,在实轴闭区间,x,y,上，若把,x,y,看成,CPO,时，则通常计算意义下连续函数依然连续,任何,CPO,上常函数是平凡地连续,若,D,是离散序，则,D,上每个函数都连续,从提升集合,A,到任何,CPO,单调函数连续,24/38,递归数学函数不动点语义,函数不动点,若,f,:,D,D,是,集合,D,到它,本身,函数，,则,f,不动点是使得,f,(,x,)=,x,值,x,例,在,自然数上,平方函数不动点有,0,和,1,恒等函数有没有数个不动点,后继函数没有不动点,25/38,递归函数不动点语义,函数匿名表示：,抽象表示法,1.,通常表示,如恒等函数,Id,(,x,:,nat,)=,x,Id,是函数名,不便于把函数看成一级对象来操作,2.,抽象表示法（抽象表示式是表示式一个）,f,(,x,:,nat,)=,x,+1,x,:,nat,.,x,+1,g,(,x,:,nat,)=10,x,:,nat,.10,f,5,(,x,:,nat,.,x,+1),5=5+1=6,(,f,:,nat,nat.,y,:,nat,.,fy,)(,x,:,nat,.,x,+1)5,=,(,y,:,nat,.(,x,:,nat,.,x,+1),y,)5,=(,y,:,nat,.,y,+1)5=,5+1=6,26/38,递归数学函数不动点语义,递归定义解与对应函数不动点主要联络,递归定义,f,(,x,:,D,)=,M,对应,函数,：,f,:,.,M,（注：,在此表示,D,D,）,函数,f,:,.,M,不动点恰好是方程,f,=,M,解,若,(,f,:,.,M,),N=N,即,M,N,/,f,=,N,则,N,是,f,=,M,解,方程,f,=,M,求解,就,转化,为,找函数,f,:,.,M,不动,点,例：,f,(,x,)=if,x,=0 then 1 else,x,f,(,x,1,),对应函数：,F,f,:,nat,nat,.,y,:,nat,.,if,x,=0 then 1 else,x,f,(,x,1,),阶乘函数是,F,不动点,27/38,递归数学函数不动点语义,不动点语义,函数,f,:,.,M,不动,点作为,递归定义,f,(,x,:,D,)=,M,语义,1.,怎样计算得到不动点,2.,不动点可能不唯一，取哪个不动点作为语义,不一样场所有不一样选择：最小或最大不动点,（注：不动点集上偏序关系：函数包含序）,本讲座内容需要最小不动点，第九讲用到最大不动点,28/38,递归数学函数不动点语义,不动点算子,不动点算子是一簇函数，其类型是,fix,:(,),fix,为任何,函数产生一个不动点,不动点算子等式公理是,fix,=,f,:,.,f,(,fix,f,),使用表示式演算规则，可得易于了解等式,fix,g,g,(,fix,g,),等式公理定向可得归约规则,fix,f,:,.,f,(,fix,f,),，,fix,g,g,(,fix,g,),29/38,递归数学函数不动点语义,把不动点算子用于阶乘函数定义,阶乘函数,定义对应高阶函数,是,F,f,:,nat,nat,.,x,:,nat,.if,x,=0 then 1 else,x,f,(,x,1,),(,fix,nat,nat,F,),n,/,用不动点归约来,计算,n,阶乘,F,(,fixF,),n,(,f,:,nat,nat,.,x,:,nat,.if,x,=0 then 1 else,x,f,(,x,-1),),(,fix F,),n,if,n,=0 then 1 else,n,(,fix F,)(,n,-1),从这里已经知道,0,阶乘等于,1,若,n,若,n,值给定，则对,fix F,有限步展开可得,n,阶乘,30/38,递归数学函数不动点语义,最小不动点定理,若,D,是有底元,CPO，,且,f,:,D,D,是连续函数，则,f,有最小不动点,fix,(,f,)=,f,n,(,)|,n,0,先证,a,是不动点（,a,f,n,(,)|,n,0,）,f,(,a,),f,(,f,n,(,)|,n,0),=,f,n,+1,(,)|,n,0)/,依据连续函数性质,f,n,(,)|,n,0,和,f,n,+1,(,)|,n,0,最小上界相同,所以,f,(,a,)=,a,再证,a,是最小不动点（略）,最终证实,fix,连续（略）,31/38,编程语言递归函数数学语义,C,阶乘函数定义对应高阶函数最小不动点,对应高阶函数,是,（其连续性证实略去）,F,f,:,nat,nat,.,x,:,nat,.if,x,=0 then 1 else,x,f,(,x,1,),计算过程：（,F,n,表示对,F,最多展开,n,次）,F,0,(,)=,F,1,(,)=,0,0!,F,2,(,)=,0,0!,1,1!,F,3,(,)=,0,0!,1,1!,2,2!,fix,(,F,)=,F,n,(,)|,n,0,=,0,0!,0,0!,1,1!,0,0!,1,1!,2,2!,=,阶乘函数,32/38,编程语言递归函数数学语义,第二个,C,函数定义对应高阶函数最小不动点,g,(,x,),if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),对应高阶函数,是,F,g,:,nat,nat,.,x,:,nat,=,if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),计算过程：,F,0,(,)=,F,1,(,)=,0,1,F,2,(,)=,0,1,F,3,(,)=,0,1,2,1,fix,(,F,)=,F,n,(,)|,n,0,=,0,1,0,1,2,1,0,1,2,1,4,1,=,f,(,x,)=1,（,x,为偶数）,33/38,编程语言递归函数数学语义,第二个,C,函数定义对应高阶函数其它不动点,1,x,是偶数,h,(,x,)=,都是,a,x,是奇数,(,a,可任意取值,),函数,g,:,nat,nat,.,x,:,nat,=,if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),不动点,因为,(,g,:,nat,nat,.,x,:,nat,=,if,x,=0 then 1 else,(if,x,=1 then,g,(3)else,g,(,x,2,),),h,=,x,:,nat,=,if,x,=0 then 1 else,(if,x,=1 then,h,(3)else,h,(,x,2,),所得这个函数就是函数,h,34/38,编程语言递归函数数学语义,为何选择最小不动点,C,函数：,int g(int x)if(x=0)return 1 else,if(x=1)return g(3)else return g(x,2,);,对应高阶函数：,F,g,:,nat,nat,.,x,:,nat,=,if,x,=0 then 1 else(if,x,=1 then,g,(3)else,g,(,x,2,),F,最小不动点,f,(,x,)=1,（,x,为偶数）,最小不动点特点：,是定义得最少不动点,仅包含从递归定义能演绎出来信息，没有来自对对应递归方程任何“个人臆想”,对某个变元没有定义，意味着计算不终止,35/38,编程语言递归函数数学语义,实分析中不动点,求解实数方程,x,=1+1/,x,经惯用迭代方法求解,x,:,R,.1+1/,x,(,连续函数,),0,5(,迭代初值,),x,i,(,x,i,1,),i,1,得到迭代序列,1.2,1.833333,1.545455,1.647059,1.607143,1.622222,1.616438,1.618644,1.617801,1.618123,收敛于极限,(1+5)/2,，即上述连续函数不动点,36/38,小 结,本讲座小结,概述离散数学与计算机科学关系。,并,以计算阶,乘递归程序为例，介绍完全偏序集合及其上函数,单调性,、,连续性,、,不动点等概念是怎样用于程序,语义解释,偏序理论在计算机科学中应用,程序理论各个方面，如形式语义、类型论、程,序分析、程序优化、程序验证都离不开偏序理论,在计算机科学很多其它方面也都包括偏序,这部分内容在“代数结构”课程中,37/38,小 结,离散数学是很多专业课程先行课程,数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、程序设计语言基础等,离散数学发展方向,离散数学本身研究方面进展伴随计算机科学,发展而深入，比如在下述方面都有很多新结果，,也有值得继续研究问题,研究智能推理非经典逻辑,领域专用自动定理证实,代数结构深入探讨,图论与群论相互结合理论,38/38,