判断强连通自动机同构的一个多项式时间算法

众所周知,自动机的同构、图的同构等问题是多项式时间等价的(Booth,SIAM J.Comput,7(1978),3)。因此,讨论自动机的同构及其子问题是十分有意义的。最近,李慧陵给出了计算强连通自动机的自同构群的一个多项式时间算法。本文借助于此结果,在固定字母表的情况下,给出了判断两个强连通自动机是否同构的一个多项式时间算法。     

计算多项式零点的PL同伦算法的成本估计

零点计算问题。文献[1]提出一种分片线性(PL)同伦方法,简称KNA算法.因为引进一个扰动项,该方法不但计算零点,同时也给出零点的重数。然而,因为没有与多项式系数无关的误差估计,一直未能得出多项式     

图的二分问题唯一全局最优解实例与骨架计算复杂性

骨架分析是近年来理论计算机科学研究的热点, 对于NP-难解问题的启发式算法设计具有重要意义. 由于骨架计算复杂性研究十分困难, 现有的骨架分析方法多采用实验统计手段. 针对现有方法中存在的骨架规模小的缺陷, 给出图的二分问题GBP(graph bi-partitioning problem)的唯一全局最优解实例构造算法, 有效提高了骨架的规模. 同时, 利用该算法从理论上证明了寻找GBP问题的完整骨架属于NP-难解问题, 即在P≠NP的假设下, 不存在多项式时间的算法可以确保得到GBP问题的完整骨架. 本文的工作拓广了骨架计算复杂性研究的范围, 所提出的唯一全局最优解实例构造算法对于NP-难解问题启发式算法设计亦具有较高的参考价值.     

中国数学会理事长吴文俊访问美国、加拿大

今年7月5日至8月25日,中国数学会理事长、著名数学家吴文俊应邀参加了在美国举行的国际数学家大会和在加拿大举行的多伦多符号与代数计算讨论会,并到库朗研究所、得克萨斯大学等处进行了学术访问,受到热烈欢迎.吴文俊于1977年开始提出并发展了一套证明定理和处理多项式运算的机械化方法,即公认的吴氏方法.这一方法受到了各国数学家和计算机科学家的高度重视.库朗研究所为吴文俊访美期间的学术活动特     

矩阵乘法的一个最佳算法

一、引言 矩阵乘法是线性代数中常见的问题之一,许多数值计算问题都包含着矩阵乘法的计算。因此,降低矩阵乘法算法的时间复杂度问题,多年来一直引起算法研究者们的高度重视。 1969年,Strassen提出了一个时间复杂度为O(n~(log_2~7))的矩阵乘法算法,第一次突破了O(n~3)的界限,被誉为“在代数复杂性理论中最激动人心的结果”。以后,又出现了一系列新     

经济均衡理论及其计算方法

历史上,数学的发展曾从天文学、力学、物理学得到巨大的推动。而最近二三十年,则是生物学、经济学等学科所提出的数学问题,对数学的发展产生深刻的影响。本文所要介绍的就是这方面的一个生动例子:数理经济学中经济均衡理论的发展要求找到计算均衡价格的有效算法,这种要求导致美国经济学家斯卡夫(H.E.Scarf)先于数学家发明了不动点算法,从而开创了计算数学中高度非线性问题数值方法研究的新方向。“看不见的手”英国古典经济学派的创始人亚当·史密斯     

论Канторович型算子和积分Schoenberg样条

§1.设f(x)∈C[0,1],n和k是自然数,schoenberg引进了样条函数的逼近方法S_(n,k)(f),它们是多项式的推广,1977年德国数学家Müller引进了积分Schoenberg样条T_(n,k)(f),它们是多项式的推广,并研究了用T_(n,k)(f)的L~p逼近阶,作者曾引进了广义的多项式的概念,本文引进一般的型算子A的概念(记为)这是T_(n,k)(f)的推广,通过对积分算子核的分析和精巧计算,证明了一个有趣的等式     

突变理论：形成、发展与应用

突变理论(Catastrophe Theory)是新近诞生的一门边缘学科,也是一门迅速发展而有重大理论与实际意义的学科。著名的法国数学家R.汤姆(R.Thom)于1972年在《结构稳定性与形态发生学》一书中,提出并系统地阐述了“突变理论”,从而引起国际学术界广泛的注意,著名的数学家E.C.齐曼(E.C.Zeeman)等人将这一     

平面三次微分系统多重Hopf分枝的环性:M(3)≥7

近年来,英国数学家M.G.Lloyd等三人,中国奥地利访问学者D.M.Wang和刘一戎等先后给出不同的例子证明,平面三次多项式微分系统至少存在六个小振幅极限环,即由原点产生的多重Hopf分支的环性(Bautin意义下)值M(3)≥6。 我们研究具有中心型奇点的N次多项式系统的一次非线性unfolding系统(n>     

全国高等院校计算数学第四次学术交流会简讯

全国高等院校计算数学第四次学术交流会于1985年5月21日～25日在昆明市召开,参加会议的有国内53所高等院校以及中国科学院、出版部门的代表114人。提交会议的学术论文共134篇,会上宣读了72篇.会议组织的综合报告对于一些当今国内外计算数学比较活跃的新方向,例如数学软件的设计与实现、弹性变分问题的数学方法、边界元方法、同伦算法、多元样条、矩阵特征值摄动问题、解线性规划的新多项式算法等内容进行了介绍.会议期间,代表们还就计算数学专业的人才培养方向、课程设置、教材编写,以及对计算     

“硬问题”就一定硬吗?

数学家们曾开玩笑说,若要长生不死有一个办法,就是找到这样一个问题,它极其重要,重要到你不解决它就不能够死,然后你就把它束之高阁,不去解决它。在计算复杂性理论的领域中,多项式分层结构问题好象正合那些想永远不死的人的意。它很困难——是那样地难,以至于就象美国电话电报公司贝尔实验室的罗纳尔德·格雷汉(Rouald Graham)形容的一样,“多     

关于幂和问题的进一步研究

设n与k都是正整数,令S_k(n)=sum from m=1 to n m~k。由于组合数学的发展,近代数学家们对寻求S_k(n)的解析表达式这个有趣的问题又进行了大量的研究,并在他们的文章中提出或用不同的方法来处理这个问题,他们给出了最高次数为13的幂和公式,证明了S_k(n)是n的k 1次有理多项式。我们在文献[3,4]中也用了不同的方法来解决这个问题,给出了最高次数为     

最大集团问题的DNA计算机进化算法

进化算法是克服DNA计算中穷举法极限的可能途径之一. 借用生物进化的概念, 设计了可用于DNA计算的进化算法来求解最大集团问题. 算法中所有的操作都可以在今天的分子生物技术水平上实现. 计算机模拟实验表明使用这种进化算法有可能由一个小的样本空间得到问题的解, 而不必穷举所有可能情况. 对于随机生成的问题, 这种进化算法能以高概率在很少的进化循环数内正确地给出问题的解. 结果显示这种进化算法所需的时间随问题的规模呈多项式增长, 这可能使DNA计算机在求解复杂问题时比传统电子计算机拥有更多的优势.     

计算多项式GCD渐近快速算法的缺陷及其修正

令a_0和a_1是两个多项式,计算它们的最大公因式GCD,用DEG(a)表示多项式a的次数,设DEG(a_1)相似文献   

自然信息

π的新纪录美国哥伦比亚大学的数学家丘得诺夫斯基兄弟(D.Chudnovsky& G.Chudnovsky)最近把圆周率π计算到4.8亿位数字,从而打破了由日本东京大学金田康正所保持的2.1亿位的纪录。数学家们如此热哀于π的计算,这有必要吗? 原因之一是,这是一场竞赛,就好比攀登珠穆朗码峰,既然它存     

探究天体运行的数学法则:从牛顿到废加莱

在1900年国际数学家大会上,大数学家希尔伯特在他著名的演讲[1]中提出了23个困难的数学问题,这些问题在20世纪的数学发展中起了非常重要的作用.在同一演讲中,希尔伯特也提出了他所认为的完美数学问题的准则:问题要能被简明清晰地表达出来,而问题的解决又必须要有全新的思想方法才能够实现.为了说明他的观点,希尔伯特举了两个最典型的例子:第一个是费马大定理,即代数方程xn+y2=zn在n＞2时没有正整数解;第二个就是这篇文章所要介绍的N体问题及其特例——三体问题.     

图论结果得到证明

两位研究一个违反直觉的猜想的数学家,解决了一个50年之久的难题。大约在二十年前,德国数学家库尔特·魏格纳(Kurt Wagner)提出了一个关于图的性质的猜想。这个猜想乍一看来令人难以置信,甚至连他的研究生也不敢相信。然而,这个猜想很吸引人,而且因为它很基本和重要,许多数学家都想证明猜想对还是错。俄亥俄州立大学的内尔·罗伯逊(Neil Robertson)是其中     

错型结构的预测和Welch-Berlekamp定理的拓广

Welch-Berlekamp(W-B)定理准确地预测错型的定位多项式,导出译循环码的W-B算法,但适用范围仍未突破BCH限,今由极小插值问题理论出发,给出定位多项式预测通式,拓广W-B定理,扩充W-B算法使之突破BCH限而成为超BCH限译循环码与超最小码距限的完全译码的普适算法.设α为有限域F_qr的本原元,Ω为集合{α~(m+i)}_(i=1)~d_(BCH)~(-1)所确定的q元本原BCH码,(m     

关于黎曼猜想

在人类进行科学实验的过程中,常常会遇到这样一种问题:从人们的实践经验看来,这些问题有一个肯定的答案,但是我们暂时却无法对它进行严格的证明.而在数学上,一个命题如果不能严格地证明,它就不能为人们所公认,这种命题只能被称为“猜想”.大家熟知的哥德巴赫猜想就是一个著名的尚未被证明的命题.由著名的数学家黎曼(Riemann)在1859年提出的黎曼猜想,是又一个难以证明的猜想.它的重要之处在于,如果这个猜想解决了,则一大批尚未解决的难题都将得到突破。     

五边形石墨烯:碳材料的拓广与数学模型的实现

正1900年德国著名数学家希尔伯特(David Hilbert)在巴黎数学家大会上提出了"希尔伯特23个问题",其中第18个问题就是"如何用多面体构造空间".在此基础上,1928年莱茵哈特(Karl Reinhardt)提出了如何用五边形密铺二维空间的问题.在几何学上,五边形具有无与伦比的美学特征,正五边形中,次近邻顶点之间连线的交点恰为"黄金分割点".晶体中不存在五重旋转对称性,这是早已被证明并写入固体物理学教材中的定理,因此,正五边形无法像正