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

计算机科学 2018年第04期杂志 文档列表

计算机科学杂志综述

数据质量的历史沿革和发展趋势1-10

摘要：在互联网时代,数据成为了新的生产要素,也成为了基础性资源和战略性资源,同时还是重要的生产力.大数据服务业在全国广泛开展,数据交易所纷纷成立.这时,数据质量就逐渐变成制约数据产业发展的关键问题.首先,按照时间顺序将数据质量的研究内容划分为3个阶段,全面梳理和总结每个阶段的代表性成果,包括理论、方法、技术、工具和框架;然后,分析了在物联网、云计算和大数据环境下,数据质量研究所面临的各种挑战和机遇;最后,从数据质量模型、大数据质量管理、大数据质量相关技术、众包、物联网以及数据开放6个方面对数据质量的研究热点和发展方向进行了展望.

图编辑距离概述11-18

摘要：图编辑距离是图模式匹配技术中常用的方法之一.基于图编辑距离的匹配方法能够处理多种类型的图数据,因而受到了学术界的广泛关注.首先介绍了图编辑距离的相关概念;然后简述了基于启发式搜索技术的精确图编辑距离算法,重点分析了基于二分图匹配的近似图编辑距离算法;最后对现存的一些图编辑问题进行了总结,并对未来的发展趋势进行了展望.

移动低占空比无线传感网中数据收集的研究进展19-24

摘要：移动低占空比无线传感网(Mobile Low-duty-cycle Wireless Sensor Networks,MLDC-WSN)是一种新型的传感器网络,它能克服传统无线传感网络(WSN)中仅考虑静态网络、网络能耗大等问题。但是,MLDC-WSN的新特性给数据收集应用带来了新的挑战,例如:移动性会导致网络拓扑结构不断改变,造成网络连通性不稳定;节点的苏醒时间短,造成通信延迟大。针对MLDC-WSN中数据收集的研究现状进行了分析和对比,分别从节点移动性管理、节点睡眠调度、数据收集协议等3个方面进行了综述。此外,还总结了该领域中待解决的重要科学问题,并对未来的研究方向进行了展望。

工业控制系统的安全技术与应用研究综述25-33

摘要：为应对控制系统与互联网技术深度融合引发的安全新挑战,抵御震网病毒、火焰病毒、BlackEnergy等靶向攻击,针对工业控制系统漏洞挖掘、修复与控制等技术滞后,以及工业控制安全面临的“难发现、难监测、难防护”等问题,通过对工业控制系统的理论模型、关键技术、装备研制及测试评估进行研究,以漏洞挖掘与利用研究为主线,以理论与体系架构研究和安全技术测试验证平台的建设为基础,以动态监测防护和主动防御为目标,以测试样例集的攻防验证与典型示范为应用,提出了包含工业控制系统漏洞挖掘、深度检测、动态防护、主动防御等的整体安全技术解决方案,设计并构建了集漏洞挖掘、验证评估、动态防护、主动防御于一体的工业控制系统安全技术体系.

基于四叉树分割的地形LOD技术综述34-45

摘要：层次细节(Levels of Detail,LOD)技术是在大规模地形模型简化方面使用得最多的技术,它极大地提高了地形场景的漫游速度。在众多LOD模型中,应用最为广泛的是基于四叉树(Quadtree)分割的LOD算法。国内外学者对LOD模型做了大量的研究工作,文中对基于四叉树分割的LOD算法进行了系统的梳理与总结,对涉及到的核心算法进行了归类并详细分析了各自的优缺点,深入且全面地介绍了其研究现状。

计算机科学杂志2017年全国理论计算机科学学术年会

同态加密在加密机器学习中的应用研究综述46-52

摘要：现有的机器学习算法不能对加密后的数据进行分析计算,而很多领域如医疗、金融等又要求数据保持机密性和安全性,这促进了加密机器学习的产生和发展。同态加密技术是解决这一问题的主要思路,它可以保证在不解密的情况下对密文进行计算,使得解密后的结果与对明文执行相同计算得到的结果相同。文中对同态加密在加密机器学习中的相关应用研究进行了综述,主要介绍了目前用同态加密实现加密机器学习的3种算法(加密神经网络、加密k-NN、加密决策树和完全随机森林),并从正确性、安全性、执行效率方面分析了方案设计,总结并对比了不同加密机器学习算法的构造思路,指出了同态加密用于加密机器学习的关键问题和进一步研究需要关注的内容,为同态加密和加密机器学习提供参考。

考虑时间因素的0-1背包调度问题53-59

摘要：文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为w i,连续加工时间为t i),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长t i后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500 s内得到比动态规划算法更好的结果。

基于极大团的边缘云节点聚合算法60-65

摘要：组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个NP完全问题。子图的选择策略是决定云组合性能的重要因素,现有的minStar算法贪心地选择节点之间通信延迟最小的子图,将最优资源分配给当前用户,导致了局部最优和全局性能不良的问题。鉴于此,提出基于极大团的边缘云资源分配算法,提取图中的极大团并将其划分为若干互不重叠的规模较小的完全子图,以子图为单位构建资源块,以资源块为单位进行资源的分配。实验结果表明,与minStar算法相比,新算法将全局最大通信延迟降至原来的50%。

基于注意力长短时记忆网络的中文词性标注模型66-70

摘要：针对传统的基于统计模型的词性标注存在人工特征依赖的问题,提出一种有效的基于注意力长短时记忆网络的中文词性标注模型。该模型以基本的分布式词向量作为单元输入,利用双向长短时记忆网络提取丰富的词语上下文特征表示。同时在网络中加入注意力隐层,利用注意力机制为不同时刻的隐状态分配概率权重,使隐层更加关注重要特征,从而优化和提升隐层向量的质量。在解码过程中引入状态转移概率矩阵,以进一步提升标注准确率。在《人民日报》和中文宾州树库CTB5语料上的实验结果表明,该模型能够有效地进行中文词性标注,其准确率高于条件随机场等传统词性标注方法,与当前较好的词性标注模型也十分接近。

可能性测度下的LTL模型检测并行化研究71-75

摘要：分布式模型检测是一种缓解状态空间爆炸的有效途径,已有文献提出了定性的分布式模型验证算法,然而定量LTL验证算法并行化问题还未得到有效解决。对此,展开两个方面的工作:提出一种新的动态系统状态空间划分方法;在定性LTL分布式验证算法的基础上给出了定量模型检测并行化验证算法。首先,将系统模型转化为可能的Kripke结构并选取一个并发分量,依据状态之间的关系完成系统状态的分割,使得关系紧密的状态尽可能分布在同一个计算节点上;其次,调整划分结果以使得计算负载平衡;然后,将划分结果与其他并发分量的状态进行叉乘,以完成系统状态空间的划分;最后,将待检测性质用自动机表示,在两者的乘积上,利用扩展的基于嵌套DFS的分布式验证算法完成系统的定量验证。

用于求解混合车辆路径问题的混合进化算法76-82

摘要：文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。

带权混合支配问题的近似算法研究83-88

摘要：图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为w v,所有边的权重均为w e,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。

城市道路建设时序决策的鲁棒优化89-93

摘要：为提高城市道路建设时序决策的鲁棒性,提出了城市道路建设时序决策优化的双层规划模型。模型假定出行需求在一定范围内扰动,上层规划是在有限资金的约束下寻求各建设阶段的系统总出行时间与系统总出行时间对出行需求的灵敏度之间的综合最小值,下层规划为各建设阶段的随机用户均衡配流。文中推导出了系统总出行时间对出行需求灵敏度的计算式,并给出了模型的求解算法。最后以一个测试路网为例,对基于系统总出行时间、基于灵敏度、基于系统总出行时间与灵敏度综合出行时间的决策优化模型进行了计算分析,结果显示3种决策优化模型均可寻求到各自目标最优的城市道路建设时序,但在需求不确定的情景下基于灵敏度、基于系统总出行时间与灵敏度综合出行时间的决策优化结果更具鲁棒性。

针对移动云计算任务迁移的快速高效调度算法94-99

摘要：计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过实验将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942,这进一步说明了提出的启发式算法能够产生高质量的近似解。

基于L1-范数距离的最小二乘对支持向量机100-105

摘要：最小二乘对支持向量机(LSTSVM)是一种有效的分类技术。然而,该方法需计算点到平面的平方L2-范数距离,从而易受野值或噪声的影响。为了缓解此问题,提出了一种有效的鲁棒LSTSVM方法,即基于L1-范数距离的LSTSVM(LSTSVM L1D)。该方法由于使用L1范数作为距离度量,因此不易受到野值或噪声数据的影响。此外,设计了一种有效的迭代算法,旨在求解目标问题,并从理论上证明了其收敛性。在人工数据集和UCI数据集上验证了LSTSVM L1D的有效性。

基于多生长时期模板匹配的玉米螟识别方法106-111

摘要：玉米螟是玉米种植中的主要虫害之一。为了解决人工识别的劳动强度大,且识别不够准确、及时的问题,文中提出了一种在自然场景下基于多生长时期模板匹配的不同生长时期亚洲玉米螟的识别方法。该方法首先对获取到的图像进行数学形态学预处理;其次利用直方图反向映射法和多模板图像得到总的概率图像;然后利用约束空间的大津法对二值图像进行轮廓提取,并根据周长和面积特征进行初步筛选;最后结合基准轮廓,利用Hu矩等特征选出符合亚洲玉米螟特征的轮廓,进而得出识别结果并以三角形标记。实验和理论分析证明,在复杂自然场景图像中,该方法不仅时效性强,而且具有很好的识别准确度,能够有效降低不同生长时期的玉米螟颜色变化带来的影响。

计算机科学杂志网络与通信

基于有向无环图的互联网域内节能路由算法112-116

摘要：互联网在快速发展的过程中面临新的挑战,其中网络能耗问题尤为突出。学术界提出了大量用于解决网络能耗问题的方案,然而这些方案都考虑了网络中的实时流量数据,计算复杂度较高,不利于实际部署。对此,提出一种基于有向无环图的互联网域内节能路由算法(Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph,EEBDAG),该方法利用有向无环图来解决因链路关闭造成的路由环路和网络性能下降等问题,仅须考虑网络拓扑结构,不需要考虑网络中的实时流量数据。实验结果表明,EEBDAG不仅具有较低的节能比率,而且具有较低的链路利用率,为ISP解决互联网节能问题提供了一种全新的方案。

基于节点修复的网络化指挥信息系统弹性分析模型117-121

摘要：提出一种基于节点修复的网络化指挥信息系统弹性分析模型。首先,确立了网络化指挥信息系统弹性的概念,构建了指挥信息系统网络模型,对网络级联失效和恢复过程进行了描述;然后,在建立负载分配模型和节点修复模型的基础上,根据网络化指挥信息系统弹性过程构建了弹性度量模型;最后,进行仿真分析,计算不同模型参数下的网络弹性。结果表明,恢复概率和平均修复时间等参数对网络弹性的影响显著,为提高网络化指挥信息系统的弹性提供了参考。