Глава 21. Индуктивные вычисления

Пространство последовательностей
Индуктивные функции на пространстве последовательностей
Определение
Достоинства индуктивных функций
Примеры
Стационарные значения
Индуктивные расширения
Примеры
Минимальные индуктивные расширения

Задача, с которой часто приходится сталкиваться программисту — обработка последовательно поступающих данных. Примерами подобных вычислений являются подсчёт суммы последовательности чисел, поиск максимального или минимального числа, среднего арифметического. В этой главе мы рассмотрим общий подход к решению таких задач.

Пусть X — некоторое множество. Назовём n-элементной последовательностью над множеством X упорядоченный набор ω = x 1 x 2 x n , x i X . Формально выражаясь, последовательностью над X является отображение из множества первых n натуральных чисел 1 2 n в X: каждому числу i ставится в соответствие некоторый элемент x i множества X. При n = 0 получается пустая последовательность , заслуживающая такого же внимания, как и непустые. Последовательности над множеством иногда называют также цепочками.

Обозначим множество последовательностей над X как Ω X .

Из последовательности ω = x 1 x 2 x n Ω X и элемента x X можно сконструировать новую последовательность ω x = x 1 x 2 x n x . Операция удлинения отображает декартово произведение Ω X × X в Ω X , добавляя в конец последовательности ω новый элемент x. Любая последовательность может быть построена путём многократного удлинения пустой последовательности: x 1 x 2 x n = x 1 x 2 x n (мы не стали злоупотреблять скобками, предполагая, что операция удлинения левоассоциативна, то есть группируется слева направо).

Информатика-54© А. Н. Швец