Индуктивные расширения

Во всех рассмотренных примерах неиндуктивных функций причина неиндуктивности была одна и та же: нехватка дополнительной информации при вычислении f ω x через f ω и x. Поскольку индуктивные функции удобно вычислять, очень желательно научиться сводить вычисление неиндуктивной функции f к вычислению другой, индуктивной функции f ^ . Эту новую функцию назовём индуктивным расширением функции f. Индуктивное расширение содержит всю необходимую информацию для вычисления исходной функции.

Более формально, функция f ^ называется индуктивным расширением функции f, если:

Для записи последнего условия мы приготовили особое обозначение f f ^ . Обратите внимание, что здесь сравниваются не значения функций f и f ^ (которые во многих случаях вообще могут не подлежать сравнению), а сами функции. Поэтому-то мы и выбрали искривлённый значок неравенства. Лучше всего понимать это «неравенство» так: функция f ^ содержит не меньше информации о последовательности, чем f.

[Примечание]Примечание

Можно проиллюстрировать отношение на примере более привычных числовых функций. Например, x 2 x (зная x, можно вычислить и x 2 ; для этого нужно x возвести в квадрат). Обратное «неравенство» не имеет места: при возведении в квадрат утрачивается информация о знаке числа x. С другой стороны, выполняются оба «неравенства» x 3 x и x x 3 .

Воспользуемся уже известным равенством avg ω = sum ω len ω . Возьмём в качестве индуктивного расширения функцию f ^ ω = sum ω len ω , вычисляющую пару значений — сумму и длину последовательности. Каждая из этих величин индуктивна, поэтому и функция индуктивна. Искомая функция легко извлекается из индуктивного расширения — нужно поделить сумму на длину последовательности: avg ω = π sum ω len ω = если len ω > 0 , то sum ω len ω иначе любое значение.

Приводим текст программы, вычисляющий этим способом среднее арифметическое чисел, заданных в командной строке:

#!/usr/bin/perl

use warnings;

my ($sum, $len)=(0, 0);

for my $x(@ARGV)
{
	($sum, $len)=($sum+$x, $len+1);
}

my $avg=NAN;	# любое значение
$avg=$sum/$len if $len;

print "$avg\n";

Не следует думать, что индуктивное расширение строится единственным образом. Мы могли бы поступить иначе, выбрав в качестве индуктивного расширения пару функций f ^ ω = avg ω len ω . Хотя avg не индуктивна, тем не менее пара avg len индуктивна, поскольку avg ω x и len ω x выражаются через avg ω , len ω и x: avg ω x = avg ω len ω + x len ω + 1 , len ω x = len ω + 1 .

Очевидно, совершенно всё равно, как доопределить avg для пустой последовательности.

Так выглядит соответствующая программа:

#!/usr/bin/perl

use warnings;

my ($len, $avg)=(0, 0);

for my $x(@ARGV)
{
	($avg, $len)=(($avg*$len+$x)/($len+1), $len+1);
}

print "$avg\n";

Третий, но далеко не последний способ индуктивно расширить среднее арифметическое — вычислять пару величин avg sum . Тут нам помогут формулы avg ω x = avg ω sum ω + x sum ω + avg ω , sum ω x = sum ω + x .

Здесь, во избежание деления на ноль, мы вынуждены дать ненулевое значение величине avg (какое именно — неважно).

#!/usr/bin/perl

use warnings;

my ($sum, $avg)=(0, 1);

for my $x(@ARGV)
{
	($avg, $sum)=($avg*($sum+$x)/($sum+$avg), $sum+$x);
}

print "$avg\n";

Из приведённых здесь трёх программ наиболее простой будет, по-видимому, первая.

Ещё один хрестоматийный пример, помимо среднего арифметического, даёт дисперсия.

Среднее арифметическое служит важной статистической характеристикой числовой последовательности. Другая величина, дисперсия, показывает, насколько велик разброс элементов последовательности вокруг среднего значения. Здесь уместна аналогия со стрельбой: если аналогом среднего является центр мишени, точка, в которой вероятность поражения пулей максимальна, то дисперсии соответствует кучность попаданий. Латинский термин dispersio означает рассеяние. В западной математической литературе дисперсию часто называют вариацией.

Вот точное определение дисперсии числовой последовательности. Это средний квадрат отклонения элементов последовательности от среднего арифметического: var x 1 x n = 1 n i = 1 n x i 1 n k = 1 n x k 2 = 1 n i = 1 n x i avg x 1 x n 2 . Ясно, что лишь у постоянных последовательностей дисперсия равна нулю. Во всех же остальных случаях (то есть когда имеется хоть какой-то разброс элементов последовательности) она положительна.

Для доказательства неиндуктивности функции var предъявим противоречивые равенства: var 0 0 0 = 0 = F var 0 0 0 = F 0 0 , var 1 1 0 = 2 9 = F var 1 1 0 = F 0 0 .

Построим индуктивное расширение для функции var. Для этого преобразуем соответствующее выражение, обозначив для краткости a = avg ω : i = 1 n x i a 2 = i = 1 n x i 2 2 a x i + a 2 = i = 1 n x i 2 2 a i = 1 n x i + a 2 i = 1 n 1 = sumsq ω 2 a sum ω + a 2 len ω (здесь мы обозначили сумму квадратов элементов последовательности как sumsq). Таким образом, удалось выразить неиндуктивную функцию через три индуктивных: var ω = 1 len ω sumsq ω 2 avg ω sum ω + avg 2 ω len ω = sumsq ω len ω sum ω len ω 2 . Действительно, функции sum и len нам хорошо знакомы, а индуктивность функции sumsq очень легко проверить. Для пустой последовательности дисперсия не определена, но мы вправе доопределить её как угодно.

Программа inductive-var.pl вычисляет дисперсию чисел, заданных в командной строке:

#!/usr/bin/perl

use warnings;

my ($sumsq, $sum, $len)=(0, 0, 0);

for my $x(@ARGV)
{
	($sumsq, $sum, $len)=($sumsq+$x**2, $sum+$x, $len+1);
}

my $var=NAN;	# любое значение
$var=$sumsq/$len-($sum/$len)**2 if $len;

print "$var\n";

Для последовательности ω = x 1 x n можно определить так называемые элементарные симметрические многочлены: σ k ω = 1 i 1 < i 2 < < i k n x i 1 x i 2 x i k . (здесь из элементов последовательности составляются всевозможные произведения, состоящие из k различных множителей, и эти произведения складываются). Эти многочлены называются симметрическими, поскольку, очевидно, не меняют своих значений при любых перестановках элементов последовательности: все x i входят в выражение многочлена симметричным образом. Элементарные симметрические многочлены имеют прямое отношение к теореме Виета.

При некоторых k элементарные симметрические многочлены оказываются нашими старыми знакомыми. В частности, при k = 1 получается σ 1 ω = x 1 + + x n = sum ω , а при k = n σ n ω = x 1 · · x n = prod ω . Оба многочлена, σ 1 и σ n , как мы уже знаем — индуктивные функции.

Нас в данный момент интересует функция σ 2 , сумма попарных произведений элементов последовательности.

Функция σ 2 , к сожалению, не индуктивна. Чтобы это установить, предъявим, как обычно, контрпример: σ 2 0 0 1 = 0 = F σ 2 0 0 1 = F 0 1 , σ 2 0 1 1 = 1 = F σ 2 0 1 1 = F 0 1 .

Ничего другого не остаётся, кроме как заняться поисками индуктивного расширения. Для коротких последовательностей, из которых можно выбрать хотя бы одну пару элементов, получаем: σ 2 a b = a b , σ 2 a b c = a b + a c + b c , σ 2 a b c d = a b + a c + a d + b c + b d + c d . Здесь видна закономерность: при удлинении последовательности функция увеличивается на добавляемый элемент, умноженный на сумму элементов исходной последовательности. Это приводит к предположению, что пара функций σ 2 sum осуществляет индуктивное расширение функции σ 2 : σ 2 ω x = σ 2 ω + x · sum ω , sum ω x = sum ω + x .

Осталось лишь доопределить функцию для пустой и одноэлементных последовательностей, то есть для тех случаев, когда последовательность не содержит ни одной пары, причём так, чтобы доопределение было согласовано с индуктивностью. Положим в формуле перевычисления ω = a . Тогда σ 2 a x = a x = σ 2 a + x · sum a = σ 2 a + a x , откуда σ 2 a = 0 для любых a. Далее, σ 2 x = 0 = σ 2 + x · sum = σ 2 + x · 0 , откуда σ 2 = 0 . Итак, начальное значение функции следует считать нулевым, и это логично: нет ни одной пары — нет попарных произведений — нулевая сумма.

#!/usr/bin/perl

use warnings;

my ($sigma2, $sum)=(0, 0);

for my $x(@ARGV)
{
	($sigma2, $sum)=($sigma2+$x*$sum, $sum+$x);
}

print "$sigma2\n";

В разделе «Схема Горнера» мы обсуждали вычисление значения многочлена, заданного своими коэффициентами в порядке убывания степеней. А как насчёт коэффициентов в порядке возрастания степеней?

Положим polynom ω = x 1 + x 2 t + x 3 t 2 + + x n 1 t n 2 + x n t n 1 . Заметим, что polynom ω x = polynom ω + x t n . С учётом того, что n = len ω , построим индуктивное расширение polynom len : polynom ω x = polynom ω + x t len ω , len ω x = len ω + 1 .

Программа inductive-polynom.pl получает в командной строке значение t и последовательность коэффициентов многочлена и вычисляет значение многочлена в точке t:

% ./inductive-polynom.pl 1 1 2 3 6 % ./inductive-polynom.pl 2 1 2 3 17

#!/usr/bin/perl

use warnings;

my $t=shift;
my ($polynom, $len)=(0, 0);

for my $x(@ARGV)
{
	($polynom, $len)=($polynom+$x*$t**$len, $len+1);
}

print "$polynom\n";

Функция maxcount ω вычисляет количество максимальных элементов числовой последовательности ω. Она, очевидно, не индуктивна. Удлинение последовательности элементом x не меняет значения функции, если он меньше максимума, увеличивает на единицу, если добавляемый элемент совпадает с максимумом, и обращает значение функции в единицу, если оказывается больше. Зная лишь количество максимумов и добавляемый элемент, перевычисление организовать невозможно. Ясно, как построить индуктивное расширение: нужно, помимо подсчёта максимумов, вычислять также максимальное значение. Для пары функций maxcount max получаются следующие формулы перевычисления: maxcount ω x = если x < max ω , то maxcount ω , если x = max ω , то maxcount ω + 1 , иначе 1 , max ω x = max max ω x . Доопределим функции: maxcount = 0 , max = .

#!/usr/bin/perl

use warnings;

my($maxcount, $max)=(0, -INFINITY);

for my $x(@ARGV)
{
	($maxcount, $max)
		=(
			$x<$max? $maxcount: $x==$max? $maxcount+1: 1,
			$x>$max? $x: $max
		);
}

print "$maxcount\n";

Функция const x 1 x n принимает значение да, если все элементы последовательности равны между собой, и нет в противном случае.

Функция не индуктивна, однако пара const last , кажется, осуществляет индуктивное расширение: const ω x = const ω x = last ω , last ω x = x .

Однако следует доопределить обе функции, const и last, для пустой последовательности. И тут-то нас постигает неудача. Из равенства const x = const x = last следует, что нужно положить const = да (иначе функция const будет равна нет для любой последовательности). Кроме того, по той же самой причине для любого x должно выполняться равенство last = x , что невозможно. Это затруднение преодолевается, если особым образом обрабатывать пустую последовательность в функции перевычисления: const ω x = const ω x = last ω len ω = 0 , last ω x = x , len ω x = len ω + 1 . Вот теперь, чему бы ни равнялось last , функция перевычисления будет работать правильно. Таким образом, тройка const last len даёт требуемое индуктивное расширение.

Программа inductive-const.pl проверяет последовательность чисел из командной строки на постоянство:

#!/usr/bin/perl

use warnings;

my ($const, $last, $len)=(1, undef, 0);

for my $x(@ARGV)
{
	($const, $last, $len)
		=(
			($len==0 or $const and $last==$x),
			$x,
			$len+1
		);
}

print $const? '': 'не ', "постоянная\n";

Ломаная задаётся на плоскости точками с координатами x 1 y 1 x n y n . Длину ломаной определим как функцию на пространстве последовательностей координатных пар Ω 2 . Назовём её polylen (polyline length — длина ломаной): polylen x 1 y 1 x n y n = x 2 x 1 2 + y 2 y 1 2 + x 3 x 2 2 + y 3 y 2 2 + + x n x n 1 2 + y n y n 1 2 .

Попытаемся составить функцию перевычисления для polylen ω . Добавление новой точки x y приводит к появлению нового звена длиной x x n 2 + y y n 2 . Эта длина добавляется к polylen ω : polylen ω x y = polylen ω + x x n 2 + y y n 2 .

Поскольку в правой части помимо polylen ω и чисел x, y фигурируют также и другие величины, x n и y n , эта формула не задаёт перевычисление. Обозначим x n как lastx ω , а y n как lasty ω . Эти функции на пространстве последовательностей числовых пар устроены точно так же, как и функция last: lastx ω x y = x , lasty ω x y = y .

Может показаться, что набор, включающий функции polylen, lastx, lasty осуществляет индуктивное расширение функции polylen, но это не так, потому что функция polylen определена лишь для последовательностей, состоящих как минимум из двух точек. Исправить положение может небольшое изменение в формулах перевычисления: polylen ω x y = если len ω > 0 , то polylen ω + x lastx ω 2 + y lasty ω 2 , иначе 0 . Раз мы включили в правую часть формулы перевычисления индуктивную функцию len, она (вместе с функциями polylen, lastx, lasty) становится составной частью индуктивного расширения.

Запрограммируем вычисление длины ломаной. Чтобы разнообразить наши примеры реализации индуктивных алгоритмов на Perl, заставим программу читать элементы последовательности (пары чисел) со стандартного ввода. В каждой строке ввода размещаются два числа, разделённых пробелами или символами табуляции. Вот пример сеанса работы программы inductive-polylen.pl:

#!/usr/bin/perl

use warnings;

my ($polylen, $lastx, $lasty, $len)=(0, undef, undef, 0);

while(<STDIN>)
{
	chomp;
	my ($x, $y)=split /\s+/;
	($polylen, $lastx, $lasty, $len)
		=(
			$len? $polylen+sqrt(($x-$lastx)**2+($y-$lasty)**2): 0,
			$x,
			$y,
			$len+1
		);
}

print "$polylen\n";

Как мы выяснили, функция wc не индуктивна. Однако пара wc last уже оказывается индуктивной: wc ω x = если x ¬ last ω , то wc ω + 1 , иначе wc ω , last ω x = x .

Чтобы индуктивное расширение заработало, необходимо доопределить его для пустой последовательности. Логично предположить, что wc = 0 , но что же взять в качестве last ? Подстановка в индуктивные формулы ω = и wc = 0 требует, чтобы было last = нет , что соответствует добавлению перед началом последовательности воображаемого пробела. Счётчик слов увеличивается при смене пробела на непробел, и этот воображаемый пробел перед первым словом нужен, чтобы ситуация, когда слово начинается с самого начала символьной последовательности, не было исключением из правила.

Программа inductive-wc.pl вычисляет количество слов в тексте, переданном в первом параметре командной строки (раз он может содержать пробелы, заключаем его в кавычки или апострофы):

#!/usr/bin/perl

use warnings;

my $text=shift;

my($wc, $last)=(0, ' ');

for my $x(split //, $text)
{
	($wc, $last)=(($x ne ' ' and $last eq ' ')? $wc+1: $wc, $x);
}

print "$wc\n";

Этой задаче посвящена глава 24. «Подсчёт символов, слов и строк».

Мы опять имеем дело со строками — символьными последовательностями. Обозначим как maxwl ω (MAXimum Word Length) максимальную длину слова в символьной последовательности ω. Несложно понять, что эта функция не индуктивна.

Постараемся определить, какой информации не хватает для перевычисления функции maxwl. При удлинении последовательности её значение либо увеличивается на единицу, либо остаётся неизменным. Необходимым условием увеличения является непробельность добавляемого в последовательность символа. Для достаточности следует также потребовать, чтобы непробелы, стоящие в самом конце последовательности, образовывали слово максимальной длины. Таким образом, нужно знать количество непробелов в конце последовательности. Обозначим эту величину как lastwl ω  — LAST Word Length. Итак, получаем maxwl ω x = если x maxwl ω = lastwl ω , то maxwl ω + 1 , иначе maxwl ω .

Функция lastwl, в свою очередь, индуктивна. Она при удлинении последовательности или увеличивается на единицу, или обращается в нуль. Увеличение происходит в единственном случае — при добавлении к последовательности непробела. Если же добавляется пробел, функция обнуляется: lastwl ω x = если x , то lastwl ω + 1 , иначе 0 .

Совокупность функций maxwl lastwl осуществляет индуктивное расширение функции maxwl, если положить maxwl = lastwl = 0 .

Как и при подсчёте слов, программа, реализующая индуктивное вычисление наибольшей длины слова, получает текст в командной строке:

#!/usr/bin/perl

use warnings;

my $text=shift;

my($maxwl, $lastwl)=(0, 0);

for my $x(split //, $text)
{
	$x=($x eq ' ');
	($maxwl, $lastwl)
		=(
			($maxwl==$lastwl and $x)? $maxwl+1: $maxwl,
			$x? $lastwl+1: 0
		);
}

print "$maxwl\n";

Обратите внимание, что в цикле мы первым делом заменяем очередной символ на логическое значение, истинное для пробелов и ложное в противном случае, и затем уже имеем дело с этим значением.

Последовательность состоит из символов круглых скобок — ( и ). Функция balanced принимает значения да или нет в зависимости от того, сбалансированы ли скобки в последовательности.

Прежде чем исследовать эту функцию, нужно дать строгое определение сбалансированности. Для простых и коротких последовательностей проверка баланса не вызывает затруднений: ясно, что последовательности (), (()) или ()() сбалансированы, а )(, ()) или (()() — нет.

Будем называть для краткости сбалансированную последовательность группой. Ясны способы конструирования новых групп на основе уже имеющихся. Группа может быть получена в результате заключения в скобки другой группы, или же в результате конкатенации двух групп. Что касается группы (), то, чтобы не делать исключения в этом случае, примем по определению, что пустая последовательность также является группой. Тогда () может быть получена из пустой последовательности как первым, так и вторым способом: как заключением пустой группы в скобки, так и конкатенацией пустой группы и группы ().

Функция balanced, очевидно, не индуктивна. Для гипотетической функции перевычисления получим следующие противоречивые равенства: balanced ( ) = balanced () = да = F balanced ( ) = F нет ) balanced (( ) = balanced (() = нет = F balanced (( ) = F нет )

Однако имеется функция, осуществляющая индуктивное расширение. Это уровень вложенности скобок: при добавлении открывающей скобки он увеличивается на единицу, при добавлении закрывающей — уменьшается. Нулевое значение уровня вложенности является необходимым условием сбалансированности последовательности скобок. Но не достаточным.

Обозначим функцию, вычисляющую уровень вложенности, как level. Очевидно, level )( = 0 , несмотря на то, что последовательность )( не сбалансирована. Причина в том, что level ) = 1 . Какие бы скобки не добавлялись бы в дальнейшем к последовательности ), сбалансированной она уже не станет. Таким образом, достаточными условиями сбалансированности последовательности скобок ω = x 1 x n являются следующие:

Получается, что знания только лишь level ω оказывается недостаточно для того, чтобы судить о сбалансированности последовательности, и, следовательно функция level не является расширением функции balanced. Но если определить level немного по-другому, проблема будет решена. Определим функцию level индуктивно, предъявив для неё функцию перевычисления: level = 0 , level ω x = если level ω 0 x = ( , то level ω + 1 если level ω 0 x = ) , то level ω 1 иначе 1 . Здесь фраза «иначе» означает «при level ω < 0 ». Иными словами, стоит лишь значению level опуститься ниже ноля, таким оно и останется при любом удлинении последовательности. Если этого не происходит, функция вычисляет, как и прежде, уровень вложенности групп, увеличиваясь с каждой открывающей и уменьшаясь с каждой закрывающей скобкой. Функцию balanced определим так: balanced ω = level ω = 0 . Индуктивное расширение построено.

Между прочим, значение 1 является стационарным для функции level. Не забудем это учесть в готовой программе.

Программа inductive-balanced.pl проверяет баланс в первом параметре командной строки. Запуская программу, не забудьте заключить строку из скобок в кавычки или апострофы: скобки имеют особый смысл в командном языке:

#!/usr/bin/perl

use warnings;

my $text=shift;

my $level=0;

for my $x(split //, $text)
{
	if($level>=0)
	{
		if($x eq '(')
		{
			$level++;
		}
		elsif($x eq ')')
		{
			$level--;
		}
	}
	else
	{
		last;
	}
}

my $balanced=not $level;

print $balanced? 'баланс есть': 'нет баланса', "\n";

Эта же задача рассматривается в главе 23. «Проверка баланса скобок» в более общей постановке, когда помимо круглых скобок последовательность может содержать скобки других видов: квадратные, фигурные, и так далее.

Вопрос с единственностью индуктивного расширения данной функции на пространстве последовательностей решается отрицательно. Как показывает пример среднего арифметического, нашлось как минимум три способа расширить функцию до индуктивной. Всегда хочется из всевозможных способов выбрать наилучший. Но в каком смысле наилучший?

Пусть для данной функции f нашлось два индуктивных расширения f ^ 1 и f ^ 2 . Если для них выполняется f ^ 1 f ^ 2 , то первое индуктивное расширение может оказаться предпочтительнее второго. Действительно, если вторая функция содержит не меньше информации о последовательности, чем первая (а, может быть, больше), её, возможно, труднее вычислять, а для хранения вычисленной информации требуется больше памяти. Поэтому полезно искать минимальное индуктивное расширение, то есть такую функцию f ^ * , что для любого индуктивного расширения f ^ выполняется f ^ * f ^ . У математика должен возникнуть вопрос: всегда ли существует минимальное индуктивное расширение для функции f? Если да, единственно ли оно? На эти вопросы отвечает теорема. Да, минимальное индуктивное расширение всегда есть. Да, в определённом смысле оно единственно. В том смысле, что если найдётся два минимальных индуктивных расширения f ^ 1 * и f ^ 2 * , то для них будут выполнены оба соотношения, f ^ 1 * f ^ 2 * и f ^ 1 * f ^ 2 * . Если употреблять умные слова, то можно сказать: минимальное индуктивное расширение единственно с точностью до изоморфизма. Все минимальные индуктивные расширения изоморфны, то есть равноценны с точки зрения содержащейся в них информации — любое из них можно вычислить из другого.

Другой, ещё более интересный вопрос — как найти минимальное индуктивное расширение — увы, не имеет простого ответа. Его поиск во многих случаях является сложной творческой работой.

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