提升C语言程序运行效率 马尔可夫 计算机程序编程课程设计报告(马尔可夫链算法生成随

PAGE 1

计算机程序编程课程设计报告

(马尔可夫链算法生成随机可读文本)

引言：

马尔可夫链的数学背景：

马尔可夫链，因安德烈?马尔可夫(A.A.Markov，1856－1922)得名 ，是数学随机过程的一种。

在20实际的初期，由于物理学、通讯与控制、生物学、管理科学等领域的需要，随机过程的理论逐步产生和发展起来。随机过程理论为诸多领域的随机现象提供了数学模型。

随机过程的数学定义：设试验E的样本空间为Ω，T是一个数集(T?

(-∞，+∞))，如果对于每一个t∈T，都有一个定义在样本空间Ω上的随机变量X(ω，t)，ω∈Ω，则称依赖于t的一族随机变量{X(ω，t)，t∈T}为随机过程。

马尔可夫链是一种特殊随机过程。

马尔可夫链的数学定义：设随机序列{X(n)，n=0,1,2,……}满足如下条件：

(1)对于每一个n(n=0,1,2,……)，X(n)取整数或它的子集(记为I)；

(2)对于任意r+1个非负整数n1，n2 ，…，nr，m(0≤n1＜n2＜…＜nr＜m)和任意正整数k ，以及状态i1，i2，ir，i，j∈I，有P{X(n1)=i1，X(n2)=i2，…，X(nr)=ir，X(m)=i}＞0，且

P{X(m+k)=j│X(n1)=i1,X(n2)=i2,…,X(nr)=ir,X(m)=i}

=P{X(m+p)=j│X(m)=i}，

则随机序列{X(n),n=0,1,2,…}为马尔可夫链。条件概率P{X(m+k)=j│X(m)=i}称为马尔可夫链{X(n),n=0,1,2,…}在时刻m从状态i出发，在时刻m+k转移到状态j的k步转移概率，记作pij(m,m+k),即

Pij(m,m+k)=P{X(m+k)=j│X(m)=i}.

马尔可夫链的性质：

对于齐次的马尔可夫链有C-K方程成立，这一方程表明“从状态i出发经k+l步转移到达状态j”这一事件，可以分解为“从状态i出发经k步转移到达中间状态s(s∈I)，再从s出发经l步转移到达状态j”这样一些事件的并。对于不同的中间状态s(s∈I)，这样的事件是互不相容的。

如果马尔可夫链具有遍历性，那么它的直观意义是：不论质点从哪一个状态i出发，当转移步数k充分大时，到达状态j的概率近似于常数πj 。如果已求出πj 值，则当k充分大时πj 可以作为pij(k)(i,j∈I)的近似值。

如果马尔可夫链具有平稳分布，并取初试概率分布为平稳分布，则它在任意时刻m的概率分布都相同，都等于初始概率分布。

2、马尔可夫链的典型应用：

物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码(著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码)。马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。

马尔可夫链最近的应用是在地理统计学(geostatistics)中。其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟。这一应用类似于“克里金”地理统计学(Kriging geostatistics)，被称为是“马尔可夫链地理统计学”。

相关图书介绍：

《马尔可夫决策过程引论》(作者：胡奇英/刘建庸 )

简介:马尔可夫决策过程是研究马氏型序贯(动态)决策问题的工具。本书提供了处理离散时间、连续时间、半马氏等三类基本马氏决策过程模型的一般化方法。在此基础上，本书研究了状态部分可观察、多目标、带约束条件等一般化马氏决策过程以及处于随机变化环境中的马氏决策过程。

《生灭过程与马尔可夫链 》(作者：王梓坤 )

简介：本书叙述生灭过程与马尔可夫链的基本理论并介绍近年来的一些研究进展第一章概述随机过程的一般概念：第二章至第四章讲述马尔可夫链；第五、六章研究生灭过程的基本理论和构造，主要是用概率方法；第七、八章研究生灭过程和双边生灭过程构造论，主要是用分析的方法。同时还讨论了用两种方法所得结论之间的联系。

数据结构设计：

本程序的数据结构在用哈希表设计。

哈希表介绍：哈希表是一种散列结果，它只通过关键字的特征便可以查找出所需结果，是一种十分便捷的用于查找的数据结构。在记录的存储地址和它的关键字之间建立一个确定的对应关系H，使每个关键字和结构中唯一的一个存储位置相对应。因而在查找时，只要根据这个对应关系H找到给定关键字值K的像H(K)，即对应的存储位置。若结构中存在关键字和K相等的记录，则必定在H(K)的存储位置上，因此，不需要进行比较便可直接取得所查记录。

哈希表的设计：

前缀表设

提升C语言程序运行效率 马尔可夫 计算机程序编程课程设计报告(马尔可夫链算法生成随机可读文本).doc...