澳门新葡8455最新网站,新葡萄京娱乐场8455

网站旧版 | English

学院资讯

当前位置: 澳门新葡8455最新网站 > 学院资讯 > 正文

计算机学院姜海涛副教授在理论计算机科学领域顶级期刊IandC发表论文解决PQ-树相关问题

澳门新葡8455最新网站:2020-04-13 编辑:林喜文 来源:

澳门新葡8455最新网站姜海涛副教授作为第一编辑在理论计算机科学领域顶级期刊IandCInformation and Computation)上发表文章“Breakpoint distance and PQ-trees”,揭示了PQ-树所产生的排列的断点距离特性,解决了比较基因组学领域的两个十几年悬而未决的公开问题。新葡萄京娱乐场8455为该论文的第一编辑单位,美国Montana State University和加拿大Simon Fraser University为合作单位。

   

PQ-树是一种基本的树状数据结构,它包含PQ两种树结点,其中P结点的后代节点可自由排列,Q结点的后代结点只有正反两种顺序。因此,它能用以有限的空间(O(n))存储大量(指数级)的排列。现已被广泛应用于平面图判定、矩阵连续1性质判定、基因组片段映射等方面。

PQ-树被用来存贮非确定性的基因组排列时,如何从PQ-树中产生一个与已知排列最相似的基因组排列(PQ-树断点中心问题)?如何从两个PQ-树中产生两个最相似的排列(PQ-树断点距离问题)?这是两个比较基因组学的亟待解决的典型组合优化问题,其计算复杂性一直未知。

在姜海涛副教授发表的论文中,以最基本的断点距离作为两个排列相似性的评价指标,采用Karp归约,分别证明了这两个问题都是NP-困难的。对两个公开问题的计算复杂性,给出确切的回答。这意味着,在P¹NP的前提下,这两个问题都不存在多项式时间的精确算法。从而,使后续的近似算法和参数算法的研究变得有意义。同时,论文中对于PQ-树断点中心问题,设计了第一个参数算法,证明了该问题的参数可解性。

IandC是中国计算机学会认定的理论计算机科学领域的A类顶级期刊。理论计算机科学以“图灵机”为现代计算机的理论模型,研究关于计算复杂性、算法、计算逻辑等计算机科学的基础理论问题,有十几位“图灵奖”得主从事这个领域。研究工作难度大,论文发表周期长。

IandC2017年、2018年和2019年发表正刊论文分别为45篇、37篇和43篇,其中来自国内科研单位的论文仅为5篇、3篇、4篇,论文编辑来自于上海交通大学、南京大学、北京大学、中科院App所等几所著名高校和科研院所。本项研究是澳门新葡8455最新网站首次在理论计算机科学方向CCF-A类期刊上发表论文。该项研究工作得到国家自然科学基金重点项目、国家自然科学基金面上项目和新葡萄京娱乐场8455青年学者“未来计划”项目的支撑。

姜海涛副教授所在的理论计算机科学研究团队成立于上世纪八十年代,先后在马绍汉教授、朱大铭教授的带领下,一直处于国内理论计算机科学领域前列。近年来,在ACM Trans. on Algorithms, Journal of Computer and System Sciences, Algorithmica, Theoretical Computer Science等理论计算机科学领域的重要期刊发表论文20余篇。受到国内外同行的关注。


文章链接:https://www.sciencedirect.com/science/article/pii/S0890540120300729




(图/文 姜海涛  编辑/林喜文  供稿单位:澳门新葡8455最新网站)

    友情链接

  • 新葡萄京娱乐场8455
  • 青岛校区
  • 本科生院
  • 研究生院
  • 党委研究生工作部
  • 党委学生工作部、武装部

联系大家

地址: 山东省青岛市即墨区滨海公路72号

           新葡萄京娱乐场8455(青岛)第周苑C座

邮编:266237

电话:(86)-532-58630620

传真:(86)-532-58630620

微信公众号

山大微信公众号

XML 地图 | Sitemap 地图