基于悖论证明与局部搜索的不可满足子式求解算法

随着软硬件设计规模日益增加,功能越来越复杂,功能验证与调试在整个设计周期中占有的比重越来越大,迫切需要高效的方法诊断与定位设计中的错误,而求解不可满足子式可以显著提高自动化工具定位错误的效率.近年来,求解不可满足子式的算法多是基于DPLL(Davis-Putnam-Logemann-Loveland)回溯搜索过程的完全算法,很少有研究涉及到不完全方法.文中针对求解不可满足子式的不完全方法,提出了悖论证明与悖论解析树的概念,并提出一种启发式局部搜索算法,从布尔公式的悖论证明中求解不可满足子式.算法首先采用融合了布尔推理技术、动态剪枝方法及蕴含消除方法的局部搜索过程,逐步构建悖论证明所对应的悖论解析树;然后调用递归函数搜索悖论解析树,最终得到不可满足子式.基于实际测试集与随机测试集进行了实验对比,结果表明文中提出的算法优于同类算法,而且动态剪枝与蕴含消除技术能够有效地减少存储空间及运行时间.

云环境下安全的可验证多关键词搜索加密方案

云计算的高虚拟化与高可扩展性等优势,使个人和企业愿意外包加密数据到云端服务器。然而,加密后的外包数据破坏了数据间的关联性。尽管能够利用可搜索加密(SE)进行加密数据的文件检索,但不可信云服务器可能篡改、删除外包数据或利用已有搜索陷门来获取新插入文件相关信息。此外,现有单关键词搜索由于限制条件较少,导致搜索精度差,造成带宽和计算资源的浪费。为了解决以上问题,提出一种高效的、可验证的多关键词搜索加密方案。所提方案不仅能够支持多关键词搜索,也能实现搜索模式的隐私性和文件的前向安全性。此外,还能实现外包数据的完整性验证。通过严格的安全证明,所提方案在标准模型下被证明是安全的,能够抵抗不可信云服务器的离线关键词猜测攻击(KGA)。最后,通过与最近3种方案进行效率和性能比较,实验结果表明所提方案在功能和效率方面具有较好的综合性能。

证据计数法在落子类机器博弈中的应用

详细阐述了基于"与或树"的证据计数法原理,综述了证据计数法在一些落子类博弈系统中的应用;论述了证据计数法和PN2算法的缺陷.基于PN2算法,提出了一种两级的PN算法,即PN-DFPN,其中第一级采用标准的PN算法,第二级采用一种深度优先的PN算法代替PN2算法中的第二级PN算法,弥补了PN2算法存在的不足.将PN2和PN-DFPN算法应用于求解7×7和9×9棋盘的六子棋开局局面上,实验证明,PN-DFPN在搜索效率和求解能力上都明显优于PN2.

搜查理由及其证明标准比较研究

搜查作为对权利人“基本权利之侵犯”行为 ,国外及我国台湾等地区的法律在确定司法令状予以节制门槛后 ,仍难以避免搜查权力过度张扬而克扣、缩减个人正当权利 ,于是确立了搜查理由作为第二门槛 ,对此的证明标准因犯罪严重程度、搜查对象保护程度、搜查时间不同、被搜查权利人阻碍等差异设置了不同层次的要求。我国刑事诉讼法再修正时应借鉴其有益经验 ,在确立司法令状 (司法审查 )的框架内 ,针对搜查的不同情况 。

基于分布式集群的语料库防篡改检索方法

为了保证语料库的安全性,提出基于分布式集群的语料库防篡改检索方法。通过分布式集群运行结构,采用决策树ID3算法分析节点的检测属性,构建语料库行为样本判定数,挖掘语料库浏览行为数据;采用数据关键特征防篡改检索方法,将监控代码植入到语料库浏览行为数据中,对语料库资源数据各特征函数进行加密处理,从而实现资源数据加密及防篡改检索。实验结果表明,上述方法的浏览行为挖掘效率较高,且能够将篡改信息全部检索出来,防篡改检索错误率较低,应用该方法后可较大程度提高语料库的安全性。

MANET虚假路由形式化验证

提出了Ad-hoc网络虚假路由攻击的形式化验证和分析方法,主要是在参数化Ad-hoc路由协议串空间模型的基础上采用改进的Athena状态表示法来描述问题域,并采用相应的证明搜索过程来完成目标验证。最后设计实现了虚假路由自动验证系统FRpoofor,用它验证和分析了Ariadne安全路由协议运行环境下某些虚假路由的建立过程,以此说明方法的有效性。

基于关键点检测的数字打样颜色质量控制方法研究

针对数字打样准确模拟印刷颜色存在色差的问题,本研究提出基于影响ICC映射关系的关键颜色点检测的数字打样颜色质量控制方法。以ICC的数字打样颜色控制方法为基础,分析IT8.7/3色表的印刷样张和打印样张的基本色差(包括所有色块平均色差、四色实地色差、色差极差、灰平衡色块的平均△H、灰平衡色块的平均△E、纸白色差)、累积相关频率(CRF)分布曲线、阶调、彩度比等数据,检测出影响数字样张颜色质量的关键颜色点,编辑影响ICC映射关系的关键颜色点数据,优化印刷机ICC特性文件和数字打印机ICC之间的映射关系。实验显示,优化后的打印样张与印刷样张的基本色差均在要求范围之内;累积相关频率分布曲线落在基本匹配和理想匹配曲线之间,符合颜色模拟要求;打样阶调曲线完全接近印刷阶调曲线;彩度比集中在1左右,无小于0.5或大于1.5的比值。结果表明,本研究提出的检测关键颜色点,编辑影响ICC映射关系的关键点数据的方法能够实现数字打样颜色与印刷颜色的准确匹配。

比较法视域下西方国家刑事搜查证明标准考察——以完善我国刑事搜查证明标准为视角

伴随我国司法体制改革的逐步深入和社会主义法律体系的全面建构,《刑事诉讼法》的再修改势在必行,特别是随着刑事侦查理论的不断完善,被搜查人的人权保障日益受到学界的普遍关注,而作为《刑事诉讼法》重要内容之一的"刑事搜查证明标准"部分的规定却极不完善,相关司法解释对于被搜查人权利实现之救济机制亦存在诸多缺陷。且这些缺陷在《刑事诉讼法》再修改草案中并未得到实质性的改变。当前应借鉴西方国家刑事搜查证明标准的合理内核,从不断完善我国搜查行为的证明标准、被搜查人权利救济途径以及相关配套制度等方面着手,重构我国刑事搜查证明标准。

多项式等式型几何定理的可读证明

目前的智能几何软件都使用基于搜索法的定理证明器作为推理引擎,其主要缺点是不能可读地证明涉及到几何量代数运算的几何定理,这极大地限制了智能几何软件的实际应用.对一类结论为几何量多项式等式的几何定理,文中提出了一种能给出可读证明的启发式搜索算法.该算法通过引入多项式的变形操作算子——标准项代换,把证明结论为多项式等式g=0的几何定理转化为寻找从g到0的标准项代换序列的搜索问题.采用Lisp语言实现了该算法,并做了30个结论为几何量等式的几何定理的推理实验.实验结果表明算法具有较高的推理效率.

几种史学方法及其在医学史研究中的应用举隅

医学史研究的内容有结构层次的不同,而任何研究方法都有其相对应的研究对象和适用范围,如口述史学方法,乾嘉考据学方法;计量史学方法等,从不同的角度对医学史进行研究。

支持多关键字的可搜索公钥加密方案

为了提升可搜索公钥加密方案中服务器端关键字的搜索效率,提出了基于拉格朗日多项式的互逆映射构造方法和支持多关键字的可搜索加密公钥方案.该方案中,每组关键字对应一对互逆映射,发送者将该组关键字密文的变换结果输出给服务器,接收者向服务器发送陷门,只有当陷门关键字属于该组关键字时,服务器才能还原出陷门关键字的密文以进行匹配计算,仅需一次双线性对计算即可搜索多个关键字.该方案在标准模型中是语义安全的,关键字匹配效率较高且没有限制条件.

一种安全的具有匿名性的可搜索加密方案

2004年,Boneh等利用匿名的基于身份加密方案构造了一个公钥可搜索加密方案(PEKS),解决了特定环境下对加密数据进行检索的这一困难工作。已有的可搜索加密方案,都是实现对关键词信息的保护,其实一个真正安全的可搜索加密方案,在保证搜索能力的前提下,不仅要实现对关键词信息的保护,也要实现对消息查询方信息的保护。提出具有匿名性的基于身份可搜索方案(ANO-IBEKS)的构造算法,给出了方案在随机预言机模型下语义安全性的证明。该方案可以很好地解决大量数据交给第三方服务器存储(比如网络存储)的关键词密文查询问题,可以有效地保护查询关键词和查询者身份等敏感信息,无法追踪究竟是哪个用户查询了什么信息。

比较法视野中的刑事搜查证明标准

刑事搜查是侦查机关获取犯罪证据的有效侦查手段,它也是可能侵犯公民人身权、隐私权以及财产权等基本权利的强制措施。因此,国外主要法治国家均对侦查机关的搜查行为规定了严格的证明标准或条件。我国刑事诉讼中的搜查法律规范非常粗放,侦查机关的搜查行为具有较大的随意性,侦查机关无须向第三者证明采取搜查措施具有必要性和正当性,对公民的基本权利造成损害的搜查屡见不鲜。借鉴法治国家的成功制度和技术性规定以完善我国的搜查实为必要。

浅谈通信领域专利审查中公知常识的检索和举证

本文以牢固树立证据意识,规范公知常识使用为出发点,参考了欧洲、美国、日本关于公知常识的规定,并归纳了通信领域中公开技术信息的典型载体,以及各载体便于检索的"公知常识库",在此基础上,挖掘了一些新的公知常识来源及其检索方法,并就公知常识的举证和适用提出了一些建议。

使用不同的博弈树搜索算法解决计算机围棋的吃子问题

使用Alpha-Beta搜索和proof-number(pn)搜索解决计算机围棋的吃子问题.对吃子问题形式化并给出了简单有效的评估函数.Alpha-Beta搜索使用了包括置换表在内的各种扩展技术.pn搜索使用了包括df-pn在内的4种变体.研究结果显示,对于解决吃子问题pn搜索优于Alpha-Beta搜索.并且搜索过程中所产生的数据的一些模式可以帮助在结果未知的情况下对结果进行预测.所设计的算法可以用于解决单独的吃子问题或者计算机围棋比赛中的吃子计算.

图搜索问题算法推导及形式化证明

用非形式化方法解决图搜索问题规模受限,对于一些复杂问题难以保证其正确性.传统的形式化方法推导图搜索问题难以理解且不易于形式化证明,现有形式化方法对这类问题的解决方案较少,在保证可靠性和正确性方面有欠缺.该文通过对图搜索问题的深入研究,开发出一种针对解决图搜索算法的新方法.首先刻画问题的规约,利用循环不变式的递归定义技术给出了开发图搜索问题循环不变式的新策略,在此基础上得到Apla抽象算法程序,并对该算法程序进行了形式化证明,再将已验证的Apla算法程序自动生成C++可执行程序,实现了从抽象的形式规约推演出具体的面向计算机的程序代码的程序精化完整过程.以拓扑排序和广度优先遍历为例对所提方法进行实验,实验结果验证了所提方法的有效性,不仅可以推导和证明已知算法,而且对未知算法的推导也有指导性作用.

让曹雪芹哭笑不得的“旷世知音”——兼与刘再复先生商榷

刘再复先生给今年即将再版的梁归智的《红学泰斗周汝昌传》作序,他的题目直言"周汝昌是中国文学第一天才的旷世知音"。刘先生的"首先如此肯定曹雪芹的无比崇高地位的是周汝昌先生"的论断是错误的。纵观周汝昌研红的一生及成果只能证明他"根本不懂《红楼梦》",在《红楼梦》研究上他一生都是在证假为真,都是在曲解、颠覆《红楼梦》的思想内容、艺术构思。周汝昌其实不是考证派,而是典型的索隐派;他的一切所谓的考证,其实都打着索隐派的烙印,他也把自己定位为索隐派。他的索隐其实都是脱离了文本的"悟证",是猜笨谜,乱索隐。因此,他绝对不能被称为中国文学第一天才曹雪芹的旷世知音。

“政府信息不存在”案件举证责任问题研究--以指导案例101号案件为例

属于行政机关应当制作或者保护的政府信息自始至终不存在,或者之前存在但由于某种原因已经灭失,行政机关在这两种情况下可以做出“政府信息不存在”的答复。在由此引起的“政府信息不存在”诉讼案件中,由于否定性事实难以证明,行政机关应当对其尽到充分合理的检索、查询义务进行举证,以证明其“政府信息不存在”的主张。对行政机关已经履行举证责任而原告不服的,由原告承担政府信息存在的证明责任。人民法院应当对案件采取重新审查的证明标准,发挥人民法院依法调取证据的职能,实现对案件事实的把握。

逐步逼进法测规定非比例伸长应力在微机上的应用

本文介绍了在拉力试验机微机系统上结合拉力试验标准,独立开发的一个具有广泛应用价值,操作简便、运算速度快的微机系统程序——采用逐步逼进法测定规定非比例伸长应力的微机系统程序。并且阐明了程序的编制过程、原理以及使用特点和效果。

基于感知哈希的英语语料库防篡改检索方法

为进一步提高各种英语语料库的安全性,提出一种基于感知哈希的英语语料库防篡改检索方法,实现检索安全性的进一步提升。其中,英语语音特征的提取选择改进的PNCC特征提取法;通过感知哈希技术对语音特征进行进一步处理。仿真结果表明,使用提出的检索方法进行英语语音检索,能够进一步提高检索系统的安全性和鲁棒性,验证了改进的可行性和检索方法的优越性,具有一定的实用价值。