Quelle iterative_methods.gi Sprache: unbekannt

#############################################################################
##
#W  iterative_methods.gi                         Victor Bovdi <vbovdi@gmail.com>
#W                                       Vasyl Laver  <vasyllaver@uzhnu.edu.ua>
##
##
#Y  Copyright (C)  2018,  UAE University, UAE
##
#############################################################################
##
##  This file contains some iterative methods for threshold element training.
##
#############################################################################

######################################################################
##
#F  ThresholdElementTraining(te,step,f)
##
##  Returns the Threshold Element realizing the Boolean function f
##  or [] if the function is not realizable.
##

InstallMethod(ThresholdElementTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsObject, IsPosInt], 4,
function(te,step,f,maxit)
local t, l, i,y,err,j,tup,w,T,st, niter, n;

if (IsLogicFunction(f)=false) then
  Error("f has to be a logic function.");
fi;

n:=f!.numvars;

if (f!.dimension<>2) then
  Error("f has to be a Boolean function.");
fi;

f:=f!.output;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

st:=StructureOfThresholdElement(te);
w:=st[1]; T:=st[2];

if (Size(w)<>n) then
  Error("Theshold element and f should be of one dimension!\n");
fi;

if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;
l:=ShallowCopy(w);
niter:=maxit;
return THELMA_INTERNAL_ThrTr(l,T,step,f,niter);
end);

InstallOtherMethod(ThresholdElementTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsFFECollection, IsPosInt], 4,
function(te,step,f,maxit)
local t, l, i,y,err,j,tup,w,T,st, niter, n;

n:=LogInt(Size(f),2);
if Size(f)<>2^n then
   Error("Number of elements of the vector must be a power of 2! \n");
   return [];
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

st:=StructureOfThresholdElement(te);
w:=st[1]; T:=st[2];

if (Size(w)<>n) then
  Error("Theshold element and f should be of one dimension!\n");
fi;

f:=List(f,Order);

if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;
l:=ShallowCopy(w);
niter:=maxit;
return THELMA_INTERNAL_ThrTr(l,T,step,f,niter);
end);

#f - is a polynomial over GF(2)
InstallOtherMethod(ThresholdElementTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsPolynomial, IsPosInt], 4,
function(te,step,f1,maxit)
local t, l, i,y,err,j,tup,w,T,st, niter,f, var, n;
st:=StructureOfThresholdElement(te);
w:=st[1]; T:=st[2];
f:=[];

n:=Size(w);

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

f:=THELMA_INTERNAL_PolToOneZero(f1,n);
if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;

l:=ShallowCopy(w);
niter:=maxit;

if (Size(f)<>2^n) then
  Error("Theshold element and f should be of one dimension!\n");
fi;

return THELMA_INTERNAL_ThrTr(l,T,step,f,niter);
end);

#f - string
InstallOtherMethod(ThresholdElementTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsString, IsPosInt], 4,
function(te,step,f1,maxit)
local t, l, i,y,err,j,tup,w,T,st, niter,f, n;
st:=StructureOfThresholdElement(te);
w:=st[1]; T:=st[2];
f:=[];

n:=LogInt(Size(f1),2);
if Size(f1)<>2^n then
     Error("Number of elements of the vector must be a power of 2");
  return [];
fi;

if 2^n<>(Size(Positions(f1,'1'))+Size(Positions(f1,'0'))) then
  Error("Input string should contain only '1' and '0'. \n");
  return [];
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

if (Size(w)<>n) then
   Error("Theshold element and f should be of one dimension!\n");
fi;

for i in [1..Size(f1)] do
  if f1[i]='1' then Add(f, 1);
  elif f1[i]='0' then Add(f, 0);
  fi;
od;

if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;
l:=ShallowCopy(w);
niter:=maxit;
return THELMA_INTERNAL_ThrTr(l,T,step,f,niter);
end);

######################################################################
##
#F  ThresholdElementBatchTraining(te,step,f)
##
##  Returns the Threshold Element realizing the Boolean function f
##  or [] if the function is not realizable.
##

#f - vector over GF(2)
InstallMethod(ThresholdElementBatchTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsObject, IsPosInt], 4,
function(te,step,f, maxit)
local t, l, i, y,err,j,Tc,wc,tup,st,w,T,niter,n;

st:=StructureOfThresholdElement(te);
w:=st[1];
T:=st[2];

if (IsLogicFunction(f)=false) then
  Error("f has to be a logic function.");
fi;

n:=f!.numvars;

if (f!.dimension<>2) then
  Error("f has to be a Boolean function.");
fi;

f:=f!.output;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;
l:=ShallowCopy(w);

if (Size(w)<>n) then
  Error("Theshold element and f should be of one dimension!\n");
fi;

niter:=maxit;
return THELMA_INTERNAL_ThrBatchTr(l,T,step,f,niter);
end);

InstallOtherMethod(ThresholdElementBatchTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsFFECollection, IsPosInt], 4,
function(te,step,f, maxit)
local t, l, i, y,err,j,Tc,wc,tup,st,w,T,niter,n;

st:=StructureOfThresholdElement(te);
w:=st[1];
T:=st[2];
f:=List(f,Order);
n:=LogInt(Size(f),2);

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;
l:=ShallowCopy(w);

if (Size(w)<>n) then
  Error("Theshold element and f should be of one dimension!\n");
fi;

niter:=maxit;
return THELMA_INTERNAL_ThrBatchTr(l,T,step,f,niter);
end);

# f is a polynomial
InstallOtherMethod(ThresholdElementBatchTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsPolynomial, IsPosInt], 4,
function(te,step,f1,maxit)
local t, l, i, y,err,j,Tc,wc,tup,st,w,T,niter, var, n, f;

st:=StructureOfThresholdElement(te);
w:=st[1]; T:=st[2];
f:=[];

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

var:=OccuringVariableIndices(f1);
n:=Size(w);

f:=THELMA_INTERNAL_PolToOneZero(f1,n);

if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;
l:=ShallowCopy(w);
niter:=maxit;

if (LogInt(Size(f),2)<>n) then
  Error("Theshold element and f should be of one dimension!\n");
fi;

return THELMA_INTERNAL_ThrBatchTr(l,T,step,f,niter);
end);

#f is a string
InstallOtherMethod(ThresholdElementBatchTraining, "threshold element, step, function, max_iter", true, [IsThresholdElementObj, IsPosInt, IsString, IsPosInt], 4,
function(te,step,f1, maxit)
local t, l, i, y,err,j,Tc,wc,tup,st,w,T,niter,f,n;

st:=StructureOfThresholdElement(te);
w:=st[1]; T:=st[2];
f:=[];

n:=LogInt(Size(f1),2);

if (Size(w)<>n) then
  Error("Theshold element and f should be of one dimension!\n");
fi;

if Size(f1)<>2^n then
     Error("Number of elements of the vector must be a power of 2");
  return [];
fi;

if 2^n<>(Size(Positions(f1,'1'))+Size(Positions(f1,'0'))) then
  Error("Input string should contain only '1' and '0'. \n");
  return [];
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

for i in [1..Size(f1)] do
  if f1[i]='1' then Add(f, 1);
  elif f1[i]='0' then Add(f, 0);
  fi;
od;

if w=[] then
  for i in [1..LogInt(Size(f),2)+1] do Add(w,1); od;
fi;
l:=ShallowCopy(w);
niter:=maxit;
return THELMA_INTERNAL_ThrBatchTr(l,T,step,f,niter);
end);

######################################################################
##
#F  WinnowAlgorithm(f,step)
##  The algorithm for learing the monotone disjunctions
##

#f - vector over GF(2)
InstallMethod(WinnowAlgorithm, "function, step, maxiter", true, [IsObject, IsPosInt, IsPosInt], 3,
function(f,step,maxit)
local f1,niter;

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

if (IsLogicFunction(f)=false) then
  Error("f has to be a logic function.");
fi;

if (f!.dimension<>2) then
  Error("f has to be a Boolean function.");
fi;

f1:=f!.output;

niter:=maxit;
return THELMA_INTERNAL_Winnow(f1,step,niter);
end);

InstallOtherMethod(WinnowAlgorithm, "function, step, maxiter", true, [IsFFECollection, IsPosInt, IsPosInt], 3,
function(f,step,maxit)
local f1,niter;

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

f1:=List(f,Order);
niter:=maxit;
return THELMA_INTERNAL_Winnow(f1,step,niter);
end);

#f - string
InstallOtherMethod(WinnowAlgorithm, "function, step, maxiter", true, [IsString, IsPosInt, IsPosInt], 3,
function(f,step, maxit)
local f1,niter,n,i;

f1:=[];

n:=LogInt(Size(f),2);
if Size(f)<>2^n then
     Error("Number of elements of the vector must be a power of 2");
  return [];
fi;

if 2^n<>(Size(Positions(f,'1'))+Size(Positions(f,'0'))) then
  Error("Input string should contain only '1' and '0'. \n");
  return [];
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

for i in [1..Size(f)] do
  if f[i]='1' then Add(f1, 1);
  elif f[i]='0' then Add(f1, 0);
  fi;
od;

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

niter:=maxit;
return THELMA_INTERNAL_Winnow(f1,step,niter);
end);

#f - polynomial
InstallOtherMethod(WinnowAlgorithm, "function, step, maxiter", true, [IsPolynomial, IsPosInt, IsPosInt], 3,
function(f,step,maxit)
local f1,niter,var,n;

var:=OccuringVariableIndices(f);
n:=InputFromUser("Enter the number of variables (n>=",Size(var),"):\n");

f1:=THELMA_INTERNAL_PolToOneZero(f,n);

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

niter:=maxit;
return THELMA_INTERNAL_Winnow(f1,step,niter);
end);

######################################################################
##
#F  Winnow2Algorithm(f,step)
##  The algorithm, which generalizaes Winnow1
##

#f - vector over GF(2)
InstallMethod(Winnow2Algorithm, "function, step, maxiter", true, [IsObject, IsPosInt, IsPosInt], 3,
function(f,step,maxit)
local f1,niter;

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

if (IsLogicFunction(f)=false) then
  Error("f has to be a logic function.");
fi;

if (f!.dimension<>2) then
  Error("f has to be a Boolean function.");
fi;

f1:=f!.output;

niter:=maxit;
return THELMA_INTERNAL_Winnow2(f1,step,niter);
end);

InstallOtherMethod(Winnow2Algorithm, "function, step, maxiter", true, [IsFFECollection, IsPosInt, IsPosInt], 3,
function(f,step,maxit)
local f1,niter;

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

f1:=List(f,Order);
niter:=maxit;
return THELMA_INTERNAL_Winnow2(f1,step,niter);
end);

#f - string
InstallOtherMethod(Winnow2Algorithm, "function, step, maxiter", true, [IsString, IsPosInt, IsPosInt], 3,
function(f,step,maxit)
local f1,niter,n,i;

f1:=[];

n:=LogInt(Size(f),2);
if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

if Size(f)<>2^n then
     Error("Number of elements of the vector must be a power of 2");
  return [];
fi;

if 2^n<>(Size(Positions(f,'1'))+Size(Positions(f,'0'))) then
  Error("Input string should contain only '1' and '0'. \n");
  return [];
fi;

for i in [1..Size(f)] do
  if f[i]='1' then Add(f1, 1);
  elif f[i]='0' then Add(f1, 0);
  fi;
od;

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

niter:=maxit;
return THELMA_INTERNAL_Winnow2(f1,step,niter);
end);

#f - polynomial
InstallOtherMethod(Winnow2Algorithm, "function, step, max_iter", true, [IsPolynomial, IsPosInt, IsPosInt], 3,
function(f,step,maxit)
local f1,niter,var,n;

var:=OccuringVariableIndices(f);
n:=InputFromUser("Enter the number of variables (n>=",Size(var),"):\n");

if step<1 then
  Error("Step has to be a positive integer!\n");
  return [];
fi;

if maxit<1 then
  Error("Maximal number of iterations has to be a positive integer!\n");
  return [];
fi;

f1:=THELMA_INTERNAL_PolToOneZero(f,n);

if step=1 then
  Error("Step must be integer > 1. \n");
fi;

niter:=maxit;
return THELMA_INTERNAL_Winnow2(f1,step,niter);
end);

######################################################################
##
#F  STESynthesis(f,step)
##  The algorithm, which generalizaes Winnow1
##

#Build threshold element (find w and T). Input - f with values from GF(2), output - structure vector (w;T) in [0,1] base;
#if such vector does not exist - return [].

#f - vector over GF(2)
InstallMethod(STESynthesis, "function", true, [IsObject], 1,
function(f)
local n,i;

if (IsLogicFunction(f)=false) then
  Error("f has to be a logic function.");
fi;

if (f!.dimension<>2) then
  Error("f has to be a Boolean function.");
fi;

f:=List(f!.output,i->Elements(GF(2))[i+1]);

return THELMA_INTERNAL_STESynthesis(f);
end);

InstallOtherMethod(STESynthesis, "function", true, [IsFFECollection], 1,
function(f)
local n;
n:=LogInt(Size(f),2);
if Size(f)<>2^n then
     Error("Number of elements of the vector must be a power of 2");
  return [];
fi;

return THELMA_INTERNAL_STESynthesis(f);
end);

#f - string
InstallOtherMethod(STESynthesis, "function", true, [IsString], 1,
function(f)
local i,f1,n;

  n:=LogInt(Size(f),2);
  if Size(f)<>2^n then
      Error("Number of elements of the vector must be a power of 2");
   return [];
  fi;

  if 2^n<>(Size(Positions(f,'1'))+Size(Positions(f,'0'))) then
   Error("Input string should contain only '1' and '0'. \n");
   return [];
  fi;
   f1:=[];
   for i in [1..Size(f)] do
     if f[i]='1' then Add(f1, Z(2)^0);
     elif f[i]='0' then Add(f1, 0*Z(2));
     fi;
   od;

  return THELMA_INTERNAL_STESynthesis(f1);
end);

#f - polynomial
InstallOtherMethod(STESynthesis, "function", true, [IsPolynomial], 1,
function(f)
local f1,var,n;

var:=OccuringVariableIndices(f);
n:=InputFromUser("Enter the number of variables (n>=",Size(var),"):\n");
f1:=THELMA_INTERNAL_PolToGF2(f,n);
return THELMA_INTERNAL_STESynthesis(f1);
end);

Quelle iterative_methods.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.31 Sekunden (vorverarbeitet) ]