面向SoC的系统级并行划分方法

为缩短复杂SoC系统的设计周期,降低系统设计的复杂性,提出了一种SoC系统级的并行划分方法.引入带有信号激活率和输入输出延时的过程模型图,为SoC系统构建模型.设计一启发式算法对该过程模型图进行并行划分,同时,该算法能解决有环图的划分问题.通过大量的实验证明,划分结果同要求吻合,说明该划分方法是可行、有效的.     

Design and Performance Evaluation of Sequence Partition Algorithms

Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone （increasing or decreasing） subsequences. This problem is NP-hard and the number of monotone subsequences can reach [√2n＋1/1-1/2]in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than [√2n＋1/1-1/2]monotone subsequences in O（n^1.5） time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O（n^3）, a known greedy algorithm of time complexity O（n^1.5 log n）, and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.     

Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs

The constrained minimum vertex cover problem on bipartite graphs (the Min-CVCB problem) is an important NP-complete problem. This paper presents a polynomial time approximation algorithm for the problem based on the technique of chain implication. For any given constant ε > 0, if an instance of the Min-CVCB problem has a minimum vertex cover of size (ku, kl), our algorithm constructs a vertex cover of size (ku*, kl* ), satisfying max{ku*/ku, kl* /kl} 1 ε.     

一种带有链约束的连续型批处理机调度问题

针对链式约束下工件释放时间和工期同序的情况,证明了即使所有工件都是单位加工时间时,极小化最大拖期问题也是强NP-难的.对于工件的零时刻都到达且同一链中工件工期相同的特殊情况,给出了多项式时间的最优算法.     

基于C0复杂度和能量的语音端点检测算法

复杂性测度是反映信号序列的一个重要的非线性特征,复杂性测度的语音端点检测技术具有非线性技术的本质特征。对C₀复杂度作出改进,并与增强后的短时能量相结合,提出了一种更有效的端点检测算法——C₀复杂度能量的语音端点检测方法。实验证明,该算法对噪声有很强的鲁棒性,在低信噪比（0 dB）下仍能准确地检测出语音段。     

可伸缩变换编码在H．263下的应用研究

本文给出了一种复杂度可伸缩的实现转换编码器设计方法,实现了计算量与视频转换编码质量之间的平衡。提出了一种基于H．263编码模型的复杂度可伸缩算法。     

基于依赖矩阵的构件软件复杂性的度量模型

目前的构件软件复杂性度量模型未考虑构件之间不同依赖关系和软件构件内部复杂性两个重要因素,度量结果不够完整、准确.针对该问题,通过将软件体系结构抽象为加权的有向图,获得构件之间的依赖矩阵和影响矩阵,进而获取复杂性的度量公式.从度量公式分析和最后的示例可以得出,该度量模型可以更加真实、准确地反映构件之间不同的依赖关系和构件内部复杂性对软件复杂性的影响,而且具有简单、易于实现等特点.     

两台流水机器协调分解调度问题

研究钢管加工流程中一类新型两台机器流水车间调度问题,工件在第一台机器上加工后被分解成多个子工件.对于最小化最大完成时间的情况,给出一个多项式时间的最优算法;对于最小化最大完成时间与惩罚费用之和的情况,给出一个拟多项式时间的动态规划算法;对于考虑生产前运输的最小化最大完成时间的情况,分析了问题的复杂性.证明了第一种情况的最优算法可作为后两种情况的2-近似算法.数值实验表明了算法的有效性.     

F_p上周期序列S~∞与~∞的线性复杂度分析

研究了有限域Fp上周期序列S∞的极小多项式、生成函数和它的对偶序列S∞的极小多项式及生成函数之间的关系,并建立了明确的关系式。这一结果对研究流密码密钥序列线性复杂度有一定的应用价值。