检索结果-南通市图书馆

计算机应用 2014年第7期34卷 2080-2084页

作者：陈明雁曾振柄上海高可信计算重点实验室(华东师范大学) 上海200062 上海大学数学系上海200444

将几何定理机器证明的研究方法概括为确定性算法与概率性算法两大类,针对已有的确定性算法和概率性算法的证明速率偏低或占用内存过大等问题,提出一种改进的概率性算法。主要是在改进对多项式中独立变元次数的上界估计的算法的基础上,结... 详细信息

将几何定理机器证明的研究方法概括为确定性算法与概率性算法两大类,针对已有的确定性算法和概率性算法的证明速率偏低或占用内存过大等问题,提出一种改进的概率性算法。主要是在改进对多项式中独立变元次数的上界估计的算法的基础上,结合Schwartz-Zippel定理和统计学理论,通过随机检验若干实例来证明几何定理,并能控制证明结果不真的概率在给定的小范围内。通过改进的概率性算法,成功在2秒内证明出代数法难以证明的五圆定理。最后的多组对比实验进一步表明,改进的概率性算法具有明显高效性。

关键词：几何定理机器证明确定性算法概率性算法构造性几何变元次数上界

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

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

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

引用

作者：陈明雁华东师范大学

学位级别：硕士

几何定理机器证明是指通过机器自动地证明几何定理,常用的证明方法可分为三类：代数法、向量法以及基于推理数据库的搜索法。上述三类方法都属于确定性方法,即只要按正确的步骤计算执行,总能得到确定性的结果。然而,当涉及到复杂问题时... 详细信息

几何定理机器证明是指通过机器自动地证明几何定理,常用的证明方法可分为三类：代数法、向量法以及基于推理数据库的搜索法。上述三类方法都属于确定性方法,即只要按正确的步骤计算执行,总能得到确定性的结果。然而,当涉及到复杂问题时,确定性方法的复杂度会偏高,从而严重影响到解题的效率。于是,便有了与“确定性”方法相对应的能够高效执行的“概率性”方法。为此,国外已有研究学者开始探索概率性方法在几何定理机器证明的应用,并取得了一定的成效。但是目前国内尚未有人对概率性方法进行研究,并且已有的确定性方法和概率性方法尚存在复杂度过高或者对非线性类构造性几何定理的证明力度偏弱等问题。本文针对已有的确定性方法和概率性方法的证明速率偏低或占用内存过大等问题,从代数簇构造理论出发,对几何定理机器证明的概率性方法做了以下研究工作：(1)提出一种改进的估算余式次数上界的算法。分析构造性几何定理的多项式组代数簇的不可约分解的基本特点,在此基础上提出了一种改进的估算余式R(结合假设部分的多项式组消去结论部分多项式的全部约束变元后得到的只含独立变元的多项式)关于每个独立变元次数的上界的快速算法。在改进的算法的基础上,成功推导出构造性几何定理的余式R关于每个独立变元次数的上界满足Bound1=O(30[n/2])。此外,若定理限制为线性类的构造性几何定理,则还可将其上界改进为Bound2=O(3n)。(2)提出三种统计总体采集标准。在改进算法和相关推论基础上,结合Schwartz-Zippel定理和统计学理论,提出了三种不同的具有一定针对性和适用范围的统计总体采集标准。其中,第一和第二种采集标准是基于改进的算法提出来的,而第三种则是针对改进算法的推论提出来的,二者具有不同的适应范围。在实验部分,我们还设计了对比实验对这三种采集标准的适用范围进行分析和评价。(3)比较分析两种实例检验方法。给出两种不同的随机实例检验方法,即数值检验法和连续伪除检验法。文中还进一步探讨了这两种检验方法对退化情况及多项式组可约性情况的处理方法。最后还结合多组对比实验数据对这两种不同的检验方法的适用性进行评价。(4)开发基于概率检测组合模型的几何定理证明器——-ProbProvero在上述理论研究和分析的基础上,本文还进一步设计了概率检测组合模型并对模型进行了显著性检验及统计错误分析。进一步地,我们采用Maple编程语言实现此基于概率检测组合模型的几何定理证明器——ProbProver。通过ProbProver证明器,我们成功在2秒内证明了代数法难以证明的Five Circles和Miquel定理。为了进一步证实本文提出的基于概率检测组合模型的几何定理证明器具有一定的高效性,本文从多个维度出发,对若干个复杂程度不尽相同的几何定理进行了多组重复实验。实验数据表明,本文提出的基于概率检测组合模型的几何定理证明器具有显著的高效性,并具有一定的应用前景。

关键词：定理机器证明构造性几何概率性方法代数簇不可约分解变元次数上界统计总体采集标准

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：