两个参数化匹配计数问题的难度分析

匹配计数问题是一个著名的难问题,考虑它的两个参数化问题p-deg-#MATCHING与p-#MATCHING,证明了p-deg-#MATCHING是固定参数易解的,p-#MATCHING有固定参数易解随机近似方案.     

有限等待置换流水车间调度问题的IGA算法

在对经典遗传算法进行研究的基础上,针对具有等待时间置换流水车间调度问题,以最小化最大完成时间为优化目标建立整数规划模型,并提出一种解决该问题的IGA算法。算法中部分染色体的初始种群由原问题所转化而成的具有等待时间两台机器的置换流水车间调度问题的解所组成。交叉方法采用基于顺序和位置相结合的OPX方法。通过对Taillard算例中置换流水车间调度问题基准数据的测试,并对仿真实验的结果进行了分析,验证所提出IGA算法的有效性和可行性。     

一些简化的NP完全实例类

(k，s)-SAT是命题满足性问题限制在一种特殊的命题公式上，该命题公式具有每个子句只有k个不同的文字且每个变元出现的次数少于s次的特点。已经验明对于正整数k，s存在一个指数函数f，满足：对任意s≤f(后)，所有的(k，s)-SAT例都是可满足的，而(k,f(k)-SAT却是一个NP-完全问题。目前为止，只知道f(3)和f(4)的精确值．对于，是否可计算是一个仍未解决的问题．由于每个满足某种条件的数值序列对应一个MU(1)中的公式，在[2]中，作者S．Horry和S．Seizder通过对数值序列的运算来构造(k，s)-SAT中的MU(1)公式例，得到了函数厂的可计算上界函数。但当k比较大时，该方法不太实用。作者定义了一种树规则来减少数值计算的步数，得到了一个确定的实用的算法来计算函数f的上界，该上界接近[2]中的上界，同时，也得到了一些NP-完全满足性问题类。     

图论意义下的Laplace定理

根据Valiant图论方法给出的矩阵行列式定义，证明了图论意义下的Laplace定理。     

基于一种树型方法的自动推理

根据表方法建立了一种树型证明方法,在机器实现方面比表方法优越,而且还可以证明这一方法是可靠的和完备的.以PROLOG语言为背景,实现了由此方法而建立的命题逻辑中命题演绎的自动推理.     

范式的PROLOG程序实现

本文使用PROLOG语言程序,对一阶逻辑中命题公式的真值表和谓词公式的前束范式进行了处理。文章分为两个部份:     

随机图G(2n,p)中k-匹配的相变性质

随机图G(n,p)模型中有两个参数n和p,n表示图中的结点数,p表示图中任意两个不同结点之间独立生成边的概率。证明了随机图G(2n,p)中存在k-匹配的临界值为p=kn-2。实验分析了随机图G(2n,p)实例中10-匹配和25-匹配以及k=n-1匹配的相变。最后总结出临界函数与匹配的边数和结点数有关系。实验表明,理论与实验一致。     

随机均衡正则恰当(2s,k)-SAT问题的可满足相变

为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s?.当ss?时,随机均衡正则恰当(2s,k)...     

高职院校物流管理专业项目式教学模式探索

项目教学法是通过＂项目＂的形式进行教学,是一种将理论知识和实际项目相结合的教学模式,通过项目的处理来提高学生分析问题、解决问题的综合能力,在实施项目教学法时,重点研究项目的设计和实施.