离散数学实验指导书(2011-5-16)

《离散数学实验指导书(2011-5-16)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学实验指导书姜楠焉德军李笑牛（校内自编教材）大连民族学院计算机科学与工程学院2011年3月292929前言通常人们对离散数学教学的认识就是概念、定理、公式和解题。但是，离散数学不仅仅是这些，还有实验。在理论教学过程中，学生的活动只是“智力活动”，或更为直接地说是解题活动，教师在上面讲离散数学，而学生则每天在课堂上听课并在纸上做题目。这样，对多数学生而言，离散数学的发现探索活动没有能够真正开展起来。　　离散数学实验教学，通常由教师提出问题，让学生在计算机上做实验，利用小组合作学习或者组织全班讨论，开展研究性学习活动；实验过程中，依靠计算机，让学生主动参与发展、探究、解

2、决问题，从中获得离散数学研究、解决实际问题的过程体验、情感体验，产生成就感，进而开发学生的创新潜能，因而对离散数学实验课程教学进行研究具有重要意义。　　利用计算机进行离散数学实验教学，不仅是开展离散数学研究性学习的一种有效方式，而且也为数据结构及程序设计课程教学的开展提升了层次。知识经济时代对创新人才的需求与离散数学教育中忽视学生创造性能力培养的矛盾日益凸显。在教学中倡导研究性学习，开展离散数学实验课程教学的研究与探索，与当前社会对离散数学教学的需求是一致的。目前国内外很少有人对离散数学实验课程教学进行研究，尤其是国内进行这方面研究的人员更少，人们更重视离散数学理论课程教

3、学的研究，忽视了离散数学实验课程对理论课程教学的辅助与促进作用，也忽视了离散数学实验课程与数据结构等课程的有机联系。因而我准备进行离散数学实验课程教学的研究与探索，以便更好的做好离散数学课程的教学改革工作。本课程主要包括四个部分：集合与关系、图论、代数系统、数理逻辑。要求学生了解算法，理解运用C或C++语言把书中的部分内容的算法编写出能在计算机上运行的程序的思想，掌握实现离散数学部分算法程序设计的基本编程技术。29目录前言1第一章集合3实验一集合的运算3实验二求集合的笛卡儿乘积6第二章关系7实验三判断关系R的性质7实验四判断关系R是否为等价关系10实验五求等价类11实验六

4、由两个已知关系通过合成构造新的关系12实验七关系的闭包运算13实验八求关系个数的运算14实验九求自反关系和对称关系的运算15实验十求集合A上所有等价关系和偏序关系16二、求集合A上的所有偏序关系17实验十一求满射函数18第三章图论19实验十二求可达矩阵的Warshall算法19实验十三最小生成树的Kruskal算法20实验十四判别图的连通性21实验十五求无向图中顶点的度数23实验十六求有向图中顶点的度数24第四章代数系统25实验十七判断是否为代数系统的算法25实验十八判断是否为群的算法26第五章数理逻辑28实验十九构造合式公式的真值表2829第一章集合实验一集合的运算一、

5、求集合的并集1、实验类型：操作性2、实验目的通过编程实现求给定集合A和B的并集C（C=A∪B）的运算。3、实验内容已知所给集合A和B，求A与B的并集C（C=A∪B）。4、实验原理因为并集的定义为：C={x

6、x∈A∨x∈B}，所以，只要将集合A与B合在一起就得到了并集C。但是，在一个集合中，同样的元素没必要出现两次或两次以上，所以，在将集合A送入并集C后，应将集合B中与A中相同的元素删除，再将集合B送入并集C之中。5、实验仪器设备或软件环境及工具运行Windows或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。

7、6、实验要求复习集合运算中交集的定义，实验由一人一组完成。所编程序能够通过编译，并能够实现求两个给定集合的交集。7、实验步骤及注意事项（1）集合B的元素个数送M，集合A的元素个数送N。（2）AC。（3）1i。（4）若i>M,则结束。（5）否则，对于j=1，2，…….，n，判断：bi=aj，若相等，则转（7）。（6）否则，biC。（7）i+1i，转（4）。8、实验报告要求（1）写出实验过程中遇到的问题及其解决过程。（2）写出类c的算法并编写一个程序求给定集合A和B的并集。（3）写出实验结束时的程序清单及运行结果及实验总结。29二、求集合的交集1、实验类型：操作性2、实验目的

8、通过编程实现求给定集合A和B的交集C（C=A∩B）的运算。3、实验内容已知所给集合A和B，求A与B的交集C（C=A∩B）4、实验原理根据交集的定义：C={x

9、x∈A∧x∈B}，我们将集合A的各个元素与集合B的元素进行比较，若在集合B中存在某个元素并和集合A中一元素相等，则将该元素送入交集C之中。5、实验仪器设备或软件环境及工具运行Windows或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。6、实验要求复习集合运算中并集的定义，实验由一人一组完成。所编程序能够通过