3《离散数学课程实验教学大纲05(网络、软件、计算机).doc

《离散数学》课程实验教学大纲 （Discrete Mathematics） 一、基本信息 课程编号：E1132106 课程类别：学科基础课必修课 适用层次：本科 适用专业：网络工程、软件工程、计算机科学与技术 开课学期：3 学 分： 学 时：10 考核方式：考查 二、教学目的 离散数学实验教学的目标是加深学生对理论课程的理解，掌握利用算法如何编程，并把所编程序在计算机上实现。 三. 基本要求 本课程主要包括四个部分：数理逻辑、集合与关系、代数系统、图论。要求学生了解算法，理解运用C或C++语言把书中的部分内容的算法编写出能在计算机上运行的程序的思想，掌握实现离散数学部分算法程序设计的基本编程技术。 四、教学内容 实验一 要求判断关系的性质（4学时,设计性实验,必做） 教学内容：对给定表示有穷集上关系的矩阵，确定这个关系是否是自反的或反自反的；对称的或反对称的；是否传递的。 目的是使学生掌握利用计算机语言实现判断关系性质的基本方法。 实验二 要求判断给定的代数系统〈G，*〉是否为群（2学时, 设计性实验,必做） 教学内容：对给出的一个代数系统〈G，*〉，其中G={1，2，…,n}，*运算由运算表矩阵给出，要判断： 〈G，*〉是否为半群； 〈G，*〉是否为含幺半群； 〈G，*〉是否每个元素关于*运算都是可逆的。 如果满足上述三个条件，则〈G，*〉是群。 目的是目的使学生掌握利用计算机语言实现判断给定的代数系统〈G，*〉是否为群的基本方法。 实验三 要求利用最小生成树的Kruskal算法编制程序（2学时, 验证性实验,必做） 教学内容：设给定的无向连通图具有n个节点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边的时候，使得生成树形成回路，则删除这条边。这样，直至生成树有n-1条边时，我们所得到的就是一棵最小生成树。 目的是学会最小生成树的判断方法。 实验四 要求实现合式公式的表示（2学时, 验证性实验,必做） 教学内容：对给出的任意一个合式公式（不超过四个命题变元），使学生会用C语言的语句表示出来，并且能够计算它在各组真值指派下所应有的真值。 目的使学生熟练掌握利用计算机语言实现逻辑运算的基本方法。 实验五 要求求出并集（2学时, 验证性实验,选做） 教学内容：对给定集合A和B，能够编出求A和B的并集C的程序。 目的是使学生熟练掌握利用计算机语言求出并集的基本方法。 实验六 要求判别图的连通性（2学时, 设计性实验,选做） 教学内容：给定n个结点的有向图的邻接矩阵，可判断该图是否为强连通的，单向连通的，或弱连通的。 目的： 使学生掌握利用计算机语言判别图的连通性的基本方法。 实验七 要求求出笛卡儿乘积（2学时，验证性。选做） 教学内容：笛卡儿乘积是以有序偶为元素组成的集合，对给定的集合A和B，求笛卡儿乘积，只需取尽由集合A的元素及集合B的元素，并构成序偶ai，bj送入C之中即可。 目的是使学生熟练掌握利用计算机语言实现求出给定集合的笛卡儿乘积的基本方法。 实验八 关系的合成运算（2学时，设计性。选做） 教学内容： 设关系A是从集合X={1，2，….，n}到集合Y={1，2，…..，m}的二元关系，而关系B是从集合Y到集合Z={1，2，….，p}的二元关系，求A与B的合成关系C。 目的是使学生熟练掌握利用计算机语言实现求出给定关系的合成关系的基本方法。 五、考核方法 实验占本课程总成绩的百分比：10% 以学生的实验报告情况和做实验时的表现为考核依据。 六. 教材与参考资料 1.建议教材： [1] 屈婉玲等编著.离散数学.清华大学出版社,2005.6 [2] 方世昌编著.离散数学.西安电子科技大学出版社,2002.6 2.建议参考书目： [1] Bernard Kolman, Robert C.Busby, Sharon Cutler Ross. DISCRETE MATHEMATICAL STRUCTURES. 高等教育出版社，2001.7 [2]李盘林等编著.离散数学. 高等教育出版社，1999.6 [3] K.H.Rosen. Discrete Mathematics and Its?Application. McGraw-Hill,1999 [4] 朱洪等编著.离散数学教程.上海科学技术文献出版社，1999.11 [5] 左孝凌等编.离散数学.上海科学技术文献出版社,1982.9 编写人（签字） 姜楠 编写人职称： 副教授 审阅人（签字）： 审阅人职称： 审批人（签字）： 审批人职务：