离散数学应用论文

离散数学应用论文（共8篇）

离散数学应用论文 篇1

证明等价关系：即要证明关系有自反、对称、传递的性质。

证明偏序关系：即要证明关系有自反、反对、传递的性质（特殊关系的证明就列出来两种，要证明剩下的几种只需要结合定义来进行）。

证明满射：函数f：X®Y，即要证明对于任意的yÎY，都有xÎX，使得f(x)=y。

证明入射：函数f：X®Y，即要证明对于任意的x1，x2ÎX，且x1≠x2，则f(x1)≠f(x2)；或者对于任意的f(x1)=f(x2)，则有x1=x2。

证证明集合等势：即明两个集合中存在双射。有三种情况：第一，证明两个具体的集合等势，用构造法，或者直接构造一个双射，或者构造两个集合相互间的入射。

第二，已知某个集合的基数，如果为א，就设它和R之间存在双射f，然后通过f的性质推出另外的双射，因此等势；如果为א0，则设和N之间存在双射。第三，已知两个集合等势，然后再证明另外的两个集合等势，这时，先设已知的两个集合存在双射，然后根据剩下题设条件证明要证的两个集合存在双射。

证明群：即要证明代数系统封闭、可结合、有幺元和逆元（同样，这一部分可以作为证明题的概念更多，要结合定义把它们全部理解透彻）。

证明子群：虽然子群的证明定理有两个，但如果考证明子群的话，通常是考第二个定理，即设是群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1ÎS，则是的子群。对于有限子群的相关证明，则可以考虑第一个定理。

证明正规子群：若是一个子群，H是G的一个子集，即要证明对于任意的aÎG，有aH=Ha，或者对于任意的hÎH，有a-1 *h*aÎH。这是最常见的题目中所使用的方法。

离散数学应用论文 篇2

离散数学是计算机专业的核心基础课程, 是学习数字电路、数据结构、操作系统、数据库、编译原理等课程的基础, 同时提供了培养学生的抽象思维能力和逻辑推理能力的重要途径。该课程如此重要, 但是学生学习的积极性不高是比较普遍的。怎样改革教学模式和教学方法, 从而提高离散数学的教学质量, 已经有众多的学者进行了大量的研究。笔者针对应用型本科院校学生特点, 对离散数学教材内容的表述以及体系安排, 谈几点看法, 以达到抛砖引玉, 与同行商榷的目的。

2 离散数学教材存在的问题及建议

教材是教与学的依据, 是保证教学质量的重要因素之一。教材内容的表述和安排应该方便学生预习和自主探究学习, 方便教师组织教学。教材作为教科书, 而非学术专著, 应该写得明明白白, 容易阅读。但是当前的许多离散数学教材没有做到这一点, 教材内容的表述与体系安排, 不适合学生自主学习。

2.1 教材内容组织结构存在的问题及建议

当前大多数离散数学教材包括以下内容:数理逻辑、集合论、代数结构、图论, 与学生已有的中学数学知识之间的跨度较大。相比较而言, 集合论的知识与中学数学衔接最近, 其它模块与中学数学之间的鸿沟更大, 特别是数理逻辑, 知识内容与知识的表述形式对学生来说都是全新的。大多数离散数学教材, 是按照数理逻辑、集合论、代数结构、图论的次序组织的。数理逻辑作为教材第一部分的弊端是非常大的, 大量的概念、定义、定理扑面而来, 形式化的表述方式、抽象的逻辑推理都是学生从来没有接触过的, 增加了学习难度。任何人做任何事都有如下的体会:成功会带给我们喜悦和成就感, 刺激我们更加努力;失败会带给我们很大的失落感, 甚至会丧失信心, 从而半途而废;那种屡战屡败的人还是少数。开篇遇到较大的阻力, 会打击学生学习该课程的积极性。以数理逻辑、集合论的次序安排内容的离散数学教材中, 经常出现大段的用数理逻辑知识形式化地表示集合论的公式和定理证明。这样做, 不仅人为地增大了教学内容的抽象程度, 而且冲淡了集合论的主题, 因为离散数学中集合论的重点是笛卡尔积、建立在笛卡尔积上的关系, 而不是传统的并、交、差等集合的基本运算。

应用型本科院校学生, 数学基础比较薄弱, 教学中深刻体会到学生欠缺的不仅仅是数学知识基础, 更重要的是数学素养。数学素养的缺失, 使得学生接受抽象程度高、逻辑性强的知识时很困难。建构主义教学观认为, 复杂的学习领域应针对学习者先前的经验和学习者的兴趣, 只有这样, 才能激发学习者的学习积极性, 学习才可能是主动的。数理逻辑、集合论、代数结构、图论这四部分基本上彼此独立, 那么可以考虑把集合论作为教材的第一部分, 把数理逻辑作为最后的内容。通过与中学数学的衔接, 学生在已有的知识基础和学习经验上建构新知识, 可以降低难度。教材应该拥有一定的开放性, 给教师留有一定的根据学生特点灵活处理的余地。如上所述, 用命题演算和逻辑演绎证明集合并、交、差等运算公式, 可以由教师在集合论的教学过程中介绍, 介绍的多少由教师根据学生特点自主掌握, 而不应该大量的出现在关系运算中, 否则有喧宾夺主之嫌, 也增加了学生阅读的负担和难度。

2.2 教材内容表述存在的问题及建议

大多数离散数学教材内容的呈现方式基本雷同:形式化的数学定义, 随后是验证性例子, 然后是定理 (大多数有证明) 或者规则, 接着是定理或者规则的应用。这种组织教材内容有以下两个主要弊端: (1) 离散数学内容抽象程度高, 逻辑性强, 这是该课程教学内容的本质特征。但是过分地追求数学的形式化表示, 人为地增大了内容的抽象程度, 极大地增加了教学难度。教师按照这种教材进行教学, 必须花大力气讲解定义、定理的含义, 进行大量的形式化的推导论证, 由于太抽象, 学生还不能够很好地理解和接受;对于满篇都是数学符号的形式化定义、定理及证明, 学生很难预习, 更不可能自主学习。 (2) 著名物理学家杨振宁曾经指出:中国学物理的方法是演绎法, 先有许多定理, 然后进行推演;美国对物理的了解是从现象出发, 倒过来的, 物理定理是从现象归纳出来的, 是归纳法。演绎法是对付考试用的办法, 归纳法是做学问的办法。这种评价也可以用于离散数学教材。先给出定义、定理, 就是给出了结果, 这样的教材编写体系, 违背了人类的认知规律, 不利于学生独立思考, 探究和发现问题, 主动地自我建构知识, 只是被动地接受知识, 其结果学生只能用所学知识去应付考试, 学校也只能造就出高分低能、缺乏创新意识的学生。

作为教科书, 离散数学教材应该由浅入深, 循序渐进, 方便学生自主学习, 特别是应用型本科院校的教材, 需要适当弱化形式化的推导证明和抽象表述。在保证科学性、准确性、严谨性的前提下尽可能的通俗地阐述知识, 尽可能多的从学生熟悉的日常生活、已有知识出发引入新知识, 在此基础之上给以严格的数学表示。例如, 命题逻辑中的合取运算, 举一个例子:让甲乙两人去抬一个笨重物体, 分析四种可能的情况:甲乙同去、甲去乙不去、乙去甲不去、甲乙都不去, 其结果是只有“甲乙同去”才能完成任务。在分析实例的基础上给出合取运算的数学定义和运算真值表, 学生自学就可以看懂, 并且不失科学性与严谨性。再看笛卡尔积的定义, 平面上点坐标、取部分点坐标坐标组成的集合, 分别是学生最熟悉的有序对和笛卡尔积的例子。离散数学教学内容中的许多概念、定义、定理和运算规则, 都可以类似处理, 先把深奥的内容通俗化、具体化, 然后上升到严格的数学表示这一抽象层面。笔者在教学过程中采用这种方法组织教学, 收到了较好的效果。

结束语

教材是教与学的依据, 教材改革是教学改革的重要组成部分, 广大教育工作者应该充分认识到这一点, 编写出适合学生自主建构知识的教材。编写应用型本科院校的离散数学教材, 需要同时考虑课程和学生特点, 既不失科学性和严谨性, 又通俗易懂, 为提高离散数学课程的教学质量提供必要的物质保证。

参考文献

[1]金旭亮.计算机教材:写给自己, 还是读者[J].计算机教育, 2006, 6.

[2]李其龙.从德国教科书看当代教学论思想[J].全球教育展望, 2001, 3.

[3]江雪松.论大学教材建设中的学本教材建构[J].高等工程教育研究[J].2003, 1.

离散数学应用论文 篇3

【关键词】离散数学 ； 密码学 ； 教学

【中图分类号】G64 【文献标识码】B 【文章编号】2095-3089（2015）7-0250-02

一、引言

离散数学是计算机专业的基础课，为计算机专业的后续课程提供专业的数学理论基础。该课程可以全方位培养学生的抽象思维能力和解决实际问题的能力，为学生学习其它专业课程建立数学的思想。

该课程包括数理逻辑、集合论、代数系统、图论四个大部分。每个部分与数据结构，数据库，人工智能，数字逻辑，编译原理等课程都密切相关。

本文我们将阐述离散数学中的代数系统理论部分与密码学的相关性，并且分析该理论在密码学领域的若干应用。

二、代数系统理论与密码学的相关性及在密码学的应用

离散数学中的代数系统理论包括代数系统的一些基本概念、半群与独异点、群、环与域、格与布尔代数。代数系统与密码学联系非常紧密，为密码学提供非常重要的数学基础。现将代数系统理论在密码学中的若干应用列举如下：

密码学中，凯撒密码是一种最简单且最广为人知的加密技术，是一种简单的基于替换原理的加密技术。凯撒密码将明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文，其中固定数目的偏移量为加解密密钥。例如当偏移量为3，字母A将被替换成D，B变成E，其它的字母按此规则类推。在代数系统理论中群是一种典型的代数系统，具有封闭性、可结合性、含单位元以及每个元素都有逆元等性质。从本质上来说凯撒密码就是一个特殊的群，是建立在26个字母之上，字母与密钥进行运算的剩余模群。通过对于群理论的学习可以帮助学生更好的理解凯撒密码的本质。

在密码学中有一个重要的公钥加密算法的RSA，该算法是目前最安全的公钥加密算法，可以抵抗目前已知的绝大多数密码攻击。数论中的费马小定理为RSA提供数学上的安全性保证。通过对于费马小定理的原理和正确性的理解可以更好的理解RSA算法的安全性，在实际中更好地使用RSA算法。

在密码学中的椭圆曲线密码是基于椭圆曲线的一种公钥密码算法，该密码安全性基于椭圆曲线离散对数的困难性上，是一个有限域上椭圆曲线的阿贝尔群。对于在代数系统理论中群和域的概念以及性质进行认真学习和理解可以用于椭圆曲线密码的学习。

三、离散数学在计算机其他学科中的应用

离散数学在计算机研究中的作用越来越大，计算机科学中普遍采用离散数学中的一些基本概念、基本思想、基本方法，使得计算机科学越趋完善与成熟。离散数学在计算机科学和技术中有着广泛应用，除了在上述提到的领域中发挥了重要作用外，在其他领域也有着重要的应用，如离散数学中的数理逻辑部分在计算机硬件设计中的应用尤为突出，数字逻辑作为计算机科学的一个重要理论，在很大程度上起源于离散数学的数理逻辑中的命题与逻辑演算。利用命题中各关联词的运算规律把由高低电平表示的各信号之间的运算与二进制数之间的运算联系起来，使得我们可以用数学的方法来解决电路设计问题，使得整个设计过程变得更加直观，更加系统化。集合论在计算机科学中也有广泛的应用，它为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了进行抽象和描述的一些重要方法，在软件工程和数据库中也会用到。代数结构是关于运算或计算规则的学问，在计算机科学中，代数方法被广泛应用于许多分支学科，如可计算性与计算复杂性、形式语言与自动机、密码学、网络与通信理论、程序理论和形式语义学等，格与布尔代数理论成为电子计算机硬件设计和通讯系统设计中的重要工具，图论对开关理论与逻辑设计、计算机制图、操作系统、程序设计语言的编译系统以及信息的组织与检索起重要作用，其平面图、树的研究对集成电路的布线、网络线路的铺设、网絡信息流量的分析等的实用价值显而易见。

四、结束语

通过上面的分析，我们可以发现离散数学中的代数系统理论在密码学领域的作用非常重要，离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化表述能力的动力源，离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到分布式系统，无不与离散数学密切相关。在现代计算机科学中，如果不了解离散数学的基本内容，则在计算机科学中就寸步难行了。

参考文献

[1]任勋益.离散数学与计算机安全结合改进教学[J].软件导刊，2009（12）

[2]刘宏月，张行进等.面向信息安全学科的离散数学教学探究[J].计算机教育，2012（15）：23-26

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

[4]丁宝康主编.数据库原理[M].经济科学出版社，2000

[5]冯登国，裴定一编著.密码学导引[M].科学出版社，1999

[6]魏献祝主编.高等代数[M].华东师范大学出版社，1997

[7]华东师范大学数学系编.概率论与数理统计教程[M].高等教育出版社，1983

离散数学应用论文 篇4

（2011年3月18日）

实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅 依托单位： 福州大学

实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。实验室位于福州大学铜盘校区。2007年11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到 “环境优美、设备一流”。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室3000平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。

一、实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。

二、在本，实验室主任范更华教授获全国优秀科技工作者。实验室在研科研项目国家973计划课题1项，国家自然科学基金7项，其中重点项目1项，面上项目6项，新增国家973计划课题1项，为

1.大规模集成电路物理设计中关键应用数学理论和方法（2011CB808003），范更华 新增国家自然科学基金3项，其中面上项目2项，青年项目1项，分别是：

1.超大规模集成电路多目标划分的算法研究（61070020），朱文兴，国家基金面上项目。

2.近景摄影测量中的自动图像分割技术（11071270），王美清，国家基金面上项目。

3.几类图染色问题的研究（11001055），侯建锋，国家基金青年项目。

实验室在2010年8月顺利完成了国家重点基础研究发展计划（973计划）课题“大规模集成电路设计中的图论与代数方法（2006CB805904）”。课题实施期间，课题组共发表研究论文133篇，其中被SCI收录104篇；由于出色完成了该课题，我们将继续承担新一轮的973课题：大规模集成电路物理设计中关键应用数学理论和方法（2011年1月至2015年12月）。

三、实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。本培养博士研究生2名，硕士研究生21名。

四、科研成果

实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本课题组研究成员在国内外重要专业刊物上发表SCI收录论文27篇，EI收录论文6篇，具体研究成果如下：

（1）图论与组合研究工作 关于连通图支撑树的计数问题，给出了连通图支撑树个数的紧的上界，并且考虑的连通度为k的图的支撑树的个数，同时给出了连通图支撑树的个数和图色数之间的关系，其结果发表在《Applied Mathematics Letters》上。

一个图的Laplacian谱半径是指该图Laplacian矩阵的最大特征值，对于图n个顶点，最大度为△，直径为D的非正则图，Shi给出了该图的Laplacian谱半径的上界，我们改进了该上界，并且证明了该上界给出了在某些情况是紧的，同时，给出了不含三角形图的Laplacian谱半径的上界。对于连通二部图，给出了Laplacian谱半径紧的上界和下界，从而改进了Shi的结果。

在图染色领域，考虑了图的列表染色问题，给出了考虑图列表染色的新的思路，并且用该思路证明了某些形式的完全k部图是(2, 2)-total weight choosable，并证明了除了一条边外的所有完全二部图都是(1, 2)-total weight choosable。研究了稀疏图和平面图的列表全染色问题，证明了如果平面图的最大度不超过8，则其列表全色数不超过11；如果平面图最大度至少是8，且不含5-圈，则其列表全色数等于最大度加一；如果图的最大度是4，并且最大平均度不超过3，则其列表全色数是5，该项成果发表在《Information Processing Letters》上。考虑了有向图博弈染色，给出了有向图博弈色数以及弱的博弈色数的定义，证明每个定向平面图的博弈色数不超过9，每个定向外平面图的博弈色数不超过4，同时研究了有向图强博弈染色，证明了每个定向平面图的强博弈色数不超过16。考虑的外平面图的无圈边染色问题，完全确定了外平面图无圈边色数的上界，其结果发表在《Journal of Graph Theory》上。在化学图论方面，一个图的能量是指该图所有特征值绝对值的和，一个图的能量小于图的顶点数，称该图是hypoenergetic，我们研究了图的能量，构造了顶点数为4n+2的树T，使得T是hypoenergetic，从而验证了Gutman等人在2008年提出的猜想，该文发表在《Applied Mathematics Letters》上。同时考虑的图的能量和Estrada指标之间的关系，给出了图Estrada指标紧的上界。（2）VLSI中的图论与优化算法研究工作

为了开展大规模集成电路设计领域的研究工作，实验室于2010年建立了一个150m2的大规模集成电路设计EDA实验室，拥有16个研究工作位，装备国产熊猫EDA系统软件16台套，对所有实验室研究成员和研究生开放使用。

布局是大规模集成电路电路设计重要环节，决定了超大规模集成电路芯片的性能，尺寸，产量和可靠性，我们给出了基于粒子群优化算法新的智能决策，利用该决策可以超大规模集成电路较快的获得一个可行的电路物理布局。同时在遗传算法的变异和交叉的原则中引入了粒子群优化算法，可以使得该算法脱离局部最优和实现更好的多样性。实验通过采用MCNC和GSRC基准测试表明，该算法是有效的。同时该算法可以避免局部最小，并有很好的收敛性。实验结果表明所提出的方法可以大大帮助集成电路设计中的布局决策，其结果发表在《Soft Comput.》上。

从计算的角度来看，超大规模集成电路布局规划是一个NP-困难问题。我们给出了非分层和模块VLSI布图规划问题的一个混合演化算法（HGA），该算法使用一个有效的遗传搜索方法来探索搜索空间和一种有效的局部搜索方法，利用信息在搜索区域。MCNC基准的实验结果表明该算法是有效的。同时，借助于进化算法和模拟退火算法的概念，给出了另外一种混合演化算法，实验表明该算法也是有效的。

（3）优化理论与算法

我们提出了一个高效求解三维装箱问题（Three Dimensional Container Loading Problem 3D-CLP）的混合模拟退火算法；研究了极大可满足性问题的局部搜索算法，提出了用单纯形法产生“初始概率”(每个变量取1的概率)，用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束；研究了箱约束非线性整数规划问题，提出了该问题的离散动态凸化算法，同时还证明了算法的收敛性；对非线性约束连续全局优化问题，我们构造一个结合罚函数的辅助函数，构造了解非线性约束连续全局优化的一个动态凸化算法，该算法避免了传统罚函数法中罚参数选取困难的问题。

五、学术交流

为推动福建省数学教育和研究活动开展，在范更华教授的大力倡导下，协同福建省数学会，于2010年10月16日至17日召开福建省首届数学大会，1100多名来自全省各地高校和中学的数学教师参会。为了使基层农村学校数学教师有机会参加会议，在省政府、省教育厅等部门的大力支持下，会议为300名工作在乡镇学校的教师提供了交通、住宿等经费支持。会议期间，“院士与中学教师互动座谈会”和“专家讲座”等专项活动交流和讨论热烈，这种面对面的交流让来自中小学的数学教师受益匪浅、耳目一新，为广大基层学校特别是农村学校教师提供了良好的学习机会，有效地调动了全省中学教师参与数学研究的积极性，对提升福建省数学教育水平起到了积极的推动作用。

2010年5月，实验室协同中国运筹学会，召开中国运筹学会第八届三次常务理事会。

离散数学一单元 篇5

一单元测试题

1.将下列命题翻译成符号逻辑形式

（1）银行利率一降低，股价随之上扬。

（2）尽管银行利率降低，股价却没有上升。

（3）占据空间的、有质量而且不断变化的对象称为物质

（4）如果一个整数能背6整出，那么它就能被2或3整除。如果一个整数能被3整

除，那么它的各位数字之和也能被3整除。

2.判断下面各语句是否是命题，如果是命题，说出它的真值。

（1）可导的实函数都是连续函数。

（2）凡是都有例外。

（3）白天比夜晚时间长

（4）两个三角形全等当且仅当它们的对应角相等。

3.简述命题的定义。

4.简述原子命题的定义。

5.下列公式中，（）不是永真式。（单选，写清楚每个属于什么公式）

A.(P∧Q)→QB.P→(P∨Q)

C．（P→Q）↔（~Q→~P）D.(~P∨Q)∧(~(~P∨~Q))

5.下列语句，是命题的有（）（多选）

1）美国的首都是纽约。2）你喜欢日本吗？3）我们一定要解放台湾！

4）所有实数都是整数。3）如果3>2，那么有人不死。

6.构造公式的真值表，判断哪些是永真式，矛盾式，和可满足式

（1）(P→(Q→R))↔((P∧Q)→R)

（2）(P∧(P∧Q))↔~P

（3）~（P∨Q）→R

7.如果P∨QQ∨R，能否判断PR？如果P∧QR∧Q,能否判断PR？如果~P~R能否判断PR。

8．判断下面等式是否是等价式：P→（Q∨R）（P→Q）∨（P→R）

9．求下列两式的对偶式

（1）（P∧~Q）∨（R∧T）∨F

（2）~（P∨~（Q∨R））∧（R∧~Q）

10．分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式。

（1）P→（R∧（Q→P））

（2）（P→（Q∧R））∧（~P→（~Q∧~R））

11．证明（P→Q）∧（Q→R）P→R

12．证明R→S是{P→（Q→S），~R∨P，Q}的逻辑结果（使用直接法，CP规则法，和反证法）

13．求公式（P→（R∨P））∧（Q ↔P）的主合取范式和主析取范式。

离散数学 篇6

第一部分 集合论

第一章集合的基本概念和运算

1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是[ B ]

A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2}  A。

1-2 A,B,C 为任意集合，则他们的共同子集是[ D ]

A．C；B．A；C．B；D．Ø。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？

（1）N  Q，Q ∈S，则 N  S［不成立］

（2）-1 ∈Z，Z ∈S，则-1 ∈S［不成立］

1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø，C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F = { 4，Ø，3，3}，试问哪两个集合之间可用等号表示 ？

答：A = E；B = C；D = F

1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

答：（1）A = { 0，1，2，3 }；

（2）A = { 1，2，3，4，……} = Z+；

第二章二元关系

2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：

R = {〈x，y〉x，y ∈X 且 x≤ y }

求：(1)domR =?;(2)ranR =?;(3)R 的性质。

答：R = {<2，3>，<1,2>，<1,3>}；

DomR={R中所有有序对的x}={2,1,1}={2,1};

RanR={R中所有有序对的y}={3,2,3}={3,2}；

R 的性质:反自反,反对称,传递性质.2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即

R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，试求：

（1）R 的列元表达式；（2）给出 dom（R。R）。

答：根据方程式有：y=4-x/3，x 只能取 3，6,9。

（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；

至于(2),望大家认真完成合成运算 R。R={<3,3>}.然后,给出 R。R 的定义域,即

（2）dom（R。R）= {3}。

2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→B 指出他的性质，即

是否单射、满射和双射，并说明为什么。

（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）A = B = R，f=x。

（4）A = B = N，f=x2。

（5）A = B = N，f = x + 1。

答：（1）是 A 到 B 的函数，是满射而不是单射；

（2）是双射；

（3）是双射；

（4）是单射，而不是满射；

（5）是单射而不是满射。

2-4 设 A ={1，2，3，4}，A 上的二元关系

R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1)=[C]

A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。

2-5 设 A ={1，2，3}，则商集A/IA =[D]

A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。

2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝[C]

A．x+1；B．x-1；C．x；D．x2。

第三章 结构代数(群论初步)

3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 *是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元运算。定义如下：对于所有 ai，aj ∈S2，都有 ai。aj = ai。

（3）S3 = {0，1}，二元运算 * 是普通乘法。

答：（1）二元运算*在S1上不封闭．所以，＂S1，*＂不能构成代数系统。

（2）由二元运算的定义不难知道。在 S2 内是封闭的，所以，〈S2。〉构成代数

系统；然后看该代数系统的类型：该代数系统只是半群。

（3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异

点；而 0 为零元；结论：仅为独异点，而不是群。

3-2 在自然数集合上，下列那种运算是可结合的［A］

A．x*y = max(x,y)；B．x*y = 2x+y ；

C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 设 Z 为整数集合，在 Z 上定义二元运算。，对于所有 x，y ∈Z都有

x。y=x + y，试问〈Z。〉能否构成群，为什麽 ？

答：由题已知，集合Z满足封闭性；二元运算满足结合律，依此集合Z为半群；有幺元为 －5，为独异点.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e。x= e + x，一个方程来自该特殊元素的定义的性质,即e。x = x.由此而来的两个方程联立结果就有: e+x=x 成立.削去 x,e=0 的结果不是就有了吗!；每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理；结论是：代数系统〈 Z。〉构成群。

第二部分图论方法

第四章 图

4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？ 答：因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。这样一来，一个无向简单图 G 的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，Ｇ的补图中应有 10-4＝6 个奇数度顶点。

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点.[是]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为[2]

第五章树

5-1握手定理的应用（指无向树）

（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有(有1个4度顶点)个？

（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有(9个1度顶点)片？

5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x=

答：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = Σi（i—2）i + 2，（i = 2，3，……k）。

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1）T 的权 W（T）？（2）树高几层 ？

答：用 Huffman 算法，以 1，2，3，5，7，8 为权，最优 2 元树 T ；然后，计算并回答所求问题：（1）T 的权 W（T）= 61；（2）树高几层：4 层树高。

5-4以下给出的符号串集合中，那些是前缀码？将结果填入[]内.B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [非]

5-6(是非判断题)二元正则树有奇数个顶点。[是]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.求传输他们的最佳前缀码。

1、最优二元树 T；2.每个字母的码字；

答：每个字母出现频率分别为：G、D、B、E、Y：14%，O：28%；(也可以不归一,某符号

出现次数即为权，如右下图).。100（近似）7.。563..4。282..2..2。..1..14141414111

1所以，得到编码如下：G（000），D（001），B（100），E（101），Y（01），O（11）。

第三部分逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

（1）2月 17 号新学期开始。[真命题]

（2）离散数学很重要。[真命题]

（3）离散数学难学吗 ？[真命题]

（4）C 语言具有高级语言的简洁性和汇编语言的灵活性。[复合命题]

（5）x + 5 大于 2。[真命题]

（6）今天没有下雨，也没有太阳，是阴天。[复合命题]

6-2 将下列命题符号化.（1）2 是偶素数。

（2）小李不是不聪明，而是不好学。

（3）明天考试英语或考数学。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

答：（1）符号化为： p ∧ q。

（2）符号化为：p ∧ ﹃q。

（3）符号化为：p ∨ q。

（4）符号化为：（﹃p ∧ q）∨（p ∧ ﹃q）。

6-3分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；

（2）Σ（0，1，2，3）；

（3）Σ（1，3）。

以下两题(6-4;6-5)为选择题,将正确者填入[]内.6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B]

A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为［B］

A． p→q；B．q→p；C．p∧q；D．﹁q→p

6-6证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。答：将公式分成前提及结论。

前提：（p→﹃q），p；

结论：﹃q；

证明：（1）（p→﹃q）前提引入

（2）p前提引入

（3）（p→﹃q）∧p（1）（2）假言推理

（4）﹃q

要证明的结论与证明结果一致，所以推理正确。

第七章谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化

（1）这台机器不能用。

（2）如果 2 ＞ 3，则 2 ＞ 5。

答：（1）﹃F（a）。

（2）L（a，b）→ H（a，z）。

7-2 填空补缺题：设域为整数集合Ｚ，命题xy彐z（x-y=z）的真值为（0）

7-3在谓词逻辑中将下列命题符号化

（1）有的马比所有的牛跑得慢。

（2）人固有一死。

答：（1）符号化为：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。

（2）与（1）相仿，要注意量词、联结词间的搭配：

x（F（x）→y（G（y）→ H（x，y）））。

《附录》习题符号集

Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。

离散数学应用论文 篇7

离散数学是计算机专业课中重要的先修课程,离散数学的水平也是衡量计算机专业人才素质的重要标准之一。离散数学基础很好的人,学会了某种计算机语言后,可以很容易的过度到其他计算机语言,也能够深入理解某些算法,编写出高效、规范、时间与空间复杂度都较优的算法。但是离散数学也是教师难教,学生难理解的一门课程。这是因为离散数学中包含大量的隐性知识,因此,离散数学课程中隐性知识的获取,是离散数学教学中的关键问题。

英国物理化学家和哲学家波兰尼1958年在著作《个人认识》中最早提出隐性知识这一概念。他认为隐性知识是一种无形的不确定的知识,虽然经常使用但不能通过语言文字进行清晰表达,是只可意会不可言传,且植根在主体的经验、判断、联想、创意和潜意识的心智模式内的知识。他指出隐性知识包括认识和技术两个方面。认识方面的隐性知识是由动物的非言述的智力发展而来一种人的认识能力,无法用语言穷尽。而技术方面的隐形知识是在隐性知识动态结构中人们对辅助项的认识,也是用语言无法表达的[1]。隐性知识的转化研究始于对知识的隐性知识和显性知识分类[2]。

本文通过教学实践,认为离散数学教学中可以使用KM教学法,对书本中隐性知识挖掘以及合理转化为能被学生掌握、利用的有用知识。本文将KM教学法引入到离散数学隐性知识转化中,分析其在隐性知识转化中的技术优势,从创建学习环境、引导学生行为等方面详细地论证了KM教学法在离散数学隐性知识转化中的重要作用,以一个新视角探求解决离散数学隐性知识转化中问题的方法。

1 KM教学法原理

KM教学是将知识的逻辑结构和思维导图相结合的教学方法。其中K是指“知识逻辑结构”(Knowledge Logic Structure),M是指“思维导图”(Mind Map)。知识逻辑结构表达了课程知识以及知识要点之间的逻辑关系,它是所讲授课程的知识体系的表示。知识是由一系列的概念(Concept)组成,概念是组织起来的经验,是对事实、事件、特性、感知信息等进行分类、推理和抽象出来的知识,它使我们能有效地认知、交流、发展我们对世界的认识。概念按照人们对其接受程度由高到低可分为公理、定理、论点和观念[4]。相关概念之间按照其内在联系可组成线形、环形、集中式、层次式以及网状知识逻辑结构[5]。

KM教学法的核心是根据知识的抽象层次以及各知识子系统之间的关系,构造出具备层次结构的知识系统。在这个知识系统的高层,知识的表现形式是知识逻辑结构图(KLSG),它给出所学课程的知识总体架构,并且表征了各知识子系统间的内在联系以及子系统内部的概念、命题、推演、证明、问题求解、分类及聚类等内在联系;在这个知识系统的低层,思维导图融入到概念、证明、问题求解等环节中,表征其具体、细致、动态及发展的逻辑构成与逻辑推理特征,揭示概念形成规律与问题求解思路,是一个逐步求精、逐步细化的过程。KM教学法的精髓就在于在教学过程中引导学生构造出这种综合的、多层次的知识系统。[6]

2 离散数学中隐性知识的识别

E·B·Grant认为以下性质的知识是隐性知识:(1)如果引发行为的知识深藏于个人认知中,很难找出掌握某一技术所需的全部知识;(2)如果知识产生过程非常快速,不易掌握到;(3)如果知识提供完全的认知须仰赖传播及辅助性线索;(4)如果技术很复杂且易在语言中失传,或无法描述其实体特色。根据这四种标准,对于离散数学中群论部分,以拉格朗日定理证明题为例,完全符合上述特点。题目如下:证明6阶群中必含有3阶元。首先需要知道元素的个数只能是1阶、2阶、3阶和6阶,这个知识隐藏在群的阶、元素的阶和有限循环群的概念和拉格朗日定理推论中,并且在掌握上述概念的基础上需要做一定量的练习才能理解,符合特点(1)和(2);其次这个理论的整体证明方式如果没有见过,基本上无法想到,符合特点(3);最后证明过程中还使用到了拉格朗日定理及推论和以及交换群的证明,从逻辑推理角度看同时使用了演绎法、反证法和排除法、分治法,证明十分复杂,符合特点(4)。类似这样的证明,在离散数学全书中,经常能够看到。因此,在离散数学中存在大量的隐性知识,导致了教学的困难。

3 离散数学中基于实例的KM教学法

如图1所示,可以用KM教学法得到的逻辑思维导图,进行隐性知识的教学。

在教学实施过程中,先讲证明步骤,使得学生对所要学的知识的全貌一目了然,有一个宏观的认识。然后引导学生自行寻找证明的依据,即完善学习知识框架,使学生能够巩固和接受知识点。最后介绍证明的逻辑结构。通过逐步在框架中填充知识的方法,学生很容易理清知识点,并且引导学生自行思维,总结经验,把抽象的隐性知识变成显性知识并加以记忆。这种教学方法,是一种微观学习的过程,适合于对有一定难度的综合性知识点的教学中使用。

当然,KM教学法不仅可以应用在离散数学的隐性知识点中,对于显性知识点,也可以通过逻辑思维导图进行很好的描述。对此北京科技大学的杨炳儒教授明确提出离散数学教学的过程的“薄—厚—薄”的方法,先对教师经逻辑加工得到的讲授内容的朴素、形象初级的概括性描述,然后将基本架构逐步进入各组成分的微观结构逐步蚕食的“厚”的体现,要弄清各相关的细节,最后是使学生掌握螺旋式上升的、带着丰富的知识细节的“本质框架”。[7]本文提出的使用KM教学法进行隐性知识转化,属于第二、三阶段的“由厚到薄”的过程,学习过程中属于第二阶段“厚”的细节学习,等到学生能够掌握相应的知识点并举一反三,就达到了第三阶段“薄”的阶段了。

4 结束语

隐性知识是离散数学教学中的难点,也是离散数学教学中的重点内容。学习并掌握离散数学知识,可以使学生更加深入的了解计算机的运算本质、概念定义和推理方式,从而培养出更多更高层次的软件人员。本文根据KM教学法按照知识延伸和发展的内在逻辑性,从细节出发,以讲授综合性问题中的隐藏知识为例,通过实际介绍分析问题、解决问题的逻辑结构、知识框架和证明方法,对思维活动加以诱导,采用“框架填充式”和“知识诱导式”结合的方法,进行隐性知识的组织和教学。通过实践证明,学生的学习兴趣大大增加,对知识点的掌握也更加牢固,是一种行之有效的的教学方法。

摘要：离散数学是计算机专业课中重要的先修课程,包含许多隐性知识。针对离散数学课程中隐性知识获取难的问题,本文提出采用KM教学法,将隐性知识加以逻辑结构化,转化为直观的逻辑思维导图的方法进行教学,从而更好的组织教学过程,提高教学质量。

关键词：KM,离散数学,隐性知识

参考文献

[1](英)波兰尼,许泽明译.个人知识[M].贵阳:贵州人民出版社,2000:38-47.

[2]方华等.论隐性知识[J].沈阳师范大学学报(社会科学版),2004,28(2):27-32.

[3]Yin Y Vanides,J Ruiz-Prinmo,et al.Comparison of Two Concept-mapping Techniques:Implications for Scoring.

[4]Interpretation,and Use[J].Journal of Research in Science Teaching,2005,42(2):166-184.

[5]鞠小林,陈继红.基于KM教学法的软件工程教学研究[J].计算机教育,2010(10):107-110.

浅谈如何上好《离散数学》课 篇8

【关键词】离散数学 学生自主性 教学方法

【中图分类号】G642.0【文献标识码】A【文章编号】1673-8209(2010)05-0-01

离散数学课程是计算机科学与技术系各专业的一门重要的基础课程,也是计算机科学基础理论的核心课程。本课程介绍计算机科学与技术系各专业所需要的离散数学基础知识,为进一步学习计算机科学的基本理论和方法、学好专业课奠定基础,内容包括数理逻辑、集合论、代数结构与布尔代数、图论和在计算机中的应用共五部分。该课程是培养学生抽象思维能力、逻辑推理能力、缜密概括能力以及分析和解决实际问题能力的主干课程,对学习其他诸多课程,具有重要的指导作用。离散数学教学内容具有知识点多、散、抽象等特点,加之许多学生不能认识到该课程的重要性,缺乏学习兴趣和学习主动性,不仅忽视该课程的学习,甚至害怕这门课程。因此,创新教学方法,提高学生自主学习的积极性,对提高学生的能力、提升教学质量和水平,具有重要的意义。作者在离散数学教学和实践中,积累了若干经验和做法,仅供大家参考。

1 引导学生提高对离散数学课程应用性的认识,激发学生学习的兴趣和爱好,增强汲取知识的自主性

离散数学课程是一门基础性课程,由于许多学生并不能认识到离散数学课程对后续诸多主干课程的指导性作用,看不到该课程的实际应用价值,加上该课程知识比较难而且抽象,很多学生对该课程缺乏学习兴趣和学习主动性,对该门课程只是应付,甚至根本不愿意去学习。

学习离散数学课程对学生今后的学习和工作,具有重要的作用,例如,对数据结构、操作系统、数据库、编译原理、软件工程等后续课程学习的指导作用;培养学生的抽象思维能力和缜密的逻辑推理能力,并为学生今后处理离散信息,提高专业理论水平,从事计算机的实际工作提供必备的数学工具;通过学习,可以掌握数理逻辑,集合论,代数结构和图论的基本概念和原理,并会运用离散数学的方法,分析和解决计算机理论和应用中的一些问题等。学习主动性是学生的力量之源,因此,引导学生充分认识学习离散数学课程的作用,能够激发学生学习的爱好和热情,提升学生学习的积极性和主动性,从而使学生学有成效。

2 认真备课,合理准备教学内容和安排教学环节,优化教学方式方法

备好课是教学取得预期效果的前提和基础,针对学生学习具体情况,合理准备教学内容和安排教学环节,使用恰当的教学方法,在教学中可以起到事半功倍的效果。

(1)合理地准备教学内容。根据课程教学大纲和离散数学课程定理定义比较多、知识比较抽象的特点以及学生的实际情况,准备深度和广度适合学生特点的教学内容。

(2)合理地讲解课程内容,重难点突出讲解,注意轻重缓急。对于离散数学中比较重要、比较抽象的概念和定理,如逻辑的推理理论、关系的性质、群、图等,认真分析,用多种方式和方法深入讲解,可以使用解析法、图示法、矩阵法举实例等多种方法讲解,例如对关系的对称性质的讲解中,可以使用矩阵法进行讲解,判断一个关系是否对称,只需观察它的关系矩阵是否对称即可,再如对关系的传递性质的讲解中,可以使用关系图进行讲解,判断一个关系是否传递,只需观察在关系图中,当x到y有一条路径时,x与y是否有关系即可。对于比较容易理解和掌握的内容,可以一笔带过。这样,学生对所学内容就会有重点地学习,主次分明,学生不仅可以对所学内容掌握透彻,更能熟练把握离散数学中分析问题和解决问题的思路、方式和方法。

(3)启发式教学和教师讲授相结合。很多人认为,大学教学课时紧,内容多,关键靠学生自主学习,所以,大学教学以教师的讲授为主,不需要通过提问、讨论等方式进行教学互动。笔者认为这是不全面的。如果教师不顾学生的理解情况,只顾在讲台上讲授知识,课堂氛围会很沉闷,很多同学不能专注于该门课程的学习,经常走神,教学很难达到预期的效果。因此,有针对性地提问和展开讨论,不仅能够培养学生的思考能力,更能调动学生学习的兴趣和积极性,从而使教学达到最佳效果。

然而,由于离散数学课程在教学难度、课堂教学时间等方面的原因,很多学校都出现师生、学生之间的交流较少,致使学生对该门课程缺乏兴趣,教学效果不佳。所以,教师有必要针对课程中的主要问题或疑难问题适时地提问或者让学生展开讨论,鼓励他们进行独立思考,各抒己见,引导他们逐步深入地对问题进行实质性地分析,必要时,教师对其进行引导,及时总结,使教学达到预期效果。

3 合理布置作业,认真批改作业,有针对性地安排习题课和课后答疑

为了强化学生能力的训练,培养学生的抽象思维能力、逻辑推理能力、实际问题的解决能力等,在保证作业数量的同时,更要提高布置作业的质量,增加典型简答题、讨论题、推理题、实际应用题等习题在作业中的分量,使学生在掌握各种基本知识和基本技能的同时,提高自身的综合能力。当然,布置作业是一回事,学生能否认真完成作业,是预期目标能否实现的关键所在,认真检查和批改作业,是督促学生学习的主要途径,也是教师了解学生理解和掌握所学课程情况的主渠道。必要时,教师可以批改一部分作业,其他作业让同学们之间互相检查和批改,不仅可以督促学生学习,更能让学生在批改其他同学作业时逐步认识到自身的缺陷和不足,以备今后更有针对性地学习。

教师在作业检查和批改过程中发现的主要问题和疑难以及学生提出的有代表性的问题,有必要安排习题课进行讲解,帮助学生对解决疑难,加深对所知识的理解。对于学生比较争论的问题,可以展开讨论,鼓励学生大胆发言,培养学生探索未知的精神和创造性解决实际问题的能力。

因此,上好离散数学课,关键是根据学生具体实际,有针对性地安排教学内容,合理使用教学方式方法,最大限度地激发学生的学习兴趣,充分发挥教师的主导作用和学生的主体作用,达到教与学和谐。

参考文献

[1] 屈婉玲,耿素云,张立昂.离散数学[M].北京:高等教育出版社.2008.

[2] 黄巍,金国祥.”离散数学”课程教学改革的探讨[J].中国电力教育,2009(8):82-83.

[3] 周小燕,胡丰华.对提高离散数学教学质量的探讨[J].浙江科技学院学报,2007,19(2):156-158.

[4] 龙浩,张佳佳.怎样教好《离散数学》课[J].贵阳学院学报,2007,2(1):53-57.