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

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

树的枚举与树算法复杂性计算

树结构上算法复杂性分析近几年来得到越来越多的注意。Flaiole研究了树上递归下降算法的复杂性分析,办法是为一个形式化的树算法描述语言中的各种构造建立一个复杂性度量表。平行于树上的可加枚举问题,本文作者在文献[3]中引入了所谓“树结构上可加复杂性算法”,得到过一些本质上只能用于递归算法分析的结果。     

求解析取范式永真性问题的一个近似快速算法

NP完全问题是一类在计算复杂性理论中被证明为较难求解的问题,这类问题中包含有很多在理论和实际中很有意义的问题。NP完全问题中的一个问题的对偶问题若存在快速(多项式意义下)的求解算法,则所有NP完全问题都有快速的求解算法。但目前人们还没有找到一个求解NP完全问题的真正快速算法,并且有迹象表明求解NP完全问题的真正快速算法是不存在的。本文针对一个典型的NP完全问题的对偶问题——析取范式永真性     

太阳系的起源

这是近十年来京都大学物理系的天文学家们对于太阳系起源理论工作的一篇总结性文章。本文主要部分已于1979年7月15日到8月3日在santa Cruz关于恒星和行星系统形成的暑期讨论会上报告过。并在1980年7月22日到25日在东京举行的国际天文学会第九十三次讨论会,关于恒星演化理论中的基本问题的会上作补充报告。     

矩阵乘法的一个最佳算法

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

斜方辉石中Fe~(2+)电子光谱的研究

引言 关于斜方辉石Fe~(2 )电子光谱的实验测定和晶场分析,已有过许多工作。在2200～27000 cm~(-1)范围内已观测到20多条吸收带。但对光谱的理论分析还只限于较强的三条红外吸收带;对可见区和紫外区的大量吸收肩、峰,由于问题的复杂性,至今尚无人作出完整的理论解释。文献[4,5,9]通过对三条红外吸收带的理论分析所作的关于Fe~(2 )晶位对称性的论断,由于参数多、谱带少,似嫌根据不够充分。     

复杂性问题研究综述：概念及研究方法

复杂性问题研究是近年来的科研热点之一。然而由于研究背景的不同,有关概念和研究方法既存在着一定的联系,又有着千差万别和不相统一之处。本文试图概括总结国内外有关复杂性研究的工作,从而在学术思想方面有一条清晰的线索。我们认为,我国著名科学家钱学森提出的复杂性是开放复杂巨系统的动力学特性这一观点,较全面地概括了国内外关子混沌理论、反混沌理论等与复杂性研究相关的工作。并提出,从定性到定量的综合集成技术是分析开放复杂巨系统的有效工具,从而开辟了探索复杂性的一条可行之路。     

弱条件下Halley族迭代的收敛性

我们曾在Smale的点估计判据下得到整个Halley族迭代的收敛性定理。点估计判据假设被求零点的映照f在初始近似z_0的某个适当大的邻域内解析。按数值泛函文献的通常理解,这是强条件的假设,尽管这种假设对于实计算的复杂性研究有其特殊的需要。对于其迭代映照中涉及f的k阶导数(或差商)的迭代法,通常理解的弱条件是假设f在z_0的某个邻域有连续的k 1阶导数,就像Канторович关于Newton法的经典工作那样。弱条件下建立收敛性定理的最大困难是关于优映照正根存在的判定。由于优映照通常被选为多项式,所以在关于算法的理论中,这是一个已经被彻底解决的问题。但成功的收敛性定理要求把这种条件明快地表示出来,而不是只给出一种判定的算法。对照文献[6]的成功和文献[7]的差强人意,这是很明显的。长期以来,还没有能够在弱条件下建立Halley族迭代的收敛性定理,其困难就在于此。对原来意义的Halley法来说,已经建立不少弱条件下的收敛性定理,但不能令人信服地说哪个比哪个更好,其原因亦在于此。     

多项式时间、指数时间复杂性类和Tally集

可计算复杂性类之间的差异和联系是结构复杂性理论中主要研究的问题,而多项式时间复杂性类P和NP与指数时间复杂性类E和NE之间的关系更加引人注目.众所周知:如果P=NP,则E=NE.但反过来是否有:如果E=NE,则P=NP,仍是一个未解决问题.有多种途径试图解决这个问题.Book证明了:E=NE当且仅当在NP-P中不存在Tally集;Hartmanis等证明了:E=NE当且仅当在NP-P中不存在稀疏集(sparse set),这就是著名的向上分离结果(upward-separation result).此外是相对化的应用,到目前为止,关于这个问题     

人工神经网络和模糊理论在短期负荷预测中应用

对于电力系统负荷预测的复杂性,为提高短期预测的准确性,采用以人工神经网络为基础,提出了一种利用神经网络与模糊理论相结合进行负荷预测的模型。该算法克服了传统BP算法的训练速度慢、存在局部极小点的缺点,使预测精度大有改善。实例计算表明了该算法的改进成果和可行性。     

人工神经网络和模糊理论在短期负荷预测中应用

对于电力系统负荷预测的复杂性,为提高短期预测的准确性,采用以人工神经网络为基础,提出了一种利用神经网络与模糊理论相结合进行负荷预测的模型.该算法克服了传统BP算法的训练速度慢、存在局部极小点的缺点,使预测精度大有改善.实例计算表明了该算法的改进成果和可行性.     

全国浮选药剂学术会议

中国科学院技术科学部和中国金属学会于1961年12月1—7日共同召开了第一届全国浮选药剂学术报告会。大会共收到有关药剂的制备、应用、理论研究以及有关国内外浮选药剂发展评述等论文和工作报告59篇。就收到的报告内容来看,主要反映在三个方面:一、关于有效利用煤焦油原料作浮选药剂的研究;二、关于直链脂肪族类型浮选药剂的研究;三、关于起泡剂、抑制剂、絮凝剂以及药剂与矿物作用机理的研究等。     

大脑皮层信息传递复杂性的研究

在研究人大脑皮层的信息传输时，我们常常会遇到大量的短时间的序列，如何把这些时间序理用参数来刻划，从而使得我们可以看到全局性经典解对短序列的研究是个困难的总理２，晨线性这所提供的理论都需要比较多的数据，为此我们尝试用复杂性的测试来描述，但现有的复杂性测试很多方法和观点也各有不同，我们采用了Ｋｏｌｍｏｇｏｒｏｖ最初的建议面的所胃算法复杂性，但这方面也有很大的局限性，本文提提出了一个新的测度，试图对原有     

生态系统复杂性研究的几个基本理论及其局限性

生态系统的复杂性研究与当前的非线性科学和复杂性科学不期而遇,已受到人们的重视.本文介绍了生态系统复杂性研究中的几个基本理论,分析了它的局限性,指出生态系统复杂性的研究还有待于复杂性科学理论的发展和新的复杂性科学理论的出现.     

O(n)时间有限Abel群同构检验算法

计算群论和复杂性理论中的一个重要问题是,有限群同构检验是可行的,还是NP完全的?这个问题迄今没有解决。C.Savage和陈溧分别得到一个O(n~2)时间的n阶Abel群同构检验算法。 本文得到,存在O(n)时间的n阶Abel群同构检验算法。即使使用对数成本的RAM,完成这样     

三重DES的量子中间相遇搜索算法

融合量子计算原理和经典密码分析方法, 基于Grover量子搜索算法和中间相遇攻击思想, 给出了对三个密钥的三重DES攻击的量子中间相遇搜索算法, 该算法可以在O(56×2⁵⁶)步完成对三个密钥的三重DES的攻击, 所需存储复杂性为O(2⁵⁶), 与已有的攻击算法相比, 显著地降低了算法的计算复杂性.     

重量固定的目标解量子搜索算法

针对重量固定为d的n维布尔向量目标解搜索问题, 给出了重量固定的向量标签表示方法与向量标签还原算法, 在此基础上提出了计算复杂性优于经典搜索算法的重量固定目标解量子搜索算法. 新算法计算复杂性是相似文献   

洪水灾害研究的复杂性理论

作为一种高度复杂的自然现象,洪水灾害表现了不均匀性、多样性、差异性、随机性、突发性、迟缓性、重现性以及无序性等复杂性的特点,使经典的理论和手段已不适于伴随着人类经济活动的开展而日趋复杂化的洪水灾害系统的研究.由于复杂系统和复杂性理论的引入,为洪水灾害的研究注入了新的生机.复杂性理论在洪水灾害的研究中将扮演重要的角色,为解释洪水灾害中的复杂现象提供了崭新的方法论.本文提出从复杂大系统理论出发,借助于复杂性理论的基本数学工具(分形、混沌、神经网络等非线性动力学方法),研究和分析洪水灾害中的复杂现象,建立洪水灾害分析与模拟、反演与预测的综合集成方法,构造洪水灾害研究的复杂性理论框架.     

网络最优化中的一个扩容算法

提出了网络最小割集与网络瓶颈的关系。提出了解决网络瓶颈问题的一个优化容算法，并分析了算法复杂性，算法通过在给出了容量的网络中全局正向分段引入虚拟发点，构造扩容网络搜索全部最小割集；对于指定的网络最大流量，算法反向逐级计算各个最小割集弧组相应的调整量，通过增加调整最来重新布局各弧的容量，逐级回代直至恢复原网络拓扑结构，从而改善网络的通行能力，解决网络瓶颈问题。     

构造对偶族的一个新算法

本文提出了构造布尔函数的对偶族的一个新算法。通过双取对偶,可以求得布尔函数或者非相干故障树的全部质蕴含项。在非相干系统故障树分析的领域里,为识别所有可能的系统故障模式,必须引进质蕴含项(PIS)这一重要概念。在开关函数最小化理论中,关于寻求质蕴含项的算法的研究已有很长历史了。卡诺图法简单易行,但一般只适用于变量少于6的布尔函数。Quine-McClusky算法本质上是列表化简法。它借助于coosensus运算求出全部PIS。虽然经过Petrick、Tilson等