毕业设计（论文）《离散数学课程设计论文--基于二元树的随机序列独立性分析算法与实现》.doc

武汉工程大学本科课程设计(论文) PAGE 139 PAGE I 09 届课程（设计）论文 题 目 基于二元树的随机序列独立性分析算法与实现 专业班级 信息与计算科学(2)班 学 号 学生姓名 指导教师 指导教师职称 副教授 学院名称 理学院 完成日期： 2011 年 7月1日 目 录 TOC \o 1-2 \h \z 目 录 I 摘 要 II 前 言 III 第1章 课题背景 1 1．1问题背景 1 1．2 基础知识 1 1．3 意义 1 1．4 文献综述 2 第2章 基于二元树的随机变量序列相依阶数估计 3 2．1 算法概述 3 HYPERLINK 第3章 功能函数实现 5 3．1二叉树结点插入 5 3．2 二叉树的建立 5 3．3 二叉树层次遍历 6 3．4 程序与所实现的调度方案 7 3．5 程序的优缺点及改进 13 第4章 总 结 14 致 谢 15 参考文献 16 附 录 17 摘 要 随机变量序列中的符号不是独立的，通过程序的结果，统计出二元随机序列每一维序列频数，最后，我们要根据所得出的频数来分析与统计二元树随机变量序列相依阶数，找出随机序列中的最大独立单元。在该程序中，随机变量序列为随机的二进制串。 关键词：二元随机序列，频数，相依阶数，最大独立单元，二进制串 前 言 本文解决了通过二叉树的链表方式存储数据并计算二叉树每个结点的频数。全文共四章。 第1章介绍了问题背景以及相关的基础知识。在本章中，还给出了具体的实例分析和与之相关的定理。 第2章主要介绍了解决课题的算法概述以及数据结构设计。 第3章主要介绍了功能函数的实现，其中包括二叉树结点插入、二叉树的建立以及二叉树层次遍历。 第4章是本次课程设计的总结。 全文的最后是致谢、参考文献和对程序优化处理的源代码。 **** 2011 第1章 课题背景 1．1问题背景 随机变量序列的独立性与相依性是概率论中很重要的概念。许多随机变量序列中的符号的出现都与其前面若干个符号有依赖关系，在研究分析时限制随机序列的记忆长度，当记忆长度固定时，这样的记忆信源为马尔可夫信源。而实际上，有很多随机序列的记忆长度不是固定的，这样随机序列相依阶数是变化的。基于二元树随机变量序列相依阶数估计是通过分析树结点的空间分布，可以判定出该随机变量序列是独立还是相依的。若随机序列是相依的，可以统计出该序列相依阶数。 1．2 基础知识 独立性是概率论中一个重要的概念，两个事件之间的独立性是指：一个事件的发生不影响另一个事件的发生。这在实际问题中是很多的。譬如在掷颗骰子，记事件A为“第一颗骰子的点数为1”，记事件B为“第二颗骰子的点数为4”。则显然A与B的发生是相互不影响的。若事件A与B相互独立，称A与B独立，否则A与B不独立即A与B相依。 在多维随机变量中，各分量的取值有时会相互影响，但有时会毫无影响。譬如一个人的身高X和体重Y就会相互影响，但与收入Z一般无影响。当两个随机变量取值互不影响时，就称它们是相互独立的。同理，若它们的取值之间有影响，则它们之间是相依的。 1．3 意义 在信息论中，多符号离散稳信源是多符号离散信源中最简单，最常用，而且也是至今为止讨论最充分、理论最成熟的一种信源。多符号离散信源发出的消息是由一系列离散符号组成的时间（或空间）序列来表示。例如，电报系统发出的消息，就是由“正”脉冲表示的“0”符号和“负”脉冲表示的“1”符号组成的一连串“0”、“1”符号的时间序列来表示的。根据信息的定义，这种由离散符号的时间序列代表的消息要含有信息的前提条件是消息具有随机性，也就是每一单位时间出现的离散符号必须具有随机性。 1．4 文献综述 文献 REF _Ref217351818 \r \h [1]介绍了二叉树结点的形成与层次遍历。 文献 REF _Ref228010686 \r \h [2]介绍了概率论中随机连续型序列与离散型序列独立性的分析。 文献[3]以实例较为详细地介绍了二叉树的分析算法与实现。 第2章 基于二元树的随机变量序列相依阶数估计 2．1 算法概述 根据课题要求，我们将通过二叉树的链表方式存储数据，计算二叉树每个结点的频数。当将二进制序列读取后，按指定的维数N，从第一个字符开始一次读取N个字符，依次插入结点建立二叉树，再从第二个字符开始读取N个字符，从根结点开始依次插入，依次类推，直到循环到最后一个字符读取N个字符依次插入后，二叉树建立完成。在插入结点的过程中，若二叉树此处结点已存在，只需次其频数增1，若结点不存在，则插入结点，并将频数增1。 当输出二叉树每个结点的频数时，利用二