Метод индуктивной функции

Введём обозначения:

А- некоторый алфавит, т. е. какое-то конечное или бесконечное множество, например множество букв русского языка или множество действительных чисел;

W_k – множество конечных последовательностей длины >= к.

f : W_k ® Y.

Цель : подсчитать значение функции на этой последовательности.

Выделим класс функций, для которых указанная задача решается легко.

Функция f называется индуктивной, если $ отображение g:Y*A®Y такое, что " w Î W_k " 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 : W_k ® Y_F называется игдуктивным расширением f:W_k® Y_f если

1) F – индуктивна;

2) Всегда значение функции f можно восстановить по F, т.е. $ p:Y_F®Y_f, такое что "wÎW_k f(w) = p(F(w)).

Например, нахождение номера максимального элемента последовательности не является индуктивной функцией. Индуктивное расширение:

1) номер максимального элемента на w;

2) максимальный элемент на w;

3) номер последнего элемента в w.

Теорема. Для любой неиндуктивной функции существует индуктивное расширение.

Функция отображающая последовательность в себя, является универсальным индуктивным расширением для любой функции.

Определение. Пусть F₁, F₂ – два индуктивных расширения для функции f. Будем говорить, что F₁<=F₂ если существует преобразование p:Y₂®Y₁ такое что "w F₁(w) = p(F₂(w)).

Функция F^{^} называется минимальным индуктивным расширением функции f, если "F- индуктивное расширение f.

1. F^{^}<=F

2. F^{^}(W_к)=Y_F^ (если отображение «НА»)

Теорема. Для любой неиндуктивной функции существует бесконечное количество минимальных индуктивных расширений, но все они изоморфны друг другу.

 

Практические выводы:

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);

 

Определение: Значение уÎY_f называется стационарным для функции f, действующей из пространства последовательности в Y_f, то есть f:W®Y_f , если

 

алфавит

"wÎW/ f(w)= y "x ÎA f(w*x)=y

 

Пример Существует ли в последовательности элемент, удовлетворяющий указанному условию.

 

Пусть j:W®Yj; f<=j<=F

y_j=p_j(y_F)

Тогда схему можно изменить

 

P.GoTop;

F:=F0;

While not (P.IsEnd or stat (p_j(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

 

Написать программу, осуществляющую анализ правильности формулы.

 

Индуктивное расширение.

f₀(w)-w может быть продолжено, до правильной формулы

F(w)= f₁(w)- разность числа открывающих и закрывающих скобок

f₂(w)- последний символ в w

 

Докажем, что эта функция является индуктивным расширением.

f(w)=истина Û f₁(w)=0 & f₀(w) & (f₂(w))=’t’ Ú f₂(w)=’)’)

 

f₀(D)=истина

f₁(D)= 0 ‘(’

f₂(D)= два решения

‘t’

 

Построение g

 

f₂(w*x)=x

x=’(’Þ f₁(w)+1

f₁(w*x)= x=’)’Þ f₁(w)-1

иначе Þ f₁(w)

 

f₀(w*x)= f₀(w) & (сочетание f₂(w) и х-правильное) & (f₁(w*x)>=0)

 

Индуктивное расширение и формула не имеют стационарных точек.

Стационарные точки имеют f₀

 

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;