李肯立，学者主页-中国科技论文在线

李肯立

主要研究兴趣为并行处理、网格计算、DNA计算、实时与混成嵌入式系统。

个性化签名

TA的关注(0) 关注TA的(1)

留言板

暂无留言

主页成果学术会议学者精选辑更多功能敬请期待

姓名：李肯立
目前身份：
担任导师情况：
学位：
学术头衔：

博士生导师，教育部“新世纪优秀人才支持计划”入选者
职称：-
学科领域：

计算机科学技术
研究兴趣：主要研究兴趣为并行处理、网格计算、DNA计算、实时与混成嵌入式系统。

个人简介

　李肯立，男，1971年生，2000年在中南大学应用数学与应用软件系获理学硕士学位，2003年在华中科技大学计算机学院国家高性能计算中心（武汉）获工学博士学位，主要研究兴趣为并行处理、网格计算、DNA计算、实时与混成嵌入式系统。研究简历为： (1) 2000-2001年在华中科技大学国家高性能计算中心（武汉）从事整数与线性规划的并行算法研究工作，国家863-306重大项目《国家高性能计算中心（武汉）网格结点建设》（项目编号：863-306 ZD-11-01-06）的研究； (2) 2001-2003年在华中科技大学国家高性能计算中心（武汉）从事背包公钥系统的并行分析算法研究，作为主要成员参与国家自然科学基金项目：《面向入侵检测的并行数据挖掘算法研究》(项目编号：60273075)，和国家高性能计算基金项目《网络优化高性能算法与应用研究》 (项目编号：00301) 的研究工作，同年博士毕业分配至湖南大学工作； (3) 2003-2004年在湖南大学从事“并行处理与网格计算”与“计算机密码学”的教学和科研工作，主持湖南大学科学基金重点项目：《接触碰撞问题的网格计算技术研究》（项目编号：0010）和国家发改委“中国网上教育平台试点项目”子项目《基于项目反映理论的移动考试系统》（已鉴定为国内领先水平）,以及纵向课题《福建省消防装备网络信息系统》 (4) 2004.12-2005.5在美国伊利偌伊大学计算机科学系从事火箭发射仿真模拟的网格计算访问研究。现正主持教育部重点项目《接触碰撞问题的网格计算技术研究》（项目编号：050128）和国际合作项目《地震数据并行处理系统》(2005.9-2008.7)。

主页访问

2289
关注数

1
成果阅读

663
成果数

14

TA的成果

上传时间

2009-12-22

【期刊论文】Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

李肯立， Ken-Li Li.， Ren-Fa Li， and Qing-Hua Li

J.Comput.Sci.&Technol.2004,19(6)，-0001，（）：

-1年11月30日

摘要

The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.

knapsack problem,， NP-complete,， parallel algorithm,， optimal algorithm,， memory conflict

43浏览
0点赞
0收藏
0分享
54下载
0评论
引用

上传时间

2009-12-22

【期刊论文】背包类问题的并行O(25n/6)时间-空间-处理机折衷∗

李肯立，李肯立+，赵欢，李仁发，李庆华

JournalofSoftware，2007，18（6）：1319～1327，-0001，（）：

-1年11月30日

摘要

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法。基于EREW-PRAM模型,该算法可使用O（2n/8）的处理机在O（27n/16）的时间和O（213n/48）的空间求解n维背包类问题,其时间-空间-处理机折衷为O（25n/6）。与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能。由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义。

NP完全问题，并行算法，时间-空间-处理机折衷，背包问题

37浏览
0点赞
0收藏
0分享
89下载
0评论
引用

上传时间

2009-12-22

【期刊论文】背包问题的最优并行算法∗

李肯立，李庆华+，蒋盛益，张薇

软件学报，2003，14（5）：891～896，-0001，（）：

-1年11月30日

摘要

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法。算法允许使用O（2n/4）1−ε个并行处理机单元,0≤≤ε1,O（2n/2）个存储单元,在O（2n/4（2n/4）ε）时间内求解n维背包问题,算法的成本为O（2n/2）。将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法。同时还指出了相关文献主要结论的错误。

背包问题， NP完全，并行算法，分治法

61浏览
0点赞
0收藏
0分享
231下载
0评论
引用

上传时间

2009-12-22

【期刊论文】背包问题的一种自适应算法

李肯立，李肯立'，李庆华，戴光明，周炎涛

计算机研究与发展，2004，41（7）：1292～1297，-0001，（）：

-1年11月30日

摘要

背包问题是经典的NP- hard组合优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用，基于求解背包问题著名的二表算法和动态二表算法，利用归并原理和4个非平衡的子表，提出一种求解该问题的自适应算法，算法可根据计算资源和问题实例规模的大小，允许使用O（2N/2-ε）的存储空间（1≤ε≤n/4），在O（ε（2n/2））的时间内求解背包问题，对算法性能的理论分析和数值实验结果表明，自适应算法可显著扩大背包实例的求解规模，从时间和空间上改进背包问题现有算法的性能．

背包问题， NP-hard，目适应算法，密钥系统

59浏览
0点赞
0收藏
0分享
73下载
0评论
引用

上传时间

2009-12-22

【期刊论文】背包问题无存储冲突的并行三表算法

李肯立，李肯），），李仁发），李庆华）

计算机学报，2006，29(2)：345～352，-0001，（）：

-1年11月30日

摘要

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法。算法使用O（2n/4）个处理机单元和O（23n/8）的共享存储空间，在0（23n/8）时间内求解n维背包问题，将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2n/2）的硬件资源上，以小于O（2n/2）的计算时间求解背包问题的无存储冲突并行算法．

背包问题， NP难问题，并行算法，存储冲突，硬件-时间折衷

38浏览
0点赞
0收藏
0分享
100下载
0评论
引用

上传时间

2009-12-22

【期刊论文】纵横多路并行归并算法

李肯立，王颖，，李浪，李仁发

计算机研究与发展，43(12)：2180～2186，-0001，（）：

-1年11月30日

摘要

基于倾斜与振荡法多路归并排序算法，提出了纵横多路并行归并算法，与已有方法递归应用两路归并过程不同．该算法直接对m×k的矩阵（m,k为任意整数）进行排序，消除了对两路递归过程的依赖，是一种新的多路归并排序算法．通过和倾斜与振荡法多路归并排序算法和高效的任意路并行归并算法的性能分析比较，当3<k<40时，该算法的时间复杂性低于同类算法．同时，该算法在专用硬件实现的设计复杂性上也具有明显的优势．

倾斜与振荡法，归并排序，多路归并，并行算法

37浏览
0点赞
0收藏
0分享
39下载
0评论
引用

上传时间

2009-12-22

【期刊论文】基于分治的背包问题DNA计算机算法

李肯立，，姚凤娟，李仁发，许进

计算机研究与发展，2007，44（6）：1063～1070，-0001，（）：

-1年11月30日

摘要

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数，已成为DNA计算机研究的重要内容，将分治策略应用于背包问题的DNA分子计算中，提出一种求解背包问题的新的DNA计算机算法，算法由咒位并行减法器、咒位数据搜索器和其他4个子算法组成，算法的DNA链数可达到亚指数的O（2q/2），其中q为背包问题的维数．与最近文献结论进行的对比分析表明：算法将求解背包问题所需的DNA链数从O（2q）减少至O（2q/2），最大鲢长度减少为原来的1/2，因此，理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120，

DNA计算， NP完全问题，背包问题，分治法

61浏览
0点赞
0收藏
0分享
101下载
0评论
引用

上传时间

2009-12-22

【期刊论文】子集和问题的O(1.414n)链数DNA计算机算法

李肯立，李肯立)， )，姚凤娟)，许进)，李仁发)

计算机学报，2007，30（11）：1947～1953，-0001，（）：

-1年11月30日

摘要

随着DNA计算机研究的不断深入，如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一，为设计可扩展的子集和问题DNA计算机算法，文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合，引入荧光标记和凝胶电泳技术，通过设计DNA并行搜索器，提出一种求解子集和问题的DNA计算机模型和算法．与已有文献结论的对比分析表明：文中算法在保持多项式生物操作复杂性的条侔下，将穷举算法中的DNA分子链数从O（扩）减少至O（1。414l），其中”为子集和问题的维数，因此，文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维敷从60提高到120．

DNA计算，子集和问题，分治法，并行处理， NP完全问题

42浏览
0点赞
0收藏
0分享
65下载
0评论
引用

上传时间

2009-12-22

【期刊论文】一种可扩展的线性规划并行算法

李肯立，李庆华，王多强，熊家军

小型微型计算机系统，2003，24（9）：1718～1721，-0001，（）：

-1年11月30日

摘要

由于线性规划在理论和实践中的重要性，对求解人规模规划问题并行算法的研究已引起许多学者的兴趣。本文根据Galperin提出的线性规划的一种线性时间的立方算法特别适合并行的特点，提出了一种基于SPMD模型和主从式MPI的线性规划并行算法，并对算法性能进行了深入分析，理论分析和在曙光3000上的实验结果表明：该算法具有粗粒度并行、良好的可扩展性和理想加速比模型等优点，明显优于目前为止：求解同类不对称线性规划问题的其他并行算法，可用于求解此类火规模线性规划问题的高性能计算。

并行算法，线性规划，可扩展性，高性能计算

57浏览
0点赞
0收藏
0分享
87下载
0评论
引用

上传时间

2009-12-22

【期刊论文】整数规划的新算法

李肯立，李庆华

小型微型计算机系统，2004，（7）：1298～1302，-0001，（）：

-1年11月30日

摘要

整数规划是NP困难的经典问题之一，将传统的二分搜索方法推广应用到整数规划的解空间中，提出一种求解整数规划的新算法．当问题变量数固定时，算法的时间复杂性为O（LlogL），其中L为问题实例的输入规模．理论分析和实验结果表明：新算法不仅初步解决了目前求解系数旱指数增长的整数规划问题时存在的实质性困难，可直接用于此类人规模问题的求解．同时由于其特别适合并行处理的算法结构，可望为一般火规模整数规划问题的精确求解提供新的途径．

整数规划，算法复杂性，类二分方法， NP-hard

70浏览
1点赞
0收藏
0分享
74下载
0评论
引用

上传时间

2009-12-22

【期刊论文】背包问题的最优并行算法∗

李肯立，李庆华+，蒋盛益，张薇

软件学报，2003，14（5）：891～896，-0001，（）：

-1年11月30日

摘要

背包问题， NP完全，并行算法，分治法

61浏览
0点赞
0收藏
0分享
231下载
0评论
引用

上传时间

2009-12-22

【期刊论文】A GENETIC ALGORITHM FOR THE UNBOUNDED KNAPSACK PROBLEM

李肯立， KEN-LI LI， GUANG-MING DAI， QING-HUA LI

，-0001，（）：

-1年11月30日

摘要

In this paper a new evolutionary algorithm is presented for the unbounded knapsack problem, which is a famous NP complete Combinatorialoptimizationproblem. The proposed genetic algorithm is based on two techniques. One is a heuristic operator, which utilizes problem-speciflc knowledge, and the other is a preprocessing technique.Computational results show that the proposed algorithm is capable of obtaining highquality solutions for problems of standard randomly generated knapsack instances, while requiring only a modest amount of computational effort.

Genetic Algorithm， Unbounded Knapsack Problem， Combinatorial Optimization