离散数学考试大纲

离散数学考试大纲（共8篇）

离散数学考试大纲 篇1

一、考试要求共济

要求考生系统地掌握离散数学的基本概念、基本定理和方法，具有较强的逻辑思维和抽象思维能力，能够灵活运用所学的内容和方法解决实际问题。考

二、考试内容济

1、数理逻辑济

1)命题和联结词，谓词与量词，合适公式，赋值，解释与指派，范式共

2)命题形式化，等价式与对偶式，蕴含式，推理与证明

3)证明方法3

4)数学归纳法

2、集合论院

1)集合代数，笛卡尔乘积，关系与函数，关系的性质与运算

2)等价关系，划分共济

3)偏序关系与偏序集，格辅导

3、计数336260 37

1)排列与组合，容斥原理，鸽巢原理共

2)离散概率正门

3)函数的增长与递推关系院

4、图论 共济网

1)欧拉图与哈密顿图，平面图与对偶图，二部图与匹配，图的着色021-

2)树，树的遍历，最小生成树正门

3)最短路经，最大流量

5、形式语言与自动机 院

1)语言与文法，正则表达式与正则集

2)有限状态自动机，自动机与正则语言

6、代数系统

1)二元运算，群与半群，积群与商群，同态与同构

2)群与编码

3)格与布尔代数，环与域

三、试卷结构

1、考试时间为3小时，满分100分。

2、题目类型：计算题、简答题和证明题。

参考书

1．离散数学，胡新启，武汉大学出版社，2007年。

2．离散数学，尹宝林、何自强、许光汉、檀凤琴等，高等教育出版社，1998年。

离散数学考试大纲 篇2

1 离散数学简介

离散数学正式形成于20世纪70年代初期,主要包含五部分的内容:数理逻辑、集合论、代数系统、图论、形式语言和自动机。组成离散数学的五部分内容都有一定的发展历史。随着计算机学科不断的发展,离散数学也在不断的改革和变化。离散数学当前发展主要是沿着两个发展方向:一个是演算、另一个是算法。这两个方向平行发展。这几年由于人工智能的快速发展,促进了形式推理和代数结构的演算研究,同时在演算过程中强调算法的技巧。算法是计算机解决实际问题的主要手段。在计算机学科中占有非常重要的地位。所以在以后的离散数学中将加强自动机理论体系,并独立对算法进行研究。由于算法的发展,随之和算法相关的可计算性理论、不可计算性问题、算法分析与复杂性等理论也会迅速发展。因此离散数学进一步发展的内容,应该成为“理论计算机科学”的基础。

2 学习离散数学的重要性

2.1 离散数学在计算机学科中的地位

计算机学科中普遍采用了离散数学的基本概念、基本思想和基本方法,并把离散数学作为自己的理论基础和重要的数学工具。离散数学能够培养学生的抽象概括能力、逻辑思维能力、归纳构造能力、创新能力、分析问题和解决问题能力。离散数学与计算机学科中的后续课程数据结构、操作系统、编译原理、算法分析、逻辑设计、机器定理证明等联系紧密,为它们提供了必要的数学基础,所以离散数学在计算机学科中占有非常重要的地位。

2.2 离散数学与编程的关系

计算理论与算法是计算机程序设计的灵魂。程序设计者都需要一定的数学修养。严格的说,一个离散数学基础不扎实的程序员不能算一个合格的程序员。如果离散数学和算法设计技术没有学好的话,这样的程序员基本上只能算是背程序的机器,只能停留在写写简单的classes或用SQL语句实现查询等基础的编程工作,对于一些需要用到离散数学知识的编程的工作就无能为力。为什么这样说呢,大家可以了解一下计算机解决实际问题的一个过程:“分析问题→建立数学模型→选择数据结构→设计算法→翻译成计算机语言”的过程。从在这个过程中,大家可以看出来最后一步才是通常所说的编程序。所以,学会C编程语言或者会用一两种开发工具只不过学会了最后一步,而前面的四步不学会的话,想用计算机解决实际问题的能力是非常有限的,除非是特别简单的问题。但是前面四步的掌握都与离散数学学习有关。所以要想成为一名合格的程序员,必须提高离散数学修养。

2.3 离散数学应用举例

数学的源泉在于应用。离散数学的应用主要是通过一些数学模型与学科的联系来实现的。这里以表格形式列出离散数学与计算机科学实际应用的一些结合点[4],如表1所示:

这样的“结合点”还很多很多,由上表同学们就可以看出离散数学在计算机科学中是最基础的学科了。学好离散数学是学好计算机的基础,这就是为什么计算机专业的研究生考试,离散数学都采用最难试题的缘由。

3 离散数学学习方法

3.1 了解离散数学与一般数学的区别

离散数学是计算机科学的数学,和一般的工程数学,计算数学都有一定的区别。传统的数学系一般开的主干课程有数学分析、微分方程、复变函数、泛函分析等。讨论的对象基本是连续的变量,关心的比较多的是解的存在性,唯一性,稳定性和收敛性等等。而离散数学作为计算机学科的基础数学,主要研究的对象是离散的量,比如说自然数、整数、有限个结点,{真,假},等等。离散数学涉及的结构类似于图、树、排列和组合这样的结构。并不热心于解的存在性等的讨论。比较注意的是概念的描述和能行性问题。离散数学的论证方法也和传统数学所采用的分析方法不一样.离散数学除了采用一般分析课程的分析方法外,最主要的论证方法是数学归纳法,构造法,反证法等。尤其是构造性证明方法体现了计算机科学的特性。程序员采用编程语言写代码解决实际问题的过程,其实就是程序员构造代码的过程。集合论中康托尔的对角线论证是构造性论证的范例,在图论当中好多定理的证明都采用的构造性证明的方法,所以学习离散数学可以很好的培养学生的构造性思想。同学们要充分了解离散数学与一般数学的区别,掌握离散数学的学习方法。

2.3 充分了解离散数学的特点、难点有针对性的学习

离散数学的特点是:内容散,概念多和好理解;难点是:离散数学概念多易忘。头几次离散数学上课一般都没有问题,容易给同学造成错觉,认为该课程简单,听不听都能学好,正如学习语言,一天记20个单词没有问题,天天记20个单词且保证以前记的不忘就太难了。当学生一旦忘记前面的概念,就会影响相关知识的学习,如果不及时补救就会形成连锁反应,所以并不是聪明的人才能学好离散数学,而是能够坚持的人才能学好。所以建议同学:除了认真听课,认真做作业,有问题及时解决外,能和同学做到每天讨论几分钟离散数学,加强概念的记忆。

2.4 学习离散数学的本质

在知识大爆炸的今天,学会知识的意义是有限的,学会学习的技能才是最重要的,学数学就是要做数学,学习离散数学也不例外,学习数学不仅限于学习数学知识,更重要的是学习数学思维。在平时学习中要善于总结和归纳。计算机系的学生对数学的要求跟数学系是不同的,跟物理的差别就更大。所以计算机系学生学习离散数学一定要先了解学习离散数学的主要目的是什么,学习这门课的主要目的是将理论再应用于实践,培养和训练自己的推理能力,这也是学习离散数学的本质。所以在做离散习题的时候不仅要掌握题目的解题方法,更要掌握解题的思路。对于定理的学习不能像学高等数学一样只记住结论,强调套用公式计算而不去深究它的由来。定理证明的过程恰巧是训练思维能力的过程。所以对定理证明过程的学习对于计算机系学生来说是非常重要的。

4 结论

总之,绪论课教学作为教师与学生的第一次接触,在整个学科教学中具有特殊的教学地位和重要意义,搞好离散数学绪论课的教学可以起到”抛砖引玉”的作用。此绪论课使学生充分认识到学习《离散数学》的重要性和必要性。并了解离散数学的学习方法,从而对本门课程的学习产生浓厚的学习兴趣,为学习好这门课奠定了基础。

摘要：离散数学是计算机专业的核心基础课,在教学中具有特殊的地位和作用。第一堂课是学好离散数学的关键。该文通过三个方面就如何上好离散数学绪论课做了探讨。

关键词：离散数学,绪论课,教学

参考文献

[1]Kenneth H.Rosen.离散数学及其应用[M].袁崇义,等译.北京:机械工业出版社,2006.

[2]杨卓娟,杨晓东.关于高校课程绪论教学的思考[J].中国大学教学,2011(12):39-41.

[3]黄震.《离散数学》课程在计算机科学中的作用及其应用[J].赤峰学院学报:自然科学版,2011.

浅谈《离散数学》的教学 篇3

摘要：为了激发学生的学习热情，培养其思维能力和应用能力，根据离散数学课程教学的特点，笔者结合课程教学经验，对离散数学教学进行了研究.文章提出一些教学方法和手段的改革，在实际教学中起到了一定的作用，提高了教学质量.

关键词： 离散数学，教学方法，教学手段

【中图分类号】O158-4

On the Teaching "Discrete Mathematics" in

Chenxue Gang Zhou Jiquan

（North China Electric Power University Mathematics， Beijing， 102206， China）

Abstract： In order to stimulate students' enthusiasm for learning， develop their thinking skills and ability， according to the characteristics of Discrete Mathematics Instruction， author of Teaching experience， discrete mathematics teaching were studied. This paper presents some of the reform of teaching methods and means， in the actual teaching has played a certain role in enhancing the quality of teaching.

Keywords： discrete mathematics， teaching methods， teaching means

《离散数学》是计算机科学中重要的基础理论课程之一，它不仅是许多计算机专业课的必备基础，而且对培养学生抽象思维能力和逻辑推理能力有着重要的作用.然而采用以往的教学方法，教学效果往往不够理想.一方面，离散数学知识的分散性令许多学生感到无从下手.另一方面，在传统的离散数学教学中，往往采用“纯数学”教学方法，学生不能很好地体会离散数学对计算机科学的重要意义，所以学习积极性不高.因此，通过教学方法和手段的改革来激发和增强学生的学习兴趣，从而培养学生的创新思维和综合能力，是离散数学教学中非常迫切的需求.本文结合作者近年来从事离散数学课程教学的经验，从教学内容、教学方法、教学手段等方面进行了一些初步探讨.

1精选教学内容

《离散数学》教学内容主要包括数理逻辑、集合论、代数结构及图论等几大分支.各分支均有悠久历史.如果这几部分的内容都要详细讲授，时间上来不及，所以在在教学过程中对讲授内容的选择应当有所侧重.比如简单介绍集合论的理论基础，重点是如何利用集台论的方法解决实际应用问题.在二元关系这部分，重点是二元关系的几个与性质相关问题的论证方法的训练.在数理逻辑上通过将一般命题公式和一阶逻辑公式化成范式，达到强化训练学生逻辑演算能力.图论部分重点放在基本概念的理解和实际问题的处理上，通过对相关定理及其证明思路的理解来体会图论的研究方法.代数系统这部分内容重点放在群论上，尤其要在代数系统、群、子群、循环群、变换群、正规子群的概念及相关问题的理解上下功夫.

2 教学方法探讨

2.1 增加讨论课

老师首先选定讨论的课题，学生分组准备查询相关的文献，并形成自己观点.在讨论课上大家共同交流探讨，从而加深对这门课程的认识.最后各小组完成论文的书写.该方法不仅可以提高学生对离散数学重要性的认识，还可以提高学生互相协作的能力以及书写论文的能力.

2.2 增加趣味性，激发学生的学习兴趣.

“兴趣是 最好的老师”，只有激发起学生的学习兴趣，他们才有真正自主学习的欲望.在教学过程中，根据具体的知识点，介绍它的发展史或者引入趣味问题，增加了学生学习离散数学的兴趣，拓宽了学生们的知识面，提高了学生对离散数学课程学习的积极性与主动性.

2.3 注重归纳与小结

离散数学的内容虽然多且散，但通过归纳和小结，可以用一条主线贯穿始终.离散数学讨论的内容主要包含系统中涉及到的静态（基本概念）与动态（运算、操作、推理）.如集合论中是元素（静态）及其上的运算（动态）；代数系统中是集合（静态）及运算（动态）；数理逻辑中是公式（静态）和推理（动态）.通过归纳与小结，学生能够理清头绪，提高学习效率.

3 教学手段改革

3.1 教学网站建设

信息技术对提高教学质量具有重要的影响，必须予以高度重视.为了提高教学质量，我们建设了一个教学支撑网站，一方面大力推进信息技术在教学中的实际运用，促进教学手段和教学方法现代化；另一方面以此提高教与学的效率.

3.2 重视学生作业，定时测验

离散数学的知识不经过学生的独立思考和多做练习是无法牢固掌握的，因此一定要给学生留一定数量的课后习题.但大部分学生不可能把课本上的习题全部做完，教师也不可能完全批阅.这就要求教师布置作业要选其精华，选题必须要有一定的深度和广度，要覆盖所学的内容，尽量选有启发性质的习题.对于学生的作业，要认真仔细批改，将作业中暴露出来的普遍问题，要进行课堂讲评.通过讲评作业，帮助学生澄清模糊和错误的认识.

3.3 新的考核方式

传统的考核方法就是试卷考试，考察学生的基本知识和基本技能，以及解难题的能力.我们尝试做了一些考核方法的改革，把原来的试卷考试和平时的考核两部分，改成了三部分成绩的统一， 即添加了一个新的内容：写离散数学的论文.把它的评定结果作为成绩的一个重要部分.所写论文必须要求观点明确、主题鲜明和论述严谨，并且具有一定的创新.

4 结束语

总之，要把离散数学这一门课教好，教师就要不断研究新的教学方法和手段，认真掌握教学规律，借助于现代化教学手段，提倡“启发”式教学.教师只要具有扎实的理论功底，并具有对学生高度负责的精神，就一定能够达到良好的教学效果.

参考文献：

[1]赵青杉，孟国艳.关于离散数学教学改革的思考[J].忻州師范学院学报，2005，21（5）：6 .

[2]耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2001.

[3]翁梅，刘倩，冯志慧等.“离散数学”课程教学实践与探索[J].计算机教育，2004（12）：62—63.

[4]钟敏，时念云.改革课程实验提高离散数学教学质量 [J].计算机教育，2008，18.

[5] 张艳华，周雪琴，马新娟，王举辉，张立红. 基于卓越工程师的“离散数学”教学改革探索[J]. 当代教育理论与实践. 2013（12）

上海海事大学离散数学考试提纲 篇4

一、判断哪些是命题

*命题的表示（联结词），符号化命题(样题2)*真值表（用来证明）

*等价式的证明（用已知的等价式推导）(样题3)蕴涵的证明(样题4)对偶式（化对偶式）

*写出主析（合）取范式（真值表，公式推导）(样题5)*命题的推理（真值表，直接，间接）(样体6)

二、*谓词公式的翻译（存在，全称）(p60习题2,批p61例题,批p62习题1)约束变元及其换名(p63例题1)等价式和蕴涵式（转换，扩展和收缩，分配，多量词）(p66-p70)前束范式(p73例题)*推理 p76-p77

三、*集合的表示

*集合的运算（。。幂集）*包含排斥

序偶（同集合）

关系（定义域，值域，特殊的关系，*关系的表示,特别是矩阵）*关系的性质（5大性质，）

复合关系和逆关系 p114例题1,p115例题5,p118例题4 关系的闭包运算（三个）p121例题1,p124例题4 集合的划分和覆盖（能判断哪些是划分和覆盖）

*等价关系（判定，要会用等价关系对集合划分即写出等价类）p131,132例题, *序关系（判定，哈斯图，链反链）p140,141例题, *求极大（小），最大（小），上（下）界，上（下）确界 p146习题6

四、*判定是否函数，满，入，双

*逆函数、复合函数（判定原函数是满，入，双复合后是否满，入，双）判定二个集合是否等势（构造双射函数）有限集，无限集（可数，不可数）

自然数 实数集

可列

五、*代数运算的表示（包括运算表）p189例题

*判断代数系统的运算性质：封闭，可交换，可结合，可分配，吸收率，等幂性 *代数系统的幺元和零元（唯一性证明），逆元 p184 半群的判断，独异点的判断

*群与子群的判断，群的性质证明 交换群的性质，循环群的性质 *定理5-7.1,意义，性质

任何一个群不是4阶循环群就是Klein群

*同构同态的判断（满，单一，）p214例题，同余 环，域判断，同态象

六、*格、子格的定义

*并，交运算的定义及其性质 p233例题 p241例题 p242习题 格的同态与同构

*分配格的性质，p244例2,3 ,有补格的性质，补元素 p252习题1 布尔代数，布尔表达式及其范式

七、图简单性质（点边数目关系），图的同构判断，生成子图，补图 路，回路，通路，连通，点割集（割点），边割集（割边）及其性质

有向图的单侧连通（分图），强连通（分图），弱连通（分图）p287习题8 *图的矩阵（邻接，可达性，完全关联）p290例题1, *欧拉图的判定，H图的判定,p306,p310,样体21平面图的判定（K3,3 K5）p317习题5 对偶图和着色 p318,p319 p321习题 *树的等价定义和证明

离散数学考试试题(A卷及答案) 篇5

一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((PQ)∧Q)((Q∨R)∧Q)2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解：1)永真式；2）永假式；3)可满足式。

二、（8分）个体域为{1，2}，求xy（x+y=4）的真值。

解：xy（x+y=4）x（（x+1=4）∨（x+2=4））

（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））（0∨0）∧（0∨1）1∧10

三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？

解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。

四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。

解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}

五、(10分)75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。

解 设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。

由容斥原理，得

|A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以

|A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。

六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S∈R∩S∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()＝。证明h是双射。

证明：1）先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是满射。

2）再证h是单射。

、∈A×C，若h()＝h()，则＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。综合1）和2），h是双射。

八、（12分）是个群，u∈G，定义G中的运算“”为ab=a*u-1*b，对任意a,b∈G，求证：也是个群。

证明：1）a,b∈G，ab=a*u-1*b∈G，运算是封闭的。

2）a,b,c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），运算是可结合的。3）a∈G，设E为的单位元，则aE=a*u-1*E=a，得E=u，存在单位元。

4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，则xa=u*a-1*u*u-1*a=u=E，每个元素都有逆元。所以也是个群。

九、（10分）已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。

解：D的邻接距阵A和可达距阵P如下：

A= 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0

0 0 1 0 0

P= 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1

十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

权＝148

离散数学考试试题（B卷及答案）

一、（10分）求命题公式(P∧Q)(PR)的主合取范式。

解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）(P∧Q)∨(P∧R)(P∨R)∧（Q∨P）∧（Q∨R）

(P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）M1∧M3∧M4∧M5

二、（8分）叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。命题符号化为x（F（x）G（x）），F（a）G（a）证明：

（1）x(F(x)G(x))P（2）F(a)G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I

三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)证明：∵x A∩（B∪C） x A∧x（B∪C）

 x A∧（xB∨xC）

（x A∧xB）∨（x A∧xC） x（A∩B）∨x A∩C  x（A∩B）∪（A∩C）

∴A∩（B∪C）=（A∩B）∪（A∩C）

四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。

解：x∈A，因为R和S是自反关系，所以∈R、∈S，因而∈R∩S，故R∩S是自反的。

x、y∈A，若∈R∩S，则∈R、∈S，因为R和S是对称关系，所以因∈R、∈S，因而∈R∩S，故R∩S是对称的。

x、y、z∈A，若∈R∩S且∈R∩S，则∈R、∈S且∈R、∈S，因为R和S是传递的，所以因∈R、∈S，因而∈R∩S，故R∩S是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S∈R∩S

∈R∧∈S x∈[a]R∧x∈[a]S x∈[a]R∩[a]S 所以[a]R∩S=[a]R∩[a]S。

五、(10分)设A＝{a，b，c，d}，R是A上的二元关系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解 r(R)＝R∪IA＝{，，，，，，，} s(R)＝R∪R＝{，，，，，} R＝{，，，} R＝{，，，} R＝{，，，}＝R

t(R)＝R＝{，，，，，，，，} i1i

4232-

1六、(15分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()＝。证明h是双射。

证明：1）先证h是满射。

∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝＝，所以h是满射。

2）再证h是单射。

、∈A×C，若h()＝h()，则＝，所以f(a1)＝f(a2)，g(c1)＝g(c2)，因为f是A到B的双射，g是C到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。

综合1）和2），h是双射。

七、(12分)设是群，H是G的非空子集，证明是的子群的充要条件是若a，bH，则有a*bH。

证明： a,b∈H有b∈H，所以a*b∈H。a∈H，则e=a*a∈H-1-

1-1-1a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵HG且H≠,∴*在H上满足结合律 ∴是的子群。

八、（10分）设G=是简单的无向平面图，证明G至少有一个结点的度数小于等于5。

解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图-

1-1

-1-1-1的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=,A={a,b,c},*的运算表为：(写过程，7分)

（1）G是否为阿贝尔群？

（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿贝尔群

（2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a（3）因为a*a=a 所以G的幂等元是a（4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b

十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树为

离散数学考试大纲 篇6

答案及评分细则

课程名称： 离散数学 考试形式： 闭卷 考试日期：2013 年 月 日 考试时长：120分钟

I.Multiple Choice(15%, 10 questions, 1.5 points each)C, C, B, A, B, B, D, A, B, C II.True or False(10%, 10 questions, 1 point each)F, T, T, T, F, F, F, F, T, F

III.Fill in the Blanks(20%, 10 questions, 2 points each)27=128, [-1,1], (aa)(bb)(cc)(ab)(ba), (12)(23)(33)(42), Some tests are easy, gcd（45，12）=3=12  4  45 (1), 6!, 52, ∀x ∃y(xy <>0), {(a,b)2|ab}

IV.Answer the Questions(35%,7 questions, 5 points each)： 1．

(1 point for each row)

2.Ans:(a)0123

(3points)

(b)[612).(2points)113.Ans: 001110011100.(one entry 1 point)114.Ans:

(one point for each step)

5.Ans: Encrypted form: CTOA.(one character 1 point)6.Ans: 5  11k.(the inverse of 5 module 11 is 9, 3 points, the result 2 points)7.Ans: The graphs are isomorphic(2 points): A–7, B–4, C–3, D–6, E–5, F–2, G–1.(3 points)

V.(6%)

(a)R is reflexive:(a, b)and(a, b)lie on the same line through the origin, namely on the line y = bx/a(if a≠0), or else on the line x = 0(if a = 0).(1 point)

R is symmetric: if(a, b)and(c, d)lie on the same line through the origin, then(c, d)and(a, b)lie on the same line through the origin.(1 point)R is transitive: suppose(a, b)and(c, d)lie on the same line L through the origin and(c, d)and(e, f)lie on the same line M through the origin.Then L and M both contain the two distinct points(0, 0)and(c, d).Therefore L and M are the same line, and this line contains(a, b)and(e, f).Therefore(a, b)and(e, f)lie on the same line through the origin.(1 point)Note: The proof that R is an equivalence relation can be carried out using analytic geometry: if(a, b)and(c, d)lie on the same nonvertical line through the origin, then the slope must equal b/a because the line passes through(0, 0)and(a, b)and the slope must also equal d/c because the line passes through(0, 0)and(c, d);thus, b/a = d/c, or ad = bc.If(a, b)and(c, d)lie on the same vertical line through the origin, then the points must have the form(0, b)and(0, d), and again it must happen that ad = bc.Therefore,(a, b)R(c, d)means that ad = bc.This equation can be used to verify that R is reflexive, symmetric, and transitive.(b)Each equivalence class is the set of points of A on a line of the form y = mx or the vertical line x = 0.(2 points)(c)If A is replaced by the entire plane, R is not an equivalence relation.It fails to satisfy the transitive property;for example,(1, 2)R(0, 0)and(0, 0)R(2, 2), but(1, 2)R(2, 2)because the line passing through(1, 2)and(2, 2)does not pass through the origin.(1 point)

VI(7%)

Using the variables: p: Lynn works part time;f: Lynn works full time;t: Lynn plays on the team;b: Lynn is busy, the argument can be written in symbols:

(3 points)If p∨f;t →p;t → b;f Then b

(1 point)One method to find whether the argument is valid is to construct the truth table:

We need to examine all cases where the hypotheses(columns 5, 6, 7, 8)are all true.There is only one case in which all four hypotheses are true(row 5), and in this case the conclusion is also true.Therefore, the argument is valid.(3 points)Alternately, rules of logic can be used to give a proof that the argument is valid.We begin with the four hypotheses and show how to derive the conclusion, b.1.p∨f;premise 2.t →p premise 3.t → b premise 4.f premise 5.p disjunctive syllogism on(1)and(4)

(1 point)6.p → t contrapositive of(2)

7.t modus ponens on(5)and(6)

(1 point)8.b modus ponens on(7)and(3)

(1 point)

VI I(7%)

Ans: {a} {a, b} {a, b, c}

离散数学课程教学改革探讨 篇7

离散数学课程形成于20世纪70年代, 是比较新兴的学科.近年来随着信息技术的飞速发展, 离散数学课程的经典内容已不适应实际应用的需要, 很多学校电子和信息类专业研究生入学考试课程中, 将过去单一的离散数学考试改为结合计算机编程等多种内容结合的考试.离散数学课程内容多, 分散繁杂, 学生做习题普遍感到难以下手.目前学生学习离散数学课程感觉理论脱离实践, 所以兴趣不大.

我们应该改革教学内容, 使教学内容适应当前信息及电子类专业的需要, 适应相应专业考研的需要.修订《离散数学》教材和教学大纲, 实现教材内容与教学大纲的统一.探讨离散数学练习题中的“母题”, 编写《离散数学要点及题解》, 便于学生举一反三, 帮助学生自学和做练习题.探讨离散数学知识在实际问题中的典型应用, 编制使用离散数学知识解决实际问题的计算机语言程序, 让学生学习期间感觉到理论与实践的结合.

二、研究离散数学练习题中的母题

离散数学课程内容多, 分散繁杂, 学生做习题普遍感到难以下手.若搞题海战术, 学生时间紧, 又要顾及其他课程, 所以往往采取应付回避的态度, 做题能力很差.我们应该仔细研究各部分的练习题, 探讨各种题型, 分析练习题之间的联系以及与知识点之间的关系, 选择和编制出有代表性的“母题”, 尽量使学生做了这些题以后, 能够举一反三, 事半功倍.

我们编写了《离散数学要点及题解》, 内容包括集合论、数理逻辑、图论和代数系统等四个部分的基本知识点、重点与难点、典型题解析、自我检测题.集合论部分包括集合的概念和集合的运算、二元关系、映射;数理逻辑部分包括命题逻辑和谓词逻辑;图论部分包括图论基本概念和一些特殊图;代数系统部分包括群、环、域, 格、与布尔代数等内容.

各章节的“基本知识点”分为基本概念、基本理论和基本计算;“典型题解析”选择具有代表性的例题进行详细分析, 并给出标准解题步骤, 对于有些题目还给出一题多解, 或对相应的知识点和难点加注, 指出容易犯的错误及犯错误的原因;各章最后一节是“自我检测题”, 这些题中尽量避免近似程度很高的题;附录部分提供近年来的研究生入学考试题中的离散数学部分及其解答.作为离散数学教材的教辅材料, 书中尽量避免偏题怪题, 围绕基本知识点和基本要求, 分析典型题例, 从易到难, 循序渐进, 帮助学生轻松掌握基本内容.

三、介绍编程软件, 编写结合课程内容的算法语言小程序

离散数学虽是一门比较抽象的课程, 但和其他数学分支有明显的不同, 它是20世纪一门新兴的学科, 是将计算机和信息行业需要的数学知识收集在一起形成的一门课程.一方面它有自己的应用背景, 另一方面, 又有数学的抽象性和严密的科学性.在讲解概念和定理的同时, 如何将所学知识与实践相结合, 如何与编写程序相结合, 应该进行这种探索和尝试.

例如, 离散数学课程中关于集合的交、并等运算, 在很多计算机语言中都有直接实现的语句.例如, Pascal语言、Matlab软件、SEQ语言等.

例如, 离散数学中函数的递归定义在常用算法语言中都有直接实现方法.

例如, 在离散数学中, n个集合A1, A2, …, An的笛卡儿叉积的任一子集B称为一个n元关系, B中每一个元素 (a1, a2, …, an) 称为一个n元组.关系数据库中的关系、元组 (或记录) 的概念正是从这里得来的.

例如, 离散数学中数理逻辑部分, 利用已有的规则进行推理, 可用人工智能语言实现.人工智能 (AI) 语言是一类适应于人工智能和知识工程领域的、具有符号处理和逻辑推理能力的计算机程序设计语言, 能够用它来编写程序求解非数值计算、知识处理、推理、规划、决策等具有智能的各种复杂问题.典型的人工智能语言主要有LISP, Prolog, Smalltalk等.

例如, 离散数学中的树、二叉树、图是数据的逻辑结构的重要类型, 只有将树的遍历、图的遍历原理搞清楚, 才能编写较复杂的算法.例如, 最短路算法, 最小生成树算法, 中国邮路问题算法, Huffman最优树算法等.可利用C语言编写相应的程序, 实现算法功能.

例如, 离散数学中的代数系统、群环域、布尔代数在编码学、信息安全中有重要应用, 应该寻找这方面的实例, 将主要部分拿来, 深入浅出地介绍给学生, 提高学生的学习积极性.

多媒体课件在教学中的作用越来越明显, 尤其与计算机相关的课程中更是如此.

四、改革成果的推广

离散数学课程教学方法和手段的改革模式可推广到信息专业和数学专业相似课程中去, 例如组合优化、数值分析、运筹学等.另外课程内容的改革、多媒体课件、教材、要点及题解等都可以在同类课程的自学和实践中推广.

参考文献

[1]王忠义等.离散数学.西安:陕西科学技术出版社, 2001.

离散数学翻转课堂教学改革探讨 篇8

关键词：离散数学；翻转课堂；教学改革

中图分类号：G434 文献标识码：A 论文编号：1674-2117（2016）15/16-0162-03

离散数学是研究离散量的结构及其相互关系的一门学科。它是计算机学科及相关专业的基础课程。离散数学为后续课程提供必要的数学基础，目的是让学生掌握处理离散结构的描述工具和方法，同时，培养学生的抽象思维和逻辑推理能力，为他们将来从事科学研究打下坚实的基础。

翻转课堂（Flipped Classroom或Inverted Classroom）是指重新调整课堂内外的时间，将学习的决定权从教师转移给学生。

本文针对新的教育环境下，“离散数学”教学如何与时俱进，实现翻转课堂这一问题提出了以下几点思路。

回归“因材施教”

如今的大学，迫于教学任务，教师很难做到“因材施教”，学生也很少提问，这种师生分离的教学很难培养出优秀的人才。现在受人热捧的翻转课堂虽然强调了学生的主体地位，对传统的教学模式产生了冲击，但也从以下几个方面对教师提出了更大的挑战：①翻转教学理念。教师要走进学生的心灵，了解他们在想什么，在做什么，才能知道他们更需要什么。在翻转课堂中，教师应该尊重学生的个性、兴趣、能力等差异，平等、宽容、民主地对待学生，因材施教。②翻转教学方式。离散数学课程章节多，知识结构分散，有的内容理论性强，有的内容很抽象。如何做到让学生想学，乐学，且学有所获呢？这是每位教师应该认真思考解决的问题。③翻转教学目的。完成教学任务不是目的，培养国家和社会需要的合格人才才是我们最终的教学目标。学习能力强的学生，教师应给予更前沿的学习内容；题做错的学生，教师应和他一起分析错的原因……

建设面向“本校”的MOOC及SPOC平台

翻转课堂需要翻转教师的教学方式和学生的学习方式。MOOC是当下流行的网络学习模式。MOOC是针对大多数人的在线课程，特点是大规模、在线、开放，人们可以通过网络自由选择感兴趣的课程，费用低且学习资源丰富。SPOC是小规模限制性在线课程，“small”意为学生规模相对于MOOC较小，“private”是指对学生设置进入条件，达到要求的申请者才能被纳入进来。

1.鼓励教师制作面向本校学生的MOOC和SPOC课程

鼓励教师制作面向本校学生的MOOC和SPOC课程，一方面，把教师从教学任务的束缚中解放出来，教师可以在课下从论坛和后台了解学生的学习状态、学习兴趣、性格特点等，课堂上会有更多的时间答疑解惑，而不是忙于灌输。有了MOOC和SPOC平台，教师才有机会在课堂上整合各种教学手段，组织或要求学生对本课程的知识点做不同层面、不同深度的思考和讨论。另一方面，会让教师重新审视自己的教学方式和教学理念。因为MOOC和SPOC课程不是面向本班几十个学生，而是全校所有师生，而且MOOC平台会及时真实地反映教学中存在的问题，这就形成了竞争，使教师不得不认真思考教学内容的组织、教学方式，甚至是教学语言的准确、教学仪态的得体等问题，对提高教师的教学能力，并进一步提高教学质量无疑能起到良好的促进作用。

2.鼓励学生通过带课教师的MOOC课程进行基本知识的学习

有了带课教师的MOOC课程，学生的学习时间、学习地点更加自由，还可以根据自己的实际情况灵活调整学习计划，有利于学习兴趣的培养。学生只有拥有学习的主动性、积极性，才有可能对本课程的知识点进行思考，课堂上才可能提出好的问题，同时，翻转了的教学方式使学生上课时不再只是“听”，还被鼓励“问”和“说”。表面上学生的学习任务看似加重了，但实际上是教师和学生的能力都得到了增强。

3.鼓励学生通过带课教师的SPOC课程进行进一步的学习

SPOC采用课堂教学与在线教学相结合的混合教学模式，比MOOC更具有针对性地为学生提供适合其学习程度和学习特点的课程，同时利用在线视频、在线互动及线下面授等环节，提供了更多与教师沟通的机会。教师开设SPOC课程，不仅能加深自己对课程知识的认识，达到教学和科研协调发展，而且能更全面地了解学生各方面的情况，可以更好地“因材施教”。

4.调整考核方式

学生的考核方式要能激发学生的学习兴趣，提高学习主动性，在给予其压力的同时更赋予动力，以培养学生的综合能力及素质为目标。考核可以从以下几个方面开展：①注重课堂表现和平时作业完成的质量，改变期末考试“一锤定音”的局面。②学生参与。学生可以根据自己的表现，为自己打分。③家长参与。学校在教育学生的同时，也需要得到家长的理解和配合，让家长了解孩子在校表现的同时，也接受家长的监督。

教师的考核方式也应该以学生为主，学生满意才是教学的宗旨。考核可以从以下几个方面开展：①增大学生选课的比例，促进学生主动学习的同时增强教师的教学水平和教学能力。②教学考核与科研考核并重，形成教学促科研，科研辅教学的良性循环。

5.加强实践环节，增强学生应用离散数学解决实际问题的能力

“知之而不行，虽敦必困”，数学的魅力在于应用。因为离散数学是计算机专业的基础课程，所以对学生编程兴趣和能力的培养不容忽视。增设离散数学实验课不仅能让学生深入体会离散数学应用的广泛性，而且也有助于锻炼和加强学生的编程能力。实验课的形式也可以翻转，如由教师讲解编程思想，学生动手编写，或由学生讲解算法，教师组织讨论甚至辩论，再由学生编写程序进行测试等。实验课的内容可根据学生的情况灵活设定。例如，教师可以在实验课中介绍和讲解搜索引擎的设计与实现，学生在动手编写程序的同时，也会更深地体会到逻辑联接词在网页检索技术中的应用。又如，某公司在多个城市（代表名为的城市）有分公司，从城市到城市的直接航程票价记在矩阵的位置上（∞表示无直接航路），请帮助该公司设计一张从城市到其他城市的票价最便宜的路线图。学生在编程实现的同时，对迪克斯特拉（Dijkstra）算法也有了更深的体会，教师还可以趁机引导学生了解其他最短路程的算法（如Floyd-Warshall算法等），启发学生对现有算法提出改进。

开展离散数学翻转课堂是一项艰巨而有意义的工作，笔者将身体力行，更深入、更具体地投身到教学改革的实践中，为取得更好的教学成果而努力。

参考文献：

[1]萨尔曼·可汗.翻转课堂的可汗学院——互联时代的教育革命[M].刘婧，译.杭州：浙江人民出版社，2014.

[2]于歆杰.以学生为中心的教与学——利用慕课资源实施翻转课堂的实践[M].北京：高等教育出版社，2015.

[3]张金磊，王颖，张家辉.翻转课堂教学模式研究[J].远程教育杂志，2012，30（4）：46-51.

[4]李海龙，邓敏杰，梁存良.基于任务的翻转课堂教学模式设计与应用[J].现代教育技术，2013，23（9）：46-51.

[5]邓秀勤，郝志峰，刘海林.基于创新能力培养的离散数学课程教学改革探索[J].计算机教育，2013（16）：62-66.

[6]张小峰，蔡春波，李秀芳，杨洪勇.基于程序设计能力培养的离散数学教学改革[J].计算机教育，2015（2）：44-47.

[7]屈婉玲，耿素云，张立昂.离散数学[M].北京：清华大学出版社，2014.

[8]左孝凌.离散数学[M].上海：上海科技文献出版社，1982.

作者简介：郭慧娟（1979.9—），女，山西省定襄县人，太原师范学院计算机系教师，讲师，硕士，研究方向为机器学习、压缩感知及信号处理。