毕业设计论文：离散数学课程设计论文

《毕业设计论文：离散数学课程设计论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、我濮Z理2罟基于二元树的随机序列独立性分析算法与实现题目专业班级学号学生姓名指导教师指导教师职称学院名称完成日期：年7月1日IIIII第1章课题背景1.I问题背景11.2基础知识11.3意义11.4文献综述22.1算法概述3第2章基于二元树的随机变量序列相依阶数估计2.2数据结构设计第3章功能函数实现53.1二叉树结点插入53.2二叉树的建立53.3二叉树层次遍丿力63.4程序与所实现的调度方案73.5程序的优缺点及改进13第4章总结14致谢15参考文献1617摘要随机变量序列中的符号不是独立的，通过程序的结果，统计出二元随机序列每一维序列频数，最后，我们要根

2、据所得出的频数来分析与统计二元树随机变量序列相依阶数，找出随机序列中的最大独立单元。在该程序中，随机变量序列为随机的二进制串。关键词：二元随机序列，频数，相依阶数，最大独立单元，二进制串刖旨本文解决了通过二叉树的链表方式存储数据并计算二叉树每个结点的频数。全文共四章。第1章介绍了问题背景以及相关的基础知识。在本章中，还给出了具体的实例分析和与之相关的定理。第2章主要介绍了解决课题的算法概述以及数据结构设计。第3章主要介绍了功能函数的实现，其屮包括二叉树结点插入、二叉树的建立以及二叉树层次遍历。第4章是本次课程设计的总结。全文的最后是致谢、参考文献和对程序优化处

3、理的源代码。****第1章课题背景1.1问题背景随机变量序列的独立性与相依性是概率论屮很重要的概念。许多随机变量序列中的符号的岀现都与其前面若干个符号有依赖关系，在研究分析时限制随机序列的记忆长度，当记忆长度固定时，这样的记忆信源为马尔可夫信源。而实际上，有很多随机序列的记忆长度不是I占I定的，这样随机序列相依阶数是变化的。基于二元树随机变量序列相依阶数估计是通过分析树结点的空间分布，可以判定出该随机变量序列是独立还是相依的。若随机序列是相依的，可以统计岀该序列相依阶数。1.2基础知识独立性是概率论中一个重要的概念，两个事件之间的独立性是指：一个事件的发生不影

4、响另一个事件的发生。这在实际问题中是很多的。譬如在掷颗骰子，记事件A为“第一颗散子的点数为1”，记事件B为“第二颗骰子的点数为4”。则显然A与B的发生是相互不影响的。若事件A与B相互独立，称A与B独立，否则A与B不独立即A与B和依。在多维随机变量中，各分量的取值有时会相互影响，但有时会毫无影响。譬如一个人的身高X和体重Y就会相互影响，但与收入Z—般无影响。当两个随机变量取值互不影响时，就称它们是相互独立的。同理，若它们的取值之间有影响，则它们之间是相依的。1.3意义在信息论中，多符号离散稳信源是多符号离散信源中最简单，最常用，而且也是至今为止讨论最充分、理论最

5、成熟的一种信源。多符号离散信源发出的消息是由一系列离散符号组成的时间（或空间）序列来表示。例如，电报系统发出的消息，就是由“正”脉冲表示的“0”符号和“负”脉冲表示的“1”符号组成的一连串“0”、“1”符号的时间序列来表示的。根据信息的定义，这种由离散符号的时间序列代表的消息要含有信息的前提条件是消息具有随机性，也就是每一单位时间出现的离散符号必须具有随机性。1.4文献综述文献［1］介绍了二叉树结点的形成与层次遍历。文献［2］介绍了概率论中随机连续型序列与离散型序列独立性的分析。文献［3］以实例较为详细地介绍了二叉树的分析算法与实现。第2章基于二元树的随机变量

6、序列相依阶数估计1.1算法概述根据课题要求，我们将通过二叉树的链表方式存储数据，计算二叉树每个结点的频数。当将二进制序列读取后，按指定的维数N,从第一个字符开始一次读取N个字符，依次插入结点建立二叉树，再从第二个字符开始读取N个字符，从根结点开始依次插入，依次类推，直到循环到最后一个字符读取N个字符依次插入后，二叉树建立完成。在插入结点的过程中，若二叉树此处结点已存在，只需次其频数增1,若结点不存在，则插入结点，并将频数增1。当输岀二义树每个结点的频数时，利用二叉树的层次遍历。按层次顺序访问二叉树的处理需要利用一个队列。在访问二叉树的某一层结点时，把下一层结点

7、指针预先记忆在队列中，利用队列安排逐层访问的次序。因些，当访问一个结点时，将它的子女依次加到队列的队尾，然后再访问己在队列队头的结点。这样，二叉树每个结点按照层次遍历的顺序存储在了队列中。最后，将得到的结点频数通过计算研究，分析m元树同高度的结点空间分布以及最大独立单元和其状态空间，并且通过计算分析估计随机变量序列的相依阶数。2.2数据结构设计定义一个结构体来表示二叉树的结点，结构体里包含结点频数，结点符号串，结点符号，结点左右指针。结点频数表示循环二叉树建立后，经过该结点的总次数；结点符号主要是读取二进制串时，结点符号取0表示新建结点为左孩子，符号取1表示新

8、建结点为右孩子；将频数、符号，结点符号