Общая формулировка задания

ИНДУКТИВНЫЕ ФУНКЦИИ

Общая схема вычисления индуктивных функций

Основные определения, схема программ и примеры алгоритмов вычисления индуктивных функций на последовательностях подробно изложены в [6]. Более краткое изложение дано в [1] и ориентировано на представление последовательности в виде последовательного файла. Конечно, последовательность может быть реализована и как массив, и как линейный список, и некоторыми другими способами. Далее в заданиях будем рассматривать реализацию последовательности именно в виде файла, так как этот способ делает более естественным использование однопроходных алгоритмов, что и достигается при вычислении индуктивной функции.

В приведенных далее заданиях указана функция f(w), значение которой надо вычислить. Будем использовать обозначения, введенные в [1]: w – последовательность элементов заданного типа, т. е. w = x₁x₂…x_n, где x_i Î X, а X – произвольный алфавит; пустая последовательность обозначается как D; W_k(X) – пространство всех конечных последовательностей над X длины не менее, чем k; при этом W₀(X) º W(X).

Напомним определение индуктивной функции (см.[1], с.20). Функция f: W(X) ®Y называется индуктивной, если f(w*x) можно вычислить, зная f(w) и x, т. е. если существует функция G:Y ´ X®Y, такая, что для всех w Î W(X), x Î X выполняется соотношение f(w*X) = G(f(w), x).

Если последовательность реализована в программе файлом fin типа file of X, то вычисление индуктивной функции может быть реализовано следующим фрагментом программы:

Reset(fin); y:=y0; {y0=f(D)}

While not Eof(fin) do

Begin

Read(fin,x);

y:=G(y,x)

end {while}

Очевидно, что это фактически схема, из которой конкретная программа может быть получена интерпретацией абстрактных типов X и Y, переменных x, y и y0, функции G(y, x). Эта схема имеет инвариант цикла y = f(L(fin)) и ограничивающую функцию Length(R(fin)). Здесь использованы обозначения: L(fin) – прочитанная часть файла fin, R(fin) – непрочитанная часть, а Length(fin) – длина файла (количество элементов представленной в нем последовательности).

Общая формулировка задания

Заданы алфавит X и функция f: W(X) ®Y. Требуется определить, является ли функция f(w) индуктивной. Если “да” – выписать функцию G(*,*), если “нет” – подтвердить это, применяя критерий индуктивности [1, с. 21], а затем придумать индуктивное расширение [1, с. 23] и выписать G для него.

Далее требуется написать на языке Паскаль программу вычисления указанной функции f(w), считая, что w – это состояние последовательности элементов типа X, находящейся во входном файле.

При формулировке задания используются следующие обозначения типов, реализующих алфавит X: Z – Integer, N – натуральные, N0 – натуральные с нулем, S – Char, B – Boolean, R – Real, R0 – неотрицательные Real, R+ – положительные Real, R2 = R * R (декартово произведение).

Используется также следующая специальная терминология:

а) отрезок – это связная подпоследовательность (т. е. подпоследователь-ность подряд идущих элементов основной последовательности);

б) отрезок с некоторым заданным свойством (знакопостоянный, возрастающий и т. п.) предполагается максимально длинным, т.е. не является частью другого отрезка с тем же свойством.