没有合适的资源?快使用搜索试试~ 我知道了~
懒惰思维算法综合:实例与定理实现
理论计算机科学电子札记93(2004)24-59www.elsevier.com/locate/entcs基于懒惰思维的算法综合:实例与定理实现BrunoBuchberger1 AdrianCrapuzziun2RISC -符号计算研究所约翰内斯开普勒大学奥地利林茨摘要最近,我们提出了一个系统的方法,自顶向下的综合和验证的引理和算法所谓的“宽松的知识管理方法”作为一个部分的系统的懒惰思维方法的特点是:• 通过使用定理和算法方案库• 以及通过使用包含在失败尝试中的信息来分别证明用于发明引理或子算法要求在本文中,我们给出了几个使用懒惰思维范式的算法综合的例子这些示例说明了合成算法如何取决于所使用的算法方案。并在Theorema系统的框架在该实施方式中,示例算法的合成可以完全自动地执行,即没有任何用户交互。关键词:算法发明,算法验证,程序综合,算法正确性,可重用算法,算法方案,从失败中学习,猜想生成,懒惰思维,需求工程,编程教学法,数学知识检索,数学知识管理,排序,合并,归并排序,定理。由FWF(OüsterereichischerFondszurFoürderungderWissenschaftlichen)提供的1个关键点Forschung; Austrian Science Foundation),项目SFB 1302,在J o h a nnes Keple r Uni v e r s i t y,Linz,Austria的SFB“Scientic C o mputing g“的框架内。电子邮件地址:buchberger@risc.uni-linz.ac.at2由Calculemus欧洲项目赞助。电子邮件地址:acraciun@risc.uni-linz.ac.at1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2003.12.027B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24251介绍自2001年以来,第一作者在各种演讲中介绍了正确算法合成的懒惰思维方法,参见会议论文[5]。算法综合的懒惰思维方法是对[4]中引入的引理发明的懒惰思维范式的改编。引理发明是系统理论探索的一般哲学的一部分,参见[4],作为在自动定理证明领域中流行了几十年的孤立定理证明范式的替代方案。系统理论探索是新兴领域“数学知识管理”的主要主题之一,粗略地说,我们的懒惰思维算法合成方法如下:• 我们从特定数据域中的算法(谓词逻辑)规范开始。我们假设所有出现在规范中的辅助运算(函数和谓词)都被定义,并且这些运算的所有重要性质都是已知的,也就是说,• 该方法现在一个接一个地尝试存储在给定数学域的算法方案库中的各种一个算法方案是一个谓词逻辑公式,它用未指定的子算法描述一个算法(递归地),以及一个适合于(归纳)证明遵循这个方案的算法的性质的证明方法。• 对于所选择的算法方案,证明方法被称为证明正确性定理,即证明未知算法满足给定的规范。通常,这个证明会失败,因为对未指定的子算法一无所知。• 在证明失败的情况下,通过一个猜想生成算法,生成未知子算法的“需求”(规格),使证明者能够成功地完成证明。将这些要求添加到知识库中,并再次尝试正确性定理的证明。现在,证明将克服失败的情况,并将成功或将在稍后的证明情况下再次失败。• 这个过程是在递归级联迭代,直到正确性定理的证明通过(或放弃)。成功终止后,以下情况将成立:假设所有成分26B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24子算法满足生成的要求,主算法满足问题的具体化。• 在这个阶段,有两种可能性:或者,在初始知识库中,算法可以满足引理中描述的子算法的要求,我们完成了,即,已经为初始问题合成了正确的算法,并且已经生成了其正确性证明。或者,满足要求的子算法可以在下一轮过程中通过相同方法的另一个应用来合成。与其他方法相比,我们的算法合成方法的显着特点是:• 使用从算法方案库中获取的算法方案,• 失败的证明和从失败的证明中产生猜想的关键作用,• 将理论探索,特别是算法发明和验证分解为理论层,• 该方法的自然性,这使得它对于计算机支持的系统中用于形式数学运算的完全或部分自动化(事实上,算法综合的懒惰思维范式的想法是在2001年10月第一作者为高中教师准备数学算法验证课程时产生的。在合成文献中引入了类似的想法(概述见[3])。然而,在一个方面或另一个,我们的合成方法是从上述每一在下文中,我们将介绍其中的一些在[1],[14]中描述的演绎综合方法使用证明规划来建立算法正确性的证明,用元变量替换算法的未知部分(规范的存在部分),这些元变量将随着证明规划的进行而被实例化。在形式方法中,从一个规范开始,通过一系列变换,得到一个正确的程序。在此基础上,关于算法开发的额外知识(数据抽象,设计抽象-对应于算法方案,如分而治之[16])导致了强大系统的实现,如KIDS [17]及其后继者Specware [19],支持使用方案进行程序合成。本着同样的精神,逻辑程序的模式,加上语义意义,通过一系列步骤转换成程序,这些步骤保持了正确的语义。”[13]中。B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2427在(自动化)软件工程中,已经有可用的软件设计模式目录,这些模式再次积累了软件开发的知识这些都是针对特定的面向对象或并发,并行和分布式编程语言(模式资源,见[20])。懒惰思维算法综合方法独立于任何形式数学系统。然而,所选系统必须具有几个属性,才能作为该方法的框架• 由系统的自动定理证明部分生成的证明对象必须是开放的,以便进行后处理。换句话说,黑盒证明器不适合该方法,因为子算法的重要(自动)需求生成是基于对生成的证明对象的详细分析。• 出于同样的原因,在系统中使用的自动定理证明器在证明失败的情况下也产生证明对象也是至关重要的。在区别于其他算法的合成方法,提取算法从成功的证明,我们的方法的本质是自动生成的子算法的要求,从失败的证明!• 系统中使用的自动定理证明器应该是在本文中,我们的所有形式发展都将在定理系统中给出,见[8],[9]。特别地,所有公式将以Theorema语法给出。并以Theorema系统为例说明了该方法的具体实现。本文包括三个案例研究的算法综合和评论的实现方法的框架中的定理,这是由第二作者进行的基础上的早期版本的定理归纳证明和猜想生成器的第一作者。第一个案例研究,通过合并排序,是[5]中的一个,我们在这里总结,因为它最适合解释一般方法。另外两个案例研究是新的。第二个案例研究(合并算法的合成)特别好地说明了,尽管找到归纳证明和子算法的要求非常容易,但跟踪这些证明和要求的组织和细节是一项非常苛刻的任务,需要自动化来使整个方法实际上具有吸引力。第三个案例研究展示了如何,对于一个固定的算法规范,28B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24输入到综合过程中的算法方案改变了综合的算法,即为子算法自动生成的规范(要求)。2第一个案例研究:合并2.1问题说明我们想合成一个“排序”的算法∀哪里is–tuple优惠 券is–tupleXY。is–sorted谓词(ForXY读作is–sorted排序的X轴∀x≥yx,y,z和我知道了,你好,y,y(x,x′,y′(F或“sequencevariables“符号x′等。,因为这是一个在地球上,例如[8]。序列变量可以被任意多个项替换。因此,对于一个示例,项s_x_x_y_x_x_y_x_x_y_x_x_y_x_x_y_x_x_y_x_x_y_x_x_y_x_x_y_x_x_y_x_y_x_x_y_x_x_y_y_x_x_y_y_x_x_y_x_x_y_y_x_x_y_y_x_y_y_ 我们使用角块作为元组的转换器:对于x个像素,2,2,3,1,4B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2429“is-sorted”和"“的定义所有这些辅助操作的定义以及描述这些辅助操作的各种性质的公式应该包含在知识库中,见附录。(In[5]我们讨论知识库的“完备性”和“充足性”问题2.2算法方案在我们看来,对于给定数据域的“算法方案”(或“算法类型”),• 是根据其他未指定的“辅助”操作和数据域的基本操作对未指定的“主”操作的递归定义• 以及以自然的方式对应于递归定义和数据域在我们的例子中(一个关于元组数据类型的问题),解函数的一个可能的递归定义是众所周知的∀is–tuple[X]sorted[X]=merged[sorted[sorted[在这里,你应该把“主函数”' sorted '和“辅助函数”' special ',' merged ','left-split '和' right-split '看作完全未指定的事实上,在这个时刻,没有什么是已知的这些功能,将证明给他们的名字,如还请注意,与“排序”等操作相反谓词30B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24此外,我们在辅助函数上包括以下自然的∀is–tupleis–tupleis–trivial–tuple∀is–tuple<$、[is–tuple类型要求对于能够证明函数' sorted '对于元组参数产生元组作为结果是很重要的最后,我们还考虑以下要求∀is–tuple<$X>作为递归定义的一部分,它保证了在' > '是诺特谓词的情况下al-出租m的终止(In在我们的例子中,我们将使用谓词其次,我们将以下特殊的归纳方法纳入算法方案中:• 为了证明,对于任意性质A,<$A[X],is–tuple对于任意但固定的x],is–tupleis–tuplex<$0这种特殊的归纳方法是基于>是诺特关系的性质。有人可能会争辩说,在算法方案中包含适当的归纳证明方法后,已经从自动发明系统中拿走了很多“发明”。然而,在未来的数学知识管理系统(特别是验证算法发明系统)中,抛弃数学家在解决问题的“方案”上积累的知识是愚蠢的相反,在未来的系统中,数学家积累的算法发明知识应该保持在“算法方案库”中B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2431一个完全自动的搜索,通过库的可能的算法方案,以适用于一个特定的算法综合问题,似乎是组合禁止。然而,在实践中,我们认为我们的战略是可行的,原因如下:• 给定一个数据类型(这是问题规范的一部分),经验表明,没有太多可能的算法方案值得存储在算法方案库中。有许多算法,但相比之下,只有少数算法方案。换句话说,给定一个数据类型,只有很少的基本思想如何攻击特定于给定数据类型的问题,但这些思想有许多变体或实例,甚至有更多的这些思想与子算法的思想(方案)的组合• 当然,对于给定的数据类型,并不是所有算法库中的算法方案都能为指定的问题带来合理的算法更具体地说,通过分析相应正确性定理的失败证明而得出的子算法的要求可能不容易满足,或者在下一轮中根本不能满足的合成过程。我们猜测,一些用户交互将是必要的,以遵循整个合成过程中只有有希望的路径,通过一对夫妇的子算法,subsubalgorithms等。然而,目前,我们还没有足够多的案例研究的实验材料,以便对我们的方法中必要或足够的用户交互量2.3懒惰思维的算法合成:第一轮我们现在从以下情况开始:• 我们有一个知识库,由问题规范中出现的操作和辅助操作(函数和谓词)的所有定义和基本属性组成(在我们的情况下:二元谓词见附录)。• 我们已经从元组域的有限算法方案库中选择了一个算法方案(包括归纳方案)我们现在做以下工作:• 我们包括' sorted '的算法方案32B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24’• 然后我们开始尝试证明正确性定理∀is–tuple• 当然,这个证明不会成功,因为在这个时刻,基本上没有什么是已知的辅助功能我们继续证明直到证明被卡住。• 当它卡住了,我们分析了当前的,失败的证明情况,并试图推测的要求(属性)的辅助子算法(It对于该方法的自动化来说是至关重要的,即可以自动化确定适当要求的步骤!)• 我们将所确定的需求添加到知识库中,并重复整个过程,即我们进入算法发明过程的下一轮。在这个例子中,失败的证明尝试(可以由Theorema归纳证明器完全自动生成)如下:证明A尝试 BEGIN为了证明正确性定理,我们使用良基归纳w.r.t.关于X:我们假设∀is–tuplex<$0is–sorted–version我们展示了is–sorted–version我们使用“sorted”的算法方案,在这种情况下,我们必须证明is–sorted–versionB. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2433也就是说,通过“is-sorted-version”的定义is-tuple[ special []],(G 1)special []]].(G3)对于(G2),由于∀((XY)惠(X=Y))is–trivial–tuple证明了特殊[<$x <$0<$]=<$x<$0 <$。(G1)是由特殊的类型要求上的真实.我们不能证明(G2)和(G3)。证明(The证明尝试自动生成的定理归纳证明器元组基本上是完全一样的证明尝试以上包括解释性的英文文本,见论文定理。然而,在本文中,我们省略了定理证明的一些中间步骤。现在我们分析失败的证明情况,并发现:• 我们把案例假设作为唯一的临时假设:is–trivial–tuple• 我们有一个临时目标:special []=。很明显,推测(我们目前的Theorma推测生成算法可以自动做到这一点),对函数“特殊”的以下要求(special[X] =X)is–trivial–tuple将使我们有可能克服失败的证明情况。我们将此要求添加到知识库中,并继续进行下一轮发明。34B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)242.4懒惰思维的算法合成:第二轮由于我们已经添加了对辅助函数“special”的要求,我们现在将克服失败的证明情况,并且我们将在证明中的某些稍后的情况下被卡住,在这些情况下,我们将再次尝试发明对辅助函数的要求,这将使进一步进行成为下一个证明尝试(可以再次完全自动地由定理归纳证明器生成)现在将如下进行:证明A尝试 BEGINCASE]:在这种情况下,我们必须证明is–sorted–version为此,通过“is-sorted-version”的定义is–tuplex<[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][19][19][19(H3)从格假设出发,通过对左分裂和右分裂的类型要求is–sorted–versionis-sorted-version [ right-split [], 排序[由此,通过定义[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[10],[11],[12],[13],[14],[15],[16],[17],[18],[19],[19],[19](AR3)B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2435is∀(H1)由(AL1)和(AR1)引出,是对“合并”的类型要求我们不能证明(H2)和(H3)。证明现在我们分析失败的证明情况,并发现:• 我们有情况假设和公式(AL1),...,(3)作为临时假设。• 我们有临时目标(H2)和(H3)。它不是那么近在眼前,但经过一些思考,相对容易conjec- ture(和我们目前的定理猜想生成算法可以自动产生这个猜想),以下要求的功能∀is–tuple左右排序的非线性[Y,Z]X⇒is–sorted将使我们有可能克服失败的证明情况。我们将这个要求添加到知识库中,现在可以证明(H2)和(H2),并且可以完成整个证明2.5合成结果如果我们现在收集的要求的功能n.知识,知识[SortIs-Merge-Sort-Algorithm [已排序, 特殊的,合并的,左分裂,右分裂] - 是的特殊、合并、∀is–tuple这里,⇒36B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24∀’合并排序算法[sorted,special,sort]特殊、合并、合并、左拆分、右拆分]⇔[X]=[X]merged[sorted[已排序[X(special[X] =X)∀is–tuple[X][X][ X ].<$[双left-split∀X,Y,Z右排序的合并[Y,Z]X⇒is–sorted<$这个定理说,如果• 谓词• 函数• 函数• 函数• 函数• 函数• 函数B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2437包含与X相同的元素,然后• 函数这个定理中最重要和最有趣的部分是两个要求,即函数这两个要求正是人们自然认为的合并的特征。令人惊讶的现象是,这两个要求完全是通过我们的“懒惰思维”方法自动发明的,没有任何先验的直觉或语义理解。事实上,我们的方法发明的要求的确切表述比人们自然期望的要求稍微更一般。这当然是好的,因为需求越弱,满足需求的函数就越多,比如“请注意,我们的算法合成方法不仅找到了一个通过合并排序的特定算法,而且还找到了整个算法谱,即所有遵循分治方案但可能具有非常不同的子算法“左分裂”、“右分裂”和“合并”实例的算法所有满足以下条件的子算法三元组都合格相对正确性定理中的要求。在[5]中,我们进一步分析了知识库,我们从这个知识库开始,目标是找出证明相对正确性定理的成分运算的那些我们不描述这个想法在本文件中。2.6数学知识检索在生成子函数“merged”、“left-split”和“right-split”的要求之后,问题出现了,满足这些要求的函数是否已经存在于我们的看起来,这是一个简单的问题,在传统的知识检索中,这个问题的答案是寻找具有这些名称或至少类似名称的函数。因此,例如,如果想要知道关于某个函数库中的“贝塞尔函数”已知什么,那么当然,人们将仅在库中查找其最外层函数符号是“贝塞尔”的项。然而,这种特设的解决方案的知识检索问题是不合适的需要出现在上述算法合成方法的框架(和其他领域的相反,我们面临着以下问题:38B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24• 给定知识库K,操作名称f,..., 并要求f,...,即式R [f,. ],• 查找操作名称F,.在K中发生,使得R [F,…]是K的一个逻辑推论。因此,在我们的背景下,知识检索本质上是一个证明问题!例如,给定附录中的知识库K,通过以下定义进行M[,]=,(M[y,yn(M[nx,x,n n x]=nx,x),x,x′∀x,x′,y,y′M[x×M[你好,y×M[L[]=,(L[X(L[x,y,z<$]=x×L[x,y,zR[]=,(R[X(R[x,y,z])x,y,z以及以下要求R[左分裂,右分裂,合并]B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2439is左t你好, 双is–tuple[]]<$X>megais-tupleis–tuple∀is–tuple左右排序的非线性[Y,Z]X⇒is–sorted那么在K中的 在我们的例子中,特别地,人们可以尝试L,R,M并试图证明R[L,R,M]成立。人们看到,这个任务无非是证明算法L,R,M是正确的w.r.t.对于规格R[L,R,M]。在这些证明中,可能是困难的、中等困难的、容易的或琐碎的,这取决于知识库中有多少知识我们在最近的一份技术报告中详细解释了这一点,见[6]。特别地,如果在知识库中没有合适的函数l,r,m可用,则该问题变成另一个综合问题,即综合满足要求R[l,r,m]的算法l,r,m的我们将在下一节中再次通过我们的懒惰思维算法合成方法来解决这个问题。、40B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24is3第二个案例研究:通过比较3.1问题说明现在我们要合成满足规范的算法[ L [ X ]]的一个X>L[X]你好, 双is–tuple[ []]<$X>R[X]Mis–tuple∀is–tupleL[X]R[X]排序的非线性M[Y,Z]⇒is–sorted原则上,再次应用我们的懒惰思维方法,这种综合是可能的。然而,事实证明,这种合成在技术上是非常繁琐的。其原因是上述三个未知算法L、R和M的具体化是“耦合的”。也就是说,最后一个公式包含所有三个算法名称在这种情况下,在开始综合问题之前,尝试“解耦”规范总是可取的在我们的例子中,这是相对容易的:人们可以通过纯粹的“符号计算证明”(重写)来证明∀is–tuple[ L [ X ]]的一个X>L[X]、[ R [ X ]]的一个<$X>R[X].B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)2441∀is–tuple(L[X]=R[X])<$X,<$Mis–tuple排序M[Y,Z]∀is–tuple非线性但是,其中备注。事实上,第二个公式是分裂函数的自然特例。它说的是,当我们通过函数L和R拆分元组X时,如果我们通过连接将拆分放在一起,我们再次得到一个包含原始X元素的元组。注意,现在,L和R的规范与M的规范解耦。我们现在可以合成L和R,然后开始合成M。由于篇幅所限,本文没有给出一些具体的L和R的综合。(In事实上,在前一节中,我们已经提供了合适的L和R的具体例子。) 相反,我们只展示了算法c满足Cis–tuple排序c[Y,Z]∀is–tuple非线性好吧排序(We现在选择不同的名称3.2算法方案我们使用下面的算法方案,我们再次假设它在我们的“算法方案库”中可用42B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24c[,]=cee,c[y,yc[x,x′∀c[x,x,y,y]=cgg1[x,c[、x,x′,y,y′cgg2[y,c[与类型要求is–tuplepixelis-tuplex,x′pixelis-tuplex,x′∀x,双、2[x,X]]其中cee、ceg、cge、cgg1、cgg2和p是未知子算法。相应的归纳证明技术是:为了证明A[X],请执行以下操作:is–tuple(1) 证明A。(2) 取x0和x]并证明A[]。这种证明技术可以扩展到以下条件公式的证明技术为了证明[X],请执行以下操作:is–tupleC[X](1) 假设C[]并显示B[]。(2) Ta k e x0andx<$0arbitrarybutfixed. 假设e]和dC[],并证明B []。(3) N是C[x<$0],B[x <$0]和C[x0,x <$0]的总和,并提供B[x0,x<$0]。请注意,(2)和(3)是一个适当的假设,假设C[x <$0]B[x <$0]等于C[x<$0]B[x<$0](C[x<$0]B[x<$0]),因此,函数的pr o不 等 于 C[x <$0]和(C[x<$0]B[x<$0])。B. Buchberger,A.Cra Rupciun/理论计算机科学电子笔记93(2004)24433.3懒惰思维的算法合成:第一轮我们首先证明∀在Y和Z上进行归纳。is–tuple这种简单的证明之所以成功,是因为对子算法cee、ceg等的类型要求和算法方案。因此,我们立即继续证明。现在我们试图证明排序c[Y,Z]∀is–tuple非线性⇒ 排序用归纳法求有条件的公式Y的归纳基础:假设是排序的[]。证明∀⟨⟩ =Z≈c[⟨⟩,Z].C-is–tupleis–sorted[[]]Y的归纳基,Z的归纳基:假设是排序的[编辑]。证明⟨⟩ = ⟨⟩ ≈c[⟨⟩,⟨⟩],is–sorted现在,=c[,]参与者cee。这个证明失败了,但直接导致了要求cee=。此外,根据这一要求,is–sortedY的归纳基础,Z,Z的归纳步骤,第一种情况:假设],证明=z0,z<$0c[,z0,z<$0]和而这两个假设是互相矛盾的因此,这种情况是不可能的。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- OptiX传输试题与SDH基础知识
- C++Builder函数详解与应用
- Linux shell (bash) 文件与字符串比较运算符详解
- Adam Gawne-Cain解读英文版WKT格式与常见投影标准
- dos命令详解:基础操作与网络测试必备
- Windows 蓝屏代码解析与处理指南
- PSoC CY8C24533在电动自行车控制器设计中的应用
- PHP整合FCKeditor网页编辑器教程
- Java Swing计算器源码示例:初学者入门教程
- Eclipse平台上的可视化开发:使用VEP与SWT
- 软件工程CASE工具实践指南
- AIX LVM详解:网络存储架构与管理
- 递归算法解析:文件系统、XML与树图
- 使用Struts2与MySQL构建Web登录验证教程
- PHP5 CLI模式:用PHP编写Shell脚本教程
- MyBatis与Spring完美整合:1.0.0-RC3详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功