首页期刊导航|计算机科学
期刊信息/Journal information
计算机科学
计算机科学

朱完元

月刊

1002-137X

jsjkx12@163.com

023-63500828

401121

重庆市渝北区洪湖西路18号

计算机科学/Journal Computer ScienceCSCD北大核心CSTPCD
查看更多>>本刊的读者对象是：大专院校师生，从事计算机科学与技术领域的科研、生产人员。办刊宗旨是：坚持“双百”方针，活跃计算机科学与技术领域的学术气氛，重点报导国内外计算机科学与技术的发展动态，为我国的计算机科学与技术立于世界之林、达到国际先进水平奋斗而矢志不渝。
正式出版
收录年代

    约束进化算法及其应用研究综述

    李笠李广鹏常亮古天龙...
    1-13页
    查看更多>>摘要：约束优化问题广泛存在于科学研究和工程实践中,其对应的约束优化进化算法也成为了进化领域的重要研究方向.约束优化进化算法的本质问题是如何有效地利用不可行解和可行解的信息,平衡目标函数和约束条件,使得算法更加高效.首先对约束优化问题进行定义;然后详细分析了目前主流的约束进化算法,同时,基于不同的约束处理机制,将这些机制分为约束和目标分离法、惩罚函数法、多目标优化法、混合法和其他算法,并对这些方法进行了详细的分析和总结;接着指出约束进化算法亟待解决的问题,并明确指出未来需要进一步研究的方向;最后对约束进化算法在工程优化、电子和通信工程、机械设计、环境资源配置、科研领域和管理分配等方面的应用进行了介绍.

    工程实践约束优化问题进化算法约束优化进化算法约束处理机制

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    高效计算因果网中的最大可能解释

    李超覃飙
    14-19页
    查看更多>>摘要：在因果网中,高效计算的最大可能解释(Most Probable Explanations,MPE)是一个关键问题.从有向无环图的角度,研究者们发现每一个因果网都有一个与之对应的贝叶斯网络.文中通过比较干预和微分的语义,揭示了MPE完全原子干预的微分语义.根据微分语义,因果网中原子干预MPE实例的计算可以归约为贝叶斯网络中的MPE实例的计算.接着,提出了一个联合树算法(Best JoinTree,BJT),它通过在因果网中只构建一个联合树来计算最好的原子干预,原子干预的结果包含一个BMPE(Best MPE)概率和它对应的实例.其中,BMPE概率是对MPE所有结点分别进行原子干预后得到的最高概率.BJT可以采用干预的效果来计算对应贝叶斯网络的MPE概率和MPE实例.最后,实验证实了绝大多数因果网在计算最好原子干预时,BJT的速度比目前最好的算法快了超过10倍.

    因果网贝叶斯网络干预微分MPEMPE实例

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    基于Grover搜索算法的整数分解

    宋慧超刘晓楠王洪尹美娟...
    20-25页
    查看更多>>摘要：非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的.Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统.文中提出基于Grover搜索算法并结合经典预处理实现整数分解.首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率.仿真结果验证了使用Grover算法求解素因子P和Q的可行性.文中实现了在搜索空间为16且一次G迭代条件下以近78％的成功概率搜索到目标项.文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异.通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显.

    Grover算法VQF算法IBMQ整数分解Shor算法

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    正则(3,4)-CNF公式的社区结构

    何彬许道云
    26-30页
    查看更多>>摘要：通过构造适当的极小不可满足公式以实现在多项式时间内将3-CNF公式归约转换为一个正则(3,4)-CNF公式,转换后的公式与原公式具有相同的可满足性,同时公式的结构也发生相应的变化.图的社区结构反映了图的模块特性,文中将CNF公式转化为相应的图,研究公式图的模块特性与公式某些性质之间的关系.将归约前后的两类公式转换为相应的图并研究其模块特性,发现转换后得到的正则(3,4)-CNF公式具有较高的模块度.此外,在使用DPLL(Davis Putnam Logemann Loveland)算法求解CNF公式的过程中,发生冲突时利用冲突驱动子句学习策略,得到一个学习子句并将其添加到原公式中,使得原公式的模块度降低.研究发现:将DPLL算法与冲突驱动子句学习策略结合应用到正则(3,4)-CNF公式时,其学习子句所包含的绝大部分变元位于不同的社区中.

    SAT问题DPLL正则(3,4)-CNF公式社区结构模块度

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    模糊安全性和活性

    石铁柱钱俊彦潘海玉
    31-36页
    查看更多>>摘要：形式规约使用形式语言构建所开发的软硬件系统的规约,刻画系统的模型和性质.其中,性质规约中的分支时间规约对于系统验证有着非常重要的作用.在经典情形下,系统性质规约是基于二值逻辑的,不能描述不一致或不确定的信息.因此,将其推广到模糊逻辑背景下,有助于对模糊系统进行形式验证.文中首先给出了性质规约中分支时间属性在模糊背景下的形式化定义,重点研究了其中的安全性和活性;然后,定义了两种闭包操作,从而产生了4种类型的属性,即泛安全性、泛活性、存在安全性和存在活性;最后,证明了每个分支时间属性,或是存在安全性和存在活性的交,或是泛安全性和泛活性的交,或是存在安全性和泛活性的交.

    形式规约模糊逻辑分支时间属性安全性活性

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    针对经典排序问题的一种新算法的近似比分析

    高吉吉岳雪蓉陈智斌
    37-42页
    查看更多>>摘要：给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题.如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案.Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配.该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法.文章在此基础上,考虑该新算法在一般问题上的近似比.文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2q(q∈Z+)的近似比.紧例子表明,文中对算法的两个版本的分析都是最优的.

    经典排序近似算法多项式时间算法紧例子一维装箱问题

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    (n,k)-冒泡排序网络的子网络可靠性

    冯凯马鑫玉
    43-48页
    查看更多>>摘要：并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用.为了精确度量基于(n,k)-冒泡排序网络构建的并行计算机系统的子网络容错能力,建立了(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络与特定字符串之间的一一对应关系,研究了点故障模型下(n,k)-冒泡排序网络中(n-m,k-m)-冒泡排序子网络的可靠性.当2≤k≤n-2,1≤m≤k-1时,首先在概率故障条件下给出了(n,k)-冒泡排序网络中存在无故障的(n-m,k-m)-冒泡排序子网络的概率估计,并通过仿真实验验证了所得结果的精确性;其次,得出了不同数目的(n-m,k-m)-冒泡排序子网络保持无故障状态的平均失效时间的计算公式,仿真实验表明理论结果与仿真结果趋于一致.

    并行计算机系统互连网络(n,k)-冒泡排序网络子网络可靠性概率故障平均失效时间

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    三种近似算子之间的关系

    鲁巡李妍妍秦克云
    49-53页
    查看更多>>摘要：在广义近似空间中,可以从对象、知识粒以及子系统的角度构造3种不同类型的广义粗糙近似算子.文中研究了这些近似算子的基本性质与相互关系,给出了3类近似算子相同的充要条件.另外,不同的近似空间可能生成相同的基于知识粒及基于子系统的近似算子,文中给出了不同二元关系生成相同近似算子的一些充要条件.

    广义近似空间近似算子左、右邻域

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    基于不相关属性集合的属性探索算法

    沈夏炯杨继勇张磊
    54-62页
    查看更多>>摘要：作为形式概念分析理论中的一个重要工具,属性探索算法能够以问题为导向,交互式地逐步发现系统知识,在知识的发现和获取中居于核心地位.但是,当形式背景的规模较大时,属性探索算法的计算过程过于耗时,严重制约了算法在当前大数据时代的推广与应用.耗时瓶颈主要存在于"寻找下一个与专家交互的问题"这一环节,传统算法在此过程中存在大量冗余计算.针对这个问题,在分析伪内涵和内涵与蕴涵集合的内在逻辑关系的基础上,提出并证明了3个定理,根据定理给出了一种基于不相关属性集合的属性探索算法,该算法在计算伪内涵与内涵的过程中,借助提出的定理,跳过违反该逻辑关系的属性集合是否为伪内涵或者内涵的判断过程,减小了算法的搜索空间,从而降低了算法的时间复杂度.所提算法最好的时间复杂度为O(mn 2 P 2),最坏的时间复杂度为O(mn 3 P 2).实验结果表明,与传统算法相比,该算法具有较为明显的时间性能优势.

    形式概念分析伪内涵关联规则属性探索概念格知识发现

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据

    基于双时态RDF模型的索引方法

    王引娣章哲庆严丽
    63-69页
    查看更多>>摘要：RDF(Resource Description Framework)已被广泛用于大数据的语义表示与处理.传统的RDF只能表示静态语义,无法满足时间敏感场景下随时间动态处理语义的需求.为此,几种时态RDF模型已被提出,包括支持事务时间或有效时间的时态RDF模型,以及同时支持事务时间和有效时间的双时态RDF模型.为有效支持大规模时态RDF的高效处理,文中提出了一种基于双时态模型的时态RDF三层索引结构.第一层根据最大更新次数将双时态RDF数据划分为不同的数据子集;第二层在每一个数据子集上分别建立一棵四叉树来索引时间信息;第三层构建了包含3种组合键的复合位图来索引RDF三元组的主体、谓词和客体信息.实验从索引构建时间、索引占用空间,以及查询所需时间3个方面对所提时态RDF索引结构进行验证,结果表明,所提索引方案能有效缩短查询时间并提高查询效率.

    RDF时态信息三层索引四叉树位图索引

      原文链接:
    • NETL
    • NSTL
    • 维普
    • 万方数据