布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。

伪布尔链上的α、β算子

提出了伪布尔链上的α和 β算子 。

基于伪布尔模型和启发式算法求解无容量设施选址问题

采用伪布尔模型和启发式算法来求解无容量设施选址问题。首先给出了问题的伪布尔(pseudo-Boolean)表示,然后基于Khumawala规则对问题进行预处理,最后提出两种启发式分支准则来求解问题。实验结果表明所提算法简单有效。

一类可优化的平方伪布尔函数

该文给出一类平方伪布尔函数ｆ（ｘ）＝ｘＱｘ￣Ｔ＋ｃｘ￣Ｔ＋ｄ，它的最小点与最小值可在线性时间内找到。其基本思想在于将Ｑ和Ｃ所关联的图转换为由ＮＯＴ，ＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲ，ＸＯＲ和ＸＮｏＲ门组成的逻辑电路，后者的相容信号值对应伪布尔平方函数的最小点。这种方法建立了平方伪布尔函数与逻辑电路之间的结构关系。

基于伪布尔可满足性的纳米CMOS电路单元配置

针对传统布尔可满足性(SAT)法在处理纳米CMOS电路(CMOL)单元配置时,存在合取范式(CNF)表示的约束子句个数过多、中间处理文件过大的问题,该文提出了利用伪布尔可满足性(PBS)来解决CMOL电路的单元配置问题。实验结果显示,相对于传统的SAT法,PBS法在不增加额外的布尔变量集个数的条件下,通过降低编码过程中的约束个数,能有效减少中间处理文件大小,达到提高算法效率和提高处理大电路的能力。

一种基于伪布尔可满足性FPGA布线算法

为了克服布尔可满足性算法在现场可编程门阵列布线中存在的不足,引进了一种在标准对称阵列(隔离岛状)现场可编程门阵列结构下的新型有效布线方法——伪布尔可满足性算法,并结合实例详细地阐述了将其应用于布线的原理及方法,同时采用实际工业电路将布尔可满足性算法与伪布尔可满足性算法作出比较。实验结果显示,伪布尔可满足性算法比布尔可满足性算法在布线时间上减少了10.5%,在稳定性上提高了3.3%。

线性伪布尔方程的计算机求解

伪布尔方程的求解在逻辑综合、故障诊断、网络理论和优化设计等领域是一个极需解决的问题．作者用Ｖｉｓｕａｌｃ＋＋和ＭｉｃｒｏｓｏｆｔＷｉｎｄｏｗｓ采用分枝算法编制了一个求解伪布尔方程的程序，通过读入伪布尔方程的参数，给出相应的求解结果．

基于伪布尔函数的n人对策模糊延拓方法

基于伪布尔函数,给出了不同于传统多重线性延拓和cornet延拓的一种n人对策的模糊延拓方法.由于n人对策中任意的联盟可由它的特征向量来等价的表示,利用伪布尔函数,将n人对策从集合{0,1}~n延拓到[0,1]~n上,详细讨论了这种模糊延拓的性质,研究它与经典n人对策的Shapley值之间的关系.

基于汉明重的LED代数旁路攻击研究

对CHES 2011会议提出的LED轻型分组密码抗代数旁路攻击能力进行了评估。给出了密码算法代数旁路攻击模型及LED密码代数方程表示方法;利用示波器采集微控制器ATMEGA324P上的LED实现功耗泄露,选取功耗特征较为明显的部分泄露点,基于Pearson相关系数方法推断加密中间状态汉明重;分别基于可满足性问题、伪布尔优化问题、线性编程问题给出了LED密码和汉明重泄露的3种代数方程表示方法;使用CryptoMinisat和SCIP 2种解析器对建立的代数方程求解恢复密钥,在已知明文、未知明密文、容错等场景下进行了大量的攻击实验。结果表明,LED易遭受代数旁路攻击,一条功耗曲线的1轮汉明重泄露分析即可恢复64 bit完整密钥。

基于代数决策图的路由查找算法

为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。

特征建模及图象处理

本文提出了一种图象处理与特征造型相结合的造型手段，利用图象处理的技术把三维布尔运算转化为在一维区间上处理，从而避免了实体造型中布尔运算的不稳定性．特征信息的加入使参数化修改成为可能，并在修改时自动进行关联性检查，方便了设计人员的设计与修改．该造型手段保存的信息能用于后序加工．

剩余格中基于核映射的滤子

在剩余格中,基于核映射引入了对合滤子、扩展对合滤子、Glivenko滤子的概念,讨论了它们的性质且给出了它们的特征定理。分析了滤子的一种带有核映射的扩张形式的代数性质,得到了扩展对合滤子的应用。进一步,在MTL代数中引入了相对伪布尔滤子的概念,得到了相对伪布尔滤子的特征定理。

逻辑电路的神经网络

Ｍ．Ｌ．Ｂｕｓｈｎｅｌ教授和作者给出了ＮＯＴ，ＡＮＤ，ＯＲ，ＮＡＮＤ，ＮＯＲ，ＸＯＲ和ＸＮＯＲ门的神经网络．以这些门的神经网络为基础，可构成任何逻辑电路的神经网络．由此，将电路的相容信号转换为平方伪布尔函数的全局极小．从而。

H-GRASP:一种基于GRASP改进的混合SAT解法器

为了改善GRASP的局限性,提出了一种能解决含有伪布尔(PB)和合取范式(CNF)混合约束问题的新的混合算法(H-GRASP)。该新算法采用了切削平面技术来提取PB约束条件之间的推论,并把它结合到普通的蕴涵图中,分析引起冲突的学习。与解决混合约束问题的其他两种方法——整数线性规划和纯基于SAT方法进行了彻底的比较。实验结果证明,H-GRASP方法从整体上大大减少了运行时间,加快了速度,同时还保证了加入这种方法的低耗费。

一种改进的子集可满足性算法用于FPGA布线

介绍了用布尔可满足性(SAT)和子集可满足性(sub-SAT)算法解决FPGA的详细布线问题。在布线资源固定的FPGA布线环境中,布尔公式可以证明所给电路的不可布通性,这一点要优于典型的one-net-at-a-time方法。子集可满足性方法把一个有N个约束的"严格的"SAT问题转换成一个新的"松弛的"SAT问题,仅当在原始问题中变量的不可满足个数不超过阈值k(kN)时,这一问题是可满足的。它改进了布尔可满足性,但是却产生了很多额外的变量和子句。针对这一问题,提出了用伪布尔可满足性(PBS)来消除子集可满足性公式带来的缺点。初步的实验结果表明,把这个方法加入子集可满足性方法中可以减少变量和子句数量,并显著减少运行时间。

矩阵的半张量积在进化博弈论中的应用

分析了进化博弈论,利用矩阵的半张量积方法,结合伪布尔函数的代数结构,给出了进化博弈中进化稳定策略的一种计算方法.

基于影响网络的混合约束作战方案优化方法

在复杂不确定的战场环境中,军事决策人员面临的首要问题是确定满足一定约束条件、优化的作战方案。研究考虑资源和协同约束,利用影响网络度量作战方案的优劣程度,建立基于影响网络的混合约束作战方案优化问题。优化问题是一个伪布尔约束和布尔约束混合、优化目标非解析表达的0-1整数优化问题。同时,提出遗传算法结合伪布尔约束求解的方法对优化问题求解,通过测试案例对该优化方法的有效性进行验证。