图片丢失啦 理论计算机科学

默认 最新文章 浏览次数
Please wait a minute...
选择: 显示/隐藏图片
1. 理论计算机科学专题前言
尹一通, 何琨, 张驰豪, 操宜新, 孙晓明
计算机科学    2020, 47 (5): 2-2.  
摘要378)      PDF(pc) (428KB)(1223)    收藏
相关文章 | 多维度评价
2. 在线影响力最大化研究综述
孔芳, 李奇之, 李帅
计算机科学    2020, 47 (5): 7-13.   DOI: 10.11896/jsjkx.200200071
摘要1107)      PDF(pc) (1591KB)(2997)    收藏
影响力最大化是指在给定的影响力传播模型下选取种子节点使其传播信息范围最广。此问题的应用场景十分广泛,包括推荐系统、病毒营销、信息扩散和链接预测等。在实际应用中,信息传播模型中的点对点传播概率通常是未知的,而在线学习算法可以在交互过程中自主学习未知参数,逐步逼近最优解。文中首先讨论了影响力最大化问题的定义,介绍了常用的影响力传播模型,归纳了常见的离线影响力最大化算法;随后介绍了经典的在线学习框架——多臂老虎机问题,分析了在线影响力最大化问题的研究现状,并通过实验对常见的在线影响力最大化算法在真实社交网络中的性能表现进行对比;最后总结了该课题面临的挑战并展望了未来的研究方向。
参考文献 | 相关文章 | 多维度评价
3. 关于同步部分规约的有限自动机的优化问题的近似难度
朱凯, 毋国庆, 袁梦霆
计算机科学    2020, 47 (5): 14-21.   DOI: 10.11896/jsjkx.200200073
摘要347)      PDF(pc) (1902KB)(797)    收藏
自动机是可同步的是指它具有满足以下性质的同步字:不论自动机当前所处的状态,以同步字为输入执行后它一定会到达某个特定状态。同步自动机问题的核心是计算最短同步字。聚焦于这一核心问题,文中就一类称为部分规约的确定的有限自动机的最短同步字问题,研究了近似计算这类自动机的最短同步字的复杂性,即近似计算它的难度,该工作有助于其近似算法的分析与设计。通过建立由两个优化问题(MAX SAT问题以及MAX FA-INT问题)到最短同步字长度计算这一问题(即Shortest-Syn)的归约,利用与概率可检验证明(Probabilistically Checkable Proofs,PCP)定理和概率可检验辩论(Probabilistically Checkable Debate,PCD)定理有关的若干结果证明了文中的主要结论:对于部分规约的确定的有限自动机,在某个近似因子内Shortest-Syn的近似难度是NP-难的和PSPACE-难的,除非NP和PSPACE分别坍塌到P。
参考文献 | 相关文章 | 多维度评价
4. 铁磁性双态自旋系统配分函数的可近似性
邱国良, 张驰豪
计算机科学    2020, 47 (5): 22-26.   DOI: 10.11896/jsjkx.200200119
摘要400)      PDF(pc) (1445KB)(914)    收藏
双态自旋系统是统计物理学在处理互作用粒子系统时所建立的简化模型,计算该系统的配分函数(partition function)在统计物理及计算机科学中均有重要意义。对于一般的系统,配分函数的精确计算已被证明是#P难的,但其是否能被高效地近似计算一直是理论计算机科学关注的问题。近年来,这一领域取得了较大的突破。研究者建立了配分函数的可近似性与该物理系统相变的联系,并且在很大的参数范围内理解了可近似性。文中对铁磁性双态自旋系统配分函数的可近似性研究进行了综述,介绍了目前针对该问题设计近似算法的三类技巧的主要思想,并把这些算法的结果与该问题在不可近似方面的结果进行了比较。
参考文献 | 相关文章 | 多维度评价
5. 分级论辩系统的逻辑研究
谭立兴, 王福俊
计算机科学    2020, 47 (5): 27-31.   DOI: 10.11896/jsjkx.200200052
摘要359)      PDF(pc) (1464KB)(696)    收藏
近年来,形式论证已逐渐成为人工智能领域的研究热点之一。自Dung于1995年提出抽象辩论框架起,学术界普遍认为论辩的核心任务是在各种基于外延的语义下对论点集进行评估,以确定其辩护状态。分级论辩系统(Graded Argumentation System,GAS)是对经典Dung型论辩系统(Dung-style Argumentation System,DAS)的推广,通过一般化DAS语义的两个核心性质,即无冲突性和可接受性,来提供更细化的论点状态概念。当前的论辩系统语义等效性研究主要集中在框架和论点层次上,可为其结构约简提供有力的保证。针对两个不同分级论辩系统中论点的语义等效问题,首先运用分级模态逻辑(Graded Modal Logic,GML) 形式化分级论辩系统的片段,然后建立并证明了分级论辩系统基于外延的语义和GML公式之间的一一对应关系,最后定义分级互模拟关系并证明其蕴含分级论辩系统的4个重要的语义等价性。
参考文献 | 相关文章 | 多维度评价
6. 一种布尔公式的代数逻辑约化新方法
刘江, 周鸿昊
计算机科学    2020, 47 (5): 32-37.   DOI: 10.11896/jsjkx.190400018
摘要453)      PDF(pc) (1353KB)(859)    收藏
布尔可满足问题是最早被证明的NP完全问题之一,1-in-3-SAT问题是一个NP完全的布尔可满足子类问题。1-in-3-SAT的计算复杂度取决于对应公式的变量以及子句的个数。将1-in-3公式归约为一个变量数或者子句数更少的1-in-3公式,是提高1-in-3-SAT问题求解效率的一个关键。基于一个新的范式形式——XCNF,针对1-in-3-SAT问题提出一种新的代数逻辑约化方法,用于在多项式时间内约减一个1-in-3公式的变量数和子句数。所提算法的主要思想为:首先将1-in-3公式转化为XCNF公式,然后尝试找出XCNF公式中的X-纯文字,并利用X-纯文字法则对1-in-3公式中相应的布尔变量赋值,最后得到一个约减公式,该约减公式与原公式的1-in-3可满足性等价。
参考文献 | 相关文章 | 多维度评价
7. 带膜分裂和促进剂的通讯膜系统求解QSAT问题
宋勃升, 程玉
计算机科学    2020, 47 (5): 38-42.   DOI: 10.11896/jsjkx.191100204
摘要234)      PDF(pc) (1422KB)(675)    收藏
膜计算是自然计算的一个分支,膜计算中所研究的模型均称为膜系统,而细胞间通讯是膜系统的一个重要特征。带膜分裂的通讯膜系统是一种分布式并行计算模型,可以在多项式时间内解决计算困难问题。文中将促进剂引入带膜分裂的类细胞型通讯膜系统,提出了膜系统的一种变型——带膜分裂和促进剂的通讯膜系统,其中,一个促进剂可以同时控制多条规则,而促进剂本身不参与该条规则的进化。文中研究了带膜分裂和促进剂的通讯膜系统的计算效率,证明该类膜系统在使用同向规则长度为2,每条规则中促进剂的个数最多为1时,可以在多项式时间内求解PSPACE完全问题(QSAT问题)的统一解。
参考文献 | 相关文章 | 多维度评价
8. 决定图框架下本体学习算法的稳定性分析
朱林立, 华钢, 高炜
计算机科学    2020, 47 (5): 43-50.   DOI: 10.11896/jsjkx.200100129
摘要378)      PDF(pc) (1448KB)(667)    收藏
传统的本体算法采用启发式的方法来计算语义相似度,而随着本体处理数据量的日益增大,越来越多的机器学习方法被用于本体函数的获取。稳定性是本体学习算法的必要条件,它要求在本体样本集做轻微改动的情况下不会对得到的最优本体函数产生本质的改变。文中研究了在本体样本集的依赖关系由图结构决定的框架下,本体学习算法的稳定性和对应的统计学特征。首先对传统的PO和LTO一致稳定性条件进行分析;其次在大样本情况下扩展一致稳定性条件,提出Pk和LkO一致稳定性并得到相关的理论结果;最后把替换本体样本和删除本体样本两种样本进行变换组合,提出在大本体样本前提下的组合一致稳定性概念,并利用统计学习理论的方法得到一般结果。此外,在各类稳定性条件下,对满足m-独立条件的本体学习算法的广义界进行了讨论。
参考文献 | 相关文章 | 多维度评价
9. 图的树分解算法及其应用
雷莹, 许道云
计算机科学    2020, 47 (5): 51-58.   DOI: 10.11896/jsjkx.191100118
摘要649)      PDF(pc) (2079KB)(1675)    收藏
一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。 忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。
参考文献 | 相关文章 | 多维度评价
10. 基于概率和时间因素的Petri网业务流程一致性分析
杨皓然, 方贤文
计算机科学    2020, 47 (5): 59-63.   DOI: 10.11896/jsjkx.190500119
摘要361)      PDF(pc) (1692KB)(666)    收藏
业务流程一致性分析作为业务流程管理的重要内容之一,近年来一直是业务流程管理研究领域的热点。目前已有的方法主要从控制流和数据流两方面进行研究,在实际情况下,概率和时间因素会对业务流程产生较大的影响。因此,文中提出了一种基于概率和时间因素的Petri网业务流程一致性分析方法。首先,给出了基于概率因素的控制流Petri网和基于时间因素的数据流Petri网的定义;然后,将基于概率因素的控制流Petri网和基于时间因素的数据流Petri网中的所有变迁分别映射到原业务流程Petri网中,得到各自的行为映射表,并针对两种类型的Petri网提出相应的行为兼容度算法,依据行为兼容度的值来衡量业务流程的一致性程度;最后,进行实例分析,结果显示了该方法的有效性和优越性。
参考文献 | 相关文章 | 多维度评价
11. 直觉主义视角下量子逻辑的进一步解释
周恒, 王拥军, 王宝山, 燕健
计算机科学    2020, 47 (5): 1-6.   DOI: 10.11896/jsjkx.191200056
摘要540)      PDF(pc) (1562KB)(1168)    收藏
量子计算机将成为计算机科学未来的发展方向之一,量子逻辑是反映量子计算与量子信息的数学基础。Von Neumann用希尔伯特空间的闭子空间表示量子物理系统的性质,构成正交模格,其元素有明确的物理意义,但无法刻画叠加性质;Bob Coecke填加析取元素来表示叠加性质,借助Heyting代数,基于正交模格构造命题格对量子逻辑进行刻画,命题格中元素有明确的数学含义,但物理意义不够明确。针对后者,文中对命题格中元素的物理含义做出了进一步的解释,认为补充的析取元素代表的物理意义为描述叠加性质时所依赖的“观察者视角”,使得命题格中所有元素都获得了清晰的物理含义,通过阐述量子逻辑在测量时的应用,为量子计算中的隐形传态、超距同步等技术提供了重要的理论依据。
参考文献 | 相关文章 | 多维度评价