1974年1月创刊(月刊)
主管/主办:重庆西南信息有限公司
ISSN 1002-137X
CN 50-1075/TP
CODEN JKIEBK
编辑中心
    计算机科学理论 栏目所有文章列表
    (按年度、期号倒序)
        一年内发表的文章 |  两年内 |  三年内 |  全部
    Please wait a minute...
    1. 高效计算因果网中的最大可能解释
    李超, 覃飙
    计算机科学    2021, 48 (4): 14-19.   https://doi.org/10.11896/jsjkx.200500155
    摘要 (234)   PDF (1497KB) (434)  
    在因果网中,高效计算的最大可能解释(Most Probable Explanations,MPE)是一个关键问题。从有向无环图的角度,研究者们发现每一个因果网都有一个与之对应的贝叶斯网络。文中通过比较干预和微分的语义,揭示了MPE完全原子干预的微分语义。根据微分语义,因果网中原子干预MPE实例的计算可以归约为贝叶斯网络中的MPE实例的计算。接着,提出了一个联合树算法(Best JoinTree,BJT),它通过在因果网中只构建一个联合树来计算最好的原子干预,原子干预的结果包含一个BMPE(Best MPE)概率和它对应的实例。其中,BMPE概率是对MPE所有结点分别进行原子干预后得到的最高概率。BJT可以采用干预的效果来计算对应贝叶斯网络的MPE概率和MPE实例。最后,实验证实了绝大多数因果网在计算最好原子干预时,BJT的速度比目前最好的算法快了超过10倍。
    参考文献 | 相关文章 | 多维度评价
    2. 基于Grover搜索算法的整数分解
    宋慧超, 刘晓楠, 王洪, 尹美娟, 江舵
    计算机科学    2021, 48 (4): 20-25.   https://doi.org/10.11896/jsjkx.200800117
    摘要 (297)   PDF (2269KB) (806)  
    非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的。Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。文中提出基于Grover搜索算法并结合经典预处理实现整数分解。首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子PQ;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率。仿真结果验证了使用Grover算法求解素因子PQ的可行性。文中实现了在搜索空间为16且一次G迭代条件下以近78%的成功概率搜索到目标项。文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异。通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显。
    参考文献 | 相关文章 | 多维度评价
    3. 正则(3,4)-CNF公式的社区结构
    何彬, 许道云
    计算机科学    2021, 48 (4): 26-30.   https://doi.org/10.11896/jsjkx.201000178
    摘要 (206)   PDF (1433KB) (316)  
    通过构造适当的极小不可满足公式以实现在多项式时间内将3-CNF公式归约转换为一个正则(3,4)-CNF公式,转换后的公式与原公式具有相同的可满足性,同时公式的结构也发生相应的变化。图的社区结构反映了图的模块特性,文中将CNF公式转化为相应的图,研究公式图的模块特性与公式某些性质之间的关系。将归约前后的两类公式转换为相应的图并研究其模块特性,发现转换后得到的正则(3,4)-CNF公式具有较高的模块度。此外,在使用DPLL(Davis Putnam Logemann Loveland)算法求解CNF公式的过程中,发生冲突时利用冲突驱动子句学习策略,得到一个学习子句并将其添加到原公式中,使得原公式的模块度降低。研究发现:将DPLL算法与冲突驱动子句学习策略结合应用到正则(3,4)-CNF公式时,其学习子句所包含的绝大部分变元位于不同的社区中。
    参考文献 | 相关文章 | 多维度评价
    4. 模糊安全性和活性
    石铁柱, 钱俊彦, 潘海玉
    计算机科学    2021, 48 (4): 31-36.   https://doi.org/10.11896/jsjkx.200500036
    摘要 (108)   PDF (1410KB) (234)  
    形式规约使用形式语言构建所开发的软硬件系统的规约,刻画系统的模型和性质。其中,性质规约中的分支时间规约对于系统验证有着非常重要的作用。在经典情形下,系统性质规约是基于二值逻辑的,不能描述不一致或不确定的信息。因此,将其推广到模糊逻辑背景下,有助于对模糊系统进行形式验证。文中首先给出了性质规约中分支时间属性在模糊背景下的形式化定义,重点研究了其中的安全性和活性;然后,定义了两种闭包操作,从而产生了4种类型的属性,即泛安全性、泛活性、存在安全性和存在活性;最后,证明了每个分支时间属性,或是存在安全性和存在活性的交,或是泛安全性和泛活性的交,或是存在安全性和泛活性的交。
    参考文献 | 相关文章 | 多维度评价
    5. 针对经典排序问题的一种新算法的近似比分析
    高吉吉, 岳雪蓉, 陈智斌
    计算机科学    2021, 48 (4): 37-42.   https://doi.org/10.11896/jsjkx.200600064
    摘要 (104)   PDF (1478KB) (204)  
    给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配。该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法。文章在此基础上,考虑该新算法在一般问题上的近似比。文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2q(q∈Z+)的近似比。紧例子表明,文中对算法的两个版本的分析都是最优的。
    参考文献 | 相关文章 | 多维度评价
    6. (n,k)-冒泡排序网络的子网络可靠性
    冯凯, 马鑫玉
    计算机科学    2021, 48 (4): 43-48.   https://doi.org/10.11896/jsjkx.201100139
    摘要 (121)   PDF (2173KB) (226)  
    并行计算机系统互连网络的拓扑性质对系统功能的实现起着重要的作用。为了精确度量基于(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)-冒泡排序子网络保持无故障状态的平均失效时间的计算公式,仿真实验表明理论结果与仿真结果趋于一致。
    参考文献 | 相关文章 | 多维度评价
    7. 三种近似算子之间的关系
    鲁巡, 李妍妍, 秦克云
    计算机科学    2021, 48 (4): 49-53.   https://doi.org/10.11896/jsjkx.200900089
    摘要 (119)   PDF (1316KB) (247)  
    在广义近似空间中,可以从对象、知识粒以及子系统的角度构造3种不同类型的广义粗糙近似算子。文中研究了这些近似算子的基本性质与相互关系,给出了3类近似算子相同的充要条件。另外,不同的近似空间可能生成相同的基于知识粒及基于子系统的近似算子,文中给出了不同二元关系生成相同近似算子的一些充要条件。
    参考文献 | 相关文章 | 多维度评价
    8. 基于不相关属性集合的属性探索算法
    沈夏炯, 杨继勇, 张磊
    计算机科学    2021, 48 (4): 54-62.   https://doi.org/10.11896/jsjkx.200800082
    摘要 (95)   PDF (1610KB) (233)  
    作为形式概念分析理论中的一个重要工具,属性探索算法能够以问题为导向,交互式地逐步发现系统知识,在知识的发现和获取中居于核心地位。但是,当形式背景的规模较大时,属性探索算法的计算过程过于耗时,严重制约了算法在当前大数据时代的推广与应用。耗时瓶颈主要存在于“寻找下一个与专家交互的问题”这一环节,传统算法在此过程中存在大量冗余计算。针对这个问题,在分析伪内涵和内涵与蕴涵集合的内在逻辑关系的基础上,提出并证明了3个定理,根据定理给出了一种基于不相关属性集合的属性探索算法,该算法在计算伪内涵与内涵的过程中,借助提出的定理,跳过违反该逻辑关系的属性集合是否为伪内涵或者内涵的判断过程,减小了算法的搜索空间,从而降低了算法的时间复杂度。所提算法最好的时间复杂度为O(mn2P2),最坏的时间复杂度为O(mn3P2)。实验结果表明,与传统算法相比,该算法具有较为明显的时间性能优势。
    参考文献 | 相关文章 | 多维度评价
    9. 哈密顿图判定问题的多项式时间算法
    姜新文
    计算机科学    2020, 47 (7): 8-20.   https://doi.org/10.11896/jsjkx.191200176
    摘要 (5031)   PDF (1760KB) (10050)  
    NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为MSP问题的新问题,文中提出了一个关于MSP问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到MSP问题的归结以及MSP问题到SAT问题的归结,因此MSP问题存在多项式时间算法这样一个研究结果对于研究NP=P有重要和积极的意义。
    参考文献 | 相关文章 | 多维度评价
    10. 一种基于模糊集和概率分布的不确定XML模型及其代数运算
    胡磊, 严丽
    计算机科学    2020, 47 (7): 21-30.   https://doi.org/10.11896/jsjkx.190700164
    摘要 (244)   PDF (1635KB) (621)  
    XML作为一种信息表示和交换的事实标准已被广泛用作不同应用之间的统一数据交换格式,其在实际应用中已经发挥着重要的作用。由于现实中很多信息包含有不确定性,而经典的XML不能表示和处理不确定信息,因此有必要对经典XML模型进行扩展。考虑到现实世界的复杂性,不确定信息往往同时包含有随机不确定性和模糊不确定,而概率理论和模糊集理论是处理不确定信息的有力工具,因此文中在现有的模糊XML和概率XML数据模型的基础上,综合利用概率和模糊理论建立一个新的不确定XML模型和相关代数,所提出的新的不确定性XML模型既能与现有的XML模型兼容,又能表达更复杂的不确定信息。
    参考文献 | 相关文章 | 多维度评价
    首页 | 前页| 后页 | 尾页 第1页 共2页 共19条记录