朱大铭
主要从事计算机算法与计算复杂性、计算生物学、神经网络领域的研究工作。
个性化签名
- 姓名:朱大铭
- 目前身份:
- 担任导师情况:
- 学位:
-
学术头衔:
博士生导师
- 职称:-
-
学科领域:
计算机软件
- 研究兴趣:主要从事计算机算法与计算复杂性、计算生物学、神经网络领域的研究工作。
朱大铭,教授,博士生导师,1964年5月生于山东省历城县。1987年毕业于中国科技大学计算机科学技术专业,获学士学位。1990年毕业于山东大学计算机软件专业,获工学硕士学位。1999年毕业于中国科学院计算技术研究所,获计算机应用技术专业博士学位。
1990年至今一直在山东大学任教师,1998-2006年间,4次访问香港城市大学,从事算法与计算复杂性、计算生物学研究,总访问工作时间15个月。
主要从事计算机算法与计算复杂性、计算生物学、神经网络领域的研究工作。主要学术贡献为:
(1)排污问题与DeBruijin序列生成问题的结果:将排污问题在树图上的多项式时间算法时间复杂性由O(nlogn)改进为O(n)。给出DeBruijin序列的新生成方法,时间复杂性恰为原算法时间复杂性的1/4。
(2)神经网络计算与学习的研究结果:首次严格证明拓扑特征映射学习党输入数据满足均匀分布时是收敛的;给出最短路经问题神经网络新求解方法,可精确求得问题最优解,突破了Hopfield网络优化计算最短路问题的限制;首次给出一般二进制映射前馈神经网络的几何学习算法,根据样本数据构造神经网络,突破了BP算法学习难以确定收敛的限制。
(3)有向基因组Translocation排序的算法设计:改进有向基因组Translocation排序的多项式算法,将其时间复杂性由O(n3)改进为O(n2logn),并进一步将该算法的时间复杂性改进为O(n2)。
(4)无向基因组Translocation排序的算法与复杂性:证明无向基因组Translocation排序为NP-Hard,设计出该问题近似度为1.5的多项式时间紧似算法。
-
主页访问
3057
-
关注数
0
-
成果阅读
1101
-
成果数
19
朱大铭, 栾峻峰+, 马绍汉
软件学报,2003,14(2):183~189,-0001,():
-1年11月30日
讨论翻转距离星树问题,将3SAT问题归约到目标序列部分固定的翻转距离星树问题,证明实例中当有向符号序列个数为3时。若目标序列符号顺序固定,且有部分符号方向给定,则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP。难解问题。同时,还给出了该问题的多项式时间近似算法。
算法, 计算复杂性, 进化树, 基因组, 翻转距离
-
84浏览
-
0点赞
-
0收藏
-
0分享
-
121下载
-
0评论
-
引用
朱大铭, 刘晓文), 朱大铭), 马绍汉), 李子茂), 王鲁生)
计算机学报第,2004,27(10),-0001,():
-1年11月30日
有向基因组移位排序问题在计算生物学研究中占有重要位置。以前最好的算法时间复杂度为0(n2logn),该文给出一个有向基因组移位排序的新多项式算法,将移位排序的时间复杂度改进为O(n2)。算法改进的关键在于找到一种寻找有效合理移位的新方法,通过在最小子排列中删除无关顶点确定一个合理移位是否有效,从而将寻找一个有效移位的时间复杂度改进为O(n),总时间复杂度由此降为O(n2)。
基因组, 移位, 计算生物学, 算法, 时间复杂度
-
55浏览
-
0点赞
-
0收藏
-
0分享
-
95下载
-
0评论
-
引用
朱大铭, 马绍汉
软件学报,7:191~198,-0001,():
-1年11月30日
本文给聘种求解图最短路径问题的实用反馈式神经网络,并证明这种网络的求解稳定性。这种网络基于最小值选择网而构成,对任意有向图和无向图均能收敛到其唯一的稳定点,由此求得力产所有顶点对间的最短路最短路径长度。本文结果最神经网求解NP-难解类优化问题的一种新尝试。
神经网络,, 突触权植,, 稳定性,, 图,, 最短路径.,
-
48浏览
-
0点赞
-
0收藏
-
0分享
-
126下载
-
0评论
-
引用
【期刊论文】基因组Translocation排序问题的改进多项式算法
朱大铭, 马绍汉
计算机学报,2002,25(2)189~196,-0001,():
-1年11月30日
该交给出基因组Translocation排序问题的一个改进多项式算法,原算法所用存储空间为O(n),时间复杂度为O(n2),文中改进算法仍采用O(n)存储空间,时间复杂度为O(n2logn)具体地,将计算Tranalocation距离的时间复杂度由O(n3)改进为O(n2), 将计算Translocation序列的时间复杂度由O(n1)改进为O(ntlogn)
算法, 时间复杂度, 基团组, 交叉排序
-
82浏览
-
0点赞
-
0收藏
-
0分享
-
102下载
-
0评论
-
引用
朱大铭, 马绍汉, 雷鹏
软件学报,2002,13(6)1117~1122,-0001,():
-1年11月30日
讨论基于基因组翻转距离的星型进化树问题的算法和复杂性。首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2。
算法, 进化树, 基因组, NP-完全性, 近似性能比
-
65浏览
-
0点赞
-
0收藏
-
0分享
-
90下载
-
0评论
-
引用
朱大铭, 朱大铭*, 马绍汉
自动化学报,2000,26(3)339~346,-0001,():
-1年11月30日
提出一种一般二进制映射问题的前馈网络学习算法,给出一种求解超平面以几何分割练点的新方法,不仅相应地构造了陷层神经网络,而且使得只需再构造一个输出层网络便可实现训练样本所描述的映射,该算法在学习收敛速度方面优于BP算法和SC算法,对样本数据的分布和密集程度变化适应性强,具有较好的容错能力。
神经网络, 学习算法, 训练样本, 超平面
-
88浏览
-
0点赞
-
0收藏
-
0分享
-
73下载
-
0评论
-
引用
朱大铭, 马绍汉
软件学报,1997,80(8)622~629,-0001,():
-1年11月30日
分类问题在前向神经网络研究中占有重要集团,本文利用几何方法给耻骨一个二进制神经网络K(≥2)分类问题的新学习算法。算法通过训练点的几休位置与类别分析,建立一个四层前向神经网络,实现网络四舍五入向量分类。 本文算法的优点在于:保证学习收敛且收敛速度快于BP算法及已有的其他一些前向网络学习算法;算法可以确定神经网络的结且能实现精确有向量分类。另外,算法所建神网络由线性阀值单元组成,神经元突触权值和阀值均为整数,特别适合于集成电路实现。
神经网络, 算法, 收敛, 训练, 几何
-
93浏览
-
0点赞
-
0收藏
-
0分享
-
80下载
-
0评论
-
引用
【期刊论文】TWO ENW ALGORITHMS FOR PRODUCING BINARY DE BRUIJIN SEQUENCES *
朱大铭, ZHU Da-ming , , MA Shao-han , and WEI Dao-zheng
Chinese Journal of Advanced Software Research, 5(2)1998,167-175,-0001,():
-1年11月30日
Binary de bruijin sequences have been widely used and studied. In this paper: two new algorithms for producing binary de bruijing sequences are presented. The first algorithm is acquired by improving the original algorithm proposed by Yuejiang Fluang. It takes An bits of storage and 2n units of time to produce one bit of sequence, witere the space complexity is identical to that of Hnang's algorithm. and the time complexity is one half that of Huang's algorithm. The sceond algorithm cmploys a new method to produce binary de bruijin sequences. It takes An bits of storage and n units of time to produce one bit, where the time complexity is one quarter that of Huang's aigorithm, THE other advantages of the two new aigorithins are that they produce de bruijin sequences with better 01 harmoniousness and can start computing from any n-tuple.
De bruijin Sequence, Algorithm, Bitary n-tuple, Time Complexity, Circulate Shift
-
82浏览
-
0点赞
-
0收藏
-
0分享
-
61下载
-
0评论
-
引用
【期刊论文】An O(n2) algorithm for signed translocation
朱大铭, Lusheng Wang a, Daming Zhu b, Xiaowen Liu b, Shaohan Ma b
Journal of Computer and System Sciences 70(2005)284-299,-0001,():
-1年11月30日
Genome rearrangement is an important area in computational biology. There are three basic operations, reversal, translocation and transposition. Herewestudy the translocation operations. Multi-chromosomal genomes frequently evolve by translocation events that exchange genetic material between two chromosomes.We focus on the signed case, where the direction of each gene is known. The signed translocation problem asks to find the minimum number of translocation operations as well as the sequence of translocation operations to transform one genome into the other.A linear-time algorithm that computes the minimum number of translocation operations was given in a linear-time algorithm for computing translocation distance between signed genomes [16]. However, that algorithm cannot give the optimum sequence of translocation operations. The best known algorithm that can give the optimum sequence of translocation operations for signed translocation problem runs in O(n2 log n) time. In this paper, we design an O(n2) algorithm.
Algorithm, Signed translocation, Genome rearrangement
-
43浏览
-
0点赞
-
0收藏
-
0分享
-
73下载
-
0评论
-
引用
【期刊论文】k-Median近似计算复杂度与局部搜索近似算法分析*
朱大铭, 潘锐, 马绍汉, 肖进杰
软件学报,2004,15(1)1~9,-0001,():
-1年11月30日
The research on approximated algorithms for k-Median problem is a focus of computer scientists all along, and most existed results are based on Euclidean and Metric k-Median problem, however, results for General distance space k-Median is not found for many years. In General distance space, let dmax/dmin denote the maximum value of the length of the longest edge divided by the length of the ortest edge for one client point. In this paper, we first prove that there are no polynomial algorithms of approximation ratio 1+e1−ωk-Median with condition dmax/dmin≤ω+ε, unlessDTIMNP⊆result implies there are no polynomial algorithms of approximation ratio 1+2elog (lognone2 for Metric k-Median unless. Then a local search algorithm for k-Median is presented. New analysis shows that local search can achieve a ratio of
k-median, algorithm, local search, approximation ratio, facility, client
-
44浏览
-
0点赞
-
0收藏
-
0分享
-
105下载
-
0评论
-
引用