一类多机排序问题算法及其计算复杂性研究

在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。     

新计算范例

近年来，经典的可计算性已被扩展到处理与代数、分析和物理学中可计算性和复杂性相关的问题。本书以数学的观点研究了计算理论和实践的新发展，涉及的课题范围从经典的可计算性到复杂性，从生物计算到量子计算。     

KNA算法计算复杂性分析

分析了ＫＮＡ算法的计算复杂性，证明了当扰动项足够小时，ＫＮＡ算法是多项式时间算法．     

能行可计算性函数渐进优超等价类的可达性质

利用理想计算机URM关于能行可计算性函数的定义以及渐进分析的方法对能行可计算性函数进行分类后，建立了能行可计算性函数渐进优超等价类子结构，并通过引进可达性概念研究能行可计算性函数渐进优超等价类之间的关系，证明了任何一致无界能行可计算性函数渐进优超等价类都具有强不可达性质。此成果对算法复杂性函数渐进优超等价类数学结构的进一步研究有一定参考价值。     

有理数理论的计算复杂性

本文讨论了有理数理论的复杂性，通过构造精确的判定过程，从而确定了有理数理论的计算复杂性上界．     

算法可解问题计算复杂性分析的新思路

计算时间下界的传统的方法是直接从算法的ＡＤＴ高度来分析或借助于问题的变换来分 析．本文提出估计算法计算时间下界的一条新思路，借助于问题的嵌入来分析计算时间下界．由此 可获得一些传统方法不易得到的结果．     

Co-regular集的可计算性探讨

引入了在TTE框架下,利用开集和闭集的表示式,定义了度量空间中co-regular集的若干不等价表示式;并对这些表示式的强弱关系进行了论证。研究表明:这些表示式的强弱,有一个明确的顺序;在被引入的不等价表示式中,η:=θ<∧ψ>是co-regular集所有表示式中最强的。     

2种产品选址问题的计算复杂性浅析

产品选址问题是组合优化中一类有重要理论意义和广泛实际背景的问题。问题的要求是要从若干厂址中选择一组厂址来建立工厂,给每个工厂指定一种需要生产的产品,并且给每一个客户提供一组指派使每个客户都能有一组工厂集合来为其供应不同的产品。对于此类问题,我们的优化目标是最小化运输费用。该问题模型在网络设施的安放、网格服务点的分布等诸多方面有着大量的应用。文中对2种产品选址问题的计算复杂性进行了分析。     

原子布尔代数理论的计算复杂性

运用Ｅｈｒｅｎｆｅｕｃｈｔ Ｇａｍｅｓ理论给出原子布尔代数理论的一个判定过程及其复杂度,并说明这个过程在初等等价意义下是最优的。     

完备布尔代数理论的计算复杂性

运用改进的Ｅｈｅｒｎｆｅｕｃｈｔ ｇａｍｅｓ理论,适当定义了范数和囿函数,给出了无原子布尔代数理论的一个判定过程,利用这个结果,直接构造出完备布尔代数的判定过程,并且分析了它们的复杂度。     

带记忆的Boyer-Moore型模式匹配算法及其复杂性分析

通过构建前缀匹配自动机,使得每轮匹配后下个匹配窗口的文本总是保持左端部分为模式的一个前缀、右端部分全为未比较过的字符的形式.对于与此相应的模式匹配算法,已证明文本内的每个字符在整个匹配过程中最多被比较一次,从而字符总比较次数不超过n,已达到任意算法最坏情况下字符总比较次数的最小值.另外,在适当条件下还从理论上证明了此算法的亚线性(即字符总比较次数小于cn,其中常数c＜1).根据实验结果,算法的实际运行速度快于Boyer-Moore算法.     

计算复杂性

纵观历史，人们对在有限的步骤内从一组输入中产生一个输出这一过程具有模糊的概念，他们认为“计算”是一个人遵循某些规则随意进行的过程。20世纪前50年中一个重要的科学进步就是“计算”这个概念获得了更为准确的定义。基于这个定义，计算可能发生在各种物理及数学系统中，这一点很快就变得很明确。     

复杂性研究思想——物质、精神和人的计算动力学 第四版

非线性复杂系统理论逐步被认为是从激光物理到生物细胞生长再到计算机仿真这些自然科学问题的解决之道。现在人们认识到：我们的社会、生态和政治问题也是一个个全局复杂非线性“自然”，甚至人的精神在很大程度上被认为是由复杂系统非线性动力学支配的。[第一段]     

粗糙集计算方法及应用研究

研究总结了粗糙集计算方法新进展,同时对它们的计算复杂性进行了分析,并给出了这些计算方法之间的逻辑关系结构图,然后讨论了粗糙集在模型方面的扩展,最后对粗糙集计算方法的应用进行了论述.     

关于桥牌的取胜策略

在桥牌运动中,若将四家的牌摊开来打,则存在判定初始牌局是否为南北方胜牌局(或东西方胜牌局)的算法,当南北方(或东西方)客观上存在取胜策略时,则存在算法来实现其取胜步骤．给出的算法不仅在可计算性意义上是最好的算法,并且计算量小．     

规则计算——探索复杂性的有力模式

自然界中存在着许许多多的复杂系统，这些系统的每一部分的结构可以非常简单，但由于各部分之间存在一定的耦合，最终表现出系统的整体性态极其复杂．基于规则计算的元胞自动机为模拟自然现象和生命现象提供了新的思路和方法，成为探索复杂系统的一种有力模式论文介绍了规则计算的产生和发展，着重阐述了规则计算的本质，并对自下而上的基于规则的建模方法中存在的一些问题进行了总结与展望．     

递归程序的复杂性问题

递归是一种程序设计方法。递归算法能将很复杂的问题用十分简洁的形式加以表达。然而递归程序的复杂性很高,所以通常光用递归程序描述问题,然后设法变换为效率较高的程序。本文给出计算递归程序复杂性的公式,并讨论了降低递归程序复杂性的几种方法。     

复杂性与密码学——引论

自古以来，密码加密与分析一直就是军事、外交领域不可少的工具。它在很大程度上是门艺术。1948年到1949年，Shannon建立了信息论基础，同时开创了编码理论和密码学。前者解决信息传输的效率和不失真问题，后者解决信息的保密和安全问题。1976年，公开密钥体制出现是密码学第二次革命。在此之前，密码学称为古典密码学，它与复杂性理论基本上没什么关系。其后的密码学是建立在复杂性理论的基础上，也就是从算法复杂性的观点来研究密码的安全性，称为现代密码学。     

大数据计算的基础理论探究

在经典计算中,对前端输入数据的复杂性不做分析。在大数据计算中,前端输入数据的复杂性分析反而成为大数据计算和分析的重点。本文讨论大数据计算的基础理论问题,将大数据计算问题分为目标任务型和内容认知型。大数据计算形式上依赖于一个外部信息源,从计算的有效性,将大数据计算的讨论限制在对数空间复杂类,涵盖了并行计算复杂类。基于带Oracle的图灵计算模型,限制在对数空间内图灵可计算,并且外部信息源能够用一个对数空间可计算的递归函数枚举,引入了大数据可计算的计算模型和大数据可计算性、可判定问题等概念。