后序遍历二叉树非递归算法的推导及形式化证明

开发涉及非线性数据结构算法程序的循环不变式一直是形式化方法的难点。本文使用PAR方法开发循环不变式的新策略,对后序遍历二叉树问题循环不变式的开发使用递归定义技术,得到了该问题循环不变式的简单精确的表达形式,简化了算法程序的推导和证明过程;利用PAR平台提供的抽象程序设计语言Ap1a中的数据抽象机制,使所得的算法程序结构简洁清晰且易于证明;最后,使用Dijkstra-Gries标准程序证明法形式证明了该问题的核心算法程序(只有4行代码),并使用PAR平台将Apla程序转换成正确的C++代码。实例的成功进一步说明PAR方法提供的循环不变式的开发技术对推导和证明非线性数据结构算法程序的有效性。     

Radl算法到Apla程序的生成系统

算法设计是一项创造性工作,传统的设计与描述方法难以保证算法的正确性.在PAR方法中通过定义具有数学引用透明性的算法描述语言Radl,可实现对问题规约进行形式化推导得到用递推关系描述的算法.Radl算法的核心就是递推关系组,从而易于进行形式化推导和证明.通过深入剖析Radl算法特性,揭示Radl算法与抽象顺序程序Apla(abstract programming language)间本质关系,定义基于Radl语法产生式的Apla程序生成规则,实现了Apla程序自动生成系统,并对其可靠性进行系统研究,着重形式化验证了实现系统的核心算法.使用PAR方法开发的算法是正确的,采用形式化证明的生成系统具有可靠性保证,从而保证了算法从设计到实现的高可靠性,并通过实现自动化开发工具提高了程序的开发效率.     

一种形式化开发非递归算法的方法*

提出了一种简单、统一的形式化开发非递归算法的方法.该方法直接面向非递归算法,在形式化方法PAR的指导下,使用循环不变式的开发新策略,在得到求解递归问题的循环不变式的同时,能直接得到易读、高效且可靠的非递归算法,并通过一个具体实例进行了阐述.对使用形式化方法及循环不变式开发新策略开发非递归算法的方法作了较深入的实践和探讨.     

Hanoi塔非递归算法的形式化推导和正确性验证

关于Hanoi塔问题的非递归算法已有大量的研究.运用薛锦云教授自创的PAR方法和循环不变式开发的新策略,形式化推导出逻辑结构清晰的Hanoi塔非递归算法及其循环不变式,并用Dijkstra最弱前置谓词法验证了该算法的正确性.充分体现了PAR方法的优越性、高效性和可靠性.     

形式化开发Hanoi塔问题非递归算法

使用形式化方法PAR及循环不变式开发新策略,开发了Hanoi塔问题非递归算法,并对其进行了形式化地正确性证明。本文直接面向非递归算法,在得到求解Hanoi塔问题的循环不变式的同时,直接得到易读、高效且可靠的非递归算法。对使用形式化方法及循环不变式开发新策略开发非递归算法作了较深入的实践和探讨。     

序列折半划分问题的形式化推导

形式化推导是在程序正确性证明理论下所进行的程序开发,最终得到完全正确的算法程序。针对序列折半划分问题,现有的形式化推导方法将推导与证明交替进行,推导过程繁琐且大多无法直接获得可执行程序。为解决上述问题,提出了一种新的序列折半划分问题的形式化推导方法。该方法基于分划递推的核心思想,应用规约变换技术对问题规约进行变换并严格保证一致性,使得在推导过程中无需交替证明,进而导出递推关系式并得到高可靠性抽象算法程序Apla,最终通过转换工具自动生成可执行程序。实现了从程序规约到具体可执行程序的完整程序求精过程。以2个序列算法为例,验证了该方法的有效性和可行性,对相关问题的形式化推导具有指导意义。     

形式化开发非递归Koch曲线算法

形式化方法是构建可信软件的重要途径。Koch曲线是典型的分形图形。基于形式化方法PAR及循环不变式开发策略,开发了Koch曲线非递归算法,并对其进行了形式化的正确性证明。在得到求解Koch曲线算法的循环不变式的同时,直接得到易读、高效且可靠的非递归算法。对使用形式化方法及循环不变式开发策略开发分形程序非递归算法作了较深入的实践和探讨。     

一种高效的算法程序设计方法-PAR方法

利用在长期的算法研究中提出的分划递推法（简称PAR方法）开发了三个问题的算法程序,说明PAR方法不仅为算法设计提供了统一而有效的途径,也为开发循环不变式奠定了基础。     

基于PAR的算法形式化开发

形式化方法是构建可信软件的重要途径.基于对算法问题的分析,针对形式化方法PAR开发算法的特征,刻划了问题分划、递推关系构造方面的规律.从一类问题的形式化功能规约出发,可机械地完成问题的分划及规约的变换,自然地揭示出求解问题的算法思想,在相关工具的支持下自动生成算法程序.研究结果将算法设计中尽可能多的创造性劳动转化为非创造性劳动,降低了形式化求解算法问题的难度,提高了算法程序的可靠性和形式化开发效率.     

PAR平台从规约出发的算法推导与自动生成

简要介绍PAR方法及其支撑平台,使用PAR方法及其平台从规约出发形式化推导并生成了两个典型的算法程序。PAR方法及其平台使用一阶谓词逻辑表示功能规约,分划与递推来进行算法形式推导,各种转换系统来自动生成算法程序。这显著地提高了算法程序的正确性和开发效率,也有助于深刻地理解算法设计思想。     

Two New Strategies for Developing Loop Invariants and Their Applications

The loop invariants take a very important role in the design,proof and derivation of the algorithmic program.We point out the limitations of the taditional standard strategy for developing loop invariants.and propose two new strategies for proving the existing algorithmic program and developing new ones.The strategies ure recurrence as vehicle and integrate some effective methods of designing algorithms,e.g.Dynamic Porgramming,Greedy and Divide-Conquer,into the recurrence relation of problem solving sequence.This lets us get straightforward an approach for solving a variety of complicated problems,and makes the standard proof and formal derivation of their algorithmic programs possible.We show the method and advantages of applying the strategies with several typical nontivial examples.     

分划递推法及其应用

分划递推法是一种新的算法设计技术。在分划递推法中使用逻辑符号和扩充的量词表示功能规约。分划是处理复杂问题的一般方法,而递推可用于循环不变式和算法设计开发。文中给出的三个实例呈现了使用分划递推法进行算法设计和开发的步骤和要点。     

PAR方法和循环不变式的范畴语义

范畴论对理解程序规约及程序设计和正确性证明十分有用。PAR方法则是建立在严格的数学基础之上的一种统一的算法程序设计方法。循环不变式在循环算法程序的设计中至关重要。使用格理论和范畴论作为工具对PAR方法建立一个理论框架,并对其用范畴论的概念加以解释,从而使得PAR有更强的理论基础。在此基础上引入不动点原理深入刻划循环不变式的含义,循环不变式可以表示为谓词泛函的最小不动点,并从范畴论的角度解释该过程。     

由规格说明到排序算法

本文给出由程序的规格说明变换出程序的一种系统化方法的新概念.对规格说明进行不同的变换可得到不同的不变式形式.这些不变式通过计算最弱前置条件给出了多种相应算法的框架。本文以若干著名的排序算法例示了以上的概念和方法。     

形式化方法在高中算法教学中的应用研究

国家教育部制定的高中新课程标准将算法初步作为高中数学课程的必修内容,算法与程序设计也首次纳入到选修课之列。全国大部分普通高中均按新课标开展教学实验,不少省份还把算法内容纳入高考。同时现有算法初步和算法与程序设计教材在介绍算法与算法设计方法时,无法说清楚算法设计的过程;在教学实践中,这一问题更加突出。这给高中生学习、理解及掌握算法和算法设计方法带来很大的困难。本文从新课程实验教材中及数学高考题中选取两个问题,用支持算法程序形式化开发的PAR（Partition And Recur）方法与PAR平台,从待求解问题的精确功能描述出发,经过一系列等价数学变换,最后得到正确的算法和程序。实践说明PAR方法与PAR平台可以在高中算法教学及学生能力评测中发挥建设性作用。     

基于遗传算法的图象不变矩匹配

研究模板和图象间的有效匹配，利用不变矩特征作为检测模板和图象中物体轮廓相似度的测度，同时把遗传算法引入图象匹配识别，并针对简单遗传算法在应用过程中出现收敛过早和早熟现象的问题，采用了一种 改进型遗传算法。该算法和不变矩相结合能有效检测出具有平移、旋转 和尺度变化的物体，该方法可以应用于实际图象匹配和识别中。     

图同构中的一类顶点细分方法

提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.     

快速不变矩算法基于CUDA的并行实现研究

不变矩自提出以来被广泛应用于目标识别系统中进行特征描述,这需要能够实时计算不变矩值。虽然人们提出了许多不变矩的快速算法,仍无法在单台PC机上实现不变矩的实时计算。本文分析了基于差分矩因子的不变矩快速算法的并行性,提出了一种基于CUDA（Compute Unified Device Architecture）的快速不变矩并行实现方法,并在NVIDIA Tesla C1060 GPU（Graphic Processing Unit）上实现。对所提出算法的计算性能与普通串行算法进行了对比分析。实验结果表明,本文所提出的并行计算方法极大地提高了不变矩的计算速度,可有效地用来进行实时特征提取。     

局部Radon变换技术及在毛杆折痕识别中的应用

针对羽毛杆折痕识别问题,提出一种新的特征提取方法。为了消除Radon变换对缩放平移敏感问题,采用改进的Radon变换提取目标区域的不变矩,并引入局部投影技术消除羽毛杆生理纹理干扰。通过改变尺度因子获得矩不变量矩阵,并采用奇异值分解(SVD)获得特征不变量用于分类识别。实验结果表明该方法具有较强的鲁棒性,具有较高的折痕识别率。