Метод индуктивной функции
Введём обозначения:
А- некоторый алфавит, т. е. какое-то конечное или бесконечное множество, например множество букв русского языка или множество действительных чисел;
Wk – множество конечных последовательностей длины >= к.
f : Wk ® Y.
Цель : подсчитать значение функции на этой последовательности.
Выделим класс функций, для которых указанная задача решается легко.
Функция f называется индуктивной, если $ отображение g:Y*A®Y такое, что " w Î Wk " xÎA f(w*x)=g(f(w),x), где f(w*x) – значение функции на последовательности расширенной на элемент x, т.е. если мы знаем значение функции на последовательности w и нам надо узнать значение на расширенной последовательности w на элемент x, то достаточно знать значение функции для w и сам элемент x.
Пусть k = 0
P.GoTop; {Встать в начало}
f := f0;{f0 – значение функции на пустой последовательности}
while not P.IsEnd do {IsEnd – означает что последовательность прочитана}
begin
P.Read(x);{или x:=P.Get;P.Skip}
f := g(f,x);
end;
{f=результат}
При k = 1.
P.GoTop;
If not P.IsEnd then
Begin
P.Read(x);
f := f({x});
while not P.IsEnd do
begin
P.Read(x);
f := g(f,x);
end;
{f=результат}
end
else … {обработка ошибки};
С ростом k текст программы существенно усложняется.
Примером индуктивной функции может служить функция нахождения максимума из последовательности чисел. Определим нашу функцию на пустой последовательности D. Max{x} = x = max(max(D),x). T. e. " x max(D)<= x . Таким образом max(D) = - 
.
P.GoTop;
Max := - ;
While not P.IsEnd do
Begin
P.Read(x);
if x>max then max := x;
end;
Или в другом виде:
i := 1;
max := -32768;
while i<=n do
begin
x := a[i];
i := i+1;
if x>max then max := x;
end;
Утверждение(критерий индуктивности). F индуктивна Û
" a, b ÎW: F (a) = F (b), "xÎX выполнено F (a*x) = F (b*x) т. е. F индуктивна тогда и только тогда, когда из равенства значений F на последовательностях a и b следует равенство и на любых “одинаково удлинненных” последовательностях a*x и b*x.
Очень часто мы имеем дело с функциями которые индуктивными не являются. Это означает, что информации, заключенной в F(w) и х, недостаточно для вычисления F (w*x). Можно, однако, посмотреть, какой именно информации нам не хватает, и рассмотреть более сложную функцию, включив в нее и эту информацию тоже. В этом случае можно использовать индуктивное расширение.
Определение. F : Wk ® YF называется игдуктивным расширением f:Wk® Yf если
1) F – индуктивна;
2) Всегда значение функции f можно восстановить по F, т.е. $ p:YF®Yf, такое что "wÎWk f(w) = p(F(w)).
Например, нахождение номера максимального элемента последовательности не является индуктивной функцией. Индуктивное расширение:
1) номер максимального элемента на w;
2) максимальный элемент на w;
3) номер последнего элемента в w.
Теорема. Для любой неиндуктивной функции существует индуктивное расширение.
Функция отображающая последовательность в себя, является универсальным индуктивным расширением для любой функции.
Определение. Пусть F1, F2 – два индуктивных расширения для функции f. Будем говорить, что F1<=F2 если существует преобразование p:Y2®Y1 такое что "w F1(w) = p(F2(w)).
Функция F^ называется минимальным индуктивным расширением функции f, если "F- индуктивное расширение f.
1. F^<=F
2. F^(Wк)=YF^ (если отображение «НА»)
Теорема. Для любой неиндуктивной функции существует бесконечное количество минимальных индуктивных расширений, но все они изоморфны друг другу.
Практические выводы:
1). С точки зрения информации надо программировать то минимальное индуктивное расширение время обработки которого минимально.
2). Минимальное расширение можно не использовать. Действительно, хранится лишняя информация, но если информация стоит мало памяти, а её использование существенно сокращает время основного преобразования, то есть получаем выигрыш по времени.
То есть использовать или не использовать минимальное расширение зависит от требований по времени и объему памяти в программе.
Общая схема вычисления неиндуктивной функции, с использованием индуктивного расширения.
P.GoTop;
F:=F0;{вычисление индуктивного расширения не пустой
последовательности }
while not P.IsEnd do
begin
P.read(x); {x:=P.Get;P.Skip}
F:=g(F,x) {g-преобразование, определ. в определ.
индуктивной функции}
end;
f:=p(F);
Определение: Значение уÎYf называется стационарным для функции f, действующей из пространства последовательности в Yf, то есть f:W®Yf , если
|
"wÎW/ f(w)= y "x ÎA f(w*x)=y Пример Существует ли в последовательности элемент, удовлетворяющий указанному условию.
Пусть j:W®Yj; f<=j<=F
yj=pj(yF)
Тогда схему можно изменить
P.GoTop;
F:=F0;
While not (P.IsEnd or stat (pj(F))) do
begin
x:=P.Read;
F:=g(F,x);
end;
f:=p(F);
Допустим A={( , ) + ,t}.
Рассматриваем класс произвольных формул, построенных на этом алфавите.
True False
t+t +t
(t+t)+t ( )
(t) t+t)
((t)) (t
Написать программу, осуществляющую анализ правильности формулы.
Индуктивное расширение.
 |
f0(w)-w может быть продолжено, до правильной формулы
F(w)= f1(w)- разность числа открывающих и закрывающих скобок
f2(w)- последний символ в w
Докажем, что эта функция является индуктивным расширением.
f(w)=истина Û f1(w)=0 & f0(w) & (f2(w))=’t’ Ú f2(w)=’)’)
f0(D)=истина
f1(D)= 0 ‘(’
f2(D)= два решения
‘t’
Построение g
f2(w*x)=x
x=’(’Þ f1(w)+1
f1(w*x)= x=’)’Þ f1(w)-1
иначе Þ f1(w)
f0(w*x)= f0(w) & (сочетание f2(w) и х-правильное) & (f1(w*x)>=0)
Индуктивное расширение и формула не имеют стационарных точек.
Стационарные точки имеют f0
Type Fch= file of char;
Function ok(var f:Fch):boolean;
{F-oткрыт для чтения; ok-возвращают правильность формулы}
var
x:char;
f0:boolean;
f1:integer;
f2:char;
begin
seek(F,0);
f0:=true;
f1:=0;
f2:=’(’;
while not(eof(F) or (not(f0)) do
begin
read(F,x);
case x of f
‘(’: f1:=f1+1;
‘)’: f1:=f1-1;
end;
f0:=(f1>=0) and Sootv(f2,x)
f2:=x;
end;
ok:=f0 and (f1=0) and ((f2=’t’) or (f2=’)’));
end;
function Sootv(a,b:char):boolean;
begin
sootV:=(((a=’(‘ )or (a=’t’)) and b=’t’) or ((a=’)’) or (a=’t’)) and (b=’t’)) or (((a=’)’) or (a=’t’)) and (b=’)’)) or (((a=’(’) or (a=’+’)) and (b=’(‘));
end;