一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.     

模糊膜计算模型与应用研究综述

膜计算是由生物细胞(群)相关机理启发的一类分布式、并行计算模型.膜计算模型已被证明是强大的并且以多项式时间复杂性求解众多的NP(non-deterministic polynomial)问题.膜计算模型与算法是膜计算领域的核心关键问题,特别是面向应用问题的模型和算法.模糊膜计算是近年开发的一种膜计算模型,它能克服先前模型在处理不确定性问题上的限制,得到极为广泛的关注.目前,模糊膜计算模型已在诸如电力系统故障诊断、微网控制中得到应用.首先简要地介绍几种模糊P系统,然后描述它们在工程问题中的应用.     

广义分子计算模型在整数问题中的应用

分子计算是一种新型的并行计算模式. 作为信息载体和计算载体的DNA,生化反应时存在不可控性. 构建具有通用性的分子计算机存在许多困难和限制. 将分子计算黏贴模型与图灵机相结合,已提出一种不依赖于特定生物技术的广义分子计算模型(generalized turing model,GTM). 对GTM模型进行扩展,通过实验说明了该广义分子计算机能够在多项式时间内求解NP完全的整数规划问题,该模型具有编码简单、错误率低等特点.     

膜计算在图像处理领域应用研究综述

随着计算机与信息技术的高速发展,图像处理已深入到各行各业,海量数据以及复杂算法所面临的高速实时处理成为图像处理领域急需解决的问题.膜计算是由生物细胞(群)相关机理启发的一类分布式、并行计算模型,已被证明能以多项式时间求解计算难问题.综述膜计算在图像处理领域中的应用,着重从图像低层处理(图像平滑、骨架提取)和中层处理(图像分割、立体匹配、图像配准、图像分解与重建)两方面对膜计算在图像处理领域的应用进行了介绍和分析,并给出了膜计算应用于图像处理领域的今后可能的发展方向.     

构建复杂Dixon矩阵递归算法的改进

针对多于5个变元的复杂多项式系统的Dixon矩阵的构建问题,基于递归算法提出了一种改进算法.采用动态规划的思想,自下而上地构建Dixon矩阵,避免了Dixon多项式的重复计算,并给出了使用该算法计算Dixon矩阵的具体实例.该算法与递归算法一样,可以在同样的计算平台上处理其他方法所不能解决的一些复杂多项式系统求解问题,但与递归算法相比,减少了须要计算的Dixon多项式的数量,提高了计算效率.     

基于Maple的原根及本原多项式的计算

在数论中,求解整数的原根和多项式的本原多项式是比较复杂的问题.本文应用Maple数学软件给出了求解它们的通用程序,大大的简化了此类问题的计算.例证表明Maple在计算原根和本原多项式的有效性.     

通讯膜计算系统研究综述

膜计算是自然计算的一个分支,文章主要研究从活细胞的结构和功能中或从组织和器官等细胞群协作中抽象的计算模型.根据膜结构不同,膜计算系统可以分为细胞型膜系统(树状结构)和组织型膜系统或脉冲神经膜系统(任意图结构).细胞间的通讯是膜系统中的一个重要特征,文章讨论的通讯规则是指同向/异向规则,对细胞型和组织型通讯膜系统的研究现状进行概述,从计算能力和计算复杂性方面介绍这2类通讯膜系统的研究进展.最后给出通讯膜系统中存在的一些问题.     

交互式马尔科夫链上弱模拟关系的计算

对交互式马尔可夫链模型(IMCs)上的弱模拟前序关系的计算算法进行讨论.在IMCs上判断弱模拟关系时,重点对概率转移关系进行弱模拟前序关系的判断,同时考虑内部动作对系统的影响.通过引入适当的变量,将IMCs上弱模拟定义中的马尔可夫转移条件转化为求解一个线性规划问题的解.利用该线性规划问题的数值求解方法,可在多项式时间内求得该线性规划问题的解.从而得到判定IMC上两个进程是否弱模拟的多项式时间算法.     

三维地电体的静电场数值计算

为解决直流电法中三维地电体静电场的计算问题,通过静电类比,把稳定电流场的计算换为相应的静电场计算,再利用模拟电荷法求解.采用模拟电荷法建立了可以模拟稳定电流场的方程组,利用点电荷作为模拟电荷解决了三维地电体静电场数值模拟问题,编制了模拟计算程序.对球体这一典型的地电模型进行了模拟,结果与理论值相比较理想.该算法解决了以往求解静电场算法复杂、剖分困难等问题,可为电法勘探的正反演理论研究提供依据.     

时间因素对脉冲神经膜系统计算能力的影响

脉冲神经膜系统是一类分布式并行的神经网络计算模型.从模型的研究着眼点来看,脉冲神经膜系统是一类全新的脉冲神经网络模型,属于第三代神经网络计算模型的研究范畴.通过分析评述脉冲神经膜系统中时间因素对其计算能力影响,讨论了异步工作模式下,时间以及时间无关模式下的脉冲神经膜系统的计算能力不会减弱,即具有图灵通用性.这些结果可为脉冲神经膜系统进行模糊信息处理提供理论支持,也可为基于脉冲神经膜系统的离散时间建模方法提供可行性论据.最后,针对目前该领域研究的热点和难点,对该领域研究的公开问题和研究方向进行讨论.     

利用谱元法计算弹性波场的若干理论问题

近来在解决弹性动力学问题中新发展起来的谱元法是一种基于组成整个研究区域的单元Galerkin算法, 并利用弹性波动力学方程的弱形式进行数值求解的方法. 针对求解弹性波动方程的谱元法中的若干数学问题以及相关的算法原理进行了系统研究, 介绍了Legendre 和Chebyshev多项式构造的基函数及其用在参考元上数值积分的Gauss-Lobbatto配置点, 推导了在利用Legendre和Chebyshev多项式展开时的单元积分的具体表达式. 在声阻抗差别很大的非均匀介质中, 通过引入空间域中在预先条件下的共轭梯度的元到元算法和时间域中时间积分的交错网格的预期/多次校正算法, 谱元法不需要形成有限元中的全局矩阵和有效载荷矢量, 能够在很大程度上提高计算精度和计算效率. 另外, 在某些情况下, 如果再利用单元积分的解析式, 也不需要形成单元矩阵, 由于采用解析式, 计算中可以节约大量内存而不会损失太多计算效率. 元到元算法中使用了最优的张量乘积技术, 使得该方法比有限元法在内存需求量和计算时间等方面更为有效.     

基于CUDA并行平台实现核膜系统求解可满足性问题的研究

膜系统能以空间换时间的方式在多项式时间内求解NP难问题,作为膜系统中的一个新类型,核膜系统不仅包含了不同类型膜系统的特征,而且能提供一种统一性的描述．因此基于核膜系统构建系统模型,并以此求解一个典型的NP难问题：可满足性问题．为了加速对核膜系统的仿真过程,程序将在CUDA并行方式下仿真实现,通过与传统的串行方式比较,使用CUDA能减少95％的仿真时间,这也表明使用CUDA并行方式非常适合仿真核膜系统．     

基于定长操作数的算术膜计算系统

将膜系统看作8位处理器,利用十进制位置编码的原码、反码及补码的概念和计算方法,设计了算术膜计算(P)系统,实现了加(减)、乘、除4种运算.由于系统中操作对象数量减少,该算术P系统更容易实现大数的运算.而且,设计的算术P系统充分利用膜系统并行运算的特征,具有多项式时间复杂度.     

膜计算研究综述

膜计算作为自然计算的一个分支,目的便是从生物细胞的结构与功能中以及从器官和组织等细胞群的协作中抽象出计算模型.膜计算发展至今,主要包括类细胞膜系统、类组织膜系统以及类神经膜系统三种基本的计算模型.在计算的过程中,每个细胞作为一个独立的单元,各个单元之间独立运行,互不干扰,整个膜系统以极大并行模式运行.目前关于膜计算的研究有很多,但是大部分都是停留在理论研究层面,关于膜计算的应用研究依然比较少.本文首先介绍了膜计算的三种膜系统的基本概念,然后分别从理论研究、应用研究和软硬件实现研究三个层面,针对近年的细胞型、组织型和神经型膜系统研究进展进行综合概述.最后给出了膜计算现存的问题以及研究前景.     

Clar覆盖多项式的直接计算

介绍一种利用计算机直接计算Ｃｌａｒ覆盖多项式的方法．这个方法使用图形界面输入要求解的六角系统,并引进适当的算法,最终直接输出相应的Ｃｌａｒ覆盖多项式,从而克服了对于较大的复杂六角系统存在的计算困难     

NP-完全性与限制性分拆

一、引言 可以利用不确定的图林机(Turing Machine)在多项式时间内解决的问题称为NP-问题。在这类问题中,有些问题具有这样的性质:所有NP-问题都可以经过多项式的时间转化为这些问题。我们称这些问题为NP-完全的。例如,众所周知的“货郎担”问题就是一个NP-完全问题。人们认为NP-问题是否可解是当代数学和计算机科学中尚未解决的重大问题。     

双时间尺度电-气耦合网络动态潮流计算

为了解决综合能源系统导在时间尺度上存在显著差异,以及网络潮流计算计算时间长和难度大的问题.通过kiuchi隐式方法,建立电-气网络的动态模型,求解天然气管道的动态潮流方程;并基于奇异摄动理论建立了燃气轮机的摄动模型,提出了一种多时间尺度特性的动态潮流算法.最后,对IEEE-9节点电力系统和3节点的天然气网络的耦合多能系统中进行仿真验证.结果表明:通过使用多时间尺度计算方法可以有效减少计算时间,并且燃气轮机入口流量变化会影响天然气网络潮流分布.     

基于膜计算模型的数独游戏基本解法

为了更好地求解数独问题,提出了一种新的求解方法,利用一个具有抑制催化和膜溶解规则以及进化规则的优先级的膜系统来进行求解;结果表明,对于一个数独问题,只要其所有部分解都至少包含一个具有唯一解的单元格,方法都是有效的;如果数独问题可以利用此策略求解,则膜系统在计算的最后一步将问题的解编码并返回物质YES,否则,膜系统可以检测出数独问题不符合上述特征,返回物质NO,计算停止;方法求解策略与人类求解数独问题的思考过程非常类似,并且给出的是数独问题的统一解,即与数独问题的维度和提示数无关。     

基于L1范数和现代内点理论的电力系统潮流计算

利用L1范数把电力系统潮流方程的求解转化为对一个新的非线性规划模型L1LF的求解.在基于原问题的扰动Karush-Kuhn-Tucker(KKT)条件基础上,导出了求解L1LF模型的内点算法公式.仿真结果显示,L1LF模型结构简洁、直观,编程应用方便.新算法计算结果正确,收敛性好.和常规潮流算法相比,新模型和新算法有效解决了病态系统潮流计算发散的问题,为给定条件下的潮流问题是否有解提供了一个新的判断途径.     

最大独立集问题的表面计算模型

DNA计算是解决一类难于计算问题的一种新方法,最大独立集问题是一个著名的NP完全问题,最大团问题及最小覆盖问题等价于最大独立集问题。本文中,我们尝试将最大独立集转化为0-1规化问题,利用0-1规化问题的表面计算模型求解最大独立集。本文充分说明了NP-完全问题可以相互转化的性质。