形式推导支持的递归程序向非递归程序的转换

本文提出一种递归消除的方法,适于一类基于递归数据结构的程序。该方法将递归程序作为初始规约,以求解过程的状态变迁序列作迭代模式;通过数据展开和变换实现初始规约向基于序列描述规约的变换,继而用PAR形式推导出序列规约的递推关系,并以之为核心近乎机械地构造出非递归算法。树和图的两个算法实例说明了本方法的有效性。     

Deriving protocol specifications from service specifications written in LOTOS

Summary.  A complete communication system is broken down into a number of protocol layers each of which provides services to the layer above it and uses services provided by its underlying layer. A service specification defines a particular ordering of the operations that a given layer provides to the layer above it. The active elements in each layer are called entities and they use a protocol in order to implement their service definition. On the basis of this relation between the service and protocol concepts we have developed algorithms for deriving protocol entity specifications from a formal service specification. The derived protocol entities ensure the correct ordering of the service primitives by exchanging synchronization messages through an underlying communication medium. This paper presents an extended version of our earlier derivation algorithms. This version of the algorithm can handle all operators and unrestricted process invocation and recursion as defined by basis LOTOS. The correctness of this derivation algorithm is formally proved. Received: January 1992 / Accepted: February 1996     

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

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

棋盘多项式非递归生成算法的提出与实现

棋盘多项式的生成算法有多种,都采用了递归的思想。递归算法效率较低,针对此问题,提出一种棋盘多项式非递归生成算法,并用Visual C++实现,给出了在禁位排列中的应用实例。算法分析及程序运行结果表明该算法在速度上优于现有的生成算法,并能同时给出具体排列方案,具有实用价值。     

Using Annotations to Make Recursion Equations Behave

The use of annotated recursion equations as a programming technique is investigated by considering the "telegram problem." The annotations are used to select alternative strategies for evaluating the applicative expressions contained in the recursion equations, while the equations serve as an abstract specification of the desired results. This method has the advantage that the annotations explicitly display certain kinds of decision that would otherwise be implicit.     

递归算法在面向内容音乐信息近似检索中的应用

针对现有面向内容音乐信息近似检索算法的弊端,结合递归算法的特点,设计了一则基于递归的面向内容音乐信息近似检索算法;为配合该算法,设计了相应的基于R-tree树的音乐信息索引结构方案;经理论分析和对比实验结果,发现以递归来设计音乐信息近似检索算法,可得到较佳的检索效率。     

Derivation of data intensive algorithms by formal transformation:the Schnorr-Waite graph marking algorithm

Considers a particular class of algorithms which present certain difficulties to formal verification. These are algorithms which use a single data structure for two or more purposes, which combine program control information with other data structures or which are developed as a combination of a basic idea with an implementation technique. Our approach is based on applying proven semantics-preserving transformation rules in a wide spectrum language. Starting with a set theoretical specification of “reachability”, we are able to derive iterative and recursive graph marking algorithms using the “pointer switching” idea of Schorr and Waite (1967). There have been several proofs of correctness of the Schorr-Waite algorithm, and a small number of transformational developments of the algorithm. The great advantage of our approach is that we can derive the algorithm from its specification using only general-purpose transformational rules, without the need for complicated induction arguments. Our approach applies equally well to several more complex algorithms which make use of the pointer switching strategy, including a hybrid algorithm which uses a fixed length stack, switching to the pointer switching strategy when the stack runs out     

递归与循环算法分析

程序设计中没有用到循环或递归算法，很难解决一些实际问题。本文以斐波那契（Fibonacci）数列为例对递归与循环算法的时间复杂度作了比较、分析。     

递归与循环算法分析

程序设计中没有用到循环或递归算法,很难解决一些实际问题。本文以斐波那契(Fibonacci)数列为例对递归与循环算法的时间复杂度作了比较、分析。     

工作团队视角看递归

递归是程序设计中一种重要的思想方法。递归算法代码量小、求解思路清晰,解决复杂问题的方案优雅而简洁,但递归算法难以掌握。结合实例以工作团队的视角进行递归算法设计,提出首先保证正确设计递归算法然后再分析递归执行过程的教学思路,在教学实践中取得良好效果。     

工作团队视角看递归

递归是程序设计中一种重要的思想方法。递归算法代码量小、求解思路清晰,解决复杂问题的方案优雅而简洁,但递归算法难以掌握。结合实例以工作团队的视角进行递归算法设计,提出首先保证正确设计递归算法然后再分析递归执行过程的教学思路,在教学实践中取得良好效果。     

跟踪式智能反汇编算法研究

研究了嵌入式系统文件反汇编过程中存在的主要问题,给出了进行跟踪式智能反汇编的关键算法。首次采用二叉树结构对代码扫描过程进行跟踪处理,给出了生长二叉树的递归遍历算法,克服了传统反汇编过程中建立大量数组、链表以及图表的缺点;通过对二叉树的逆向浏览,解决了间接转移指令的寻址问题,并给出了寻址算法;最后,给出了数据区边界校验算法。对于进行程序反解及软件逆向工程具有较重要的参考价值。     

汉诺塔非递归算法

分析汉诺塔递归算法的特点,由递归算法,结合二叉树的中序遍历算法,提出汉诺塔二叉树的概念及创建方法,并证明汉诺塔二叉树特点。由此进一步导出兼顾时间效率与空间效率的非递归算法。最后,提供实现算法的C语言程序。     

Towards a geometry of recursion

Any mathematical theory of algorithms striving to offer a foundation for programming needs to provide a rigorous definition for an abstract algorithm. The works reported by Girard (1988) in [10] and by Moschovakis (1989, 1995) in [29], [30] and [31] are among the best examples of such attempts. They both try to offer a mathematically precise and rigorous formulation of an abstract algorithm, intend to keep the algorithmic flavour present and take the notion of recursion as primary and central. The present work is motivated by Girard’s GoI 2 paper (Girard (1988) [10], which offers a treatment of recursion in terms of fixed points of linear functions. It is situated in the context of the geometry of interaction (GoI) program and is carried out in the concrete setting of the space of bounded linear maps on a Hilbert space. In this paper, we extend the work in Girard (1988) [10] to the context of traced unique decomposition categories, once again emphasizing the role of abstract trace in the theory of computing. We show that traced unique decomposition categories enriched over partially additive monoids or their variations suffice to axiomatize and hence extend the work in Girard’s GoI 2 paper. The theory developed here allows us to formulate an abstract notion of an algorithm as a pair of morphisms in a traced unique decomposition category, an abstract notion of computation as the execution formula (defined using the trace operator) applied to an algorithm, and finally a notion of deadlock-freeness for algorithms. In addition, we can treat recursive definitions, fixed points and fixed point operators in a uniform way in terms of traced unique decomposition categories.     

Radl 形式规格说明相对正确性研究

在形式规格说明的获取任务中,一个重要问题是验证获取得到的形式规格说明的正确性.即给定一个问题需求P,往往可以获取多种不同形式的规格说明,如何验证这些不同形式的规格说明均正确?问题需求的非(半)形式化与形式规格说明的形式化两者之间差异的本性,使得该问题成为软件需求工程中一个具有挑战性的问题.提出一种基于形式化推导的方法来验证同一问题不同形式规格说明的相对正确性,通过证明不同形式规格说明与问题需求某个最为直截明了的形式规格说明Si等价来实现,而Si使用PAR方法和PAR平台转换为可执行程序,通过测试已经得到确认.为了支持该方法,进一步提出了扩展的逻辑系统和辅助证明算法.使用Radl语言作为形式规格说明语言,通过排序搜索、组合优化领域的两个典型实例对该方法进行了详细的阐述.实际使用效果表明,该方法不仅能够有效地验证Radl形式规格说明的正确性,还具备良好的可扩充性.该方法在规格说明的正确性验证、算法优化、程序等价性证明等研究领域具有潜在的理论意义与应用价值.