1、Deductive and inductive methods for program synthesis,Jelena Sanko, Jaan Penjam Institute of Cybernetics,October 29, 2005,Agenda,Program construction Inductive program construction Experiments Conclusions,Program construction,Problem Statement,x,Scoring of programs,s - measure of fitness,pi=R1; R2;

2、R3; R4; R5; . ;R6,Square root fitness measure of the program p,Program synthesis as optimization,s,z,1,z0,P=R2; R3; R5; R6; R2; ; R6,h,Coding of programs,z = 0,235627,h,p=R2; R3; R5; R6; R2; ; R6,PR6,Coding of programs (2),M(P) - State Transition Machine,computational model,Coding of programs (3),x,

3、1,6,4;5,4;5,5,5,4,4,3,3,1,2,1,2,1,2,2,xyz,vxyz,uvxz,uvxyz,tuvxyz,vxz,xz,xy,0.33,0.66,Function to be optimized (f(z),1,z,s,DE is a method for finding extreme points of real-valued multi-modal functions,Optimization technique,-Differential Evolution,Rainer Storn and Kenneth Price,DE is a heuristic met

4、hod that can be used for optimization of non-differentiable functions in continuous spaces,The convergence rate of the floating-point encoded DE is more than 10 times higher than the convergence rate of the traditional binary encoded GA,Experimental Data,P=(0.75,1.87*10-07), (0.70, 1.04*10-07) (0.65

5、,5.44*10-08), (0.60,2.61*10-08) (0.55,1.17*10-08),(0.50, 3.40*10-09),P.M. Murphy and D.W. Aha, Uci repository of machine learning databases,I(R1)=“y:=ln(x)” I(R2)=“y:=exp(-x)” I(R3)=“z:=x3+6x” I(R4)=“v:=2(x2+z)” I(R5)=“(u,z):=(v+6,v/2)” I(R6)=“v:=0.16yu/7.854”,The optimal solutions like 0.37362, 0.4

6、0419, 0.795112 correspond to the following sequence of relations “R2;R3;R4;R5;R4;R5;R4;R5;R6”,Experimental Data (2),I(R1)=“y:=ln(x)” I(R2)=“y:=exp(-x)” I(R3)=“z:=x3+6x” I(R4)=“v:=2(x2+z)” I(R5)=“(u,z):=(v+6,v/2)” I(R6)=“v:=0.16yu/7.854”,where,The optimal solution of the problem obtained by the DE me

7、thod corresponds to the proposed by Knut Angstrm functional relation:,Conclusions:,The inductive approach to program construction can promote control over construction process and take an appropriate decision when several solutions are available IPS uses interpretation of relations and a fitting function IPS considers all programs and selects the best The research