离散数学知识点

时间:2023-02-08 07:50:15 其他范文 收藏本文 下载本文

离散数学知识点(共6篇)由网友“猹里猹气”投稿提供,以下是小编精心整理的离散数学知识点,希望对大家有所帮助。

离散数学知识点

篇1:离散数学证明题

证明设a,b均是链A的元素,因为链中任意两个元素均可比较,即有a≤b或a≤b,如果a≤b,则a,b的最大下界是a,最小上界是b,如果b≤a,则a,b的最大下界是b,最小上界是a,故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论:

⑴b≤a或c≤a

⑵a≤b且a≤c

如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c)

如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c)

无论那种情况分配律均成立,故A是分配格.

一.线性插值(一次插值)

已知函数f(x)在区间[xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一次函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。

1. 插值函数和插值基函数

由直线的点斜式公式可知:

把此式按照 yk 和yk+1 写成两项:

并称它们为一次插值基函数。该基函数的特点如下表:

从而

P1 (x) = yk lk (x) + yk+1 lk+1 (x)

此形式称之为拉格朗日型插值多项式。其中, 插值基函数与yk 、yk+1 无关,而由插值结点xk 、xk+1 所决定。一次插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 .

例1: 已知lg10=1,lg20=1.3010, 利用插值一次多项式求lg12的近似值。

解: f(x)=lgx,f(10)=1,f(20)=1.3010, 设

x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010

则插值基函数为:

于是, 拉格朗日型一次插值多项式为:

故 :

即lg12 由lg10 和lg20 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792).

二.二次插值多项式

已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个次数不超过二次的多项式P2 (x), 使其满足,

P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 .

其几何意义为:已知平面上的三个点

(xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ),

求一个二次抛物线, 使得该抛物线经过这三点。

1.插值基本多项式

有三个插值结点xk-1 ,xk ,xk+1 构造三个插值基本多项式,要求满足:

(1) 基本多项式为二次多项式; (2) 它们的函数值满足下表:

因为lk-1 (xk )= 0,lk-1 (xk+1 )=0, 故有因子(x-xk )(x-xk+1 ), 而其已经是一个二次多项式, 仅相差一个常数倍, 可设

lk-1 (x)=a(x-xk )(x-xk+1 ),

又因为

lk-1 (xk-1 )=1 ==>a(xk-1 -xk )(xk-1 -xk+1 )=1

从而

同理得

基本二次多项式见右上图(点击按钮“显示Li”)。

2. 拉格朗日型二次插值多项式

由前述, 拉格朗日型二次插值多项式:

P2 (x)=yk-1 lk-1 (x)+yk lk (x)+yk+1 lk+1 (x),P2 (x)

是三个二次插值多项式的`线性组合,因而其是次数不超过二次的多项式,且满足:

P2 (xi )=yi , (i=k-1,k,k+1) 。

例2 已知:

xi 10 15 20

yi=lgxi 1 1.1761 1.3010

利用此三值的二次插值多项式求lg12的近似值。

解:设x0 =10,x1 =15,x2 =20,则:

故:

所以

7利用三个点进行抛物插值得到lg12的值,与精确值lg12=1.0792相比,具有3位有效数字,精度提高了。

三、拉格朗日型n次插值多项式

已知函数y=f(x)在n+1个不同的点x0 ,x1 ,…,x2 上的函数值分别为

y0 ,y1 ,…,yn ,求一个次数不超过n的多项式Pn (x),使其满足:

Pn (xi )=yi , (i=0,1,…,n),

即n+1个不同的点可以唯一决定一个n次多项式。

1. 插值基函数

过n+1个不同的点分别决定n+1个n次插值基函数

l0 (x),l1 (x),…,ln (X)

每个插值基本多项式li (x)满足:

(1) li (x)是n次多项式;

(2) li (xi )=1,而在其它n个li (xk )=0 ,(k≠i)。

由于li (xk )=0 ,(k≠i), 故有因子:

(x-x0 )…(x-xi-1 )(x-xi+1 )…(x-xn )

因其已经是n次多项式,故而仅相差一个常数因子。令:

li (x)=a(x-x0 )…(x-xi-1 )(x-xi+1 )…(x-xn )

由li (xi )=1,可以定出a, 进而得到:

2. n次拉格朗日型插值多项式Pn (x)

Pn (x)是n+1个n次插值基本多项式l0 (x),l1 (x),…,ln (X)的线性组合,相应的组合系数是y0 ,y1 ,…,yn 。即:

Pn (x)=y0 l0 (x)+y1 l1 (x)+…+yn ln (x) ,

从而Pn (x)是一个次数不超过n的多项式,且满足

Pn (xi )=yi , (i=0,1,2,…,n).

例3 求过点(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多项式。

解 用4次插值多项式对5个点插值。

所以

四、拉格朗日插值多项式的截断误差

我们在[a,b]上用多项式Pn (x) 来近似代替函数f(x), 其截断误差记作

Rn (x)=f(x)-Pn (x)

当x在插值结点xi 上时Rn (xi )=f(xi )-P n(xi )=0,下面来估计截断误差:

定理1:设函数y=f(x)的n阶导数y(n) =f(n) (x)在[a,b]上连续,

y(n+1) = f(n+1) (x)

在(a,b)上存在;插值结点为:

a≤x0

Pn (x)是n次拉格朗日插值多项式;则对任意x∈[a,b]有:

其中ξ∈(a,b), ξ依赖于x:ωn+1 (x)=(x-x0 )(x-x1 )…(x-xn )

证明:由插值多项式的要求:

Rn(xi )=f(xi )-Pn (xi )=0,(i=0,1,2,…,n);

Rn (x)=K(x)(x-x0 )(x-x1 )…(x-xn )=K(x)ωn+1 (x)

其中K(x)是待定系数;固定x∈[a,b]且x≠xk ,k=0,1,2,…,n;作函数

H(t)=f(t)-Pn (t)-K(x)(t-x0 )(t-x1 )…(t-xn )

则 H(xk )=0,(k=0,1,2,…,n), 且H(x)=f(x)-Pn (x)-Rn(x)=0, 所以,

H(t)在[a,b]上有n+2个零点,反复使用罗尔中值定理:存在ξ∈(a,b),

使; 因Pn (x)是n次多项式,故P(n+1) (ξ)=0, 而

ωn+1 (t)=(t-x0 )(t-x1 )…(t-xn )

是首项系数为1的n+1次多项式,故有

于是

H(n+1) (ξ)=f(n+1)(ξ)-(n+1)!K(x)

得:

所以

设 , 则:

易知,线性插值的截断误差为:

二次插值的截断误差为:

下面来分析前面两个例子(例1,例2)中计算lg12的截断误差:

在例1中,用lg10和lg20计算lg12,

P1(12)=1.0602,lg12=1.0792

e=|1.0792-1.0602|=0.0190;

估计误差:f(x)=lgx,

,当x∈[10,20]时,

2

篇2:大学离散数学怎么学

离散数学是研究离散量的结构及其相互关系的数学学科,是大学里面的重要科目,那么应该怎样学好呢?

离散数学是现代数学的一个重要分支,是计算机科学中基础理论的核心课程。离散数学以研究离散量的结构和相互间的关系为主要目标,其研究对象一般地是有限个或可数个元素,因此他充分描述了计算机科学离散性的特点。由于离散数学在计算机科学中的重要性,因此,许多大学都把它作为研究生入学考试的专业课程中的一门,或者是一门中的一部分。

作为计算机系的一门课程,离散数学有与其它课程相通相似的部分,当然也有它自身的特点,现在我们就它作为考试内容时具有的特点作一个简要的分析。

1、定义和定理多。

离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。在这些概念的基础上,特别要注意概念之间的联系,而描述这些联系的实体则是大量的定理和性质。

在考试中的一部分内容就是考察大家对定义和定理的识记、理解和运用。如上海交通大学的试题,问什么是相容关系。如果知道的话,很容易得分;如果不清楚,那么无论如何也得不到分数的。这类型题目往往因其难度低而在复习中被忽视。实际上这是一种相当错误的认识,在研究生入学考试的专业课试题中,经常出现直接考查对某知识点的识记的题目。对于这种题目,考生应该能够准确、全面、完整地再现此知识点。任何的模糊和遗漏,都会造成极为可惜的失分。我们建议读者,在复习的时候,对重要知识的记忆,务必以上面提到的“准确、全面、完整”为标准来要求自己,不能达到,就说明还不过关,还要下工夫。关于这一点,在后续章节中我们仍然会强调,使之贯穿于整个离散数学的复习过程中。

离散数学的定义主要分布在集合论的关系和函数部分,还有代数系统的群、环、域、格和布尔代数中。一定要很好地识记和理解。

2、有穷性。

由于离散数学较为“呆板”,出新题比较困难,不管什么考试,许多题目是陈题,或者稍作变化的来的。“熟读唐诗三百首,不会做诗也会吟。”如果拿到一本习题集,从头到尾做过,甚至背会的话。那么,在考场上就会发现绝大多数题见过或似曾相识。这时,要取得较好的成绩也就不是太难的事情了。

本书是专门针对研究生入学考试而编写的,适合于读者对研究生入学考试的复习。如果还有时间的话,我们可以推荐两本习题集。一本是左孝凌老师等编写的《离散数学理论、分析、题解》,另一套有三本,是耿素云老师等编写的《离散数学习题集》。这两套书大多数题都是相同的,只是由于某些符号和定义的不同,使得题目的设定和解法有些不同而已。

离散数学学科内容

1.集合论部分:集合及其运算、二元关系与函数、自然数及自然数集、集合的基数

2.图论部分:图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用

3.代数结构部分:代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数

4.组合数学部分:组合存在性定理、基本的计数公式、组合计数方法、组合计数定理

5.数理逻辑部分:命题逻辑、一阶谓词演算、消解原理

离散数学被分成三门课程进行教学,即集合论与图论、代数结构与组合数学、数理逻辑。教学方式以课堂讲授为主, 课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。

篇3:离散数学的教学探讨

离散数学的教学探讨

离散数学是计算机科学与技术专业的'一门重要的专业基础课程,该课程概念多,理论性强,高度抽象.学生学习兴趣不高,教学效果不理想.因此,如何提高离散数学课程的教学水平和质量,对学生后续课程的学习和今后进一步的科学研究均具有现实的意义.文章结合笔者近年来从事离散数学课程教学的实际,从教学方法和教学手段等方面进行了一些初步探讨.

作 者:廖仲春 LIAO Zhong-chun  作者单位:长沙民政学院,湖南,长沙,410004 刊 名:湖南工业职业技术学院学报 英文刊名:JOURNAL OF HUNAN INDUSTRY POLYTECHNIC 年,卷(期): 8(5) 分类号:H319 关键词:离散数学   教学方法   教学手段  

篇4:离散数学的实验教学探讨

离散数学的实验教学探讨

离散数学是计算机专业的一门很重要的`专业基础课,该课程概念多,理论性强,高度抽象.传统教学中过于注重理论而忽略实验,学生在学习过程中往往态度消极.从教材中选取适合实验教学的重要理论的算法描述、课程实验体系建设、实际应用等方面入手,强化实验教学,培养学生学习兴趣,提高学生的应用能力.

作 者:沈来信 杨帆 Shen Laixin Yang Fan  作者单位:黄山学院信息工程学院,安徽,黄山,245021 刊 名:黄山学院学报 英文刊名:JOURNAL OF HUANGSHAN UNIVERSITY 年,卷(期): 11(3) 分类号:G642.423 关键词:离散数学   实验教学   课程实验   应用能力  

篇5:浅谈离散数学的学习心得

浅谈离散数学的学习心得

离散数学是这个学期我们新开的一门课程,刚开始学习这门功课,就一个感觉怪!比如这样的一个命题:2是整数那么北京是中国的首都。这个看似一点都不着边的命题,根据离散数学的规则,这却是一个合法的真命题。真叫人是诧异!(我想只要有点逻辑的人都会这么想的)

为此,我对离散数学这种没逻辑的学科而感冒了,甚至觉得这是个基本没用的科目。没兴趣是一回事,学习又是一回事。我硬着头皮的学习与记忆中。从命题到联接词的完备集,我都只是停留在表面的记忆之中的,只知道套用公式即可。但从理论推理这小节开始,我逐步发现以前看似定义与实际没关系的内容现在似乎与现实的推理相互牵连在了一起,通过将现实的事件转化成符号,运用一些推理规则比如P TCP规则,加上联接词判断正误的方法,一些将的逻辑推也是可以进行的.,对此我十分的好奇,有种想探索和研究的想法(其实就是再仔细的去体会下书本中概念)。

有句话说的好,书读百遍其义自现。其实自己也就是在无聊的时候再做了一次无聊复习而已。最近学习的谓词逻辑中,起初我并不知道它到底要谈些啥玩意,将命题拆了几大块,又莫名奇妙将这些小块用联结词组合在一起,还对它们进行一系列的判断,越学越没想法。也许是自己太笨了吧,其实在这一章的第一页的引言中就有一个突出主题的一段话,那就是--著名的苏格拉底三段论:所有人是要死的;苏格拉底是人;所以苏格拉底是要死的。这句话看是平淡无奇,其实它就解释了为何要研究谓词逻辑的原因。

我们回过头来再去细读离散数学中的每句话,其实开头的定义是为以后的推理进行准备的,为何我们会觉得很难去体会这样一个东西?原因其实很简单:抽象的东西往往是脱离实际的,有时近乎残酷的摆脱现实中一些实实在在的物质的,它近乎无情的定义将他们进行规定,就是在前人的一步一步的理论修正过程中,理论被变得完善,再用于刻画现实中的一些东西时,它就变得普遍符合。这也许就是很多人刚开始觉得学离散数学没用的原因。有些东西看似没用或不符合真理,但它经过修饰和一系列的规定它就成了一个真理,看待问题有时得从整体出发。

回过头来,我再去体会一下刚开始所说的一句话,它只是一个逻辑推理上的真命题并不符合事实本身。而我们所认同的推理是数学上的推理,其实在逻辑上的推理加上几个限定条件即可符合我们所认同的理论。比如条件必须是真命题,再如我们最近所学的谓词,它就是把命题本身分解开,揭示内在之间的关系。

仔细回想你会发现离散确实是一门逻辑严密的学科,我们必须得多读,多体会。

南归雁

5 11写于湖工大

篇6:离散数学的数学论文

摘要: 以信息专业的离散数学教学实践为基础,分析了大学文科数学教学内容的不足,探讨了如何在实践中进行教学改革,提高教学质量。

关键词: 离散数学;逻辑;可视化方法

引言

随着社会信息化的发展,《离散数学》逐渐成为信息学科的一门专业基础课。《离散数学》是现代数学的一个重要分支,以研究离散量的结构和相互间的关系为主要目标,其研究对象一般地是有限个或可数个元素。离散数学已经在数据结构、算法设计与分析、操作系统、编译系统、人工智能、软件工程、网络与分布式计算、计算机图形学、人机交互、数据库等领域都得到了广泛的应用。除了作为多门课程必须的数学基础之外,离散数学中所体现的现代数学思想对加强学生的素质教育,培养学生的抽象思维和逻辑表达能力,提高发现问题,分析问题,解决问题,也有着不可替代的作用[1]。

但是通过近几年的教学实践,人们对《离散数学》的课程设置和教学效果还不是很满意[2]。主要存在于教学内容取舍上和教学方法的应用上。如果教学内容的选取不当或是教学方法的使用不当,都会使学生对学习《离散数学》产生畏惧或是抵触的情绪,以至不了解学习的目的。如何提高学生对《离散数学》这一课程的认识,并学会用科学的思维方式思考问题,解决问题,进而提高自身的科学修养,这是我们每一个教育工作者应该关注的问题。本文基于笔者自身的教学经历和调查研究,对教学与学习《离散数学》的内容和方法中存在的一些问题加以分析,并且提出了一些相应的解决方案。

1 不同专业课程内容的设置

经典的离散数学内容一般包括数理逻辑、集合理论、图论基础、代数结构这四部分内容。随着信息科学的发展《组合数学》这一学科也逐步的被添加到离散数学的课程之内。但是因为不同专业培养学生的目标各异,所以对离散数学的课程要求也不一样,相应的课时分配亦不尽相同。大多数为36课时,54课时或72课时。对授课内容来说,也因为专业和课时的不同而有所差异,例如对信息与计算科学专业来说,在我校是54课时,又因为代数结构已作为一门单独的课程开设,所以在授课过程中我们主要教授其它几部分内容。而对我校的物理专业的信息课程来说,只有36课时,如何在如此少的课时讲授完四部分内容,确实是一种挑战,经过实践,我们决定讲与练结合起来,就是在课堂讲授主要部分,剩下的作为习题布置给学生,这样的好处是锻炼了学生的读书与自学能力,另外又因为数理逻辑,图论等内容与其电路设计等一些实际应用有关,所以我们加强这一方面的实际应用内容。信息管理类的开课则是54课时,在这一方面,因为学生的数学修养没有理科的好,所以我们则注重与其专业有关的内容,比如实际应用领域比较多的图论等。通过几年的授课,我们觉得,对数学基础比较好的专业,完全可以将《离散数学》分为基本不同的课程进行讲授,这样的好处是可以加深相应部分内容的理论基础以及扩展其应用的知识量,学生通过理论和应用的相互关联,加深了对本门课的认识和理解。对数学基础比较薄弱的专业,我们还是以应用为主,理论为辅。

与其他课程的联系也体现在不同专业需求上。就图论这一内容来说,在我校信息与计算数学专业与《离散数学》同时开课的有《数据结构》,而这两门课程在图的一章里面有内容的重叠,其不同点在于,《离散数学》注重的是理论的研究,而《数据结构》注重的是程序的设计。对于物理类的信息专业,其后续课程有《电路设计》,所以在课堂上,我们会举出一些与其相关的内容,使同学加以理解。

2 注重课堂授课过程的可视化方法

现在计算机辅助教学已经深入到了每一门课程中,《离散数学》也不例外。我们在讲授过程中,对于计算机的辅助教学,主要体现在如下的两个方面:一个是多媒体课件,一个是利用数学软件进行辅助计算。这是因为当学生接触到了《离散数学》这一门课程时,已经完成了从中学逻辑思维到大学逻辑思维的转换,因此,可以借用matlab这一类的辅助计算工具以加深同学们的理解。例如,在关系这一部分中有对极限定义的解释,我们先是应用课件对其进行可视化理解。具体是先复习绝对值“■”是一维坐标轴上两点的距离这一几何意义。那么对于函数极限的标准定义:“对于?坌?着>0,?埚?啄>0,当0

3 带有问题启发式的教与学

带有启发式的教与学主要体现在以下两个方面,一是对学生逻辑思维的培养,一是对所学知识在实际生活中的应用。逻辑思维主要体现在对同学的各种数学语言的理解和应用上,例如反证法一直是一种重要的逻辑思维方法,但是有的学生很难理解其内在本质,于是在数理逻辑这一部分,我们通过逻辑运算,给出这一方法的数学语言的表述。还有,对1=0.■这一在中学已接触到的知识,我们在函数这一部分应用极限的概念给予说明。很多学生在学完这些内容后纷纷表示对以前只知道机械运用的数学语言有了一个更加深刻的认识和理解。在教学生《离散数学》之前,我们通常会做一个小型的调查。最终的结果是很多学生都会问离散数学的应用。对于这一问题我们早有准备,授课过程中,尽量做到理论联系实际,而不是老生常谈式的对同学们解释,大学数学是伴随实际的应用而发展起来的,学习他可以提高学生的逻辑分析能力和处理问题的能力等等。例如,在讲授数理逻辑这一部分,我们会给学生解释,如果把一个人的所有特点都归结为前因,那么通过逻辑推理,可以得到这个人的命运结果。思维活跃的学生对这一解释很感兴趣,当场就算了起来。以致后来选择了逻辑推理作为自己的博士方向,以至于毕业留校。在讲授函数关系的时候,我们会以数据库access软件来说明。

4 结束语

通过讲授和与学生交流,我们深刻地认识到了《离散数学》开设的必要性和重要性。对如何在教学实践中进一步完善这将是我们今后重要的研究课题之一。

参考文献:

[1]屈婉玲,耿素云,张立昂.离散数学[M].清华大学出版社,2005.

[2]肖红,王辉,潘俊辉.案例教学在“离散数学”课程中的应用[J].价值工程,2013(6):271-272.

[3]石茂,张若为.数学在培养经济类文科生逻辑思维中的作用[J].价值工程,2011(18):247-248.

[4]赵军云,张璐璐,朱国春.离散数学课程教学中的探索与思考[J].电脑开发与应用,2010(10).

[5]文海英,廖瑞华,魏大宽.离散数学课程教学改革探索与实践[J].计算机教育,2010(06).

[6]师雪霖,尤枫,颜可庆.离散数学教学联系计算机实践的探索[J].计算机教育,2008(20).

离散型随机变量的期望说案

常用离散型随机变量的高阶原点矩

考研数学知识点总结

离散数学论文

数学的知识点总结

3年级数学知识点总结

概率论知识点及习题答案

多媒体制作与教学论文

网络课程学生个人学习心得体会

网络培训心得体会

离散数学知识点
《离散数学知识点.doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档

【离散数学知识点(共6篇)】相关文章:

概率论论文2023-05-29

计算机硬件学习心得2022-08-10

离散数学试卷2023-02-24

小学数学课程培训总结2023-03-26

考研数学:概率与数理统计考试内容2022-04-29

小学数学说课2022-10-31

初一数学说课的课件2023-05-14

七下数学知识点归纳总结2022-09-20

数字信号处理心得体会2022-09-25

概率论重要知识点总结2023-07-27

点击下载本文文档