讲座编号：jz-yjsb-2014-y044
讲座问题：关于准确分块问题的几个效果
主 讲 人：朱滨海，美国Montana State University盘算机系教授
讲座时间：2014年06月05日（周四）下昼14:00
讲座所在：阜成路东校区耕作楼809聚会室
加入工具：盘算机与信息工程学院西席及研究生
承办单位：盘算机与信息工程学院
主讲人简介：
朱滨海，男，1966年8月出生，美国蒙大拿州立大学盘算机科学系教授，博士学位，恒久从事盘算机算法（着重盘算几何，盘算生物）偏向的教学及研究，共揭晓65篇学术期刊论文（含近20篇顶级学术期刊论文，如SIAM J. Computing, Bioinformatics, Algorithmica, IEEE/ACM Trans. Comput. Bio. and Bioinformatics等），85篇学术聚会论文（含近20篇顶级学术聚会论文，如SoCG, SODA, ESA, CPM等），2008年获中科院王宽诚科研奖金，2009年获国家自然科学基金委外洋杰青基金。
内容简介：
字符串的相似性较量是文本处置惩罚及盘算生物中的一个主要难题。现有的要领之一是将两个字符串S,T剖析成最少的公共块（每个字符在S和T中的泛起次数相同）。这就是著名的最小公共块划分问题，该问题已知是NP-完全并且很难近似的。 2014年，欧洲学者证实晰该问题是参数可解的（FPT），但运算时间奇高。在现在的这项研究中，我们思量单面的最小公共块划分问题。也就是说，假定S已经被剖析成k块，相关的问题是T能否可以剖析成对应的（但顺序可能差别的）k块。很显着，该问题是FPT（参数可解的）。我们称该问题为“准确分块问题”。在本讲座中，我们将汇报对准确分块问题的最新研究效果，主要包括字符集为常数时的NP-完全性，当每个字符最多泛起3次时的多项式可解性等。