- •Билет №8 Вычисления с вещественными числами и машинное эпсилон №8
- •Машинное эпсилон может быть вычислено с помощью следующей программы:
- •Билет №9 Общая схема итерации и №9 рекуррентные вычисления
- •Вычисления с целыми числами
- •Билет№10 Схема интерации. Вычисление частичной суммы (вещ числа) №10
- •Общая формулировка задания
- •Пример выполнения задания
- •Вопрос №12 . Основные правила аналитической верификации программ №12
- •Вопрос №14 Ограничивающая ф-ция оператора цикла.Примеры №14
- •Билет№15. Теорема о цикле, его инварианте и ограничивающей функции №15
- •Билет №17 Теорема о цикле repeat- until ,его инварианте и ограничивающей его ф-ции. Аннотирование цикла и понимание аннотации №17
- •Вопрос№18 Алгоритм анализа двоичной записи натурального числа в двоичной сист счисления №18
- •Последовательности и файлы
- •Индуктивные функции
- •Стационарные значения индуктивных функций
- •Индуктивные расширения функций
- •Примеры задач с индуктивными функциями
- •Кванторы и запись утверждений о массивах
- •Правила вывода для цикла с параметром
- •Примеры программ работы с массивами
- •Решение последовательными обменами
- •Задача перестановки сегментов разной длины (второе решение)
- •Задача перестановки сегментов разной длины (третье решение)
- •Билет№35 Задача о равнинах (с испол массива) №35
- •Линейный поиск
- •Оптимизация программы бинарного поиска
- •Билет№44 Массивы в качестве параметров:открытые массивы №44 Сведения о массивах в языке Паскаль
- •Билет№45 Двумерные (многомерные массивы). Индексация. Исполбзование процедур. Задача: о МиниМаксе(матрица как массив строк) №45 обработка двухмерных массивов
Индуктивные функции
Пусть в файле fint записана последовательность целых чисел (Z), требуется найти максимальное из них, т. е. Max(). Программа может быть написана из естественного соображения: читаем последовательность и для каждого очередного элемента x определяем максимальный элемент прочитанной части последовательности. Очевидно, что Max(*x) = max(Max(), x), где max(a, b) обозначает максимальное из двух чисел a и b. Доопределив Max() = , получаем фрагмент программы, вычисляющий Max():
var x, y: Integer; fint: file of Integer; …
Reset(fint); y := 32768; {y := }
while not Eof(fint) do
begin
Read(fint, x);
if x > y then y := x
end {while} {y = Max()}
Инвариантом цикла здесь является соотношение y = Max(L(fint)), а ограничивающей функцией Length(R(fint)).
Функции от последовательностей, подобные рассмотренной, встречаются часто и могут быть названы индуктивными [14], или марковскими [18].
Определение. Функция f: (X) Y называется индуктивной, если f(*x) можно вычислить, зная f() и x, т. е. если существует G:Y X Y,
такая, что для всех (X), x X выполняется соотношение f(*x) = G(f(), x).
Рассмотренный пример с Max() записывается в этих обозначениях следующим образом: f() = Max(),X = Z, f: (Z) Z, G(y, x) = max(y, x).
Еще один пример индуктивной функции:
f = «число положительных элементов последовательности».
Здесь f: (Z) N0. Функция f() индуктивна. Действительно, для всех (Z), x Z имеем f(*x) = G(f(), x), f() = 0, где G: N0Z N0 и
y + 1, если x > 0,
G(y, x) =
y, если x 0.
Индуктивные функции удобно вычислять. Пусть известно значение f0 = f(). Тогда значение fn = f(n), где n = x1 x2 … xn , можно найти так:
1 = 0*x1, f1 = f(1) = G(f0, x1),
2 = 1*x2, f2 = f(2) = G(f1, x2),
…
n = n 1*xn, fn = f(n) = G(fn 1, xn).
Если математическая последовательность представлена в программе файлом fin типа file of X, то эти рекуррентные соотношения можно реализовать в виде следующего фрагмента программы.
Фактически это схема программ, из которой конкретная программа может быть получена интерпретацией абстрактных типов X и Y, переменных x, y и y0, функции G(y, x). Эта схема имеет инвариант цикла y = f(L(fin)) и ограничивающую функцию Length(R(fin)). |
Reset(fin); y := y0; {y0 = f()} while not Eof(fin) do begin Read(fin, x); y := G(y, x) end {while} |
Пример неиндуктивной функции:
f = «число максимальных элементов последовательности».
Пусть, например x R, тогда f: (R) N0. Очевидно, можно положить f() = 0 и записать 1,если x > Max(),
f(*x) = f() + 1,если x = Max(), f(),если x < Max().
Поскольку для вычисления f(*x) необходимо кроме f() и x знать еще Max(), то функция f не является индуктивной.
Можно ввести формальный критерий индуктивности
Утверждение. Функция f индуктивна тогда и только тогда, когда
, : (f() = f()) (f(*x) = f(*x))
для любого x X.
Для предыдущего примера = (0, 1, 0, 1), = (1, 2, 1, 2), f() = 2, f() = 2. При x = 1 получим f(*x) = 3 и f(*x) = 2, т. е. f(*x) f(*x), и, следовательно, f неиндуктивна.
Билет№22 Индук ф-ции на пространстве последовател :стацион значения №22