学位论文 > 优秀研究生学位论文题录展示

自然数幂和三种典型公式的等价证明及算法分析

作　者: 尹志凌
导　师: 张升
学　校: 内蒙古师范大学
专　业: 计算机应用技术
关键词: Bernoulli数 Stirling数 Euler数算法复杂性
分类号: O156.1
类　型: 硕士论文
年　份: 2010年
下　载: 35次
引　用: 0次
阅　读: 论文下载

内容摘要

Bernoulli数、Stirling数、Euler数在组合数学、函数论、理论物理及近似计算等方面均有广泛的应用。在数字图像中,可以利用欧拉数来描述物体结构,保持图像特征不变;在离散数学中,这些特殊数具有组合含义;在气象学、组合优化、随机图、Ramsey理论等方面的也可用这些特殊数来计数。著名计算机科学家、美国斯坦福大学教授克努特(Donald E.Knuth)在他的名著The Art of Computer Programming(1998,《计算机程序设计艺术》)中专门设计了计算Euler数及Bernoulli数的程序。而幂和的发展经历了两千多年,一直是人们研究的热点。自然数幂和可以分别用Euler数、Bernoulli数、Stirling数相关的表达式表示,使幂和的计算趋于简便快捷。但这三种表达式的互推多年来无人研究,同时这三种表达式的算法的复杂性也无人分析。我国著名数学家徐利治先生在给内蒙古师范大学教授罗见今先生的信中,曾经建议把这个研究作为硕士研究生的论文题目来开展工作,可见这方面的研究的确有重要意义。本文就此问题进行深入研究,给出了这三种表达式的互推,分析了这三种表达式算法的复杂度,得出了它们具有相同的Θ( k2)的复杂度的结论,力求使此方向的研究向前推进一步,以填补此研究领域的空白,并使之具有实践操作性。本文讨论了幂和的起源与发展,给出了幂和在两千年间取得的主要成果,在这一工作的基础上介绍了两种Stirling数、Euler数及Bernoulli数的发展,对其主要成果给出了说明。通过证明Stirling数、Euler数及Bernoulli数的关于幂和的表达式,最终设计出一整套的算法,给出了关于幂和分别用Stirling数、Euler数及Bernoulli数这几种特殊计数表示的结果。最后对算法进行复杂性的讨论,给出了幂和在这三种表达式的计算量上是等价的结论。

全文目录

中文摘要  4-5
Abstract  5-9
前言  9-10
1 绪论  10-19
  1.1 研究背景  10-17
    1.1.1 幂和的发展  10-13
    1.1.2 现阶段研究状况  13-17
  1.2 研究的目的和意义  17-19
2 幂和三种表达式的证明  19-35
  2.1 方幂和与Bernoulli数及Euler数及Stirling数的定义  19-22
    2.1.1 伯努利数及伯努利多项式  19-20
    2.1.2 欧拉数及欧拉多项式  20-21
    2.1.3 方幂和的定义与Stirling数的定义  21-22
    2.1.4 Bernoulli数及Euler数及Stirling数之间的转换关系  22
  2.2 方幂和与Bernoulli数及Euler数及Stirling数的关系表达式  22-23
  2.3 定理的证明  23-35
3 计算机实现幂和三种表达式  35-40
  3.1 程序需要解决的问题  35-36
  3.2 程序设计的难点  36
  3.3 程序设计思路  36-40
    3.3.1 高精度的计算  36-37
    3.3.2 几个系数的计算方法  37-39
    3.3.3 多项式的计算  39
    3.3.4 计算框图  39-40
4 幂和三种表达式的算法复杂性分析  40-46
  4.1 关于多项式的复杂度  40
  4.2 系数的计算复杂度  40-46
    4.2.1 利用 Bernourlli 数表示多项式系数  40-42
    4.2.2 利用 Euler 数来计算的多项式系数  42-44
    4.2.3 利用 Stirling 数计算的多项式系数  44-46
5 总结  46-47
参考文献  47-49
致谢  49-50
攻读硕士学位期间公开发表的学术论文  50

相似论文

发生函数在组合恒等式中的应用,O157
一个与记录时间相关的生成函数研究,O211.3
组合恒等式的Riordan法,O157
火电厂机组经济调度算法设计与分析研究,TP301.6
传感器网络设计的数学模型及其应用,TN929.5
Bernoulli多项式与幂和多项式,O174.14
K边导出子图问题研究,O157.5
基因组Reversal/Transposition排序的快速计算研究,TP399-C8
关键文字和极小不可满足公式,TP301.5
关于Bell多项式和GSN对的若干问题,O157
（n，n）图的k-终端割与（n，n+1）图的3-终端割问题研究,O157.5
容量—时间网络的时间流问题,E911
一类拟线程通信模型中的排序问题,O223
具有资源约束的排序问题,O223
深度的算法及其复杂性分析,O157.4
带传递时间的通信模型中的树约束排序问题,O223
几种最优资源分配与排序问题研究,O223
带有链优先约束的两类排序问题,O223
流程工业生产与运输协调物流调度理论研究,F426.31
约束满足问题的模型构造和相变现象,TP18