离散数学实验指导书.doc

《离散数学》试验指导

一 试验课任务、 性质与目
本试验课程是信息专业学生一门专业基础课程, 经过试验, 帮助学生愈加好地掌握计算机科学技术常见离散数学中概念、 性质和运算; 经过试验提升学生编写试验汇报、 总结试验结果能力; 使学生含有程序设计思想, 能够独立完成简单算法设计和分析。

二 试验目标
1. 掌握离散数学中包含相关概念。
2. 培养学生逻辑思维能力和算法设计思想。
3. 熟练掌握C/C++语言程序设计基础方法和多种调试手段。
4. 熟练掌握包含数组、 链表以及邻接表或邻接矩阵等数据结构建立和利用。
5. 经过试验掌握递归程序设计基础方法。
6. 掌握图存放和遍历方法。

三 试验要求
1． 试验前, 复习《离散数学》课程中相关内容。
2． 上机前编好程序, 上机时调试。
3． 编程要独立完成, 程序应加合适注释。
4． 完成试验汇报。

四 试验汇报要求

“离散数学”试验汇报

专业
班级
学号
姓名

日期

封面: 如右图

文字用小4号或4号; 程序和注释用5号
以班为单位交.

试验汇报文件名: 080x姓名学号（试验xA/B/C）
试验汇报上交时间: 做完试验后一到两周内, 在课间拷贝到教室机器指定目录中。

试验一
一 试验内容（二选一）
1. 从键盘输入两个命题变元P和Q真值, 求它们合取、 析取、 条件和双条件真值。（A）
2. 求任意一个命题公式真值表（B, 并依据真值表求主范式（C））

注意: 题目类型分为A, B, C三类, 其中A为基础题, 完成A类题目可达成设计基础要求, 其她均为加分题, 并按字母次序分数增加越高。

二 试验目
熟悉掌握命题逻辑中联接词、 真值表、 主范式等, 深入能用它们来处理实际问题。

三 试验环境
C或C＋＋语言编程环境实现。

四 试验说明
1. 逻辑联接词运算
本试验要求大家利用C/C＋＋语言, 实现二元合取、 析取、 条件和双条件表示式计算。充足利用联接词和逻辑运算符之间相同性实现程序功效。
2. 求任意一个命题公式真值表
本试验要求大家利用C/C＋＋语言, 实现任意输入公式真值表计算。通常我们将公式中命题变元放在真值表左边, 将公式结果放在真值表右边。命题变元可用数值变量表示, 适宜公式表示及求真值表转化为逻辑运算结果; 可用一维数表示合式公式中所出现n个命题变元, 同时它也是一个二进制加法器模拟器, 每当在这个模拟器中产生一个二进制数时, 就相当于给各个命题变元产生了一组真值指派。算法逻辑以下:
（1）将二进制加法模拟器赋初值0
（2）计算模拟器中所对应一组真值指派下合式公式真值。
（3）输出真值表中对应于模拟器所给出一组真值指派及这组真值指派所对应一行真值。
（4）产生下一个二进制数值, 若该数值等于2n-1, 则结束, 不然转（2）。
注意, 在进行表示式求值时候, 可先将带括号中缀表示式利用栈结构转换为不带括号后缀表示式（逆波兰式）, 然后进行计算。具体方法请参考数据结构中相关“栈”知识。

五 试验要求
在试验汇报中要写下列内容:
1. 试验目;
2. 试验内容;
3. 试验环境;
4. 试验原理和实现过程（算法描述）;
5. 试验数据及结果分析;
6. 源程序清单;
7. 其她收获和体会。

注意:
1. 程序需含有基础容错控制, 在输入错误时有处理手段;
2. 程序界面友好, 需要输入地方有输入说明, 说明输入内容和格式要求等;
3. 试验原理和实现过程应该具体分析问题, 给出处理思绪, 描述算法思想, 不能用源程序替换算法;
4. 测试数据应全方面, 包含非法输入处理结果等都应包含在内
试验二
一 试验内容（三选一）
1. 求有限集上给定关系自反、 对称和传输闭包。（有两种求解方法, 只做一个为A, 两种都做为B）
2. 求有限集上等价关系数目。（有两种求解方法, 只做一个为A, 两种都做为B）
3. 求解商集, 输入集合和等价关系, 求对应商集。（C）
注意: 题目类型分为A, B, C三类, 其中A为基础题, 完成A类题目可达成设计基础要求, 其她均为加分题, 并按字母次序分数增加越高。

二 试验目
掌握关系概念与性质, 基础关系运算, 关系多种闭包求法。了解等价类概念, 掌握等价类求解方法。

三 试验环境
C或C＋＋语言编程环境实现。

四 试验说明
1. 求有限集上等价关系数目。
集合上等价关系与该集合划分之间存在一一对应关系。一个等价关系对应一个划分, 一个划分也对应一个等价关系。我们把n个元素集合划分成k块方法数叫第二类Stirling数, 表示为S(n,k)。比如有甲、 乙、 丙、 丁四人, 若全部些人分成1组, 只有全部些人在同一组这个方法, 所以S(4,1) = 1; 若全部些人分成4组, 只能够人人独立一组, 所以S(4,4) = 1; 若分成2组, 能够是甲乙一组、 丙丁一组, 或甲丙一组、 乙丁一组, 或甲丁一组、 乙丙一组, 或其中三人同一组另一人独立一组, 即是:
1. {A,B},{C,D}
2. {A,C},{B,D}
3. {A,D},{B,C}
4. {A},{B,C,D}
5. {B},{A,C,D}
6. {C},{A,B,D}
7. {D},{A,B,C}
所以S(4,2) = 7。
给定S(n,n) = S(n,1) = 1, 有递归关系S(n,k) = S(n − 1,k − 1) + kS(n − 1,k)
上面递推式能够用组合证实: 首先, 假如将元素1单独拿出来划分成1个集合, 那么方法数是S(n-1,k-1); 其次, 假如元素1所在集合不止一个元素, 那么能够先将剩下n-1个元素划分好了以后再选一个集合把1放进去, 方法数是k*S(n-1,k); 有加法原理得证。
第二类Stirling数可用递推和递归两种方法求解。
集合上全部等价类个数即为k从1到n, 全部S(n,k)之和。

2. 求有限集上给定关系自反、 对称和传输闭包。
关系采取关系矩阵形式表示会比较轻易处理。自反闭包和对称闭包求法比较简单, 传输闭包有两种方法求解。一个直接经过定义, 另一个称为Warshall算法。
Warshall算法:
设R关系矩阵为M
(1)令矩阵A=M
(2)置i=1
(3)对全部j, 若A[j, i]=1, 则
对于 k=1, 2, …, n, 令A[j, k]=A[j, k]+A[i, k]
(4)i=i+l．
(5)若i≤n, 则转到(3), 不然结束。

3. 求解商集, 输入集合和等价关系, 求对应商集
商集即等价类组成集合, 要求商集, 首先需要判定输入关系是否为等价关系, 不然没有商集。确定集合A={a1,a2,a3,…,an}相关R等价类算法以下:
(1) 令A中每一个元素自成一个子集, 如A1={a1},A2={a2},…,An={an}
(2) 对R中每个二元组< x,y >, 判定x和y所属子集。假设x属于Ai, y属于Aj, 若Ai<>Aj, 则将Ai并入Aj, 并置Ai为空; 或将Aj并入Ai, 并置Aj为空。通常将元素少集合合并到元素多集合。
(3) A1 ,A2,…,An中全部非空子集组成集合即为所求商集。

要实现集合并运算, 采取并查集(union-find sets)是一个不错方法。并查集是一个树型数据结构, 多棵树组成一个森林, 每棵树组成一个集合, 树中每个节点就是该集合元素, 找一个代表元素作为该树(集合)祖先。并查集可用于快速实现处理部分不相交集合（Disjoint Sets）并。通常见途就是用来维护某种等价类。并查集支持以下三种操作:
(1) Make_Set(x) 把每一个元素初始化为一个集合
初始化后每一个元素父亲节点是它本身, 每一个元素祖先节点也是它本身。
(2) Find_Set(x) 查找一个元素所在集合
查找一个元素所在集合, 只要找到这个元素所在集合祖先即可。判定两个元素是否属于同一集合, 只要看她们所在集合祖先是否相同即可。
(3) Union(x,y) 合并x,y所在两个集合
合并两个不相交集合操作很简单: 首先设置一个数组Father[x], 表示x"父亲"编号。那么, 合并两个不相交集合方法就是, 找到其中一个集合祖先, 将另外一个集合祖先指向它。
相关并查集具体操作实现请参考相关资料。

五 试验要求
在试验汇报中要写下列内容:
1. 试验目;
2. 试验内容;
3. 试验环境;
4. 试验原理和实现过程（算法描述）;
5. 试验数据及结果分析;
6. 源程序清单;
7. 其她收获和体会。

注意:
1. 程序需含有基础容错控制, 在输入错误时有处理手段;
2. 程序界面友好, 需要输入地方有输入说明, 说明输入内容和格式要求等;
3. 试验原理和实现过程应该具体分析问题, 给出处理思绪, 描述算法思想, 不能用源程序替换算法;
4. 测试数据应全方面, 包含非法输入处理结果等都应包含在内