计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2016年第12期杂志 文档列表

计算机学报杂志量子计算、计算机理论与算法

量子计算复杂性理论综述2403-2428

摘要：量子计算复杂性理论是量子计算机科学的基础理论之一,对量子环境下的算法设计和问题求解具有指导意义.因此,该文对量子计算复杂性理论进行了综述.首先,介绍了各种量子图灵机模型及它们之间的关系.其次,量子计算复杂性是指在量子环境下对于某个问题求解的困难程度,包含问题复杂性、算法复杂性等.于是,该文介绍了量子问题复杂性、量子线路复杂性、量子算法复杂性,并且介绍了量子基本运算和Shor算法的优化实现.第三,格被看做是一种具有周期性结构的n维点空间集合.格密码有很多优势,包括具有抗量子计算的潜力,格算法具有简单易实现、高效性、可并行性特点,格密码已经被证明在最坏条件下和平均条件下具有同等的安全性.因此该文介绍了格的困难问题,以及主要的格密码方案现状.最后,对今后值得研究的一些重要问题和量子计算环境下的密码设计与分析给出了展望.

通用量子计算机：理论、组成与实现2429-2445

摘要：通用量子计算机是指可以在不改变量子计算机物理组成和基本体系结构的条件下针对所有可计算问题进行量子计算及其它量子信息处理的设备.通用量子计算机的研究和制造具有重要的理论和实际意义.要达成制造通用量子计算机的目标,需要在底层量子物理设备、量子计算机体系结构、量子资源调度和上层量子程序设计语言、量子算法及量子应用软件等多方面进行努力.文中结合国内外在上述各方面研究的最新进展以及作者自身的研究结果,从计算机系统的角度为通用量子计算机的研究和制造绘制一幅蓝图,并详细阐述了其中的困难与努力方向.

开放量子行走：概率分布与中心极限定理2446-2459

摘要：作为量子算法研究的一个基本工具,量子行走已经成为一个重要研究课题.在开放量子环境下,同质量子行走已经得到充分研究,包括其概率分布和中心极限定理.然而,对于高维格上且在异质环境下的开放量子行走的演化方程、概率分布和中心极限定理还未得到研究.在此基础上,该文提出高维格上异质开放量子行走以及它的演化方程,重点研究高维格上具有不同类型的量子运算的开放量子行走的概率分布和中心极限定理.首先给出高维格上量子系统的演化表达式,它不但适合于同质开放量子行走,也适合于异质开放量子行走.与已有的演化表达式相比,该结果更具有一般性.其次,利用傅里叶变换和逆变换给出开放量子行走的概率分布的计算公式,研究其对同质开放量子行走和异质开放量子行走的适用性.通过例子说明一维格上、二维格上异质开放量子行走的概率分布计算.最后,运用鞍差分序列中心极限定理,给出并证明高维格上异质开放量子行走的中心极限定理,说明一维格上同质开放量子行走的中心极限定理是它的一种特殊情况,并通过二维格上异质开放量子行走的实例给出求解极限分布的具体过程.

形状图理论的定理证明2460-2480

摘要：验证操作易变数据结构的指针程序仍面临很多挑战.数据结构中严重的指针别名显著地复杂化对操作这些结构的程序的推理.为分析和验证操作易变数据结构的指针程序,文中提出了形状图逻辑.形状图是描述程序中静态声明的堆指针变量和动态分配的结构体中指针域变量的指向的一种有向图,能准确表达指针的有效性和指针之间的相等性,可用于判断两个访问表达式是否是别名.形状图逻辑是Hoare逻辑的一种扩展,是一种直接将形状图作为程序中指针断言集的程序逻辑.该文研究形状图的等价理论和蕴含理论以及它们的判定方法和应用.首先,把形状图及其等价规则和蕴含规则分别类比为代数项及其等式规则和重写规则,像研究代数规范的理论那样来研究形状图理论.该文定义了形状图的语法理论和语义理论,定义了形状图重写系统及其终止性、局部合流性和合流性,然后得到基于形状图重写的形状图等价判定和蕴含判定的方法.其次,提出循环不变形状图和递归函数前后形状图的自动推断方法.借助形状图理论的判定方法,该文把一个基于抽象解释的推断循环不变式的一般方法改编成推断循环不变形状图的方法.由于计算终止的递归函数总有非递归的出口,可以先通过非递归路径得到函数的后形状图的初值,然后再在递归路径上迭代求解.从而,可以像推断循环不变形状图那样来推断递归函数的前后形状图.第三,参照Nelson-Oppen框架,提出形状图理论和整数理论组合的一种判定方法.对易变数据结构,除了关心数据结构各节点是否连成预定的形状外,往往还关心数据在这些节点间的排列等特性,它们不能脱离易变数据结构的形状特征而单独验证.为此,所提出的组合判定方法针对这类程序的验证条件的特点,利用程序分析阶段得到的形状图对验证条件的前件中的符号断�

带时间约束实时任务图模型上可调度性分析算法研究2481-2493

摘要：带时间约束的实时任务图（TCDRT）模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析（SA）问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型：K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度呈指数倍增长.该文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果：第一,针对需求上界函数（DBF）的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关;第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度不再与K指数相关,这使得文中算法性能较已有结果有指数级提升.更进一步地,该文方法还蕴含着一类新的TCDRT易解模型.该类模型突破了约束个数必须为常数的局限,其分析难度也较K-TCDRT有指数倍地下降.

高阶熵压缩的全文自索引2494-2511

摘要：大数据集正在以前所未有的速度产生,研制大数据集的实用压缩全文自索引是目前的挑战问题之一.该文提出了一种高阶熵压缩的全文自索引.对于长为n的文本T以及任意k≤c logαn-1和c＜1,该压缩索引占用2nHk（T）＋n＋o（n）位的空间,其中Hk（T）表示文本T的k阶经验熵,σ为字符表的大小.此外,该压缩索引可在线性时间O（n）内构造.在此基础上,该文还给出了上述压缩索引的一种实用改进.这种改进引入了混合编码方法,额外的空间开销为o（n）位.对于Pizza＆Chili Corpus上的三类典型数据的实验表明：该文的压缩索引较之主流压缩索引在压缩率和查询时间上具有显著的优势.该文所述的压缩索引软件可在GitHub上访问.

Bi-swapped网络的支配集问题研究2512-2526

摘要：图论中支配集和连通支配集概念可用于并行分布式系统中资源布局和路由策略.作为著名Swapped网络的改良形式,Bi-swapped网络是一类组合网络体系结构,它采用任意因子网络的多个拷贝作为模块并将这些模块通过一种简单的交换互连规则连通起来.Bi-swapped网络的优良特性使得它可为构建并行计算机提供潜在有竞争力的体系结构方案.文中基于Bi-swapped网络的互连规则研究Bi-swapped网络中最小支配集问题和最小连通支配集问题.首先证明这两个问题都是NP难度的,然后基于Bi-swapped网络的模块化结构特性,给出求解这两个问题的几个简单有效的近似算法.在一个N节点的Bi-swapped网络中,文中的算法以因子网络的一个（连通）支配集为输入,在O（N）时间内能构造出Bi-swapped网络的一个（连通）支配集,并且以一定性能保证了所构造的（连通）支配集的质量.相比之下,如果将Bi-swapped网络视作一般图而不利用其模块化特性,直接构造一个同样质量的（连通）支配集则需要O（N2）时间.该文也建立了因子网络和Bi-swapped网络的（连通）支配数之间的联系,由此获得Bi-swapped网络的（连通）支配数的非平凡的上下界.我们的方法为诸如Bi-swapped网络等组合网络中的大数据处理和分析提供了一条可行途径.

否定知识的代数表示及在模糊系统设计中的应用2527-2546

摘要：对于模糊系统中的否定知识的认识,首先从哲学层面上对潘正华提出的3种否定关系进行了研究,提出了矛盾否定关系、对立否定关系和中介否定关系的本质特征.接着,在Zadeh提出的语言变量中引入3种否定的概念,得到了带有3种否定的语言变量.为了能够刻画这些否定关系的本质特征和内在联系,进一步研究了它们的集合基础,定义了一种新的带有矛盾否定、对立否定和中介否定的模糊集GFScom,并讨论了GFScom的一些基本运算及性质.在此基础上,给出了基于GFScom的具有一阶逼近精度和二阶逼近精度的模糊系统的设计方法,并分析了所设计的模糊系统的逼近性能.应用示例表明,GFScom不仅丰富了模糊系统的推理功能,而且能在仅知道部分隶属函数分布的情况下设计出具有给定精度的模糊系统.

基于偏序规律的μ-演算一阶谓词界程逻辑模型检测2547-2561

摘要：基于μ-演算的一阶谓词界程逻辑,用谓词变量构造不动点公式,方便描述闭环系统的性质,公式语义简洁.该逻辑在有限控制移动界程上的模型检测目前性能最好的算法的时间复杂度与公式中不动点算子交错嵌套深度d呈指数关系,空间复杂度与d呈线性关系.文中设计了一个基于μ-演算的一阶谓词界程逻辑在有限控制移动界程上的模型检测高效算法,这也是目前已知的第3个同类算法,算法的时间复杂度与d/2＋1呈指数关系,空间复杂度与d呈线性关系.文中所做的工作有：（1）找到了基于μ-演算的一阶谓词界程逻辑模型检测计算过程中的中间结果满足的两组偏序关系;（2）利用找到的偏序关系设计了一个快速模型检测算法;（3）分析了算法的复杂度.

一种基于加权非负矩阵分解的多维用户人格特质识别算法2562-2577

摘要：随着社会媒体的普及,用户信息的爆炸式增长为深入理解在线用户行为提供了非常丰富的信息源.由于用户人格特质是用户行为的主要驱动力,人格特质的差异可能会对用户的在线行为产生一定的影响,因此,用户人格特质识别问题近年来受到了众多学者的关注.首先,基于用户网络结构信息和用户内容信息序列构建用户人格特质识别特征,并根据特征重要性为其分配权重.然后,以用户人格特质相关因子约束目标函数,从用户社会网络结构特征、语言学特征和情感特征三个维度利用非负矩阵分解方法识别社会网络中用户的五大人格特质.最后,在真实的数据集上验证了提出框架的有效性,并通过实验以更细的粒度进一步验证了用户人格特质之间相关性的存在,同时证明了特征权重和用户人格特质间的相关性在用户人格特质识别问题中的重要性.文中为社会网络中的多维用户人格特质识别问题提供了一种新思路.

基于DNA计算的线性时序逻辑模型检测方法2578-2597

摘要：该文研究基于脱氧核糖核酸（Deoxyribonucleic Acid,DNA）计算的线性时序逻辑（Linear Temporal Logic,LTL）模型检测问题.为此,该文给出了使用粘贴自动机实现LTL模型检测的方法.首先,使用3＇-5＇型单链DNA分子对LTL公式的有穷状态自动机（Finite State Automata,FSA）模型进行编码,从而获得实现公式的粘贴自动机;其次,使用5＇-3＇型单链DNA分子对系统模型进行编码,从而获得粘贴自动机的输入字符串;最后,对表征粘贴自动机的DNA单链分子和表征输入字符串的DNA单链分子实施一系列生化反应,即可判定系统是否满足公式.分子生物学仿真实验结果表明：给出的DNA编码序列能达到99.9％的碱基配对正确率,且新方法成功地对所有4种LTL基本公式与5种LTL常见公式实施了检测;与之对照,已有的方法只能有效检测1种LTL基本公式与0种LTL常见公式.在此基础上,对本实验给出的DNA编码方案直接作位数扩展即可拥有对任意给定LTL一般公式的（理论）检测能力.

基于大规模变量分解的多目标粒子群优化算法研究2598-2613

摘要：含有大规模变量的多目标优化问题是目前多目标进化算法领域的研究重点.多目标粒子群优化方法具有收敛性良好、计算简单和参数设置少等优点,但随着优化问题决策变量的增多,“变量维度”成为了瓶颈.针对上述问题,文中提出的变量随机分解策略,增加关联变量分配到同组的概率,使得算法更好的保留变量间的关联性,并将合作协同进化框架融合到算法中,提出了基于大规模变量分解的多目标粒子群优化算法（CCMOPSO）.将该算法在经典标准测试函数ZDT1、ZDT2、ZDT3、DTLZ1、DTLZ2变量扩展后进行仿真对比实验,采用加法二进制ε指标和超体积指标（HV）对算法收敛性和多样性进行对比分析,实验结果表明,在解决大规模变量的多目标函数中,变量维度越高,该算法比经典多目标算法MOPSO、NSGA-Ⅱ、MOEA/D以及GDE3越具有更好的多样性与收敛性,同时使得计算复杂度明显降低.

基于遗传算法求解折扣{0-1}背包问题的研究2614-2630

摘要：目前,求解折扣{0-1}背包问题（D{0-1}KP）的主要算法是基于动态规划的具有伪多项式时间的确定性算法,当D{0-1}KP实例中各项的价值系数与重量系数在大范围内取值时缺乏实用性.文中基于杰出者保留策略遗传算法（EGA）求解D{0-1}KP,首先建立了D{0-1}KP的两个新的数学模型;然后,为了利用EGA和第一数学模型求解D{0-1}KP,提出了一种处理非正常编码个体的贪心修复与优化算法GROA,并将其与EGA相结合给出了求解D{0-1}KP的第一遗传算法FirEGA;紧接着,利用EGA和第二数学模型求解D{0-1}KP,提出了处理非正常编码个体的另一种有效算法NROA,并将其与EGA相结合给出了求解D{0-1}KP的第二遗传算法SecEGA;最后,利用四类大规模D{0-1}KP实例,确定了FirEGA和SecEGA的交叉概率与变异概率的合理取值,比较了两个算法的实际求解性能.对四类实例的计算结果表明：FirEGA和SecEGA都非常适于求解大规模的难D{0-1}KP实例,均能够得到一个近似比非常接近于1的近似解,并且FirEGA的平均求解性能比SecEGA的更优.

一种基于局部Lipschitz下界估计支撑面的差分进化算法2631-2651

摘要：为了减少智能优化算法求解复杂问题时所需的目标函数评价次数,降低算法计算代价,在差分进化算法框架下,结合Lipschitz估计理论,提出一种基于局部Lipschitz下界估计支撑面的差分进化算法.首先,对新个体的N邻近个体构建Lipschitz下界估计支撑面,进而通过支撑面获取新个体的下界估计值;然后,根据下界估计值设计Lipschitz估计选择策略来指导种群更新;其次,利用下界估计区域的极值信息排除部分无效区域,逐步缩小搜索区域;最后,根据N邻近个体下降方向和主导支撑面下降方向设计广义下降方向做局部增强.数值实验结果表明,所提算法与文中给出的主流算法相比,能够以较少的目标函数评价次数获得高质量的最优解.

基于自适应搜索中心的骨干粒子群算法2652-2667

摘要：该文在对标准粒子群算法（Particle Swarm Optimization,PSO）和骨干粒子群算法（Bare Bones Particle Swarm Optimization,BBPSO）中粒子位置的概率密度函数进行分析比较的基础上,对BBPSO进行了改进,并证明了改进算法以概率1收敛于全局最优解.在改进算法中,主要包括如下策略：（1）基于粒子间适应值的差异,提出一种对粒子位置高斯采样均值的自适应调整策略,分析了其作用机理,提出的搜索中心自适应调整策略增加了粒子分布中心的分散度,减缓粒子在中心的聚集趋势;（2）提出了一种“镜像墙”的越界粒子处理方法,该方法能够大幅度地提高算法找到最优解的概率;（3）粒子在不同的进化时期按不同的拓扑结构选取榜样粒子：算法前期主要采用随机结构以增加群体的多样性,算法后期主要采用全局结构以使得搜索更加精细.将该文提出的算法与多种形式的改进PSO,如GPSO（Global PSO）、LPSO（Local PSO）、FIPS（Fully Informed Particle Swarm）、CLPSO（Comprehensive Learning PSO）、HPSO-TVAC（Hierarchical PSO with Time-Varying Acceleration Coefficients）、APSO（Adaptive PSO）、DMS-PSO （Dynamic Multi-Swarm PSO）、OPSO （Orthogonal PSO）、OLPSO （Orthogonal Learning PSO）、ALC-PSO（PSO with an Aging Leader and Challengers）等,以及BBPSO的标准版本和改进版本,如BBJ2（BBPSO with Jumps）、ABPSO（Adaptive BBPSO）、SMA-BBPSO（BBPSO with Scale Matrix Adaptation）等,对CEC2013标准函数进行测试,对实验数据进行非参数检验,结果表明该文改进算法的综合表现要优于其他算法.