基于概率检测组合模型的几何定理证明器

被引量 : 0次 | 上传用户:htagsll
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
几何定理机器证明是指通过机器自动地证明几何定理,常用的证明方法可分为三类:代数法、向量法以及基于推理数据库的搜索法。上述三类方法都属于确定性方法,即只要按正确的步骤计算执行,总能得到确定性的结果。然而,当涉及到复杂问题时,确定性方法的复杂度会偏高,从而严重影响到解题的效率。于是,便有了与“确定性”方法相对应的能够高效执行的“概率性”方法。为此,国外已有研究学者开始探索概率性方法在几何定理机器证明的应用,并取得了一定的成效。但是目前国内尚未有人对概率性方法进行研究,并且已有的确定性方法和概率性方法尚存在复杂度过高或者对非线性类构造性几何定理的证明力度偏弱等问题。本文针对已有的确定性方法和概率性方法的证明速率偏低或占用内存过大等问题,从代数簇构造理论出发,对几何定理机器证明的概率性方法做了以下研究工作:(1)提出一种改进的估算余式次数上界的算法。分析构造性几何定理的多项式组代数簇的不可约分解的基本特点,在此基础上提出了一种改进的估算余式R(结合假设部分的多项式组消去结论部分多项式的全部约束变元后得到的只含独立变元的多项式)关于每个独立变元次数的上界的快速算法。在改进的算法的基础上,成功推导出构造性几何定理的余式R关于每个独立变元次数的上界满足Bound1=O(30[n/2])。此外,若定理限制为线性类的构造性几何定理,则还可将其上界改进为Bound2=O(3n)。(2)提出三种统计总体采集标准。在改进算法和相关推论基础上,结合Schwartz-Zippel定理和统计学理论,提出了三种不同的具有一定针对性和适用范围的统计总体采集标准。其中,第一和第二种采集标准是基于改进的算法提出来的,而第三种则是针对改进算法的推论提出来的,二者具有不同的适应范围。在实验部分,我们还设计了对比实验对这三种采集标准的适用范围进行分析和评价。(3)比较分析两种实例检验方法。给出两种不同的随机实例检验方法,即数值检验法和连续伪除检验法。文中还进一步探讨了这两种检验方法对退化情况及多项式组可约性情况的处理方法。最后还结合多组对比实验数据对这两种不同的检验方法的适用性进行评价。(4)开发基于概率检测组合模型的几何定理证明器——-ProbProvero在上述理论研究和分析的基础上,本文还进一步设计了概率检测组合模型并对模型进行了显著性检验及统计错误分析。进一步地,我们采用Maple编程语言实现此基于概率检测组合模型的几何定理证明器——ProbProver。通过ProbProver证明器,我们成功在2秒内证明了代数法难以证明的Five Circles和Miquel定理。为了进一步证实本文提出的基于概率检测组合模型的几何定理证明器具有一定的高效性,本文从多个维度出发,对若干个复杂程度不尽相同的几何定理进行了多组重复实验。实验数据表明,本文提出的基于概率检测组合模型的几何定理证明器具有显著的高效性,并具有一定的应用前景。
其他文献
针对船舶集控系统中直流电源网络绝缘检测需要,在深入研究常用直流电源网络绝缘检测方法的基础上,提出了一种多路绝缘检测实现方案;以CPLD为核心器件设计了绝缘检测注入信号
随着全业务运营时代的到来,电信业之间的竞争业日趋激烈,在新的竞争形势下,能否对市场变化作出快速反应将是企业运营成败的关键。传输资源是电信行业的一项重要的战略性资源,是承
背景和目的经皮肾镜技术经过半个多世纪的发展,在和传统开放手术的竞争中,逐渐体现出独特的优势,并成为了复杂性肾结石的首选治疗方法。随着科技的进步,操作水平的提高,近年来不少
中国“五四“新文学中的“零余者”形象是从屠格涅夫笔下的“多余人”形象接受而来,“局外人”也是“世纪病”患者之中的典型代表,但我们不难发现,这三类人物身上具有相同的
天津滨海新区列入国家总体发展规划以来,如何实现各项资源和政策的协调整合,促进滨海新区持续快速发展成为热点问题。作为服务滨海新区的海关机构,天津海关制定了全面推进改
分析了感染科医院感染的特点,探讨了加强感染科医护人员职业防护的有效措施。认为制定并健全医护人员的职业安全管理制度,采取有效的防护措施,加强医护人员的培训,是减少感染
太阳磁暴和直流输电在大地中形成的准直流电流和直流电流,会影响变压器铁心的磁化特性和电网的正常运行。利用单相三柱变压器进行不同直流偏磁条件下的直流偏磁实验。实验结
目的针对肠外营养治疗在妊娠剧吐患者的中的治疗效果进行观察。方法以本院在2015年6月到2016年6月间接收的妊娠剧吐患者20例患者为对象,任选其中10例,采用全肠外营养治疗,为
"新课程标准修订稿"充分关注语文教学中的"整体观照"思想,要求我们的课堂需在教材研读、目标制定、内容设计、课堂执行、反馈评价等环节凸显整体意识,促进各模块间的有机融合和学
仪表自动化已经有很长的一段历史了。随着电子信息技术,高新科技的迅猛发展,仪器仪表的自动化程度越来越高,仪表自动化越来越向系统性、整体性和连贯性发展。在各种项目建设