Стационарные значения индуктивных функций

Пусть f: (X)  Y индуктивная функция, т. е. существует G:Y  X  Y, такая, что для всех   (X), x  X выполняется соотношение f(*x) = G(f(), x).

Значение y_sY называется стационарным, если y_s = G(y_s, x) для любого x  X.

Пример. Пусть f = «среди элементов   (Z) нет нулевых». Здесь f: (Z)  Boolean и решение имеет вид f() = true,  f(*x) = (f() & (x  0)). Ясно, что f() = false – стационарное значение, так как для любого b: Boolean имеем false & b = false. В этом случае программу можно записать с учетом стационарного значения:

Reset(fin); y := true; {y = f()} while not Eof(fin) & y do begin Read(fin, x); y := (x  0) end {while}

Здесь оператор y := y & (x  0) заменен на y := (x  0), поскольку в условие продолжения цикла добавлен конъюнктивный член y. В общем случае схема вычисления индуктивной функции, имеющей стационарное значение, такова:

Reset(fin);

y := y0; {y0 = f()}

while not Eof(fin) & (y  стационарное значение) do

begin

Read(fin, x);

y := G^*(y, x)

end {while}

Здесь G^* либо совпадает с G, либо является ее сужением с учетом выполнения условия «y  стационарное значение» в теле цикла.

Билет№23 индуктивное расширение ф-ции на пространстве последовательностей №23

Индуктивные расширения функций

Многие функции не являются индуктивными. Это значит, что информация, заключенная в f(), недостаточна для вычисления f(*x). Однако можно определить, какой именно информации не хватает, и попытаться ее получить. Тогда рассмотрим более сложную функцию, чем исходная, но она уже будет индуктивной.

Пример. Пусть f = «число максимальных элементов последовательности». Эта функция уже рассматривалась в 3.2(бил23) как пример неиндуктивной функции. В полученные рекуррентные соотношения

1, если x > Max(),

f(*x) =   f() + 1, если x = Max(),

 f(), если x < Max()

входит еще функция Max(). Если вычислять и ее знач, то на каждом шаге можно будет определять f(*x).

Пусть x  R, тогда f: (R)  N₀. Введем в рассмотрение функцию Max: (R)  R^*, где R^* = R  {  },  «»  идеальный элемент, используемый как значение Max(). Добавляя к соотношению для f(*x)  соотношение Max(*x) = max(Max(), x), можно написать программу:

Reset(fin);

y := 0; {y = f()} z := ; {z = Max()}

while not Eof(fin) do

begin

Read(fint, x);

if x > z then begin z := x; y := 1 end

else {x  Max()}

if x = z then y := y + 1 else {ничего}

end {while} {y = f() & z = Max()}

Определение. Функция F:  Y называется индуктивным расширением функции f:  Y_f, если 1) F – индуктивна, 2) h: Y  Y_f , такая, что для всех : f() = h(F()) Условие 2 означает, что, зная F(), можно получить f().

Билет№24 Примеры вычисления ф-ций на пространстве послед Прим:чтение натур числа,запис в позицион сист счислен №24