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

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

二叉树排序非递归算法推导及形式化证明

非线性数据结构递归问题非递归算法的循环不变式的开发一直是形式化开发的难点.研究二叉树类非递归算法的推导及形式化证明方法,对二叉树排序算法进行推导,得出非递归Apla(Abstract Programming Language)算法及其精确而简单的循环不变式,然后用Dijkstra-Gries标准程序证明法证明算法的正确性,最后使用PAR平台C++程序自动生成系统自动生成C++代码.实例的实验结果简化了算法程序的推导和证明过程,对递归问题非递归算法的循环不变式的探测具有一定的借鉴意义,而且对非线性数据结构算法程序的推导及形式化证明具有指导意义.     

关于循环与循环不变式的讨论

讨论程序设计中的循环与循环不变式的应用 .利用循环不变式可以方便地设计循环程序 ,并可证明程序的正确性 .     

2类数列问题循环不变式开发策略研究与应用

该文通过对组合数学中Catalan数列问题和Fibonacci数列问题进行深入研究,利用归纳推理、组合数学中的加法和乘法原理等方法得到问题求解函数,使用变量记录算法求解过程中子问题的解,并约束循环变量的变化范围,获得问题求解算法的循环不变式,由此得到了2类数列问题循环不变式的统一开发策略.以二叉树的形态数问题和阶梯问题为例,利用所提策略开发循环不变式,并基于循环不变式展示了这2类数列问题算法程序的形式化推导过程.     

算法的形式化推导与基于Isabelle的自动化验证

可信软件的不断发展进一步推动了形式化方法的深入研究.结合实际应用中的2个问题,采用基于递推关系的算法形式化方法,演示了算法的形式化推导过程,并运用Isabelle定理证明器结合Dijkstra最弱前置谓词方法,对得到的算法程序进行了自动化验证,避免了手工验证过程繁琐和易出错等问题.研究表明:基于递推关系的算法形式化方法不仅可以提高开发算法的效率,而且通过数学变换保证推导过程的正确性,从而有效保证了算法和程序的正确性.     

基于低代码开发范式的Web Service生成方法

针对目前软件开发人员在手工开发Web Service程序过程中出现效率低下、容易出错等问题,本文基于低代码开发范式,结合需求原型化技术RM2PT,提出一种Web Service自动生成方法。首先,根据操作契约中的OCL表达式与数据基本操作的语义关系,建立两者之间的转换规则;其次,根据Web Service功能模块的代码特征构建转换模板;然后建立解析和处理需求模型的转换算法;最后,使用转换规则、转换模板和转换算法直接将需求模型自动转换为目标应用程序。通过使用4个软件开发案例对提出的方法进行验证,结果表明,约93.3%的系统操作可以实现自动生成。相比传统的软件开发模式,本文方法可以由需求模型自动生成标准化Web Service程序,提高了软件开发效率与质量。此外,本文方法支持快速原型开发和迭代开发,用户可以通过GUI验证、编辑与修改需求,重新生成应用程序。     

二叉树队列关系问题非递归算法的推导及形式化证明

该文对二叉树类问题进行分划,寻找其递推关系,并针对具有队列递推关系的一类问题,给出了其推导过程和形式化证明策略.再结合每个算法后置断言的不同,提出3种开发循环不变式的策略,并构造出该类问题的通用循环不变式模板.同时,发现该类问题是基于2个母算法的功能加以实现的,由此派生出3类问题.首先,对这3类派生问题进行推导,得到递...     

基于B方法的内存管理模型的设计

内存管理是操作系统的重要组成部分,一个安全可靠的内存管理程序,对于操作系统的运行十分关键.采用传统软件开发方法开发的内存管理系统,安全性和可靠性得不到很好的保证.为此提出用形式化的B方法开发内存管理系统.首先使用B方法建立了内存管理的形式化模型,利用B工具对该阶段生成的证明义务进行证明,保证系统在初始规范说明层次上的内在一致性和设计的正确性.然后根据B方法分层构造的思想对上一阶段得到的抽象规范模型进行精化.最终得到一个可实现的内存管理模型,该模型更好地保证了系统的一致性和可靠性.     

基于仿真的汽车电子控制器软件开发方法研究

以车身控制系统中的车窗控制器和雨刮控制器为例,研究一种基于仿真及代码自动生成的汽车电子控制器软件的新型开发方法.利用Simulink/Stateflow建立汽车电子控制器算法模型,进行离线仿真验证和快速模型验证,然后通过RTW自动生成可执行的代码,最后可将自动生成的代码直接嵌入到控制器硬件中,实现了汽车电子控制系统的软件开发.通过与Simulink中仿真结果进行对比,验证了该方法的可行性和正确性.经过实践证明该开发模式可以大大缩短控制系统的开发周期,对于汽车电子系统的开发具有一定的实用价值.另外,在软件开发的各个阶段对设计功能进行测试验证,提高设计开发的正确性.     

程序正确性证明中逻辑公式的可满足性

采用Herbrand定理及归结原理证明在程序证明中遇到的逻辑公式是可满足的。并给出了相应的算法;同时讨论了已知循环程序中循环不变式的求解方法。     

内含定理证明器的程序开发系统

提出了一个基于重写技术的程序开发系统,它提供了扩展的函数式语言和代数规约语言相结合的混合语言,该语言中引入了优化规则和测试等式说明机制．优化规则用于优化代码和满足某些特殊需求．运用测试等式说明机制可使程序员在程序中给出一些用于测试的等式,对程序进行测试,这些测试是在被开发系统形成前进行的．对优化规则和测试等式的证明,是由系统中的证明子系统（定理证明器）完成的．定理证明器的引入,提高了所开发系统的正确性,并且有利于缩短系统的开发周期．     

用daikon发现循环不变式

随着软件行业的深入发展,软件存在的问题与日俱增,程序正确性受到了广泛的关注,形式化方法是解决程序正确性的基本途径,而发现程序循环不变式是证明程序正确性的关键。本文介绍了循环不变式的基本概念以及计算不变式的基本方法;用JAVA重写了Siemens的replace C程序,并以JAVA和C两种语言的replace程序为例,对不变式动态探测工具daikon进行了深入的实验研究,试验结果揭示了daikon在探测循环语句不变式方面的不足,依此提出了改进daikon探测循环不变式的措施。     

一个基于AI产生式系统的软件开发新模型

在设计一个程序以前，应该完整地并且精确地说明要求解的问题．作为一个产品。软件相对于其形式规格说明来说应该是可靠和正确的．规格说明是程序变换方法的起点，程序变换方法保证了程序的正确性．本文给出了ＡＤＴＳＬ的简要描述，并提出了一个基于人工智能中的产生式系统的软件开发新模型．     

3个变形背包问题的形式化推导

在对0-1背包问题的若干变形问题进行深入研究的基础上,使用二进制数组的方式形式化描述了几种背包问题的程序规约,通过程序规约变换技术获取问题求解的递推关系,给出了3个变形背包问题的算法推导过程,有效保证了算法程序的可靠性,并可将采用的推导方法在子集和问题、船装载等问题中加以推广应用.     

基于遍历序列恢复二叉树的新解法及其证明

提出了一种基于前序和中序遍历序列恢复二叉树的解法,算法以数学公式形式呈现,反映了建树过程中相关数据变化的一般规律,具备数学上的引用透明性,由此能机械获得非递归程序和循环不变式,并进行了正确性证明.通过简单变换,获得了后序+中序、前序+后序恢复二叉树的可信算法.实验效果表明了该解法的有效性.     

一种抽象泛型机制的新型Java实现

泛型程序设计可大幅度提高程序的可重用性、可靠性和开发效率,高抽象的泛型机制则有助于降低泛型编程的复杂度.该文介绍了一种抽象泛型机制的核心思想和编程技术,分析了新型Java中与之对应的实现机理,并归纳出相应的转换规则,且在既有平台中实现了抽象泛型程序到新型Java泛型程序的自动转换和运行,最后通过一个Kleen算法实例,展示了抽象泛型机制的实际运用和相应Java程序的自动生成.抽象泛型机制的新型Java实现,在降低可重用算法构件的设计复杂度、提高算法构件可靠性的同时,也为泛型构件的设计和描述提供了行之有效的新途径.     

Automatic generation of very efficient programs by Generalized Partial Computation

Generalized Partial Computation (GPC) is a program transformation method utilizing partial information about input data, properties of auxiliary functions and the logical structure of a source program. GPC uses both an inference engine such as a theorem prover and a classical partial evaluator to optimize programs. Therefore, GPC is more powerful than classical partial evaluators but harder to implement and control. We have implemented an experimental GPC system called WSDFU (Waseda Simplify-Distribute-Fold-Unfold). This paper discusses the power of the program transformation system, its theorem prover and future works.