随机正则(k,r)-SAT问题的可满足临界

研究k-SAT问题实例中每个变元恰好出现r=2s次,且每个变元对应的正、负文字都出现s次的严格随机正则（k,r）-SAT问题.通过构造一个特殊的独立随机实验,结合一阶矩方法,给出了严格随机正则（k,r）-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等,因此得到了随机正则（k,r）-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则（k,r）-SAT问题的可满足临界值上界,而且还小于一般的随机k-SAT问题的可满足临界值.因此,这也从理论上解释了在相变点处的随机正则（k,r）-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后,数值分析结果验证了所给上界的正确性.     

并行机生产与具有等待时间限制的成批运输协调调度问题

研究了运输阶段具有等待时间限制的成批运输与并行机生产协调调度问题,目标为最小化制造期与运输费用之和．通过复杂性分析,证明其是强NP难问题,提出启发式算法并证明其最坏情况性能比为4—1／m．当一个运输批必须在同一台机器加工时,证明其也是强NP难问题．将加工时间与等待时间限定值进行比较,分别提出两个启发式算法,并证明其最坏...     

若干限制形式的缺少推理的复杂性

该研究判定一字是否出现在缺省理论〈Ｄ,Ｗ〉的某一扩张中的复杂性,其中,Ｄ是一种Ｈｏｒｎ缺省规则,而Ｗ是ｄｅｆｉｎｉｔｅ公式或Ｂｉ－Ｈｏｒｎ公式。     

数值计算程序的存储复杂性分析

由于越来越多的技术用于缩小处理器与存储器之间的日益加大的速度差距,计算机的存储系统变得日趋复杂．现在,任何一个程序设计者,尤其是数值计算程序的设计者,若不考虑其所用计算平台存储系统的特点是很难获取高性能的．因此公用传统的算法评价方法,从时间复杂性和空间复杂性着手来解释一个算法的不同实现在同一计算平台上很大的性能差异,显然是不够的．计算平台存储系统的特点必须在分析算法的复杂性时加以考虑．孙家昶１９９     

Backbone analysis and algorithm design for the quadratic assignment problem

As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.     

长途通信大楼综合布线应用设计方案

工程概况 该长途通信大楼是由主楼和裙房两部分组成。主楼地下二层,地上三十三层,裙房地下一层,地上四层,建筑面积为5．8万多平方米,高达168米。其各系统的复杂性和重要性,对结构化综合布线系统提出了很高的要求。     

将过程控制进行到底

常州伍杰科技软件有限公司新近推出的拥有完整自主知识产权的产品,《软件数据管理系统USDM》,为CMMI的推行提供了一个较为完整的解决方案。在该解决方案中,首次提出管理作业和车间作业的概念,这样,既将管理流程和生产作业做了适当的分离,又保持它们的衔接关     

Special Issue on New Trends in Theory and Applications of Complex Control Systems

Complexity is one of the leading features of modern control systems. It is caused by the complex properties of controlled plants and the varied requirements in controller designs. In dealing with the control problems with complexity, in the past two decades, a lot of papers have been published that reported fruitful results on different