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

来源 :内蒙古师范大学 | 被引量 : 1次 | 上传用户:lieying110
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Bernoulli数、Stirling数、Euler数在组合数学、函数论、理论物理及近似计算等方面均有广泛的应用。在数字图像中,可以利用欧拉数来描述物体结构,保持图像特征不变;在离散数学中,这些特殊数具有组合含义;在气象学、组合优化、随机图、Ramsey理论等方面的也可用这些特殊数来计数。著名计算机科学家、美国斯坦福大学教授克努特(Donald E.Knuth)在他的名著The Art of Computer Programming(1998,《计算机程序设计艺术》)中专门设计了计算Euler数及Bernoulli数的程序。而幂和的发展经历了两千多年,一直是人们研究的热点。自然数幂和可以分别用Euler数、Bernoulli数、Stirling数相关的表达式表示,使幂和的计算趋于简便快捷。但这三种表达式的互推多年来无人研究,同时这三种表达式的算法的复杂性也无人分析。我国著名数学家徐利治先生在给内蒙古师范大学教授罗见今先生的信中,曾经建议把这个研究作为硕士研究生的论文题目来开展工作,可见这方面的研究的确有重要意义。本文就此问题进行深入研究,给出了这三种表达式的互推,分析了这三种表达式算法的复杂度,得出了它们具有相同的(O)(k2)的复杂度的结论,力求使此方向的研究向前推进一步,以填补此研究领域的空白,并使之具有实践操作性。   本文讨论了幂和的起源与发展,给出了幂和在两千年间取得的主要成果,在这一工作的基础上介绍了两种Stirling数、Euler数及Bernoulli数的发展,对其主要成果给出了说明。通过证明Stirling数、Euler数及Bernoulli数的关于幂和的表达式,最终设计出一整套的算法,给出了关于幂和分别用Stirling数、Euler数及Bernoulli数这几种特殊计数表示的结果。最后对算法进行复杂性的讨论,给出了幂和在这三种表达式的计算量上是等价的结论。
其他文献
随着计算机技术和人工智能技术的发展,组卷问题的研究受到越来越广泛的关注。智能组卷问题是一个在一定约束条件下的多目标参数优化问题,组卷的效率和质量完全取决于试题库以
随着全球电视数字化时代的到来,我国现在正在大力推进数字电视的普及和应用。数字电视的交互性赋予了它许多功能,电子节目指南(EPG)是数字电视的基本业务之一,它是实现用户友
随着嵌入式软件的广泛应用,嵌入式软件的结构和开发技术日新月异,相对于硬件的日益稳定,软件故障却经常出现。为了保证软件的质量,需要对软件进行测试。由于嵌入式软件的自身
云计算作为一种新型的计算模式为计算、存储提供了一种新的解决方式。外包计算模型随着云计算的发展而因运而生,一个计算能力较弱的用户将复杂的计算外包到云服务器,云服务器
随着Internet的发展,越来越多的单点到多点的数据传输应用应运而生。组播比传统的单播和广播协议更适合这种一对多的数据传输。传统的组播虽然具有网络利用率高、能节省发送
车间作业调度是典型的NP难题。由于车间作业调度问题在组合优化方面的复杂性,直接影响着生产效率的提高和获取利润的大小,因此,车间作业调度的研究和应用,对于企业提高管理水
XML的全称是Extensible Markup Language(可扩展标识语言)由于具有简单、可扩展、互操作性强,开放性强等特点,正迅速成为一种与技术无关的数据交换的标准和传输格式,并逐渐成
随着网络技术的迅速发展和J2EE平台的广泛应用,基于B/S的多层Web体系结构正在不断的发展完善,并逐渐成为Web应用开发的主流。但是,在现有的Web应用系统中,普遍存在着程序可重
涉及国家安全的各种秘密信息,直接关系到国家的安全利益和社会的稳定。国家机密信息一旦被窃取或破坏,将对国家造成不可估量的损失。在信息安全攻防技术发展到了较高水平的今
当前针对网络外部的入侵攻击已有相对完善的防护措施,但针对来自系统内部的用户威胁则缺乏针对性的措施。尤其在国防、公安、金融等领域,来自系统内部的越权访问、信息窃取、