Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. B5. Прочитайте текст и выполните задания.
  2. I. ТЕКСТЫ ДЛЯ ЧТЕНИЯ С ТЕСТОВЫМИ ЗАДАНИЯМИ
  3. II. ОБЩАЯ ЧАСТЬ.
  4. III.ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ
  5. VI. Общая задача чистого разума
  6. Аналитическая профессиограмма и общая схема профотбора
  7. Барическое поле и ветер. Общая циркуляция атмосферы
  8. Большая часть их верует в Аллаха, приобщая к Нему сотоварищей»[86].
  9. Вот вам два домашних задания по итогам главы. 1. Расслабляемся!
  10. Выполнение контрольного задания по уроку 1

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

 

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

 

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

В приведенных далее заданиях указана функция f(w), значение которой надо вычислить. Будем использовать обозначения, введенные в [1]: w – последовательность элементов заданного типа, т. е. w = x1x2xn, где 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 (декартово произведение).

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

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

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

 


Дата добавления: 2015-09-13; просмотров: 9; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2021 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты