![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Общая формулировка заданияСтр 1 из 2Следующая ⇒ ИНДУКТИВНЫЕ ФУНКЦИИ
Общая схема вычисления индуктивных функций
Основные определения, схема программ и примеры алгоритмов вычисления индуктивных функций на последовательностях подробно изложены в [6]. Более краткое изложение дано в [1] и ориентировано на представление последовательности в виде последовательного файла. Конечно, последовательность может быть реализована и как массив, и как линейный список, и некоторыми другими способами. Далее в заданиях будем рассматривать реализацию последовательности именно в виде файла, так как этот способ делает более естественным использование однопроходных алгоритмов, что и достигается при вычислении индуктивной функции. В приведенных далее заданиях указана функция f(w), значение которой надо вычислить. Будем использовать обозначения, введенные в [1]: w – последовательность элементов заданного типа, т. е. w = x1x2…xn, где xi Î X, а X – произвольный алфавит; пустая последовательность обозначается как D; Wk(X) – пространство всех конечных последовательностей над X длины не менее, чем k; при этом W0(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 (декартово произведение). Используется также следующая специальная терминология: а) отрезок – это связная подпоследовательность (т. е. подпоследователь-ность подряд идущих элементов основной последовательности); б) отрезок с некоторым заданным свойством (знакопостоянный, возрастающий и т. п.) предполагается максимально длинным, т.е. не является частью другого отрезка с тем же свойством.
|