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