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

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

模型驱动的Dafny程序形式化生成与自动验证

Dafny是一种内置规范结构的编程语言和静态程序证明器,它能验证程序的功能正确性以及将证明过程自动化,这既提高了软件开发的效率,又极大增强了软件开发的可靠性.该文探索了一种模型驱动的Dafny程序形式化生成的方法.首先,从问题的Radl规约出发,根据规约变换技术得到其Radl算法; 然后,根据PAR方法中循环不变式开发新策略得到问题的循环不变式; 最后,在Radl算法和循环不变式基础上利用模型等价转换规则生成Dafny程序,并由Dafny证明器自动验证其功能正确性.用该方法解决了2个典型问题的算法程序开发与验证,证实了该方法能够有效地提高Dafny程序的生成效率和可靠性.     

基于Apla语言的虚拟现实建模机制研究

针对传统的脚本建模存在语言机制复杂繁琐、开发效率不高、可靠性难保证、建模阶段和交互阶段相互独立等问题,基于分划与递推(PAR)及其Apla抽象程序设计语言,设计与原Apla语言融合的虚拟现实建模语言机制。开发的Apla→MAXScript自动生成系统可以将抽象Apla程序转换成MAXScript脚本,并借助3DSMax来实现三维建模。Apla建模机制采用直接重用MAXScript修改器API方式,既大幅度简化了重构的工作量,又延续了Apla语言抽象程度高特征,便于对Apla建模程序进行形式化推导和正确性验证。最后通过案例证明了Apla建模语言及其工具能够提高三维建模的精细度、可靠性及开发效率。     

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

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

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

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

一种基于Concurrent Apla语言的共享内存并发分布式算法2层验证方法

形式化验证共享内存并发分布式算法已成为当前极具挑战性的问题之一,尤其是在云计算、多核、无线传感器网络、分布式数据库、区块链环境下.该文基于研究团队在形式化规约语言和方法、算法形式推导和验证方面的已有工作,以自定义泛型抽象顺序设计语言Apla为基础,进一步研究并提出简明、高抽象用于并发分布式计算的Concurrent Apla语言,使其既支持顺序算法的验证又能有效地验证并发分布式算法.在依赖-卫式推理的基础上,提出一种新颖的2层并发分布式算法形式化验证方法,其中系统层用于处理并发级验证,而组件层用于处理顺序级验证.最后,通过2个实例验证了该方法的有效性和可行性.     

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

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

基于抽象不变式的程序安全性验证

程序安全性验证是软件系统安全领域的研究难点,构造程序不变式是程序安全性验证的主要方法之一。验证程序是否满足时态性质的问题可转化为不动点求解问题,然而直接构造不动点的求解算法是非常困难的。该文探讨了一类基于抽象解释框架的不变式求解构造方法。首先通过Tableau方法构造时态公式的谓词图,基于传统不变式构造规则,使用前向或逆向状态转换,改进不变式验证规则;然后采用抽象解释框架构造抽象状态转换系统,给出了抽象不变式验证规则;最后基于不动点抽象定理,通过前向或逆向转换求解近似的不动点,使用加宽近似和收窄近似操作进一步加速收敛,从而给出基于抽象不动点的不变式验证算法,最终完成了基于抽象不变式的程序安全性自动验证。     

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

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

用daikon发现循环不变式

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

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

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

A Formal Method for Developing Algebraic and Numerical Algorithms

The development of algebraic and numerical algorithms is a kind of complicated creative work and it is difficult to guarantee the correctness of the algorithms. This paper introduces a systematic and unified formal development method of algebraic and numerical algorithms. The method implements the complete refinement process from abstract specifications to a concrete executable program. It uses the core idea of partition and recursion for formal derivation and combines the mathematical induction based on strict mathematical logic with Hoare axiom for correctness verification. This development method converts creative work into non-creative work as much as possible while ensuring the correctness of the algorithm, which can not only verify the correctness of the existing algebraic and numerical algorithms but also guide the development of efficient unknown algorithms for such problems. This paper takes the non-recursive implementation of the Extended Euclidean Algorithm and Horner's method as examples. Therefore, the effectiveness and feasibility of this method are further verified.     

树非递归遍历统一的新解法及其形式证明

提出树遍历统一的新解法,使其非递归算法像递归算法一样简单.首先以后序遍历为例,基于结点状态标记和遍历规则提取,从遍历定义导出遍历的递推公式,由此机械获得非递归算法和循环不变式,并用形式化方法证明其正确性.之后按不同遍历定义变换公式参数,获得二叉树前序、中序和K叉树前序、后序的递推公式,所得算法比传统算法更简洁直观,表明本解法的有效性和通用性.     

无环配置问题研究

基于约束的配置问题提出一种无回溯搜索算法,通过弧相容技术将所有不相容的值删除,指导用户进行产品配置,并对其正确性进行了证明.探讨了将目前两种主流计算冲突解释方法应用到无环配置问题的可行性.     

一个可用于Web数据库系统的分配调度通用算法

分配调度问题是一种困难问题,有些甚至是NP完全类问题.因而解决此类问题的技术难度较大,一般采用与或图搜索技术来求解.这就给当前许多Web数据库系统中的分配调度程序的编制造成困难,笔者以毕业设计任务分配算法为例,给出了一个能解决一类约束条件为双向选择的分配调度问题的通用算法.该算法不涉及复杂数据结构和搜索过程,仅用关系数据库的表操作描述,并可用任一支持Web数据库的语言编程实现.