递归函数的应用

递归函数独特的运算方式,使其在人工智能和各种事务处理过程中有着广泛的应用,因而成为一个重要的研究课题.文中以迷宫、汉诺塔等为例,根据计算机堆栈原理,具体讨论了用递归函数解题的方法和技巧.给出了递归函数调用时利用变量传递解决复杂问题的实例,展示了递归算法在解决非数值运算问题中的独特解题方式和效果.讨论表明,在求解人工智能和各种事务处理问题中,递归函数中合理地利用变量传递可有效地完成求解任务和提高程序的品质.     

用进化算法和函数优化模型分析回溯算法上界

研究的是常出现在求解NP难问题的Davis-Putnam型指数时间回溯算法中的一类多变量递归问题。首先引入适当的赋权函数,把多变量递归函数转化为单变量递归函数;然后提出有效的优化模型,把求解单变量递归函数问题转化为一般的带约束条件的函数优化问题。传统的算法计算精度较差,并且求得的结果多为局部最优解。所以,引进新颖的遗传算法求解优化模型以改进求解精度和速度,并应用此算法求解了set packing问题,计算结果具有很高的精度。     

流场类问题并行化中数组共享变量的自动搜索

本文的目的是解决流场类问题的自动并行化．首先将流场数据均匀划分，并以SPMD模式对流场计算串行程序进行并行化；引入数组共享变量，着重讨论一种新方法──用递归函数实现数组共享变量的自动搜索．用本文方法的并行化工具已初步实现．     

在多层应用中利用事务处理中的触发器实现数据完整性

本分析了数据库管理系统中的事务处理以及在事务处理中利用散发器实现数据完整性，并以Delphi为例讨论在多层应用中如何直接调用数据库管理系统中的事务处理，最后以SQL Server和Delphi为例说明在事务处理中利用触发器实现数据完整性。     

基于符号运算的归纳变量识别与约化

针对归纳变量的识别及归约问题提出一种基于符号运算的新算法。通过初始变量替换赋值语句中的右值,用以表达变量间的迭代与依赖关系,由此建立有向依赖图用于识别归纳变量。为归纳变量构建递归方程组并利用符号运算进行求解,获得独立的仅依赖于迭代次数的数学形式。实验结果表明,该方法适用于各种复杂的归纳变量,能够解决现有算法无法处理的一些问题。     

组织进化算法求解SAT问题

基于组织的概念设计了一种新的进化算法——求解SAT问题的组织进化算法(Organizational Evolutionary Algorithm for SAT problem，0EASAT)．OEASAT将SAT问题分解成若干子问题，然后用每个子问题形成一个组织，并根据SAT问题的特点设计了三种组织进化算子——自学习算子、吞并算子和分裂算子以引导组织的进化．根据组织的适应度，将所有组织分成两个种群——最优种群和非最优种群，然后用进化的方式来控制各算子，以协调各组织间的相互作用．OEASAT通过先解决子问题，再协调相冲突变量的方式来求解SAT问题．由于子问题的规模较小，相对于原问题来说较容易解决，这样就达到了降低问题复杂度的目的．实验用标准SATLIB库中变量个数从20-250的3700个不同规模的标准SAT问题对OEASAT的性能作了全面的测试，并与著名的WalkSAT和RFEA2的结果作了比较．结果表明，OEASAT具有更高的成功率和更高的运算效率．对于具有250个变量、1065个子句的SAT问题，OEASAT仅用了1．524s，表现出了优越的性能．     

协同设计中定量化约束求解方法

通过对约束满足与约束冲突的分析，提出了约束求解的定量化策略．基于变量不确定性，量化了约束满足程度与约束冲突程度，解决了约束求解过程中的优先权问题；给出了约束变化量及关联函数，为约束求解确立了具体的目标和实施方法，实现了约束求解过程的有序搜索．定量化约束求解策略不仅实现了对约束的有序及有效求解，而且真正地实现了在上游约束求解过程中定量地考虑下游约束求解问题．最后，利用随机仿真技术实现了基于变量不确定性的约束求解策略的验证．     

求解SSSP问题图运算的复制数据算法*

本文首先提出求解SSSP问题图运算的数据并行算法及复制数据算法，并把复制数据技术成功地用于求解SSSP问题图运算证明算法的有效性，然后计算并讨论复制数据算法对数据并行算法的加速，最后指出复制数据技术不仅能用于图象的快速分析，而且也能广泛地用于解各种图运算问题．     

单片机中基于查表法的多变量函数求解方法设计

针对多变量非线性复杂函数关系式在单片机中难以实现的问题,提出了一种快速有效的查表求解算法。首先建立顺序存储数据块,接下来查找输入变量在已存变量存储块中的自然序号,最后利用查得的变量自然数序号及事先确定的算法查找这些变量所对应的函数值的存储地址,进而得到计算结果。实现了非线性复杂关系式的快速精确求解,可推广于各种运算能力有限的单片机,提高了单片机的整体使用效率。     

单片机中基于查表法的多变量函数求解方法设计

针对多变量非线性复杂函数关系式在单片机中难以实现的问题,提出了一种快速有效的查表求解算法。首先建立顺序存储数据块,接下来查找输入变量在已存变量存储块中的自然序号,最后利用查得的变量自然数序号及事先确定的算法查找这些变量所对应的函数值的存储地址,进而得到计算结果。实现了非线性复杂关系式的快速精确求解,可推广于各种运算能力有限的单片机,提高了单片机的整体使用效率。     

线性递归Da taL og 程序优化算法

提出了线性齐次ＤａｔａＬｏｇ逻辑程序的概念,并为该类程序设计了一个优化的求解算法。在此基础上提出了求解一般线性ＤａｔａＬｏｇ程序的优化算法,该算法利用带有的约束条件的递归调用方法,将线性ＤａｔａＬｏｇ程序求解问题变换成齐次程序的求解问题。算法简单,易于实现,可应用于任何线性ＤａｔａＬｏｇ程序的求解。     

Using Computer Algebra techniques for the specification,verification and synthesis of recursive programs

We describe an innovative method for proving total correctness of tail recursive programs having a specific structure, namely programs in which an auxiliary tail recursive function is driven by a main nonrecursive function, and only the specification of the main function is provided. The specification of the auxiliary function is obtained almost fully automatically by solving coupled linear recursive sequences with constant coefficients. The process is carried out by means of CA (Computer Algebra) and AC (Algorithmic Combinatorics) and is implemented in the Theorema system (using Mathematica). We demonstrate this method on an example involving polynomial expressions. Furthermore, we develop a method for synthesis of recursive programs for computing polynomial expressions of a fixed degree by means of “cheap” operations, e.g., additions, subtractions and multiplications. For a given polynomial expression, we define its recursive program in a schemewise manner. The correctness of the synthesized programs follows from the general correctness of the synthesis method, which is proven once for all, using the verification method presented in the first part of this paper.     

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

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

A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem

We consider a convex, or nonlinear, separable minimization problem with constraints that are dual to the minimum cost network flow problem. We show how to reduce this problem to a polynomial number of minimum s,t-cut problems. The solution of the reduced problem utilizes the technique for solving integer programs on monotone inequalities in three variables, and a so-called proximity-scaling technique that reduces a convex problem to its linear objective counterpart. The problem is solved in this case in a logarithmic number of calls, O(log U), to a minimum cut procedure, where U is the range of the variables. For a convex problem on n variables the minimum cut is solved on a graph with O(n²) nodes. Among the consequences of this result is a new cut-based scaling algorithm for the minimum cost network flow problem. When the objective function is an arbitrary nonlinear function we demonstrate that this constrained problem is solved in pseudopolynomial time by applying a minimum cut procedure to a graph on O(nU) nodes.     

Evolving Recursive Programs by Using Adaptive Grammar Based Genetic Programming

Genetic programming (GP) extends traditional genetic algorithms to automatically induce computer programs. GP has been applied in a wide range of applications such as software re-engineering, electrical circuits synthesis, knowledge engineering, and data mining. One of the most important and challenging research areas in GP is the investigation of ways to successfully evolve recursive programs. A recursive program is one that calls itself either directly or indirectly through other programs. Because recursions lead to compact and general programs and provide a mechanism for reusing program code, they facilitate GP to solve larger and more complicated problems. Nevertheless, it is commonly agreed that the recursive program learning problem is very difficult for GP. In this paper, we propose techniques to tackle the difficulties in learning recursive programs. The techniques are incorporated into an adaptive Grammar Based Genetic Programming system (adaptive GBGP). A number of experiments have been performed to demonstrate that the system improves the effectiveness and efficiency in evolving recursive programs. Communicated by: William B. Langdon An erratum to this article is available at .     

状态逻辑型程序设计语言

本文提出了一种新的纯逻辑式子句型程序设计语言．文中给出了语言的语法，非形式语义，子句的过程解释和基于约束归结的推理系统．对该语言来说，程序包含三类变量：输入变量，输出变量和用于控制机器资源的程序变量；被程序定义的函数符号可用于构造项或子项，并且还可用作为谓词符号；不需要低效的最广合一．由于这些因素，一个子句集本身隐含了顺序，分支，迭代和递归多种控制结构使得容易构造高效的定理证明系统．这种语言将是一种有坚实理论基础的，高效的，实际有用的高级确定性语言．     

Completing open logic programs by constructive induction

We consider part of the problem of schema-biased inductive synthesis of recursive logic programs from incomplete specifications, such as clausal evidence (for instance, but not necessarily, ground positive and negative examples). After synthesizing the base clause and introducing recursive call(s) to the recursive clause, it remains to combine the overall result from the partial results obtained through recursion, so as to complete the recursive clause. Evidence for this combination relation can be abduced from the initially given evidence for the top-level relation. A program for this combination relation can be anything, from a single clause performing a unification (such as for lastElem) to multiple guarded clauses performing unifications (such as for filtering programs) to recursive programs (such as for naive reverse). Existing methods cannot induce guarded clause programs for this combination relation from the abduced evidence. Some existing methods cannot even detect that the combination program itself may have to be recursive and thus they then do not recursively invoke themselves the overall recursive program synthesizer. We introduce our Program Completion Method as a suitable extension and generalization of the existing methods. ©1999 John Wiley & Sons, Inc.     

Symbolic evaluation with structural recursive symbolic constants

Symbolic evaluation is a technique used for many purposes: program analysis, program verification, program transformation. The paper focusses on a novel approach which allows one to symbolically evaluate programs with respect to predicates denoting subsets of a user-defined data domain. The data domain is assumed to be recursively defined and the predicates can be defined by structural induction on the data. An application of the technique to the textual reduction of recursive programs is sketched.     

Extracting reusable functions by flow graph based program slicing

An alternative approach to developing reusable components from scratch is to recover them from existing systems. We apply program slicing, a program decomposition method, to the problem of extracting reusable functions from ill structured programs. As with conventional slicing first described by M. Weiser (1984), a slice is obtained by iteratively solving data flow equations based on a program flow graph. We extend the definition of program slice to a transform slice, one that includes statements which contribute directly or indirectly to transform a set of input variables into a set of output variables. Unlike conventional program slicing, these statements do not include either the statements necessary to get input data or the statements which test the binding conditions of the function. Transform slicing presupposes the knowledge that a function is performed in the code and its partial specification, only in terms of input and output data. Using domain knowledge we discuss how to formulate expectations of the functions implemented in the code. In addition to the input/output parameters of the function, the slicing criterion depends on an initial statement, which is difficult to obtain for large programs. Using the notions of decomposition slice and concept validation we show how to produce a set of candidate functions, which are independent of line numbers but must be evaluated with respect to the expected behavior. Although human interaction is required, the limited size of candidate functions makes this task easier than looking for the last function instruction in the original source code     

Recursive assertions and parallel programs

Summary We prove that recursive assertions are enough for proofs of parallel programs considered in Owicki and Gries [7]. In other words, we prove that for any parallel program S and recursive assertions p and q if {p} S{q} is true under the standard interpretation in natural numbers then all intermediate assertions needed in the proof can be chosen recursive. Finally, we show that if auxiliary variables are used only as program counters then the above result does not hold.