二元关系的性质测试及其复杂性分析

本文介绍了性质测试的基本原理,分析了用性质测试方法解决参数化问题的可行性,并将同构性质进行了参数化。研究了二元关系的性质测试以及参数化框架同构性质的测试问题,对固定的距离参数,证明了测试复杂性低于标准判定程序的复杂性。     

基于DPLL的混合遗传算法求解SAT问题

基于"聚类排序选择"优化遗传算法求解SAT问题时,引入交叉算子和变异算子,并根据适应度函数及问题本身特性,调节阈值δ,生成新的种群聚类。这种遗传算法有效地抑制了算法的延迟收敛,从而保证了为可满足性公式能够快速找到一个可满足性指派。同时,在遗传算法中引入了DPLL算法,对部分变元进行消解,提高了算法的求解效率。相关的实验数据表明,本算法的性能明显优于同类算法。     

不可满足公式的同态证明系统

合取范式(CNF)公式H到F的同态φ是一个从H的文字集合到F的文字集合的映射,并保持补运算和子句映到子句.同态映射保持一个公式的不可满足性.一个公式是极小不可满足的是指该公式本身不可满足,而且从中删去任意一个子句后得到的公式可满足.MU(1)是子句数与变元数的差等于1的极小不可满足公式类.一个三元组(H,φ,F)称为的一个来自H的同态证明,如果φ是一个从H到F的同态.利用基础矩阵的方法证明了:一个不可满足公式F的树消解证明,可以在多项式时间内转换成一个来自MU(1)中公式的同态证明.从而,由MU(1)中的公式构成的同态证明系统是完备的,并且由MU(1)中的公式构成的同态证明系统与树消解证明系统之间是多项式等价的.     

带非线性优先连接规则增长模型的节点度分布

把非线性优先连接规则、每一时间步添加新节点或新边等考虑在内,提出了一种更一般的复杂网络增长模型,给出并采用概率方法严格证明了该模型的节点度分布表达式,利用节点度分布表达式计算了2个不同节点加权函数对应网络模型的节点度分布。研究结果表明,已有的一些著名网络模型为该模型的特例,相应网络模型的节点度分布也可由该模型的节点度分布表达式得到。此外,针对2个不同加权函数对应网络模型的实验结果表明,理论结果与仿真实验结果相符。     

BAN逻辑的可靠性分析与改进

BAN逻辑的推理过程中可能引入错误的推理条件,导致不安全的协议被验证为安全的。为解决该问题,对消息的形式化描述方式进行改进,在消息含义推理规则中加上一个隐含但不能被忽略的条件,以增强验证的可靠性,通过对发送和推理的消息单元进行限定,使消息新鲜性判定规则适用于更多类型的协议安全性验证。     

一种求解多处理机调度问题的a-平坦化调度算法

在分析多处理机调度问题的基础上,提出了α-平坦的概念,并将其引入到多处理机调度问题中;基于此,提出了一种新的基于α-平坦的求解多处理机调度问题的算法。算法首先对作业集合做平坦化处理,然后再对处理后所得的新问题进行求解,最终获得原调度问题的一个近似解。实验结果表明,通过该算法可以求得较好的结果,相对于其它启发式算法,该算法具有较好的稳定性。     

基于模板的．Net三层架构的代码自动生成

三层架构是数据库开发中最常用的分层架构。三层结构能够提高代码重用率,降低项目开发难度。为了解决手工编写三层架构的代码工作量大且容易出错的问题,使用．Net平台提供的动态编译和反射技术,设计并实现了基于可定制模板的自动代码生成器。该代码生成器利用三层架构的代码依赖数据库的架构信息这一特点,以数据库架构信息、Xml配置文件和模板文件作为输入,输出三层架构的各层代码。用户可以修改Xml配置文件的内容和使用该代码生成器提供的模板语言定制、修改自己的模板文件,方便、灵活地控制输出的目标代码。代码生成器的使用在实际的项目开发中具有重要的意义。     

基于模板的. Net 三层架构的代码自动生成

三层架构是数据库开发中最常用的分层架构.三层结构能够提高代码重用率,降低项目开发难度.为了解决手工编写三层架构的代码工作量大且容易出错的问题,使用. Net 平台提供的动态编译和反射技术,设计并实现了基于可定制模板的自动代码生成器.该代码生成器利用三层架构的代码依赖数据库的架构信息这一特点,以数据库架构信息、Xml配置文件和模板文件作为输入,输出三层架构的各层代码.用户可以修改 Xml 配置文件的内容和使用该代码生成器提供的模板语言定制、修改自己的模板文件,方便、灵活地控制输出的目标代码.代码生成器的使用在实际的项目开发中具有重要的意义     

一种有效的求解一维下料问题的启发式算法

使用了一种改进的顺序启发式算法,在排样方式的生成过程中不断修正当前排入毛坯的价值,使之趋于合理,依次选取求解背包函数获得的最大单位价值的排样方式组成当前排样方案,迭代调用该过程多次,最终选取最优的排样方案。在保证较高材料利用率的同时考虑减少排样方式,增加最后一根材料余料长度等多个优化目标。通过多组实验结果比较,证实了算法的有效性。     

基于自动机并操作的多目标AC-BM算法

AC-BM算法的优点在于能同时进行多个模式串的匹配搜索,且文本串的移位得到优化,但一次只能在一个文本串中进行搜索.为了实现一次可以同时在多个文本串中进行搜索,设计了多目标AC-BM算法.利用自动机并操作技术构造多目标多模式树自动机,借助BM算法的坏字符跳转技术来计算文本串集移位.在Snort系统中分别实现2-目标AC-BM算法和3-目标AC-BM算法.实验结果表明,新算法如果在多个文本串中找到模式串就停止(表示检测到攻击行为),其在时间性能上就明显优于AC-BM算法.