基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

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

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

基于批分离实验的最大独立集问题DNA算法

根据解决最大独立集问题的需要,讨论了简化的粘贴模型,该模型只由单链DNA的存储链和分离板组成.以分离实验为基础提出了批分离实验和生化操作过程,该实验可以快速分离存储链.基于批分离实验设计了最大独立集问题的DNA算法,并给出其生化实现过程:先形成所有顶点子集的初始解空间;接着用批分离实验对每个顶点进行检测,筛选全部满足不相邻要求的顶点子集,从而得到全部独立集;然后通过电泳实验得到全部最大独立集;最后通过检测实验输出实验结果.讨论并证明了算法的正确性和复杂性,算法的操作次数是线性的,通过仿真实验说明了算法的有效性和可行性.     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题。本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题,是第一个被证明是NPC的问题.本文主要把子句集进行分类,给出翻转定义、简单集定义,翻转同构定义,并且证明翻转同构不改变子句集的可满足性.论文证明了可满足子句集的三个充要条件.并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法.     

可满足性问题的充分必要条件

可满足性问题是计算机和人工智能领域内的一个重要的问题，是第一个被证明是NPC的问题。本文主要把子句集进行分类，给出翻转定义、简单集定义，翻转同构定义，并且证明翻转同构不改变子句集的可满足性。论文证明了可满足子句集的三个充要条件。并且这些充要条件可以用于判断可满足问题的完全搜索和不完全搜索算法。     

关于合取范式可满足性问题的复杂性分析

合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。     

抽象凸空间上广义博弈Nash平衡点的存在性

为了在满足H0-条件的抽象凸策略空间中,解决广义博弈中广义最大元对策与约束广义最大元对策的Nash平衡点的存在性问题,根据这两种对策中局中人的最优反应集值映射分别定义了两个对策的最优反应集值映射,利用抽象凸空间中的Fan-Glicksberg-kakutani不动点定理,证明了两个对策的最优反应集值映射均存在不动点,从而获得了广义最大元对策与约束广义最大元对策均存在Nash平衡点的结果.该成果对于用广义最大元方法研究广义博弈中的对策平衡具有一定的参考价值和指导意义.     

最大可满足性问题的算法研究综述

最大可满足性问题(maximum satisfiability,MaxSAT)是一个著名的、具有NP难度的组合优化问题.本研究总结了近年来求解最大可满足性问题的各类算法.首先,给出了最大可满足性问题的定义;然后,基于完备算法和非完备算法两个类型,对求解MaxSAT的各类算法进行了综述.其中完备算法包括分支定界算法和迭代...     

re-Horn子句集的Horn化及可满足性判定方法

在命题逻辑中给出将re-Horn子句转化成Horn子句的条件与方法,用同态的方法证明转化前后2个子句集的可满足性或不可满足性的一致性,给出re-Horn子句集的可满足性的判定方法。     

关于图的邻和可区别全染色的新方法

给出树的邻和可区别2-全染色方案,并结合三正则图最小消圈集的独立性以及消圈子图的无圈性,较为简洁地证明三正则图的邻和可区别全色数满足1-2猜想。进一步利用独立消圈集法确定r-正则图、Halin图以及路与路的笛卡尔乘积图的邻和可区别全色数。     

基于串行最大独立集的连通支配集构造及分析

针对传感器网络最大独立集的构造方法中并行构造算法生成的连通支配集尺寸没有明确的上界且难以确定边界节点的问题,在串行最大独立集构造算法的基础上,提出了基于权重和时序的触发式连通支配集构造算法.仿真结果表明:该算法无需构造生成树,降低了计算时延和通信开销;此外,由于最大独立集节点存在时间上的先后关系,因而使得边界节点的数量显著减少,最终求得的连通支配集存在明确的上界.     

布朗运动跑出时的光滑性

对布朗运动停时的光滑性进行了研究。运用函数的正交分解方法，证明了只需当分数次索伯列夫空间的可积性指标与可微性指标的积乘小于1这一条件满足时，布朗运动从某个开集的跑出时属于这个分数次索伯列夫空间，解决了以往证明过程中可积性指标受状态空间维数约束的问题。     

关于Erds的一个问题

讨论了Erds提出的关于图的最大完全图与最大独立集的一个问题。     

一种不一致本体的可废止推理系统

利用可废止逻辑的非单调知识表示和推理能力、线性的计算复杂性和易于实现等优点,整合描述逻辑和可废止逻辑,提出了一种不一致本体的可废止推理系统（简称为DeRS）.DeRS使用描述逻辑定义的本体和可废止理论对领域问题进行混合建模,将TBox划分为最大的一致公理集和最小的不一致公理集,并进行初始化;然后利用转换算法,将一致公理集的公理和不一致公理集的公理分别映射为硬性规则和可废止规则,并添加到可废止理论中;最后利用新定义的可废止推理规则进行非单调可废止推理,由此解决了不一致本体的推理问题,弥补了描述逻辑在非单调性方面的不足.结果表明DeRS具有协调性、易处理性、可判定性、可靠性等基本性质.     

集值测度的Orlicz-Petis定理及其应用

建立了集值情况的ＯｒｌｉｃｚＰｅｔｉｓ定理,从而解决了集值测度的强可加问题,集值函数弱可列可加的充要条件;在集值测度σ有界变差条件下给出集值测度的凸性定理     

图的最大独立集数上界

本文记明了简单连通图的最大独立集数上界定理和与图的最大独立集有关的其它几个定理。这些定理为构造求图的最大独立集的启发式算法奠定了基础。     

最大独立集在高校排课表系统中的应用

在分析排课系统特征的基础上,利用图论中最大独立集的理论,对排课资源进行合理抽象并建模,实现自动排课的功能要求,并进行算例分析.算例分析表明,该方法解决排课表问题相当实用,而且效率较高.该方法具有效性和可靠性.     

可满足性问题的基于芯片的DNA计算模型

生物芯片计算是近些年来DNA计算的新兴研究领域,其本质特性是对信息高度的处理和高度并行性。可满足性问题是NP-完全问题中一类重要的问题,本文在DNA芯片的基础上提出利用DNA芯片解决可满足性问题的DNA计算模型。